Welcome to my repository. This project represents a deep dive into advanced Operations Research and optimization algorithms, specifically tackling a constrained variant of the Traveling Salesman Problem (TSP). Developed as part of an ADEME call for expressions of interest alongside the CesiCDP team, this project aims to revolutionize delivery logistics in the context of intelligent multimodal mobility.
If you are a technical recruiter, engineering manager, or a fellow developer, this README will provide you with a comprehensive look at my algorithmic thought process, the mathematical formulations used, and the practical software engineering applied to build this logistics solver from the ground up.
- Context and Vision
- Problem Formulation
- Technical Stack
- Methodology and Algorithmic Approaches
- Experimental Results and Evaluation
- Challenges and Key Learnings
In modern logistics, efficient package delivery is not just about finding the shortest path; it is about navigating a complex web of real-world constraints. An enterprise needs to minimize the total distance traversed, the time spent on the road, and the associated operational costs.
However, real-world routes are rarely straightforward. We face constraints such as:
- Blocked or High-Cost Routes: Roads may be under construction or heavily restricted, making them infinitely expensive to cross.
- Precedence Constraints: Certain deliveries must happen before others. Some packages act as prerequisites in the supply chain.
Our objective was to model and solve an optimized routing problem that closely mirrors these real-world challenges, delivering solutions that are mathematically sound and practically viable for active transport networks.
The core of our challenge is a NP-Hard problem, proven via reduction from the classic Traveling Salesman Problem (TSP).
We represent our city network as a connected, weighted graph
-
$V$ represents the set of cities (nodes). -
$E$ represents the available routes (edges). -
$c_{i,j}$ denotes the cost (Euclidean distance) to travel from city$i$ to city$j$ .
Constraints:
-
Routing Viability:
$c_{i,j} = \infty$ for blocked or prohibited routes. -
Precedence (DAG): A set
$P \subseteq V^2$ defines dependencies. If$(i,j) \in P$ , city$i$ must be visited before city$j$ . - Hamiltonian Cycle: The route must start and end at the depot (Node 0) while covering all target cities exactly once.
This formulation transitions our challenge from a standard TSP into a TSP with Precedence Constraints and Incomplete Graphs (TSP-CP). We proved the NP-Completeness of this exact problem by demonstrating that verification takes polynomial time
To bring this mathematical model to life, I utilized a robust Python-based data science and optimization stack:
- Language: Python 3.x
- Graph Theory & Data Structures:
networkxfor graph generation, DAG validation, and shortest-path (Dijkstra) preprocessing. - Optimization Solvers:
PuLPlibrary interfacing with theCBC(Coin-or branch and cut) solver for Integer Linear Programming. - Data Engineering & Visualization:
pandas,numpy,matplotlib, andseabornfor automated benchmarking, metric aggregation, and generating deep statistical insights.
To thoroughly explore the solution space, I developed three distinct algorithms, each representing a different trade-off between execution speed and solution optimality.
Our baseline is an exact solver using the Branch and Cut method. It guarantees the absolute optimal path by evaluating the entire solution space via linear relaxation and dynamic constraint generation.
-
Variables: Binary variables
$x_{i,j}$ for edge selection, and continuous variables$u_i$ for MTZ (Miller-Tucker-Zemlin) subtour elimination and precedence tracking. -
Characteristics: Provides the mathematically perfect answer but suffers from exponential time complexity
$O(2^{n^2})$ . It is strictly viable for small network instances (typically$n \le 12$ ).
Visualization of a calculated optimal route avoiding blocked paths and respecting all precedence rules.
To handle larger networks where the exact algorithm times out, I engineered a highly optimized greedy heuristic.
- Strategy: It builds the route incrementally. At each step, it evaluates all unvisited nodes whose precedence dependencies are satisfied, selecting the one with the lowest cost using pre-computed Dijkstra shortest paths.
- Innovation: If the algorithm encounters a dead-end (due to blocked routes), it triggers a backtracking "relance" mechanism. It searches through up to two levels of already-visited nodes to bridge the gap, effectively untangling itself from complex graph topologies.
- Characteristics: Extremely fast (polynomial time) and scales well, though it sacrifices absolute optimality for speed.
The heuristic algorithm efficiently navigates the graph, finding a near-optimal solution in a fraction of a second.
To bridge the gap between the blazing speed of the heuristic and the perfect accuracy of the exact solver, I implemented a Genetic Algorithm.
- Encoding: The "DNA" of each individual in the population is an ordered sequence of cities.
- Fitness: Evaluated based on the total route distance. Individuals violating constraints are penalized heavily.
- Operators:
- Selection: Retains the top 40% of the population.
- Crossover: Uses Order Crossover (OX) to combine parent routes while preventing duplicate city visits.
- Mutation: Randomly swaps two cities (with a 10% probability) to maintain genetic diversity and escape local minima.
- Characteristics: Highly adaptable. With the right hyperparameters, it converges to exceptionally high-quality solutions on large graphs without the exponential time penalty.
The genetic algorithm evolving over generations to converge on a highly optimized delivery network.
A robust optimization system must be backed by empirical evidence. I built an automated benchmark suite to test these algorithms against thousands of randomly generated graphs (varying from
The core trade-off in operations research is between time and quality.
Execution time growth. Notice the rapid exponential scaling of the Exact (PuLP) solver compared to the stable polynomial growth of the Heuristic and Genetic approaches.
Average solution cost. The exact solver defines the absolute floor (lowest cost). The Genetic algorithm significantly outperforms the greedy Heuristic on complex instances, producing near-optimal costs.
To quantify how "good" the approximate algorithms are, we measured their relative gap to the exact optimal solution.
As graph size increases, the standard heuristic maintains a stable gap of 60-80%. The optimized genetic algorithm closely tracks the optimum, proving its value on larger datasets.
Distribution of the performance gap. The Genetic algorithm shows a tighter interquartile range, indicating much higher consistency and reliability across varying network structures compared to the heuristic.
Real-world constraints drastically alter network traversability. I conducted a deep sensitivity analysis to understand how density, precedences, and blocked routes impact our routing efficiency.
Higher graph density lowers costs (more alternative routes). Conversely, increasing precedence rules and blocked routes creates bottlenecks, forcing all algorithms into higher-cost detours.
A multi-dimensional heatmap illustrating the compounding penalty of blocked routes. Beyond a 40% blockage rate, the network cost plateaus at a high threshold, indicating severe pathing difficulties.
The performance of the Genetic Algorithm is highly dependent on its configuration. I ran exhaustive sweeps across population sizes, generation counts, and mutation rates to find the optimal balance between exploration and exploitation.
Sensitivity analysis revealing that a population of 5000 individuals over 2000 generations yields the best cost-to-time ratio. A mutation rate of 20-50% was found to be the sweet spot for avoiding local minima without destroying valuable genetic traits.
Building this routing engine pushed my technical capabilities across several domains:
- Translating Math to Code: Modeling MTZ subtour elimination constraints in PuLP required strict attention to mathematical logic. Translating theoretical ILP into functional Python code was a deeply rewarding challenge.
- Handling Graph Disconnections: The heuristic algorithm initially struggled with dead ends when facing dense pockets of blocked routes. Engineering the multi-level backtracking mechanism taught me how to blend greedy choices with dynamic path correction.
- Genetic Algorithm Validation: Ensuring that Order Crossover (OX) always produced mathematically valid offspring (no missing cities, no duplicates) required rigorous unit testing and precise array manipulations.
- Data Pipeline Optimization: Running thousands of benchmark instances could take days. I had to optimize the benchmarking pipeline, utilizing caching and efficient Pandas DataFrame merges to make the analysis computationally feasible.
This project is a testament to my passion for solving complex, computationally hard problems with a blend of rigorous mathematics and clean, scalable software engineering. By tackling a highly constrained variant of the Traveling Salesman Problem, I demonstrated the ability to not only implement theoretical algorithms but also to analyze their performance, tune their parameters, and extract meaningful business insights from the data.
Thank you for exploring this repository. I am always excited to discuss operations research, graph theory, and algorithmic design.