Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City

Omar Rifki ()
Additional contact information
Omar Rifki: Laboratoire d’Informatique Signal et Image de la Côte d’Opale (LISIC), University Littoral Côte d’Opale, UR 4491, F-62100 Calais, France

Mathematics, 2024, vol. 12, issue 4, 1-17

Abstract: Autonomous vehicles are anticipated to revolutionize ride-sharing services and subsequently enhance the public transportation systems through a first–last-mile transit service. Within this context, a fleet of autonomous vehicles can be modeled as a Dial-a-Ride Problem with certain features. In this study, we propose a holistic solving approach to this problem, which combines the mixed-integer linear programming formulation with a novel graph dimension reduction method based on the graph embedding framework. This latter method is effective since accounting for heterogeneous travel demands of the covered territory tends to increase the size of the routing graph drastically, thus rendering the exact solving of small instances computationally infeasible. An application is provided for the real transport demand of the industrial district of “Vallée de la Chimie” in Lyon city, France. Instances involving more than 50 transport requests and 10 vehicles could be easily solved. Results suggest that this method generates routes of reduced nodes with lower vehicle kilometers traveled compared to the constrained K-means-based reduction. Reductions in terms of GHG emissions are estimated to be around 75% less than the private vehicle mode in our applied service. A sensitivity analysis is also provided.

Keywords: shared autonomous mobility; first–last-mile service; vehicle routing; node embeddings (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/4/546/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/4/546/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:4:p:546-:d:1337008

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().