Online Ridesharing with Meeting Points
Wang Jiachuan et al. — 2022
Résumé (FR)
Cet article formalise le problème de covoiturage en ligne basé sur des points de rencontre (MORP), où les passagers peuvent être pris en charge et déposés à des emplacements proches de leurs origines et destinations moyennant une courte marche. Les auteurs prouvent que MORP est NP-difficile et qu’aucun algorithme déterministe polynomial ne peut offrir un ratio de compétitivité constant. Une méthode de sélection des points de rencontre candidats basée sur la commodité est proposée, ainsi qu’une structure graphique hiérarchique orientée points de rencontre (HMPO). L’algorithme SMDB est introduit pour résoudre MORP de manière efficace. Les expériences sur des jeux de données réels et synthétiques valident l’efficacité et la qualité de l’approche. Ces travaux constituent une contribution fondamentale à la théorie et à la pratique du covoiturage avec points de rencontre.
Summary (EN)
This paper formalizes the Meeting-Point-based Online Ridesharing Problem (MORP), where passengers can be picked up and dropped off at locations near their origins and destinations with a short walk. The authors prove that MORP is NP-hard and that no polynomial-time deterministic algorithm can achieve a constant competitive ratio. A convenience-based selection method for meeting point candidates is proposed alongside a hierarchical meeting-point oriented graph (HMPO) structure. The SMDB algorithm is introduced to efficiently solve MORP. Experiments on real and synthetic datasets validate the efficiency and quality of the approach. This work constitutes a foundational contribution to the theory and practice of ridesharing with meeting points.
Points clés
| Aspect | Détail |
|---|---|
| Thème | pudo-optimization-2020 |
| Venue | Proceedings of the VLDB Endowment |
| Mots-clés | online ridesharing, meeting points, NP-hard, PUDO, algorithmic optimization |
| DOI | 10.14778/3565838.3565849 |
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.