Skip to content

30.10 Look-ahead and regret

Part 4 · Heuristic algorithms · Chapter 30 · Chapter 30: Constructive heuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Constructive heuristics · App: Bin packing heuristics · App: List scheduling and LPT · App: Vertex coloring: greedy and DSATUR · App: TSP: nearest neighbour and 2-opt

  • A greedy criterion asks: which choice is best now? Its myopia can be reduced by asking two different questions:

    • regret: what do I lose if I postpone this choice? An element that has a single good option should be served before it loses it; an element with many equivalent options can wait;

    • look-ahead: where does this choice lead? Each candidate is evaluated by completing the partial solution with a fast heuristic, and the candidate with the best completed solution is chosen.

    Both ideas cost more time per step than the plain greedy criterion, and both keep the essential feature of a constructive heuristic: the choice made is final.

30.10.1 Regret insertion

  • For an insertion heuristic, let \(\Delta^{1}_q\le\Delta^{2}_q\) be the two smallest insertion costs of city \(q\) over the edges of the current subtour (with \(\Delta^2_q=\Delta^1_q\) if the subtour has a single edge). The regret of \(q\) is
\[ reg_q \;=\; \Delta^{2}_q - \Delta^{1}_q \;\ge\; 0 : \]

the extra cost paid for \(q\) if its best edge is used by another city before \(q\) is inserted.

The regret-2 insertion algorithm (denoted by \(REG_2\)) is a constructive heuristic for the TSP. Starting from the subtour \((s)\), at each step it inserts the city with the largest regret, in case of ties the one with the smallest \(\Delta^1_q\) and then the smallest index, into its edge of minimum insertion cost.

Algorithm: Regret-2 Insertion

Input: TSP instance with \(n\) cities, distances \(d[1..n][1..n]\); starting city \(s\)
Output: Tour \(\sigma[1..n]\)
1Function Regret2Insertion(\(n, d, s\))
2\(\sigma := (s)\)
3for \(len := 1\) to \(n-1\) do
4for each city \(q\notin\sigma\) do
5\(\Delta^1_q, \Delta^2_q :=\) the two smallest values of \(\Delta(\sigma[a],q,\sigma[a+1])\), \(a=1,\dots,len\)
6\(reg_q := \Delta^2_q-\Delta^1_q\) ▹ regret of \(q\)
7end
8\(k :=\) the city with maximum \(reg_q\) (ties: minimum \(\Delta^1_q\), then smallest index)
9insert \(k\) into its edge of minimum insertion cost
10end
11return \(\sigma\)

Run in Colab:PythonC++

  • Regret-\(k\) heuristics generalize the idea, summing the differences between the best option and the \(k-1\) next ones; they are widely used for vehicle routing problems, where a customer may have a single feasible route left (J.-Y. Potvin, J.-M. Rousseau, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European Journal of Operational Research 66 (1993) 331–340). The same idea applies to any assignment-like construction, such as items to bins.

  • As long as all the regrets are \(0\), the tie-breaking rule makes \(REG_2\) behave like \(CI\).

Example 30.16: \(REG_2\) against \(CI\) on the \(6\)-city instance

On the instance of Example 30.11, from city \(1\). In the first two steps all the regrets are \(0\) (the subtours \((1)\) and \((1,6)\) have one edge, or two copies of the same edge), and both \(REG_2\) and \(CI\) insert city \(6\) (cost \(4\)) and then city \(3\) (cost \(5\)), obtaining \((1,3,6)\) of length \(9\). At the third step the insertion costs on the edges \((1,3)\), \((3,6)\), \((6,1)\) are

city \(q\) costs \(\Delta^1_q\) \(\Delta^2_q\) \(reg_q\)
\(2\) \((2,2,7)\) \(2\) \(2\) \(0\)
\(4\) \((4,7,8)\) \(4\) \(7\) \(3\)
\(5\) \((6,5,6)\) \(5\) \(6\) \(1\)

\(CI\) inserts city \(2\), the cheapest, on the edge \((1,3)\). \(REG_2\) inserts city \(4\), the one with the largest regret, on the edge \((1,3)\): this edge is the only good place for city \(4\), while city \(2\) has two equally good places and can wait. The two constructions then continue:

\(CI\) \(REG_2\)
step 3 \(2\) on \((1,3)\), cost \(2\): \((1,2,3,6)\) \(4\) on \((1,3)\), cost \(4\): \((1,4,3,6)\)
step 4 \(4\) on \((1,2)\), cost \(4\): \((1,4,2,3,6)\) \(5\) on \((3,6)\), cost \(5\): \((1,4,3,5,6)\)
step 5 \(5\) on \((3,6)\), cost \(5\): \((1,4,2,3,5,6)\) \(2\) on \((3,5)\), cost \(1\): \((1,4,3,2,5,6)\)
length \(4+5+2+4+5=20\) \(4+5+4+5+1=19\)

At step \(4\) of \(REG_2\) the costs of city \(2\) on the edges of \((1,4,3,6)\) are \((6,2,2,7)\), regret \(0\), and those of city \(5\) are \((10,10,5,6)\), regret \(1\): city \(5\) goes first. City \(2\), postponed twice, is finally inserted for \(1\) instead of \(2\), between cities \(3\) and \(5\). \(REG_2(I)=19=z(I)\), while \(CI(I)=20\).

30.10.2 Look-ahead: the pilot method

The pilot method turns a constructive heuristic \(\mathscr{H}\), the pilot, into a stronger one. At each step it tries every candidate: the partial solution extended with the candidate is completed by \(\mathscr{H}\), and the candidate whose completed solution is best is added for good. With \(NN\) as pilot (denoted by \(PILOT\)-\(NN\)), the candidates are the next cities of the tour.

Algorithm: Pilot method with nearest neighbour

Input: TSP instance with \(n\) cities, distances \(d[1..n][1..n]\); starting city \(s\)
Output: Tour \(\sigma[1..n]\)
1Function PilotNN(\(n, d, s\))
2\(\sigma := (s)\)
3for \(len := 2\) to \(n\) do
4for each city \(q\notin\sigma\) do
5\(\tau_q :=\) the path \(\sigma\) extended with \(q\) and completed by \(NN\) ▹ look ahead
6end
7\(k :=\) the city \(q\) with minimum \(L(\tau_q)\) (smallest index)
8append \(k\) to \(\sigma\) ▹ the choice is final
9end
10return \(\sigma\)

Run in Colab:PythonC++

  • The pilot method is due to C. Duin and S. Voß (The pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs, Networks 34 (1999) 181–191). Each step runs the pilot once per candidate: with \(NN\) as pilot the running time is \(O(n^4)\) instead of \(O(n^2)\).

  • The pilot method is never worse than its pilot. At the first step, the candidate chosen by \(NN\) is among those tried, and its completion is the \(NN\) tour from \(s\), so the best completion found has length at most \(NN(I)\). At every later step, the completion of the chosen candidate is again among the completions tried at the next step (the candidate that \(NN\) would append), so the length of the best completion never increases. The final tour is the last completion, hence \(PILOT\)-\(NN(I)\le NN(I)\) from the same starting city.

Example 30.17: \(PILOT\)-\(NN\) on the TSP reference instance

From city \(1\), the candidates and their \(NN\) completions are:

partial path candidates: completed tour and length chosen
\((1)\) \(2\): \((1,2,4,3,5)\) \(28\); \(3\): \((1,3,2,4,5)\) \(25\); \(4\): \((1,4,2,3,5)\) \(25\); \(5\): \((1,5,2,4,3)\) \(22\) \(5\)
\((1,5)\) \(2\): \((1,5,2,4,3)\) \(22\); \(3\): \((1,5,3,2,4)\) \(25\); \(4\): \((1,5,4,2,3)\) \(25\) \(2\)
\((1,5,2)\) \(3\): \((1,5,2,3,4)\) \(23\); \(4\): \((1,5,2,4,3)\) \(22\) \(4\)
\((1,5,2,4)\) \(3\): \((1,5,2,4,3)\) \(22\) \(3\)

\(PILOT\)-\(NN\) goes first to city \(5\), the farthest from city \(1\), something \(NN\) would never do, and returns \((1,5,2,4,3)\) with \(L=9+4+3+4+2=22\), against \(NN(I)=25\) from the same city. The optimum \(18\) is not reached: the look-ahead is only as good as the pilot that performs it. On the \(6\)-city instance of Example 30.11, \(PILOT\)-\(NN\) from city \(1\) gives \(20\), against \(25\) for \(NN\).

Next: 30.11 What constructive heuristics give, and what they do not