The ridesharing routing problem with flexible pickup and drop-off points
Zuhayer et al. — 2025
Résumé (FR)
Cet article traite du problème d’acheminement en covoiturage où véhicules et clients peuvent se rencontrer à des points de prise en charge et de dépose flexibles, éloignés des localisations fixes, motivé par des applications en covoiturage, routage de drones et logistique. Les auteurs proposent une formulation en programme mixte entier de second ordre conique (MISOCP) et développent un algorithme exact de branch-and-price utilisant une décomposition lagrangienne pour résoudre des instances de taille réaliste. Les expérimentations montrent que l’autorisation de points de rencontre flexibles, même sur des ensembles continus, produit des solutions traitables et réduit le temps de trajet total par rapport à un acheminement à points fixes. Ce travail étend les formulations discrètes antérieures à des ensembles continus de points.
Summary (EN)
This paper addresses the ridesharing routing problem where vehicles and customers can meet at flexible pickup and drop-off points away from fixed home locations, motivated by applications in ridesharing, drone routing, and logistics. The authors propose a Mixed Integer Second-Order Cone Program (MISOCP) formulation and develop an exact branch-and-price algorithm using Lagrangian decomposition to solve realistically sized instances. Experiments show that allowing flexible meeting points, even over continuous location sets, yields tractable solutions and reduces total travel time compared to fixed-point routing. The work extends prior discrete formulations to continuous point sets.
Points clés
| Aspect | Détail |
|---|---|
| — | — |