/* Subroutines for dynamic program for the Traveling Salesman Problem */ /* www.contrib.andrew.cmu.edu/~neils/tsp/index.html */ /* Neil Simonetti, May 1998 */ /* ------------------------------------------------------------------- */ void SortPretour (costtype *criterion, nodeXtype *tour, nodeXtype n) /* constructs an initial tour by sorting by the criterion */ /* selection sort should be replaced by a better sorting */ /* algorithm in future for large problems */ { costtype earliest; nodeXtype earliestInx; signed int c1, c2; { for (c1 = 1; c1 < n; c1++) { earliest = inFinity; for (c2 = 1; c2 < n; c2++) { if (criterion[c2] < earliest) { earliest = criterion[earliestInx=c2]; } } tour[c1]=earliestInx; criterion[earliestInx]=inFinity; } } } /* ------------------------------------------------------------------- */ signed char CalcKval (costtype *winBegin, costtype *winEnd, costtype *servTime, int *kval, signed char k, nodeXtype n, costtype *winDepartBound, char *compromise) /* construct array of k-values based on time windows */ { signed int c1, c2; costtype bound; signed char maxK; winDepartBound[n]=inFinity; for (bound = inFinity, c1 = n-1; c1 > -1; c1--) { bound = winDepartBound[c1] = _min(winBegin[c1]+servTime[c1],bound); } kval[0]=maxK=1; for (c1 = c2 = 1; c1 < n; c1++) { while (winDepartBound[c2] < winEnd[c1]) {c2++;} while (winDepartBound[c2-1]>winEnd[c1]) {c2--;} kval[c1] = _min(k,_max(1,c2-c1)); maxK = _max(maxK,c2-c1); } *compromise = (maxK > k); printf("Maximum k requested was %d.\n",maxK); if (maxK > k) {printf(" Use this value of k to guarantee optimality.\n");} maxK=_min(maxK,k); kval[n]=1; return (maxK); } /* ------------------------------------------------------------------- */ signed char FixKval (costtype *winBegin, costtype *winEnd, costtype *servTime, int *kval, signed char k, nodeXtype n, nodeXtype *tour, costtype *winDepartBound) /* improve array of k-values by shuffling the tour order */ { signed int c1, c2, swaps, spot, dm1, dm2, bonus, penalty; costtype bound, dm3, dm4, dm5; signed char maxK; swaps = 0; winDepartBound[n]=inFinity; for (bound = inFinity, c1 = n-1; c1 > -1; c1--) { bound = winDepartBound[c1] = _min(winBegin[c1]+servTime[c1],bound); } kval[0]=maxK=1; for (c1 = c2 = 1; c1 < n; c1++) { while (winDepartBound[c2] < winEnd[c1]) {c2++;} while (winDepartBound[c2-1]>winEnd[c1]) {c2--;} kval[c1] = c2-c1; } for (c1 = 2; c1 < n-1; c1++) { if (kval[c1]+10; spot--); bonus = kval[++spot]; penalty = 0; for (c2 = spot-1; c2 > 0; c2--) { if (kval[c2]==c1-c2) {penalty=c2;} } if (bonus-1 > kval[penalty]) /* do the swap */ { swaps = 1; dm1 = kval[c1]+c1-spot; dm2 = tour[c1]; dm3 = winBegin[c1]; dm4 = winEnd[c1]; dm5 = servTime[c1]; for (c2=c1; c2>spot; c2--) { kval[c2]=kval[c2-1]-1; tour[c2]=tour[c2-1]; winBegin[c2]=winBegin[c2-1]; winEnd[c2]=winEnd[c2-1]; servTime[c2]=servTime[c2-1]; } kval[spot] = dm1; tour[spot] = dm2; winBegin[spot] = dm3; winEnd[spot] = dm4; servTime[spot] = dm5; if (penalty) {kval[penalty] += 1;} } } } for (bound = inFinity, c1 = n-1; c1 > -1; c1--) { bound = winDepartBound[c1] = _min(winBegin[c1]+servTime[c1],bound); } for (c1 = c2 = 1; c1 < n; c1++) { while (winDepartBound[c2] < winEnd[c1]) {c2++;} while (winDepartBound[c2-1]>winEnd[c1]) {c2--;} kval[c1] = _min(k,c2-c1); maxK = _max(maxK,c2-c1); } // printf("Maximum k requested was %d.\n",maxK); maxK=_min(maxK,k); kval[n]=1; return (swaps); } /* ------------------------------------------------------------------- */ signed char FixRvKval (costtype *winBegin, costtype *winEnd, costtype *servTime, int *kval, signed char k, nodeXtype n, nodeXtype *tour, costtype *winEndBound) /* improve array of "reverse" k-values by shuffling the tour order */ { signed int c1, c2, bonus, penalty, spot, swaps, dm1, dm2; costtype bound, dm3, dm4, dm5; signed char maxK; swaps = 0; for (bound = 0, c1 = 1; c1 < n; c1++) { bound = winEndBound[c1] = _max(winEnd[c1],bound); } kval[0]=maxK=1; for (c1 = c2 = 1; c1 < n; c1++) { while (winEndBound[c2] < winBegin[c1]+servTime[c1]) {c2++;} while (winEndBound[c2-1]>winBegin[c1]+servTime[c1] && c2>1) {c2--;} kval[c1] = c1-c2+1; } for (c1 = n-2; c1 > 0; c1--) { if (kval[c1]+1 kval[penalty]) /* do the swap */ { swaps = 1; dm1 = kval[c1]+spot-c1; dm2 = tour[c1]; dm3 = winBegin[c1]; dm4 = winEnd[c1]; dm5 = servTime[c1]; for (c2=c1; c2winBegin[c1]+servTime[c1] && c2>1) {c2--;} kval[c1] = _min(k,c1-c2+1); maxK = _max(maxK,c1-c2+1); } // printf("Maximum k requested was %d.\n",maxK); maxK=_min(maxK,k); kval[n]=1; return (swaps); } /* ------------------------------------------------------------------- */ nodeXtype BuildSmallTWmatrix (signed char k, char contRule, char maketour, costtype *winBeginRaw, costtype *winBegin, costtype *winEndRaw, costtype *winEnd, costtype *servTimeRaw, costtype *servTime, costtype *shortMatrix, nodeXtype *tour, nodeXtype *levtour, costtype targ, nodeXtype n, int *kval, signed char *localK, int *shrinkProbs, costtype *addlCost, char *compromise) { nodeXtype c1,c2,levn,z; signed int c3; costtype *walkPtr, *winMid, winBtemp, winEtemp; int probtotal=0, maxcost=0, h, modified, modifcount; winMid = addlCost; if (maketour) { for (c1=0; c1 maxcost) {maxcost=h;} } for (c1=0; c1= shrinkProbs[c1]) { levtour[levn] = c1; winBegin[levn] = winBtemp; winEnd[levn] = winEtemp; servTime[levn++] = servTime[tour[c1]]; winBtemp=winBeginRaw[tour[c1+1]]; winEtemp=winEndRaw[tour[c1+1]]; } else { addlCost[levn] += theNorm(tour[c1],tour[c1+1])+servTime[tour[c1]]; winBtemp = _max(winBtemp,winBeginRaw[tour[c1+1]]-addlCost[levn]); winEtemp = _min(winEtemp,winEndRaw[tour[c1+1]]-addlCost[levn]); } } addlCost[0] += addlCost[levn]; } else { for (c1=0; c1