Autonomous Ride-Sharing Service using Graph Embedding: History
Please note this is an old version of this entry, which may differ significantly from the current revision.
Subjects: Transportation

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. 

  • 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. We 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. In this study, we 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) [18], Pinto et al. (2020) [19], and Shan et al. (2021) [20], 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) [21]. Liang et al. (2016) [22] 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) [18] 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) [19] 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) [20] 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) [23] 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) [24]. 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) [26], who solved the single-vehicle DARP using dynamic programming, and Jaw et al. (1986) [27], 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) [28] 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) [29]. 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 [30]).

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 [33] 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 [34]) and LINE (Tang et al., 2015 [35]), the probabilistic model of node2vec (Grover & Leskovec, 2016 [16]) is shown to perform better. This is why we 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.

This entry is adapted from the peer-reviewed paper 10.3390/math12040546

This entry is offline, you can click here to edit this entry!
Video Production Service