The ridesharing routing problem with flexible pickup and drop-off points
Mahtab Zuhayer et al. — 2025
Résumé (FR)
Cet article aborde l’optimisation des routes dans les systèmes de covoiturage où les conducteurs ont leurs propres origines et destinations et les passagers peuvent être pris en charge ou déposés à des points de rencontre flexibles dans les limites de marche autorisées. Un algorithme Branch-and-Price est proposé pour sélectionner les emplacements optimaux de prise en charge et de dépose sur un plan continu. Le modèle est testé sur des données de taxis de San Francisco et résout efficacement des instances jusqu’à 600 nœuds en 31 minutes CPU. L’incorporation de points de rencontre flexibles réduit le temps de déplacement total des véhicules d’environ 4 % en moyenne. L’algorithme est 14,3 fois plus rapide que Gurobi sur les mêmes instances. Ces résultats valident l’intérêt opérationnel et computationnel des PUDO flexibles dans les systèmes de covoiturage à grande échelle.
Summary (EN)
This paper addresses routing optimization in ridesharing systems where drivers have their own origins and destinations and passengers can be picked up or dropped off at flexible meeting points within walking distance limits. A Branch-and-Price algorithm is proposed to select optimal pickup and drop-off locations on a continuous plane. The model is tested on San Francisco taxi data and efficiently solves instances with up to 600 nodes within 31 CPU minutes. Incorporating flexible meeting points reduces total vehicle travel time by approximately 4% on average. The algorithm is 14.3 times faster than Gurobi on the same instances. These results validate the operational and computational value of flexible PUDOs in large-scale ridesharing systems.
Points clés
| Aspect | Détail |
|---|---|
| Thème | pudo-optimization-2020 |
| Venue | Transportation Research Part B: Methodological |
| Mots-clés | flexible PUDO, ridesharing routing, branch-and-price, meeting points, vehicle travel time |
| DOI | 10.1016/j.trb.2025.103234 |
Lien avec la problématique
Cet article contribue à la compréhension de la complémentarité offre↔demande dans les systèmes de covoiturage urbain/périurbain, en lien avec l’utilisation d’un réseau structurant (PUDO, hubs, lignes) pour concentrer les flux.