Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Omar Rifki
 -- 1604 2024-02-24 12:17:46 |
2 update references and layout
Rita Xu
 -35 word(s) 1569 2024-02-26 03:35:58 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Rifki, O. Autonomous Ride-Sharing Service using Graph Embedding. Encyclopedia. Available online: https://encyclopedia.pub/entry/55407 (accessed on 28 April 2024).
Rifki O. Autonomous Ride-Sharing Service using Graph Embedding. Encyclopedia. Available at: https://encyclopedia.pub/entry/55407. Accessed April 28, 2024.
Rifki, Omar. "Autonomous Ride-Sharing Service using Graph Embedding" Encyclopedia, https://encyclopedia.pub/entry/55407 (accessed April 28, 2024).
Rifki, O. (2024, February 24). Autonomous Ride-Sharing Service using Graph Embedding. In Encyclopedia. https://encyclopedia.pub/entry/55407
Rifki, Omar. "Autonomous Ride-Sharing Service using Graph Embedding." Encyclopedia. Web. 24 February, 2024.
Autonomous Ride-Sharing Service using Graph Embedding
Edit
This entry is adapted from the peer-reviewed paper 10.3390/math12040546

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.

shared autonomous mobility first–last-mile service vehicle routing

1. Introduction

The urban expansion in most cities around the world followed an automobile-oriented pattern, leading to the emergence of several low-density metropolitan areas, thus increasing the overall infrastructure costs for public transportation (PT) (Sinha, 2003 [1]). Since then, and due to this reason, PT systems have been relegated to a secondary role behind private car use in urban mobility. The PT cover for low-density areas and commercial and industrial districts outside the city is limited. Shared mobility, which is the shared use of vehicles, bicycles, and other means of transport to access PT networks, started to appear to be a viable solution to this issue, known as the first- and last-mile commute. The concept of shared mobility is not novel in itself and could be traced back to the 1990s when it was popular, and even to the year 1948 for the first car-sharing program. Researchers refer to Shaheen & Chan (2016) [2] for a complete history of this matter. Yet, the major shift in shared mobility is still expected by many to happen with the advent of shared autonomous vehicles (SAV). Several AV manufacturers and service transportation provider companies have heavily invested in and adopted specific ride-sharing plans, e.g., Waymo in the Phoenix area (Waymo, 2020 [3]), Jaguar Land Rover (Jaguar Land Rover, 2020 [4]), and, eventually, Amazon, a fresh new competitor in this market share (Amazon, 2020 [5]).
The factors making SAV an attractive transit mode are mainly economic for both sides of customers and PT and transportation network entities. Due to lower operational and investment costs over fixed routes, transportation companies could propose services at fair prices with a higher frequency. Higher customer satisfaction and time reductions may be equally obtained compared with other transit modes such as park-and-ride and active modes. Another argument in favor of SAV lies in the environmental sustainability of this technology, which is mainly due to the application of electric vehicles in SAV services. Autonomous fleets could reduce greenhouse gas (GHG) emissions by up to 73% compared to conventional taxi fleets (Bauer et al., 2018 [6]). It was shown that each SAV could replace around 11, respectively, from 5 to 10 privately owned vehicles, with an increase of 10%, resp., from 6 to 89% travel distance via agent-based simulations of the city of Austin, Texas (Fagnant & Kockelman, 2014 [7]), resp., and Lisbon (International Transport Forum, 2015 [8]). The existence of empty trips justifies this latter increase. All these favorable reports led to a resurgence of small-size experimentations of SAV services in Europe, the U.S., and globally. Just in Lyon city in France, where the case study of this paper is located, there are currently three experimentations: Navya shuttle buses in the Confluence area, around Groupama stadium, and Mia buses in the Meyzieu-Décine suburb area. Therefore, there is a great need for efficient design models for the short-time deployment of SAVs, especially to handle the first–last-mile transit issue (see Hyland & Mahmassani (2017) [9] for a taxonomy of SAV fleet management problem classes to accompany this current mobility shift). This study is not concerned with the SAV experimentations in Lyon city, but rather targets an area of the city with a great need for a last-mile solution.
A critical component of the design of an SAV service is the vehicle assignment or the process of matching customer requests to vehicles. Most SAV approaches rely on rule-based assignment methods, e.g., Gurumurthy & Kockelman (2018) [10]. Optimization models are almost not used here. This is because SAV studies are mostly on-demand systems, which are dynamic systems that require solving approaches that are computationally cost efficient and easy to implement (Narayanan et al., 2020 [11]). On the other hand, SAV models that are reservation based or, in other terms, static systems that could be solved beforehand rely, in general, on optimization. However, they are quite few in number, e.g., Levin (2017) [12] and Ma et al. (2017) [13]. Both Levin (2017) and Ma et al. (2017) proposed a linear programming model to modelize an SAV fleet. Researchers propose using the famous routing problem of the Dial-a-Ride Problem (DARP), which is derived from the classical vehicle routing problem (VRP) with additional constraints to account for pickup and drop-off requests. VRP and DARP are both computationally intractable and can be pinned down as mixed-integer linear programming models. According to Ho et al. (2018) [14] and Gschwind & Irnich (2014) [15], the largest instance solved to optimality for the basic DARP with time windows is up to 8 vehicles and 96 requests, which is quite small for practical deployment of an SAV service. Therefore, a mechanism has to be found in order to reduce the dimension of the routing graph to be scalable for exact methods. To address this research gap, a new reduction method based on the graph embedding framework, specifically around the node2vec algorithmic framework (Grover and Leskovec, 2016 [16]), which will be seen later. The choice of node2vec is due to its property to capture the topology of any given graph, which can provide helpful information to locate nodes to be merged in the routing problem graph.

2. Integration of PT-SAV Systems

Several recent studies are starting to explore the benefits of integrating SAV services with existing PT systems. The most commonly adopted approach in this regard is agent-based simulations, whether it concerns the integration, e.g., Shen et al. (2018) [17], Pinto et al. (2020) [18], and Shan et al. (2021) [19], or the intersection of PT-SAV systems, e.g., Fagnant & Kockelman (2014) [7], or the replacement of PT by SAV, e.g., Yantao et al. (2021) [20]. Liang et al. (2016) [21] proposed an optimization model for an automated taxi service serving the last-mile transit of a train system. Their results are shown for a train station in Delft and include comparisons with human-driven taxis. Shen et al. (2018) [17] simulate several scenarios of integrating bus lines with SAVs for first-mile connectivity during the morning peak hours. Their results based on the Singapore PT show significant savings if low-demand buses are substituted by SAVs, savings that go up to 860 passenger car unit kilometers. Pinto et al. (2020) [18] proposed a bi-level optimization framework to simultaneously modelize the joint transit network parameters and the SAV mobility service. The lower-level problem is a dynamic combined mode choice–traveler assignment problem, while the upper lever is a modified transit network frequency setting problem. Their results are given for the Chicago metropolitan area. Shan et al. (2021) [19] developed a fixed-point algorithm to solve a joint system of railway transport and SAV. They provided a case study for the Melbourne railway extension. Al Maghraoui et al. (2020) [22] presented different attributes that affect travelers for SAV adoption depending on their current mode of transport. Several parameters enter into the integrated design of SAV. For instance, the locations of pickup and drop-off points can have a great impact on dynamic ride-sharing by SAV, as shown by Gurumurthy and Kockelman (2022) [23]. Special care has to be given to the design of the integration PT-SAV.

3. Dial-a-Ride Problems

Designing vehicle routes and schedules for collective people transportation such that each user request has a pickup and a drop-off point locations are referred to as Dial-a-Ride systems, as in early versions of this service, customers had to phone their requests. From a modeling perspective, DARP belongs to the family of routing problems. It is a variant of the vehicle routing problem (VRP), precisely the capacitated VRP with pickup and delivery and time windows, with hands-on transporting passengers rather than goods. Early solving approaches include Psaraftis (1980) [24], who solved the single-vehicle DARP using dynamic programming, and Jaw et al. (1986) [25], who developed one of the first heuristics to the multi-vehicle DARP. For the exact approaches, the Branch-and-Bound method and its derived algorithms are the most applied, e.g., Ropke et al. (2007) [26] and Gschwind & Irnich (2014) [15]. Concerning metaheuristics, those based on local search, especially those combining local search elements with other metaheuristics currently constitute state-of-the-art solvers, e.g., Masmoudi et al. (2016) [27]. Applications of DARPs are overall real-life problems with a diverse range of backgrounds, starting from the standard application to the elderly and disabled people’s transportation to healthcare services to the current emerging applications in public transportation and shared mobility (Ho et al. 2018 [14], Mourad et al. 2019 [28]).

4. Graph Embeddings

Graph embedding is a powerful method to represent a graph into a low-dimensional vector space by preserving as much as possible its topological structure. It addresses the research question of efficient graph analytics since traditional methods suffer from the curse of dimensionality and space cost. Essential graph analytic tasks, such as graph classification, node clustering, and link prediction, become scalable to large instances. Representation learning and visualization is another research problem tackled by graph embeddings. There are three main categories of graph embeddings: probabilistic, matrix factorization-based, and deep learning-based methods (see Goyal & Ferrara, 2018 [29] for a survey on the topic). Probabilistic models learn the embedding of graphs through random walks. The samplings given by those walks can capture the neighborhood structure of nodes, connectivities, and other graph properties such as node centrality. Compared with other probabilistic models like DeepWalk (Perozzi et al., 2014 [30]) and LINE (Tang et al., 2015 [31]), the probabilistic model of node2vec (Grover & Leskovec, 2016 [16]) is shown to perform better. This is why researchers chose node2vec implementation for the graph embedding. The random walk exploration of this algorithm interpolates between breadth-first (BFS) and depth-first (DFS) searches in order to construct a more informative embedding.

References

  1. Sinha, K.C. Sustainability and urban public transportation. J. Transp. Eng. 2003, 129, 331–341.
  2. Shaheen, S.; Chan, N. Mobility and the sharing economy: Potential to facilitate the first-and last-mile public transit connections. Built Environ. 2016, 42, 573–588.
  3. Waymo. Autonomous Ridesharing Isn’t Dead: How Waymo Is Adapting to the Post-COVID Era. By Ronan Glon. 3 July 2000. Available online: https://www.digitaltrends.com/cars/waymo-in-post-covid-era/ (accessed on 7 February 2024).
  4. Amazon. Amazon Buys Autonomous Taxi Company Zoox. Look Out, Uber and Lyft. By Eric J. Savitz. 26 June 2020. Available online: https://www.barrons.com/articles/amazon-buys-autonomous-taxi-company-zoox-51593187053 (accessed on 7 February 2024).
  5. Jaguar Land Rover. Jaguar Land Rover Reveals Project Vector Autonomous Ride-Share Vehicle. By Alistair Charlton. 19 February 2020. Available online: https://www.gearbrain.com/jaguar-land-rover-project-vector-2645188684.html (accessed on 7 February 2024).
  6. Bauer, G.S.; Greenblatt, J.B.; Gerke, B.F. Cost, energy, and environmental impact of automated electric taxi fleets in Manhattan. Environ. Sci. Technol. 2018, 52, 4920–4928.
  7. Fagnant, D.J.; Kockelman, K.M. The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transp. Res. Part C Emerg. Technol. 2014, 40, 1–13.
  8. International Transport Forum. Organisation for Economic Co-Operation and Development. Urban Mobility System Upgrade: How Shared Self-Driving Cars Could Change City Traffic; OECD Publishing: Paris, France, 2015.
  9. Hyland, M.F.; Mahmassani, H.S. Taxonomy of shared autonomous vehicle fleet management problems to inform future transportation mobility. Transp. Res. Rec. 2017, 2653, 26–34.
  10. Gurumurthy, K.M.; Kockelman, K.M. Analyzing the dynamic ride-sharing potential for shared autonomous vehicle fleets using cellphone data from Orlando, Florida. Comput. Environ. Urban Syst. 2018, 71, 177–185.
  11. Narayanan, S.; Chaniotakis, E.; Antoniou, C. Shared autonomous vehicle services: A comprehensive review. Transp. Res. Part C Emerg. Technol. 2020, 111, 255–293.
  12. Levin, M.W. Congestion-aware system optimal route choice for shared autonomous vehicles. Transp. Res. Part C Emerg. Technol. 2017, 82, 229–247.
  13. Ma, J.; Li, X.; Zhou, F.; Hao, W. Designing optimal autonomous vehicle sharing and reservation systems: A linear programming approach. Transp. Res. Part C Emerg. Technol. 2017, 84, 124–141.
  14. Ho, S.C.; Szeto, W.Y.; Kuo, Y.H.; Leung, J.M.; Petering, M.; Tou, T.W. A survey of dial-a-ride problems: Literature review and recent developments. Transp. Res. Part B Methodol. 2018, 111, 395–421.
  15. Gschwind, T.; Irnich, S. Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transp. Sci. 2015, 49, 335–354.
  16. Grover, A.; Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 13–17 August 2016; pp. 855–864.
  17. Shen, Y.; Zhang, H.; Zhao, J. Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore. Transp. Res. Part A Policy Pract. 2018, 113, 125–136.
  18. Pinto, H.K.; Hyland, M.F.; Mahmassani, H.S.; Verbas, I.Ö. Joint design of multimodal transit networks and shared autonomous mobility fleets. Transp. Res. Part C Emerg. Technol. 2019, 113, 2–20.
  19. Shan, A.; Hoang, N.H.; An, K.; Vu, H.L. A framework for railway transit network design with first-mile shared autonomous vehicles. Transp. Res. Part C Emerg. Technol. 2021, 130, 103223.
  20. Yantao, H.; Kockelman, K.M.; Truong, L.T. SAV Operations on a Bus Line Corridor: Travel Demand, Service Frequency, and Vehicle Size. J. Adv. Transp. 2021, 2021, 5577500.
  21. Liang, X.; de Almeida Correia, G.H.; Van Arem, B. Optimizing the service area and trip selection of an electric automated taxi system used for the last mile of train trips. Transp. Res. Part E Logist. Transp. Rev. 2016, 93, 115–129.
  22. Al Maghraoui, O.; Vosooghi, R.; Mourad, A.; Kamel, J.; Puchinger, J.; Vallet, F.; Yannou, B. Shared autonomous vehicle services and user taste variations: Survey and model applications. Transp. Res. Procedia 2020, 47, 3–10.
  23. Gurumurthy, K.M.; Kockelman, K.M. Dynamic ride-sharing impacts of greater trip demand and aggregation at stops in shared autonomous vehicle systems. Transp. Res. Part A Policy Pract. 2022, 160, 114–125.
  24. Psaraftis, H.N. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transp. Sci. 1980, 14, 130–154.
  25. Jaw, J.J.; Odoni, A.R.; Psaraftis, H.N.; Wilson, N.H. A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transp. Res. Part B Methodol. 1986, 20, 243–257.
  26. Ropke, S.; Cordeau, J.F.; Laporte, G. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Netw. Int. J. 2007, 49, 258–272.
  27. Masmoudi, M.A.; Hosny, M.; Braekers, K.; Dammak, A. Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem. Transp. Res. Part E Logist. Transp. Rev. 2016, 96, 60–80.
  28. Mourad, A.; Puchinger, J.; Chu, C. A survey of models and algorithms for optimizing shared mobility. Transp. Res. Part B Methodol. 2019, 123, 323–346.
  29. Goyal, P.; Ferrara, E. Graph embedding techniques, applications, and performance: A survey. Knowl. -Based Syst. 2018, 151, 78–94.
  30. Perozzi, B.; Al-Rfou, R.; Skiena, S. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, 24–27 August 2014; pp. 701–710.
  31. Tang, J.; Qu, M.; Wang, M.; Zhang, M.; Yan, J.; Mei, Q. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, Florence, Italy, 18–22 May 2015; pp. 1067–1077.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Transportation
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Omar Rifki
View Times: 70
Revisions: 2 times (View History)
Update Date: 26 Feb 2024
Table of Contents
    1000/1000
    Hot Most Recent
    Feedback