Optimisation de covoiturage électrique autonome, 31× plus rapide que la baseline Branch-and-Price publiée avec jusqu'à 11× d'écarts plus serrés
Un MILP événementiel recentré sur les prises en charge et déposes (pas la géographie) plus une heuristique Adaptive Large Neighborhood Search — benchmarké sur 38 instances e-ADARP standard contre Su (2023) Branch-and-Price
Le covoiturage à la demande avec flottes électriques autonomes est la frontière de la mobilité urbaine. Le problème d'optimisation est brutal : fenêtres de temps de prise en charge / dépose, dynamique de batterie, détours par stations de recharge, équité des durées de trajet, tout ensemble, sur des instances avec des douzaines d'utilisateurs et plusieurs stations de recharge.
Notre mémoire de master co-encadré a conçu une formulation par graphe événementiel qui recentre le modèle sur les événements de prise en charge et de dépose plutôt que sur les emplacements (encodant implicitement les contraintes de capacité et d'appariement dans la topologie), plus une heuristique Adaptive Large Neighborhood Search qui passe à l'échelle là où les méthodes exactes abandonnent.
Le défi
Le Dial-A-Ride autonome électrique (e-ADARP) étend le DARP classique avec la dynamique d'état de charge de batterie, des visites non contraintes aux stations de recharge, et un coût multi-objectif pondéré qui arbitre la distance totale parcourue contre le temps de trajet excédentaire pour les utilisateurs. Les formulations par arcs (Bongiovanni et al. 2019, Su 2023) gèrent la taille du modèle avec la génération de colonnes, mais la combinatoire par nœud, capacité du véhicule, fenêtres de temps, appariement prise en charge/dépose, produit d'énormes relaxations LP que le branch-and-price doit résoudre à chaque nœud.
Les praticiens ont besoin à la fois d'un modèle qui capture la vraie physique et d'une heuristique qui renvoie des plans déployables en quelques secondes sur les instances plus grandes où les méthodes exactes calent.
Notre démarche
Nous avons adapté la formulation par graphe événementiel de Gaul et al. (2022), étendue aux véhicules électriques par Stallhofer (2023) mais limitée au cas mono-visite de recharge, au cas multi-visite étudié par Su (2023). Idée clé : les nœuds sont des Q-tuples encodant quels utilisateurs sont dans le véhicule, triés par ordre croissant ; les arcs sont des transitions d'événement faisables. La capacité du véhicule et l'appariement prise en charge-dépose sont encodés dans la topologie du graphe elle-même plutôt que comme contraintes linéaires explicites, ce qui rétrécit drastiquement la relaxation LP.
Nous avons serré la formulation davantage avec des vérifications de compatibilité fenêtre-temps × temps-de-trajet (une avancée sur le pruning de compatibilité sans temps de trajet de Stallhofer), ce qui permet d'éliminer de nombreux nœuds d'événement infaisables a priori. Combiné aux inégalités valides pour les chemins infaisables, le MILP résultant résout les instances type-a en quelques dizaines de secondes et les instances type-r en quelques heures sur Gurobi.
Côté heuristique, nous avons construit une Adaptive Large Neighborhood Search avec un portefeuille d'opérateurs de retrait (aléatoire, pire-distance, lié), d'opérateurs d'insertion (greedy, regret-k), un ajustement adaptatif des poids et un critère d'acceptation de type recuit simulé. La stratégie d'initialisation utilise le pré-résolu du domaine faisable γ = 0,1 plus facile comme warm-start pour les cas plus durs γ = 0,4 et γ = 0,7.
Nous avons benchmarké contre la baseline exacte Branch-and-Price et l'heuristique Deterministic Annealing de Su (2023) sur les jeux d'instances standard de Bongiovanni et Ropke (scénarios urbains type-a, instances réalistes type-r, urbains avec relocalisation de station type-u).
Le résultat
Livrable : une formulation MILP événementielle pour le Dial-A-Ride autonome électrique (e-ADARP) plus une heuristique Adaptive Large Neighborhood Search, benchmarkées contre la baseline Branch-and-Price publiée de Su (2023) sur 38 instances de test standard (type-a, type-r, type-u) à trois ratios batterie fin de journée (γ = 0,1, 0,4, 0,7).
Résultats de la méthode exacte : accélération moyenne 31× sur B&P à γ = 0,4 sur type-a (28,82 s vs. 910,33 s) ; écart d'optimalité moyen 11× plus serré sur type-r γ = 0,1 (0,27 % vs. 3,02 %) ; écart 5× plus serré sur le type-r γ = 0,7 le plus dur (1,24 % vs. 6,44 %) ; résout 35 / 38 instances à l'optimalité certifiée à γ = 0,1 vs. 33 / 38 pour B&P. Résultats de l'heuristique ALNS : accélération moyenne 10× sur la méthode exacte avec moins de 1 % de perte d'objectif, et sur r8-96 (la plus grande instance type-r, 96 utilisateurs) l'ALNS trouve 1 026,08 en 2 058 s là où la méthode événementielle exacte a besoin de 18 000 s pour un 1 026,44 légèrement pire — meilleure solution en 9× moins de temps.
Plongée technique
Le modèle derrière le résultat.
Le modèle
Le e-ADARP est un problème de routage multi-objectif avec la physique de la batterie superposée à un problème classique de prise en charge et dépose. La reformulation événementielle est la pièce maîtresse : au lieu d'une variable de décision par triplet (véhicule, lieu, lieu), ce qu'une formulation par arcs vous donne, nous avons une variable par arc dans un graphe d'événements où chaque nœud encode déjà qui est dans le véhicule. La capacité du véhicule (au plus Q utilisateurs) et l'appariement prise-en-charge-avant-dépose deviennent des propriétés structurelles du graphe plutôt que des contraintes linéaires. Le MILP ne gère ensuite que le global : temps, batterie et coût multi-objectif.
Encodage des nœuds d'événement. Chaque nœud v du graphe d'événements est un Q-tuple enregistrant le dernier événement de prise/dépose dans le slot 1 et les autres passagers actuellement dans le véhicule (triés croissants) dans les slots 2..Q. Les zéros remplissent les sièges vides ; un -1 final marque les états de station de recharge. Par construction, le tuple ne peut contenir un passager déjà déposé, donc la capacité du véhicule (au plus Q passagers) et l'appariement prise-en-charge-avant-dépose sont encodés structurellement dans V, pas comme contraintes.
Coût multi-objectif et conservation de flot. L'objectif arbitre le coût de routage du véhicule (∝ temps de trajet) contre le temps de trajet excédentaire R_i des utilisateurs, avec poids w_1, w_2 choisis par l'opérateur. La conservation de flot dit : à chaque nœud d'événement non-dépôt, chaque arc entrant est compensé par un arc sortant. Combiné à la contrainte explicite ‘chaque utilisateur servi exactement une fois' (Σ_{δ^in(v), v ∈ V_i} x_a = 1), cela donne un problème de flot à coût minimal sur le graphe d'événements.
Contraintes de temps. L'heure de début de service T_w à l'événement suivant doit être au moins l'heure de début de l'événement précédent plus le temps de service plus le temps de trajet, avec un big-M (l'horizon H) désactivant la contrainte quand l'arc n'est pas utilisé. La borne de temps de trajet impose l'équité : pour tout utilisateur i, le temps entre sa prise en charge et sa dépose ne peut excéder le temps max de trajet p_i (le système ne peut pas garder quelqu'un indéfiniment dans le véhicule juste pour optimiser le routage).
Dynamique de l'état de charge de la batterie. Entre événements non-recharge, le SoC au nœud suivant B_w égale B_v moins la décharge β_{(v,w)} = µ · t_{(v,w)} le long de l'arc. Aux nœuds de station de recharge (V_z), la batterie est rechargée de α · E_v où α est le taux de recharge et E_v la durée de recharge. Les versions ≥ symétriques des deux contraintes (omises) fixent l'égalité quand l'arc est utilisé. La contrainte de fin de journée B_v ≥ γG force les véhicules à revenir au dépôt avec au moins une fraction γ de la capacité (le paramètre vedette du benchmark, γ = 0,7 est le cas dur).
Temps de trajet excédentaire. R_i est la mesure d'équité utilisateur : c'est la différence entre le temps réel dans le véhicule (T_dépose − T_prise_en_charge − temps de service) et le temps minimum t_{(i, n+i)} qu'il passerait sur un trajet direct. Minimiser le total Σ R_i est le second objectif, sans lui l'optimiseur garderait volontiers quelqu'un dans le véhicule pendant des heures pour consolider les trajets.
Pourquoi la formulation événementielle gagne. Le modèle par arcs (Bongiovanni 2019, Su 2023) a une variable par triplet (véhicule, lieu, lieu), mais la plupart de ces triplets sont infaisables (mauvais état de capacité, violation de fenêtre, violation d'appariement) et le solveur doit le découvrir pendant le branch-and-bound. Le graphe d'événements prune les états infaisables à la construction : les vérifications de compatibilité fenêtre-temps × temps-de-trajet éliminent des nœuds qu'un modèle par arcs garderait. Pour les instances type-a à Q = 6, on obtient ~150–1 500 nœuds et ~1 500–16 000 arcs, gérables pour le branch-and-cut de Gurobi.
Inégalité valide pour les chemins infaisables. Pour tout utilisateur i et tout chemin à deux arcs P = (a, b) dans le graphe d'événements où i est dans le véhicule, si le temps de trajet combiné excède p_i, alors au plus |P| − 1 = 1 des arcs peut être actif. Ajouter ces inégalités en amont (au lieu d'attendre que le branch-and-bound les découvre via les coupes) resserre la relaxation LP de manière notable sur les instances type-r et type-u.
La formulation événementielle est l'innovation structurelle ; l'ALNS est la couche d'ingénierie déployable au-dessus. Sur les instances petites à moyennes (16-48 utilisateurs, 2-5 véhicules) le MILP événementiel résout jusqu'à l'optimalité prouvée plus vite que la baseline B&P publiée. Sur les plus grandes (96 utilisateurs sur type-r, 50 sur type-u) le MILP commence à atteindre la limite à γ = 0,7, et l'ALNS prend le relais avec des solutions quasi optimales en secondes à minutes. Comparée à la baseline Deterministic Annealing de Su (2023), l'ALNS trouve des valeurs objectif égales ou meilleures dans la plupart des cas, au prix d'un temps wall-clock légèrement plus élevé. Le résultat est un système à deux niveaux : utiliser le MILP événementiel exact quand on le peut, retomber sur l'ALNS quand on ne le peut pas.
Benchmark
MILP événementiel vs Su (2023) Branch-and-Price sur les instances de benchmark type-r (banc de test réaliste Bongiovanni-Ropke, ratio batterie fin de journée γ = 0,7, le réglage le plus dur). Chaque ligne est une instance (véhicules, utilisateurs). Valeurs objectif en unités pondérées (coût de trajet + temps excédentaire) ; écarts en % vs borne inférieure prouvée. Limite de temps 18 000 s. Objectif plus bas = meilleur ; écart plus bas = meilleur.
| Instance | Obj. événementiel | EB Écart (%) | EB Temps (s) | Su (2023) B&P Obj. | B&P Écart (%) | B&P Temps (s) |
|---|---|---|---|---|---|---|
| r5-60 | 686,36 | 0,10 | 18 000 | 688,84 | 0,70 | 18 000 |
| r6-48 | 508,10 | 0,00 | 2 364 | 508,10 | 0,00 | 2 028 |
| r6-60 | 689,55 | 0,00 | 1 703 | 689,55 | 0,00 | 6 605 |
| r6-72 | 765,25 | 0,41 | 18 000 | 788,83 | 4,96 | 18 000 |
| r7-56 | 615,86 | 0,52 | 18 000 | 616,16 | 0,00 | 14 247 |
| r7-70 | 756,31 | 0,04 | 18 000 | 765,49 | 1,48 | 18 000 |
| r7-84 | 891,38 | 2,39 | 18 000 | 1 004,81 | 21,65 | 18 000 |
| r8-64 | 632,61 | 0,00 | 2 493 | 632,61 | 0,00 | 18 000 |
| r8-80 | 806,87 | 2,19 | 18 000 | 794,41 | 0,00 | 15 051 |
| r8-96 | 1 064,86 | 6,74 | 18 000 | 1 174,49 | 35,68 | 18 000 |
| Moy. | - | 1,24 | 13 256 | - | 6,44 | 14 593 |
Deux motifs. Premièrement, le MILP événementiel atteint un écart d'optimalité moyen 5× plus serré (1,24 % vs 6,44 %) sur ces instances dures γ = 0,7, et sur la plus grande (r8-96), la différence d'écart est de 6,74 % vs 35,68 %, la solution événementielle étant 9,3 % meilleure en valeur. Deuxièmement, sur les instances que les deux méthodes résolvent à l'optimalité (r6-48, r6-60, r8-64), le MILP événementiel est systématiquement plus rapide, parfois d'un facteur 7 (r8-64 : 2 493 s vs 18 000 s pour B&P). L'élagage structurel au moment de la construction du graphe paie surtout sur les instances à fenêtres serrées et nombreux utilisateurs, exactement là où le B&P par arcs galère. Sur les instances plus faciles γ = 0,1 (non montrées), l'écart est encore plus déséquilibré : événementiel 0,27 % moy. vs B&P 3,02 %, un écart 11× plus serré.
Tiré du dossier
Techniques
- Formulation par graphe événementiel
- Programmation linéaire mixte (B&C via Gurobi)
- Adaptive Large Neighborhood Search
- Portefeuille d'opérateurs de retrait/insertion
- Acceptation par recuit simulé
- Inégalités valides de chemins infaisables
Stack
- Julia
- Gurobi
- Benchmarks d'instances Bongiovanni-Ropke
Un problème de ce type ?