Navigation · Theory · M8
M8-T1 — Waypoint Missions and Route Ordering
One robot, many stops: the order in which Scout visits them can matter more than how well it drives between them.
A delivery robot rarely has one goal. The pharmacy hands it eight parcels, the wards phoned them in at random, and every metre driven in the wrong order is a metre that delays a patient. Choosing the order is a different problem from planning each leg, and it is a famously hard one. The good news is that quick rules get most of the way.
Learning objectives
After this lesson, you should be able to:
- Build a cost matrix between stops from a path planner and explain why straight-line distance is not enough.
- Construct a tour with the nearest-neighbour rule and improve it with 2-opt moves.
- State how many orders there are, and why exact search stops being feasible within a few dozen stops.
- Name the constraints that real missions add: time windows, priorities, precedence and battery.
The intuition
Imagine the pharmacy hands Scout six parcels. The request list is in the order the wards phoned: a bed on the top floor, a ward on the ground floor, the top floor again. Driven as listed, Scout rides the lift up and down and crosses the building three times. A person who sees the list sorts it first: everything on this floor, then the next. That sorting is route ordering.
The idea splits the mission into two layers. The lower layer is what the earlier modules built: given two places, find the cheapest way to drive from one to the other. The upper layer treats each of those answers as a single number, the cost of going from stop i to stop j, and chooses the order of the stops that makes the total smallest. The planner never needs to know about parcels, and the scheduler never needs to know about corridors.
The simplest scheduling rule is greedy: from where you stand, go to the closest stop you have not yet visited. It is quick and sensible and it leaves a typical mess behind, because it ignores the end of the tour: the last stops it leaves are scattered, and Scout must cross the building to reach them and again to go home. A second rule repairs the mess: look for two legs that cross, and reverse the stretch of tour between them.
The mathematics
The cost matrix
Number the depot 0 and the stops 1 to n. Let c(i, j) be the cost of driving from stop i to stop j. This is the output of the global planner (module 3), run once for each pair, on the costmap of module 2. It is a time or a distance, not a straight line, and it need not be symmetric: a one-way lane or a slope makes the way back different.
- n
- number of stops, not counting the depot
- π
- an order of the stops: a permutation π1, …, πn, with π0 = 0 the depot
- c(i, j)
- cost from stop i to stop j, from the planner
- J(π)
- total cost of the tour
If Scout does not need to come back, drop the last term (an open tour), or add a dummy stop that is free to reach from anywhere and free to leave to the depot. The problem is the travelling salesman problem (TSP); with the constraints below it is a vehicle routing problem.
How many orders?
The problem is NP-hard (Karp, 1972, listed the Hamiltonian cycle problem, from which the TSP follows). The best exact algorithm that works for any costs, the dynamic program of Held–Karp and Bellman, takes time proportional to n² 2n: 7.4 million steps for 15 points, 4.2 × 108 for 20. That is far better than n!, and it still doubles with every stop.
Nearest neighbour
- Start at the depot and mark it visited.
- From the current stop, go to the closest stop that is not yet visited; mark it visited.
- When every stop is visited, return to the depot.
The work is about n² comparisons. The tour can be much worse than the best one: for costs that obey the triangle inequality the greedy tour is never more than about (⌈log₂ n⌉ + 1)/2 times the best (Rosenkrantz, Stearns and Lewis, 1977), and there are instances that reach a ratio growing with log n. On random maps it is typically around 25 percent above the best.
2-opt
Remove two edges of the tour and reconnect the two pieces the other way. If the tour is a, b, …, c, d, … the move replaces the edges (a, b) and (c, d) by (a, c) and (b, d), and reverses the stretch from b to c (both ends included):
A tour with no such move is 2-optimal. With symmetric costs and the triangle inequality, two crossing edges can always be replaced by two shorter ones, so a 2-optimal tour has no crossings. On random maps 2-opt typically ends about 5 percent above the best tour (Johnson and McGeoch, 1997). Croes introduced the move in 1958; Lin and Kernighan (1973) generalised it to variable-depth moves that are the basis of the best practical heuristics.
A worked example
Six points, by hand. The depot D is at (0, 0) m. The five stops are A (8, 0), B (2, 6), C (10, 6), E (5, 3) and F (0, 10). The wards requested them in the order A, B, C, E, F, and driving that order and returning costs 48.92 m.
Nearest neighbour. From D the closest stop is E, at √(5² + 3²) = 5.83 m. From E the closest is A (4.24 m), then from A the closest is C (6.32 m), then B (8.00 m), then F (4.47 m), and finally F returns to D (10.00 m). The tour D, E, A, C, B, F, D has length 5.83 + 4.24 + 6.32 + 8.00 + 4.47 + 10.00 = 38.87 m (the sum of the unrounded legs), already 20.5 percent shorter than the request order.
One 2-opt move. The legs C→B (8.00 m) and F→D (10.00 m) cross. With a = C, b = B, c = F, d = D:
Reversing B, F gives D, E, A, C, F, B, D of length 5.83 + 4.24 + 6.32 + 10.77 + 4.47 + 6.32 = 37.97 m (again summed before rounding). No further move has Δ < 0. Searching all 5! = 120 orders confirms that 37.97 m is the shortest closed tour of these six points, so here the cheap rule plus one repair found the best answer. That is common for small maps and not guaranteed for large ones.
Why not try everything? For 10 stops there are 3 628 800 orders, still a fraction of a second of work. For 15 there are 1.3 × 1012: at a million tours per second that is about 15 days. Lab M8-L1 lets you feel both ends: stage 3 searches all orders of six stops with pruning, and the question asks what 12 stops would cost.
Engineering implications and limitations
Build the matrix from the planner, not from a ruler
A ward ten metres away on the other side of a wall may be sixty metres away by corridor and lift. Ordering by straight-line distance sends Scout to the wrong place first. Compute the matrix with the same planner and costmap the robot will drive with, in seconds rather than metres if speed zones differ, and recompute it when the map changes (a door closes: lab M3-L4). With n + 1 places, one search from each place gives a whole row (Dijkstra gives the cost to every place in one run), so the matrix costs n + 1 searches.
The real constraints
| Constraint | Example at Meridian General | What it changes |
|---|---|---|
| Time windows | Chemotherapy drugs must arrive within 20 minutes of mixing | The order must respect deadlines; the search is the vehicle routing problem with time windows |
| Priority | A STAT blood sample outranks the linen | Cost becomes weighted lateness, not distance alone |
| Precedence | Pick up at pharmacy, then deliver to ward 4 | Pairs of stops that must be in order |
| Capacity and battery | Scout carries four parcels, and needs a charge after 5 hours | A tour may have to be split into trips (lesson M8-T6) |
| Changes en route | A new urgent request arrives at 10:12 | Reorder the unvisited stops, keeping the one Scout is driving to |
Use a solver, and keep the greedy as a fallback
For production use, a vehicle-routing solver (for example the routing library of OR-Tools) takes the matrix and the constraints, builds a first tour with a greedy rule and improves it with local search. Keep a plain nearest-neighbour or insertion rule behind it so that a solver time-out still leaves a sensible order. Re-solve when something changes, but do not reorder the stop Scout is already driving towards.
Test with the request order as the baseline
Report the length of the chosen order against the request order and, for small cases, against the exact answer. A scheduler that is no better than the request order is not doing its job; one that is within a few percent of the exact answer on small cases is probably fine on large ones.
Common misconceptions
“Nearest neighbour is nearly optimal.”
It is cheap and often decent, but it is blind to the end of the tour. A ratio of 1.25 on random maps is typical, and designed maps can make it much worse.
“Straight-line distances are good enough for ordering.”
Walls, one-way lanes and lifts change which stop is “near”. The matrix has to be path costs from the planner.
“NP-hard means we cannot solve it.”
It means no known algorithm is fast for every instance. Dozens of stops can be solved exactly with good solvers, and heuristics are within a few percent for thousands.
“2-opt always finds the best tour.”
It finds a local optimum: a tour with no improving 2-opt move. A different start can end in a different, sometimes better, tour.
Engineering takeaways
- Route ordering is a layer above path planning: it uses planner costs between stops and chooses the order.
- There are n! orders for n stops, and the problem is NP-hard; exact methods are feasible for a few dozen stops at best.
- Nearest neighbour is a fast first tour; 2-opt repairs crossings by reversing a segment while Δ is negative.
- A 2-optimal tour is a local optimum, not a guarantee of the best tour.
- Real missions add time windows, priorities, precedence, capacity and battery, and change while Scout drives.
References and further reading
The original heuristic and complexity results, and a standard book on the travelling salesman problem.
- G. A. Croes, “A method for solving traveling-salesman problems”, Operations Research 6(6), 1958.
- M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics 10(1), 1962.
- S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem”, Operations Research 21(2), 1973.
- D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis, “An analysis of several heuristics for the traveling salesman problem”, SIAM Journal on Computing 6(3), 1977.
- D. L. Applegate, R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006.
Knowledge check
Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.
Question 1
In a tour …, a, b, …, c, d, … the edges a–b, c–d, a–c and b–d have lengths 8, 10, 6 and 7 metres. What is Δ for the 2-opt move, and do you apply it?
Explanation
Δ = c(a,c) + c(b,d) − c(a,b) − c(c,d) = 6 + 7 − 8 − 10 = −5 m. It is negative, so apply the move: reverse the stretch b … c, and the tour becomes 5 m shorter.
Question 2
Scout has a fixed depot and eight stops to visit. How many orders are there, and why can you still search them all?
Explanation
8! = 40 320 orders (20 160 different tours if a tour and its reverse count as one). That is small enough for an exhaustive search. At 15 stops the count is 1.3 × 10¹², which is not.
Question 3
Two wards are 8 m apart in a straight line, with a wall between them, and 55 m apart by corridor. Which number belongs in the cost matrix, and why?
Explanation
55 m (or the time it takes). The matrix must hold what the robot will actually drive, which is the planner’s path cost. The straight-line 8 m would make the scheduler think the wards are neighbours and put them next to each other in the order.
What’s next
Next: when the job is to touch every part of a floor rather than a list of points: coverage path planning.
Related content
Nothing below is required to finish this lesson.
- LabM8-L1: Order the Stops
Eight deliveries, one robot: find an order that is much shorter than the order they were requested in.
Get notified when the next lesson and new labs are released.
One email per new lesson or lab.