A delivery routing problem with two real-world constraints added
The project is set in a scenario where our organisation, CesiCDP, answers a call for expressions of interest from ADEME, the French agency for ecological transition, on new mobility solutions. The assignment was to propose an algorithmic solution that limits vehicle trips and fuel consumption during delivery rounds, by computing on a road network the routes that connect a set of cities before returning to the starting point, at the lowest possible total cost.
The base problem was the travelling salesman problem, and we chose to add two constraints to bring it closer to a real situation. A delivery company rarely has a single vehicle, which took us from a TSP to a VRP, where several vehicles leave the same depot and share the customers between them. Not every road in a network is always available either, so we included roads closed for works as well as surcharged roads, such as toll roads.
A four-step chain from generator to metaheuristics
The project follows a four-step chain. A generator first produces random road networks, either as a complete graph or by connecting each city to its nearest neighbours, with a share of closed and surcharged roads. A greedy constructor then provides a first valid solution: each vehicle in turn adds the cheapest reachable customer, and goes back through the depot when closed roads leave it stuck. This greedy step is randomised through a restricted candidate list, following the GRASP principle, so that each run starts from a different point.
Three metaheuristics then improve this starting solution. Tabu search explores neighbouring solutions by swapping two cities within a route or moving a city from one route to another, and keeps the latest visited solutions in memory to avoid going in circles. Simulated annealing accepts worse solutions with a probability that decreases over the iterations, and the genetic algorithm evolves a population of solutions. A final step tunes the parameters of each method and compares them on instances of increasing size.
The mathematical model then parameter tuning
We spent a significant part of the project modelling the problem clearly before writing any code. The model defines one decision variable per road and per vehicle, an objective function that sums the cost of the roads used, and five constraints that enforce a single visit per customer, flow conservation, departure from and return to the depot, and the ban on closed roads. We then showed that our problem reduces to the travelling salesman problem when the number of vehicles is set to one and the forbidden roads are removed. This reduction establishes that the problem is NP-hard, which justifies the use of metaheuristics over exact solving, and it let us build on an extensive body of literature to choose and tune our methods.
Closed roads could be handled in two ways. The first gives them a very high cost so that no algorithm picks them, known as the Big-M method, and the second removes them from the graph before solving. We went with the second, which reduces the number of variables and avoids numerical instability, while keeping a safeguard in the cost function that discards any solution still using a closed road.
To offset the local nature of tabu search, we restarted it several times from different initial solutions produced by GRASP and kept only the best. This multi-start strategy turned out to be the most effective of the study.
Parameter tuning follows the OFAT method, which varies one parameter at a time while keeping the others at their reference value. Each configuration was evaluated on ten randomly generated instances, measuring the mean cost and its standard deviation so the conclusions would not depend on one particular graph.
Tabu and annealing beat greedy by 20 to 32%
Over the full study, from twenty to a hundred cities with tuned parameters, tabu search and simulated annealing are the most robust approaches, improving on the greedy baseline by 20 to 32 % and settling around 20 % on the largest instances. Annealing reaches the same quality as tabu search but is far slower, 108 seconds against 0.8 in the quick comparison at thirty cities, which makes multi-start tabu search the best trade-off between quality and computing time.
The genetic algorithm is competitive on small instances, with an 18.5 % gain at twenty cities, then degrades as size grows and ends up below the greedy baseline at a hundred cities. With a fixed population size and number of generations, its computing budget does not keep up with the growth of the problem.
A notebook graded A then a public Python module
The deliverable is a notebook that goes from formal modelling to statistical analysis, backed by a bibliography of around fifteen references, and the project received an A for both the deliverable and the presentation. I then extracted the code from the notebook into a reusable Python module, published in a public repository with a smoke test in continuous integration, a tagged release and a bilingual README so that anyone can rerun and check the study.