# Redesigning the Wheel for Systematic Travelling Salesmen
## 2 Methods
### Local Optimization Using \(k\)-Opt Permutations
#### 2.4.4 Optimization with 6-Opt Permutations
```
1N...totalnumberofpointsintour
2x[:]...vectorwithx-coordinatesofglobaltour
3y[:]...vectorwithy-coordinatesofglobaltour
4 Jiobob:=f(availableLore);//numberofsegments(paralleljobs)
5 LmSegment:=N/3 Jiobs+1;//regularnumberofpointspersegment startTime=time(0);//getcurrenttime
7 oldfourLengthTime=startTime;
8 tourLengthOld=getTourLength(k);/*formeasuringtheimprovement+/
9 round=0;
10 do//alternationbetweenparallelprocessingandglobaloptimization
11{//i.e.,multithreadprocessingvssingle-thread
12 stop_flag:=0;
13 do//roundsofparallelprocessing
14{
15 for(j:=0;j<Njobs;j++)//foralljobs(segments)inparallel
16{
17 Ns=LenSegment;
18 if(j==Njobs-1)//segmentoflastjobisshorter
19 Ns-=lenSegment*Njobs-N;//correctnumberofpoints
20 Ns++://includevirtualpoint;
21 slc=j-1=NemSegment/;//startindexinglobalpermutationvector
22 sIdx=((lenSegment*round)/10)%lenSegment;//+10%offsetineachround
23 for(i:=0;i<Ns-1;i++)//allpointsexl.virtualone
24{
25\(\pi_{i}\)[i:=i;//initializepermutationvectorofjobj
26\(x_{i}\)[i]:=x{\(\pi_{i}\)[(sIdx+i)%N]];//copycoordinatesincurrentorder
27\(y_{i}\)[i]:=y{\(\pi_{i}\)[(sIdx+i)%N];//usemodulooperationforwrapping
28}
29\(\pi_{i}\)[Ns-1]:=Ns-1;//indexofvirtualpoint
30\(\pi_{i}\)[Ns-1]:=ININITY;//setcoordinatesofvirtualpoint
31\(y_{i}\)[Ns-1]:=INFINITY;
32 TREAD[optimizer2356(usesingleloopoverallpointsPwithinsegment);]
33}
34 for(j:=0;j<Njobs;j++)//foralljobs(segments)
35{waitforalljobstobefinished}
36 updatePermutationVector();//mergeresultsfromallparalleljobs
37 lourLength=getTourLength(j);
38 relativeInprovement=(tourLengthOld-tourLength)/tourLengthOld;
39 currTime=time(0);elapsedTime=currTime-startTime;
40d descent=relatipermovement/(1+currTime-oldfourLengthTime);
41 if(round==0)descentThreshold=descent/Njobs;//initialthreshold
42 elseif(descent<descentThreshold)
43(//tlooitchimprovementperround
44 stop_flag=1;
45}
46 oldfourLengthTime=currTime;//remembertimeandtourlength
47 tourLengthOld=tourLength;
48 round++;
49}while(stop_flag&&elapsedTime<maxDuration);//dothenextroundofparalleljobs
50 if(elapsedTime<maxDuration)
51{
52 stop_flag'=0;//forouterdo-loop
53 optimizer2356(usesingleloopoverallpointsPofentiretour);
54 tourLength=getTourLength();
55 relativeInprovement=(tourLengthOld-tourLength)(tourLengthOld;
56 currTime=time(0));elapsedTime=currTime-startTime;
57 descent=relativeInprovement/(1+currTime-oldfourLengthTime);
58 ifdescentThreshold>descent)
59{//apaptationofthresholdforparallelprocessing
60 descentThreshold=descent;
61}
62 if(relativeTourImprovement==0)
63{//noimprovement
64 stop_flag=1;
65}
66 oldfourLengthTime=currTime;//remembertimeandtourlength
67 tourLengthOld=tourLength;
68}
69}while(!stop_flag&&elapsedTime<maxDuration);//dothenextroundofparalleljobs
```
1 updatePermutationVector()
2{
3\(\pi\)...global permutation vector
4\(\pi_{\text{s}}\)... permutation vector of segment s after its optimization
5N... total number of points in tour
6 Njobs := f(available cores); // number of segments
7 lenSegment := No / Njobs + 1; // regular number of points per segment
8 for(s := 0; s < Njobs; s++) // for all segments
9{
10 Ns := lenSegment;
11 if(s == Njobs -1) // last segment is shorter
12 Ns -= lenSegment * Njobs - N; // correct number of points
13 Ns++; // include virtual point;
14 sIdx := s * lenSegment; // start index in global permutation vector
15 sIdx += (lenSegment * round) / 10) % lenSegment;// +10% offset in each round
17 for(i := 0; i < Ns; i++) // all points incl. virtual one
18{ // temporary storage since inplace operation is not possible
19 tmp[i] := \(\pi\)[sIdx + \(\pi_{\text{s}}\)[i]] % N]; // position wrapping by modulo operation
20}
21 for(i := 0; i < Ns-1; i++) // all points excl. virtual one
22{ // copy order back to global permutation vector
23\(\pi\)[ (sIdx+i) % N] := tmp[i];
24}
25}
26}
```  
Listing 4: Pseudocode showing how individual segment permutations are mapped back to the global permutation vector. See text for details.