Delivery Route Optimization for Smart Multimodal Mobility
Overview & Objective
An operations research platform developed as part of an ADEME call for expressions of interest alongside the CesiCDP research team to revolutionize logistics in intelligent multimodal urban mobility. Tackles the Traveling Salesman Problem with Precedence Constraints and Incomplete Graphs (TSP-CP), an NP-Hard problem proven via reduction from the classic TSP. Models road closures (blocked edges with infinite cost) and DAG delivery precedences. Implements and compares three distinct mathematical paradigms: an exact Integer Linear Programming solver (PuLP/CBC with MTZ subtour elimination), a greedy heuristic with 2-level backtracking ("relance"), and an evolutionary Genetic Algorithm with Order Crossover (OX) benchmarked across thousands of random topological graphs.
Mathematical Formulation & Complexity
The city network is represented as a connected, directed weighted graph G = (V, E, c) where V is the set of cities, E is the route network, and c_ij represents Euclidean distances. Three constraint classes govern the optimization: 1. Routing Viability: c_ij = infinity for blocked, prohibited, or under-construction road segments. 2. Precedence Constraints (DAG): A directed acyclic dependency set P where (i,j) in P requires city i to be visited before city j. 3. Hamiltonian Tour: The route must start and end at the depot (Node 0) while covering all target cities exactly once. We formally proved the NP-Completeness of this TSP-CP problem via reduction from standard TSP.
Three Algorithmic Paradigms Compared
Exact Solver (PuLP & CBC Branch-and-Cut)
Guarantees mathematically absolute optimality using binary edge variables x_ij and continuous MTZ variables u_i for subtour elimination. Exponential time complexity O(2^(n^2)), strictly viable for n <= 12.
Greedy Heuristic with Backtracking ("Relance")
Incrementally selects valid unvisited nodes with satisfied precedences using pre-computed Dijkstra shortest paths. If trapped in a topological dead-end, it searches two levels of visited nodes to untangle pathing.
Meta-Heuristic Genetic Algorithm
Represents candidate tours as chromosome permutations. Applies Order Crossover (OX) to preserve relative order without duplicate cities, heavy penalty functions for precedence violations, and 20-50% random swap mutation.
Engineering Artifacts & Diagrams
Click any diagram or visual artifact to examine in high resolution.
Calculated Exact Optimal Route
Visualization of the absolute optimal delivery tour computed via Integer Linear Programming, navigating blocked roads and satisfying all precedence rules.
Greedy Heuristic Route with Backtracking
Fast polynomial-time route produced by the greedy solver using Dijkstra paths and 2-level backtracking.
Evolutionary Genetic Route Solution
Near-optimal delivery path discovered by the Genetic Algorithm through generations of Order Crossover (OX).
Execution Time vs Network Size
Comparative execution time scaling: exponential growth of exact solver (O(2^(n^2))) versus stable polynomial growth of heuristic and GA.
Average Solution Cost vs City Count
Average cost comparison showing the GA tracking the exact optimal floor closely across increasing graph sizes.
Relative Optimality Gap (%)
Empirical measurement of relative error gap between heuristic solvers and exact optimum as network size increases.
Performance Gap Distribution Boxplot
Tight interquartile range of the Genetic Algorithm illustrating superior reliability and consistency over greedy heuristics.
Constraint Impact on Routing Efficiency
Sensitivity analysis showing how graph density, precedence rules, and road blockage rates compound route costs.
Multi-Dimensional Blockage Heatmap
Heatmap illustrating the compounding penalty of blocked routes: beyond 40% blockage, path costs plateau due to severe detours.
Genetic Algorithm Hyperparameter Sweeps
Sensitivity sweeps across population sizes, generation counts, and mutation rates (finding 5,000 population & 20-50% mutation optimal).
Key Engineering Highlights
Mathematical Problem Formulation (TSP-CP)
Proved NP-Completeness via reduction from classic TSP, formulating linear constraints with Miller-Tucker-Zemlin subtour elimination on weighted graphs G = (V, E, c).
Exact Integer Linear Programming Solver
Formulated Branch and Cut ILP models using PuLP and the CBC solver to calculate mathematically optimal delivery routes.
Greedy Heuristic with Two-Level Backtracking
Engineered a polynomial-time heuristic using precomputed Dijkstra shortest paths and a 2-level backtracking "relance" mechanism to escape graph dead-ends.
Order Crossover (OX) Genetic Algorithm
Implemented an evolutionary meta-heuristic with Order Crossover and heavy penalty functions, achieving near-optimal routes on large graphs.