Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/4/546 |
| _version_ | 1827343305752444928 |
|---|---|
| author | Omar Rifki |
| author_facet | Omar Rifki |
| author_sort | Omar Rifki |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-07T22:23:22Z |
| format | Article |
| id | doaj.art-fc13e8ee98d44a9e8ef3bc3d24d67b8f |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-07T22:23:22Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-fc13e8ee98d44a9e8ef3bc3d24d67b8f2024-02-23T15:26:07ZengMDPI AGMathematics2227-73902024-02-0112454610.3390/math12040546Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon CityOmar Rifki0Laboratoire d’Informatique Signal et Image de la Côte d’Opale (LISIC), University Littoral Côte d’Opale, UR 4491, F-62100 Calais, FranceAutonomous 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.https://www.mdpi.com/2227-7390/12/4/546shared autonomous mobilityfirst–last-mile servicevehicle routingnode embeddings |
| spellingShingle | Omar Rifki Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City Mathematics shared autonomous mobility first–last-mile service vehicle routing node embeddings |
| title | Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City |
| title_full | Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City |
| title_fullStr | Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City |
| title_full_unstemmed | Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City |
| title_short | Autonomous Ride-Sharing Service Using Graph Embedding and Dial-a-Ride Problem: Application to the Last-Mile Transit in Lyon City |
| title_sort | autonomous ride sharing service using graph embedding and dial a ride problem application to the last mile transit in lyon city |
| topic | shared autonomous mobility first–last-mile service vehicle routing node embeddings |
| url | https://www.mdpi.com/2227-7390/12/4/546 |
| work_keys_str_mv | AT omarrifki autonomousridesharingserviceusinggraphembeddinganddialarideproblemapplicationtothelastmiletransitinlyoncity |