Skip to content

README.md

Latest commit

 

History

History
203 lines (153 loc) · 6.48 KB

README.md

File metadata and controls

203 lines (153 loc) · 6.48 KB

🚛 Split Delivery Vehicle Routing Problem (SD-VRP)

Projet d’Optimisation Combinatoire – École Centrale Casablanca
Par Youssef Khalfa, Ismail Achbani, Ayoub Hamouch, Rayane Yajjou
Encadré par A. Ait El Cadi

Python PuLP Heuristic Status License

🎯 Objectif du projet

Le Split Delivery Vehicle Routing Problem (SD-VRP) est une variante du problème classique de tournées de véhicules (CVRP).
Ici, un client peut être servi par plusieurs véhicules, à condition que la totalité de sa demande soit satisfaite.

Le but est de minimiser la distance totale parcourue par la flotte, tout en respectant les contraintes de capacité.

Ce projet met en œuvre :

  • une modélisation exacte (MILP) avec le solveur PuLP/CBC
  • une méta-heuristique Variable Neighborhood Search (VNS) pour les grandes instances
  • une analyse comparative entre les deux approches sur 33 cas tests

Aperçu conceptuel

+-------------------------------------------------------------+
| Dépôt (0)                                                   |
|   |                                                         |
|   |----> Clients 1..n  (demandes qᵢ, coordonnées (xᵢ,yᵢ))   |
|                                                             |
| Objectif :                                                  |
|  Minimiser ΣₖΣᵢΣⱼ (distanceᵢⱼ × xᵢⱼₖ)                       |
|  Sous contraintes :                                         |
|   - Livraison complète : Σₖ yᵢₖ = qᵢ                         |
|   - Capacité : Σᵢ yᵢₖ ≤ Q                                   |
|   - Flux équilibré : Σⱼ xᵢⱼₖ = Σⱼ xⱼᵢₖ                      |
+-------------------------------------------------------------+

Structure du dépôt

📦 SD-VRP/
│
├──  README.md                 ← ce fichier
├──  rapport_sd_vrp.pdf        ← rapport complet du projet
├──  solveur.py                ← solveur exact (PuLP + CBC)
├──  SD_VRP_projet.ipynb       ← notebook explicatif + métaheuristique VNS
├──  Instances/                ← 33 cas tests (Case0 à Case32)
├──  SolutionsPulp/            ← fichiers de solutions générés
└──  Enonce_Projet.pdf         ← énoncé officiel du challenge

Installation & Exécution

Prérequis

  • Python ≥ 3.8
  • Bibliothèques : 
    pip install pulp numpy
  • Facultatif : Jupyter Notebook pour tester SD_VRP_projet.ipynb

Exécution du solveur exact (PuLP + CBC)

  1. Placez vos instances dans le dossier /Instances (format .txt)
  2. Lancez le script : 
    python solveur.py
  3. Le programme :
    • Lit automatiquement toutes les instances Case0 à Case32
    • Génère les solutions dans /SolutionsPulp/
    • Affiche la matrice des distances, le coût total et les routes

🧾 Exemple de sortie :

Route 1: 0 - 1 (4) - 2 (5) - 0
Route 2: 0 - 3 (6) - 0
Total cost: 31
Number of deliveries: 3
Truck loads: 9 6

Exécution de la méta-heuristique VNS

Dans le notebook SD_VRP_projet.ipynb :

  1. Importez les fonctions : 
    from SD_VRP_projet import variable_neighborhood_search
  2. Lancez une recherche : 
    best_solution, best_cost = variable_neighborhood_search(
    nb_customers=10,
    demands=[15, 20, 10, 5, 25, 15, 30, 20, 10, 5],
    capacity=50,
    distance_matrix=your_matrix,
    distance_depots=your_distances,
    max_iterations=100
)
print(best_solution, best_cost)
  3. Visualisez les routes avec matplotlib (intégré au notebook).

Algorithmes utilisés

Approche Type Description Avantage principal
PuLP + CBC Exacte Programmation linéaire mixte (MILP) avec Branch & Cut Solution optimale pour petites instances
VNS (Variable Neighborhood Search) Méta-heuristique Exploration multi-voisinages avec recherche locale Scalabilité et rapidité pour grandes instances

📊 Résultats principaux

Cas Méthode Coût total Nb livraisons Temps (s)
Case0 PuLP CBC 31 3 0.6
Case0 VNS 37 4 0.1
Case1 PuLP CBC — — >1000
Case1 VNS 30726 12 12

Les heuristiques se montrent plus efficaces pour les instances volumineuses.

Leçons et perspectives

  • Les méthodes exactes sont efficaces sur des cas réduits, mais peu scalables.
  • Les méta-heuristiques (VNS, Tabu, Clarke & Wright) offrent un bon compromis entre rapidité et qualité.
  • Pistes d’amélioration :
    • Hybrider CBC + VNS
    • Ajouter des contraintes réalistes (fenêtres de temps, multi-dépôts)
    • Intégrer un visualiseur dynamique (Plotly ou Folium)

🧑‍💻 Auteurs

Nom Rôle Compétences clés
Youssef Khalfa Optimisation & Programmation Modélisation MILP, Implémentation Python
Ismail Achbani Data & Solveur Analyse mathématique, résolution exacte
Ayoub Hamouch Algorithmes & Heuristiques Conception VNS, Tabu Search
Rayane Yajjou Simulation & Visualisation Tests, analyse comparative

Aperçu visuel (optionnel)

graph LR
A(Dépôt) --> B(Client 1)
A --> C(Client 2)
A --> D(Client 3)
B --> E(Dépôt)
C --> E
D --> E
Loading

Animation du projet (badges dynamiques)

Visitors GitHub last commit GitHub repo size Stars

🧾 Licence

Projet sous licence MIT — libre de réutilisation à des fins pédagogiques et de recherche.
Toute citation ou fork doit mentionner la source originale.

💬 Contact

📧 youssef.khalfa@etu.ec-lyon.fr ou youssef.khalfa1@gmail.com 📱+33 0745980437 📍 Centrale Casablanca / Centrale Lyon