Typology and literature review for dial-a-ride problems
Molenbruch Yves et al. — 2017
Résumé (FR)
Cet article propose une taxonomie détaillée et une revue de littérature des problèmes dial-a-ride (DARP), qui constituent la modélisation formelle des systèmes de transport collectif à la demande. Les auteurs classifient les problèmes selon les caractéristiques de la demande (utilisateurs, contraintes temporelles), de l’offre (flotte, dépôts) et des objectifs d’optimisation. La revue couvre les approches exactes, les métaheuristiques et les méthodes hybrides publiées depuis les origines du DARP. Une attention particulière est portée aux variantes passenger-centric intégrant le confort et les préférences individuelles des usagers dans la fonction objectif. Les auteurs identifient les lacunes de la littérature, notamment pour les systèmes à grande échelle et en temps réel. Ce travail de référence est essentiel pour comprendre les fondements de la modélisation demand-driven des systèmes MoD.
Summary (EN)
This paper proposes a detailed taxonomy and literature review of dial-a-ride problems (DARP), which constitute the formal modeling framework for collective on-demand transport systems. The authors classify problems according to demand characteristics (users, temporal constraints), supply features (fleet, depots), and optimization objectives. The review covers exact approaches, metaheuristics, and hybrid methods published since the origins of DARP. Particular attention is paid to passenger-centric variants integrating individual user comfort and preferences into the objective function. The authors identify gaps in the literature, particularly for large-scale real-time systems. This reference work is essential for understanding the foundations of demand-driven modeling of MoD systems.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Taxonomie formelle + revue systématique de littérature couvrant approches exactes (branch-and-cut, branch-and-price), métaheuristiques (algorithmes génétiques, recherche tabou) et méthodes hybrides |
| Données | Corpus de publications sur le DARP depuis ses origines ; benchmarks classiques de la littérature (instances Cordeau, instances synthétiques) |
| Résultat principal | Identification de trois grandes familles de DARP (statique, dynamique, stochastique) et mise en évidence des variantes passenger-centric comme frontière de recherche émergente |
| Lien demand/offer-driven | Le DARP est intrinsèquement demand-driven : la tournée des véhicules est entièrement construite autour des requêtes individuelles des usagers, à l’opposé d’une offre fixe prédéfinie |
| Lien réseau/flux | Les auteurs notent que la concentration de flux via des points de correspondance (hubs, PUDO) reste sous-explorée dans les formulations DARP classiques, ouvrant la voie à des modèles hybrides réseau-demande |
Lien avec la problématique
Cet article constitue le socle théorique de la modélisation demand-driven : le DARP formalise exactement la logique dans laquelle l’offre de transport s’adapte dynamiquement à la demande individuelle, contrairement à une logique offer-driven où des lignes fixes préexistent aux besoins. La complémentarité demand/offer-driven apparaît clairement dans les lacunes identifiées par les auteurs : les systèmes à grande échelle nécessitent de structurer la demande via des nœuds réseau (hubs, PUDO) pour rendre le problème tractable, ce qui revient à introduire une composante offer-driven dans un cadre initialement pur demand-driven. La concentration des flux sur un réseau de points de correspondance — centrale dans la problématique de thèse — est ainsi identifiée comme un levier d’efficacité combinatoire permettant de dépasser les limites de passage à l’échelle des DARP classiques.