🚚 Smart Mobility Optimization Engine: ACO & Genetic Algorithms

A comparative study of metaheuristics (Ant Colony Optimization vs. Genetic Algorithms) applied to the Vehicle Routing Problem (VRP) in a Smart City context.

---

📑 Table of Contents

• 📖 Context & Objectives
• 📐 Mathematical Formulation
• 🧠 Algorithms Implemented
• 📊 Key Results
• 🚀 Installation & Usage
• 📂 Project Structure

---

📖 Context & Objectives

This project operates within the framework of the CESI CDP research laboratory, addressing a call for experimentation by ADEME (French Agency for Ecological Transition).

The Challenge: Modern urban logistics face a critical "Last-Mile Delivery" problem. As cities grow, standard delivery routes become inefficient, leading to:

• 📈 Increased CO2 emissions.
• 💸 Higher operational costs.
• 🚦 Traffic congestion.

Our Solution: An algorithmic engine designed to solve the Vehicle Routing Problem (VRP). By simulating thousands of potential routes using bio-inspired metaheuristics, this tool identifies near-optimal paths that minimize total fleet travel distance while respecting capacity constraints.

---

📐 Mathematical Formulation

The problem is modeled as a Capacitated Vehicle Routing Problem (CVRP) defined on a graph $G = (V, E)$.

1. Variables

Let $x_{ij}^k$ be a binary decision variable:

• $x_{ij}^k = 1$ if vehicle $k$ travels from node $i$ to node $j$.
• $x_{ij}^k = 0$ otherwise.

2. Objective Function

Minimize the total distance traveled by all vehicles:

$$\text{Minimize } Z = \sum_{k \in K} \sum_{i \in V} \sum_{j \in V} c_{ij} x_{ij}^k$$

Where $c_{ij}$ is the travel cost (distance) between nodes $i$ and $j$.

3. Key Constraints

• Visits: Each customer $i$ must be visited exactly once. $$\sum_{k \in K} \sum_{j \in V} x_{ij}^k = 1, \quad \forall i \in V \setminus {0}$$
• Flow Conservation: If a vehicle arrives at a node, it must leave it. $$\sum_{i \in V} x_{ij}^k - \sum_{i \in V} x_{ji}^k = 0, \quad \forall j \in V, \forall k \in K$$
• Capacity: The total demand carried by a vehicle $k$ must not exceed its capacity $Q$. $$\sum_{i \in V \setminus {0}} d_i \sum_{j \in V} x_{ij}^k \leq Q, \quad \forall k \in K$$

---

🧠 Algorithms Implemented

This repository implements and compares two major metaheuristic approaches against a baseline greedy algorithm.

🐜 1. Ant Colony Optimization (ACO)

Based on the pheromone trail laying behavior of ants.

• Mechanism: Artificial ants construct solutions probabilistically. Good paths are reinforced with "pheromone" (increasing selection probability), while bad paths "evaporate" over time.
• Key Parameters: $\alpha$ (pheromone importance), $\beta$ (heuristic visibility), $\rho$ (evaporation rate).
• Code: ACO.ipynb

🧬 2. Genetic Algorithm (GA)

Based on Darwinian natural selection.

• Representation: Routes are encoded as permutations of customer indices.
• Selection: Tournament selection to prefer fitter individuals.
• Crossover: Order Crossover (OX1) to produce valid child routes.
• Mutation: Swap mutation to maintain population diversity and escape local optima.
• Code: GA_1.ipynb

---

📊 Key Results

Our benchmarks on varying dataset sizes reveal:

• ACO tends to converge faster to high-quality solutions for small-to-medium graphs ($N < 50$).
• GA shows better robustness in exploring the search space for larger instances, avoiding premature convergence.

---

🚀 Installation & Usage

Prerequisites

• Python 3.8+
• Jupyter Notebook

Setup

# Clone the repository
git clone [https://github.com/TheotimeC/VehicleRoutingProblem-ACO-GA.git](https://github.com/TheotimeC/VehicleRoutingProblem-ACO-GA.git)
cd VehicleRoutingProblem-ACO-GA

# Install dependencies
pip install matplotlib numpy pandas notebook

Running the Solvers

Launch Jupyter Notebook to interact with the solvers:

jupyter notebook

• To run the Genetic Algorithm: Open GA_1.ipynb and run all cells.
• To run the Ant Colony Algorithm: Open ACO.ipynb.
• To view comparative stats: Run Algo_statistiques.ipynb.

---

📂 Project Structure

File	Description
ACO.ipynb	Main implementation of Ant Colony Optimization logic.
GA_1.ipynb	Genetic Algorithm solver with crossover/mutation operators.
Algo_statistiques.ipynb	Benchmarking suite to compare algorithm performance.
AlgoDeBase.ipynb	Nearest Neighbor Heuristic (Baseline for comparison).
Livrable1.ipynb	Preliminary analysis and mathematical modeling notes.

---

👤 Authors

Théotime Colinet Engineering Student

Tom Seitz Engineering Student