Online Ridesharing with Meeting Points
Wang Jiachuan et al. — 2022
Résumé (FR)
Cet article définit formellement le problème de covoiturage en ligne avec points de rendez-vous (MORP), où les passagers marchent vers des points de rencontre proches plutôt que leurs origines et destinations exactes, réduisant les coûts tout en offrant une routage flexible. Les auteurs prouvent que MORP est NP-difficile et qu’il n’existe pas d’algorithme déterministe polynomial avec un ratio compétitif constant. Ils proposent l’algorithme SMDB exploitant une structure de “k-skip cover” pour une assignation efficace en temps réel. L’approche hiérarchique classe les sommets du réseau selon leur efficacité pour l’assignation des passagers aux véhicules. La validation sur des jeux de données réels et synthétiques démontre l’efficacité et la scalabilité de la méthode. Cet article contribue à la formalisation computationnelle du problème des points de collecte dans le covoiturage.
Summary (EN)
This paper formally defines the Meeting-Point-based Online Ridesharing Problem (MORP), where passengers walk to nearby meeting points rather than exact origins/destinations, reducing costs while enabling flexible routing. The authors prove that MORP is NP-hard and that no polynomial-time deterministic algorithm with a constant competitive ratio exists. They propose the SMDB algorithm leveraging a k-skip cover structure for efficient real-time assignment. The hierarchical approach ranks network vertices by their effectiveness for passenger-to-vehicle assignment. Validation on real and synthetic datasets demonstrates the method’s effectiveness and scalability. This paper contributes to the computational formalization of the collection point problem in ridesharing.
Points clés
| Aspect | Détail |
|---|---|
| Méthode | Algorithme SMDB basé sur une structure k-skip cover pour l’assignation en temps réel passager-véhicule |
| Données | Jeux de données réels et synthétiques de trajets urbains |
| Résultat principal | MORP est NP-difficile ; SMDB offre une assignation efficace et scalable sans garantie de ratio compétitif constant |
| Lien demand/offer-driven | Le modèle MORP représente une logique demand-driven où les points de collecte s’adaptent à la demande plutôt qu’à une offre fixe de stations |
| Lien réseau/flux | La structure k-skip cover hiérarchise les noeuds du réseau pour concentrer les flux, réduisant les détours et maximisant le taux de remplissage |
Lien avec la problématique
La formalisation du problème MORP illustre directement la tension entre approches demand-driven et offer-driven dans le covoiturage : les points de rendez-vous variables incarnent une offre qui se construit à partir de la demande réelle, contrairement aux arrêts fixes d’un réseau de transport traditionnel. La structure k-skip cover introduit une forme de hiérarchisation du réseau qui converge vers la logique de concentration des flux propre aux hubs et lignes de mobilité partagée, rendant l’assignation scalable à l’échelle urbaine. Ce cadre computationnel fournit ainsi une base formelle pour étudier comment des points de collecte virtuels (PUDO) peuvent émerger dynamiquement tout en structurant le réseau de manière efficiente.