Modeling an enhanced ridesharing system with meet points and time windows
Li Xin et al. — 2018
Résumé (FR)
Cet article présente un modèle d’optimisation pour des systèmes de covoiturage intégrant des points de rendez-vous où les passagers peuvent se regrouper pour être pris en charge collectivement, avec des fenêtres de temps préférées. Les passagers peuvent marcher jusqu’aux points de rencontre ou être pris en charge directement à leur origine, réduisant ainsi les détours dans les zones urbaines denses. Un algorithme de recherche tabou est développé pour résoudre le programme linéaire en nombres entiers mixtes, comparé aux solutions CPLEX. Les tests sur de petits réseaux montrent que les points de rencontre réduisent le temps de déplacement total de 2,7 % à 3,8 % par rapport au service porte-à-porte. L’heuristique proposée atteint des solutions entre 8 % et 15 % de l’optimum avec une efficacité computationnelle nettement supérieure. Cette étude quantifie précisément les bénéfices des points de collecte dans le covoiturage.
Summary (EN)
This paper presents a mathematical optimization model for ridesharing systems incorporating meet points where passengers can congregate for group pickups with preferred time windows. Passengers may walk to designated meet points or be picked up at their origins, reducing route detours in densely populated urban areas. A Tabu Search algorithm is developed to solve the mixed integer linear program, benchmarked against CPLEX solutions. Tests on small networks demonstrate that meet points reduce total travel time by 2.7%-3.8% compared to door-to-door services. The meta-heuristic achieves solutions within 8%-15% of optimal values with significantly better computational efficiency. This study precisely quantifies the benefits of collection points in ridesharing.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Programme linéaire en nombres entiers mixtes (MILP) résolu par recherche tabou, comparé à CPLEX |
| Données | Petits réseaux de test synthétiques avec passagers, points de rencontre candidats et fenêtres de temps |
| Résultat principal | Les points de rencontre réduisent le temps de déplacement total de 2,7 % à 3,8 % par rapport au service porte-à-porte |
| Lien demand/offer-driven | Les passagers s’adaptent à l’offre en marchant vers des points de collecte, hybridant logique demand-driven (prise en charge individuelle) et offer-driven (route optimisée pour le conducteur) |
| Lien réseau/flux | Les points de rencontre concentrent les flux de passagers en nœuds intermédiaires, réduisant les détours et densifiant le chargement des véhicules |
Lien avec la problématique
Ce papier illustre directement la complémentarité entre approche demand-driven et offer-driven : en introduisant des points de collecte intermédiaires, le système concède une contrainte à la demande (marche à pied) pour optimiser l’offre (moins de détours, meilleur remplissage). La logique de concentration des flux vers des nœuds fixes rejoint la question des hubs et arrêts PUDO dans un réseau de mobilité partagée, où regrouper les passagers en points structurants améliore l’efficacité globale du système. La quantification précise du gain (2,7 % à 3,8 %) fournit un ordre de grandeur empirique utile pour calibrer des modèles de simulation comparant services porte-à-porte et services structurés par lignes ou points d’arrêt virtuels.