TSP Resolver
Constrained delivery routing: eight heuristics implemented, tuned and benchmarked from 5 to 3,000 cities.
CESI · Operations research · Team project (5 people)
- Brief
- ADEME → CesiCDP: cutting emissions from delivery rounds
- Problem
- TSP-PC-ER, NP-hard
- Algorithms
- 8 heuristics, 4 families
- Experimental plan
- N from 5 to 3,000, 5 instances per size
Key points
- NP-hardness proved by reduction: Ham-Cycle ≤p TSP ≤p TSP-PC-ER
- Eight heuristics implemented, each tuned by its own experimental plan
- Shared instances with a fixed seed: every algorithm judged on the same graphs
- Recommendation by size regime, with the study's own limits spelled out
Try it yourself
Every tour starts and ends at the depot. Dashed lines are forbidden roads, arrows are deliveries that must happen in order. The tour is built with nearest neighbour, then crossings are undone by 2-opt moves, rejecting any that would break a constraint, which the “blocked” counter tallies.
- Depot
- Closed road
- Must be delivered before
- Cost = fuel × distance + toll
- Cost
- 0.00
- Gain
- 0.0 %
- Reversals
- 0
- Blocked
- 0
Escaping the local optimum
Simulated annealing starts where a 2-opt descent stops, on its own randomly drawn instance. It accepts a worse solution now and then, with a probability that collapses as the temperature drops. The dashed line marks its starting point: anything below it was won by crossing a ridge.
Pale line: current cost. Solid line: best found. Dashed: the 2-opt local optimum, where annealing starts from.
- Depot
- Closed road
- Must be delivered before
- Cost = fuel × distance + toll
- Best cost
- 0.00
- 2-opt start
- 0.00
- Worse moves accepted
- 0
- Temperature
- 0.0000
This demo was written for this page and is independent from the deliverable. It uses the project's model (cost = fuel × distance + toll, forbidden roads, precedence constraints) on randomly drawn instances, but only two of the eight algorithms studied, at sizes of around thirty cities. The deliverable itself is a Python notebook available on the repository.
How it works
- 1
Model the ground truth
The network becomes a complete graph where every edge carries a real cost: toll plus fuel price per kilometre. Two constraints come from the field, some roads are closed, and some cities must be delivered before others.
- 2
Prove we are entitled to give up
Before writing a heuristic, you have to establish that no reasonable exact algorithm exists. That is done by polynomial reduction from Hamiltonian cycle, through the classic TSP. Without this step, choosing an approximation would be an admission of laziness rather than a decision.
- 3
Cover four families
Eight algorithms rather than one, chosen to span a wide range of the quality/time trade-off: one construction heuristic, one local search, four single-solution metaheuristics, two population-based methods.
- 4
Tune before comparing
Each algorithm first gets its own experimental plan to fix its parameters, pheromone evaporation rate, cooling schedule, tabu list length. Comparing badly tuned methods says nothing about the methods, only about the tuning.
- 5
Measure on the same graphs
A single seeded generator produces every instance. All eight algorithms face exactly the same graphs, from 5 to 3,000 nodes, with five instances per size, which removes the bias of a method that got lucky on easy cases.
Context
A simulated brief from ADEME to CesiCDP: optimise delivery rounds to cut fuel consumption and the emissions that go with it. The running example is deliberately concrete, a butcher's shop delivering Christmas orders from a Paris depot to Rennes, Rouen, Bordeaux, Toulouse and Lyon.
This is not the textbook travelling salesman
The textbook TSP minimises a distance on a graph where everything is allowed. The problem tackled here, written TSP-PC-ER, adds two layers that come from the field and change the nature of the work.
- A real cost rather than a distance: toll + fuel price per kilometre
- Edge restrictions: a road under works cannot be taken
- Precedence constraints: some cities must be delivered before others
- Practical consequence: a mathematically optimal solution that uses a closed road is worthless
Establish the hardness before choosing the approach
Membership in NP is checked on a certificate, an ordered tour, in linear time: each node appears once, no edge used is forbidden, the cost stays under the threshold, precedences hold. Hardness then follows by reduction from the classic TSP, simply by setting no precedence and no blocked road: the TSP is a special case of ours.
- The number of distinct tours is (n−1)!/2
- At 15 cities: more than 4 × 10¹⁰ routes
- At 20 cities: more than 6 × 10¹⁶
- Constraints shrink that number, but dividing by a constant does not change the order of magnitude
Eight algorithms, four families
The point is not to find "the right" algorithm but to span the quality/time trade-off widely enough for the comparison to mean something.
- Construction, Nearest Neighbour, in a multi-start variant
- Local search, multi-start Hill Climbing
- Single solution, simulated annealing, multi-start annealing, tabu search, tabu search with 2-opt
- Population, genetic algorithm, ant colony optimisation
What the measurements showed
No algorithm wins everywhere, and that is the interesting result: the right answer depends on instance size and on how much time you are willing to spend.
- Up to N ≈ 300 when quality matters most: tabu search with 2-opt dominates
- Beyond N ≈ 300: simulated annealing takes over, its runtime growing near-linearly
- At any size, as a fast reference: multi-start Nearest Neighbour, with a very good quality/time ratio
- Genetic and ant colony fall off beyond N ≈ 50 with the chosen parameters
- Multi-start annealing does not beat plain annealing: splitting the iteration budget across restarts leaves each one short of converging
What the experiment does not say
This is the part of the report I am happiest with. The measured gaps are expressed against a deliberately simple lower bound, half the sum of outgoing minima, which badly underestimates the optimal cost. The gap percentages therefore look enormous and do not reflect the true quality of the solutions: they rank the algorithms against each other, they do not measure a distance to the optimum.
- A tighter bound (Held-Karp, linear relaxation) would give a far more accurate picture
- Five seeds per size: too few to conclude below N = 30, where differences stay within noise
- Parameters tuned on N ≤ 30: transferring them to large instances is approximate, and a gap spike around N ≈ 50 gives it away
- That spike is not a property of the algorithms but an artefact of our own tuning, telling the two apart was the point of the analysis
What I took away
- Proving a problem's hardness before choosing how to attack it, rather than the other way round
- Tuning each method before comparing: otherwise you compare settings, not methods
- A measurement is only as good as its reference, here a loose bound made the gaps spectacular and uninformative
- Telling a result apart from an artefact of the protocol
- The same reflex serves me at Thales: trading accuracy against latency on measurements whose limits I know