The dial-a-ride problem: models and algorithms
Cordeau Jean-François et al. — 2007
Résumé (FR)
Cet article passe en revue la littérature scientifique sur le problème du dial-a-ride (DARP), qui consiste à concevoir des routes et des horaires pour des utilisateurs spécifiant des requêtes de ramassage et de dépose entre origines et destinations. Les auteurs décrivent les principales caractéristiques du problème et résument les modèles et algorithmes les plus importants développés jusqu’en 2007. Le DARP est fondamentalement demand-driven : les routes sont entièrement déterminées par les requêtes individuelles des passagers et leurs contraintes temporelles. L’article analyse l’impact des contraintes de fenêtres de temps, de capacité des véhicules et de qualité de service sur les solutions optimales. Les auteurs comparent les approches exactes et les métaheuristiques pour la résolution du problème à grande échelle. Ce travail de référence établit le cadre conceptuel fondamental de la modélisation des systèmes de transport à la demande passager.
Summary (EN)
This paper reviews the scientific literature on the dial-a-ride problem (DARP), which involves designing vehicle routes and schedules for users specifying pickup and delivery requests between origins and destinations. The authors describe the main problem features and summarize the most important models and algorithms developed up to 2007. DARP is fundamentally demand-driven: routes are entirely determined by individual passenger requests and their temporal constraints. The article analyzes the impact of time window constraints, vehicle capacity, and service quality requirements on optimal solutions. The authors compare exact methods and metaheuristics for large-scale problem solving. This reference work establishes the fundamental conceptual framework for modeling passenger demand-driven transport systems.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Revue de littérature exhaustive des modèles exacts (branch-and-cut, branch-and-price) et métaheuristiques (tabou, génétique) pour le DARP |
| Données | Instances de benchmark issues de la littérature ; cas réels de transport médical et para-transit |
| Résultat principal | Aucun algorithme universel optimal ; les métaheuristiques offrent le meilleur compromis qualité/temps de calcul pour instances réelles |
| Lien demand/offer-driven | Le DARP est le paradigme pur du demand-driven : la topologie des routes est entièrement construite à partir des requêtes passagers, sans réseau fixe prédéfini |
| Lien réseau/flux | L’absence de structure réseau dans le DARP illustre en creux le rôle des hubs et lignes fixes pour concentrer les flux et rendre le partage efficace à grande échelle |
Lien avec la problématique
Le DARP représente l’extrémité demand-driven pure du spectre offre/demande : chaque route est une réponse directe aux requêtes individuelles, sans ancrage dans un réseau structuré, ce qui en fait un point de comparaison fondamental pour évaluer les gains apportés par une logique offer-driven. La concentration des flux sur des noeuds (hubs, PUDO) et des lignes fixes — au coeur de la problématique de thèse — peut être vue comme une contrainte imposée au DARP pour en améliorer la scalabilité et l’efficacité du partage. Ce travail de référence permet ainsi de quantifier le coût en flexibilité et le gain en efficacité collective lorsque l’on passe d’un système purement dial-a-ride à un système hybride articulé autour d’un réseau structurant.