Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem

Ye, Jinwen; Pantuso, Giovanni; Pisinger, David Article Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem EURO Journal on Transportation and Logistics (EJTL) Provided in Cooperation with: Association of European Operational Research Societies (EURO), Fribourg Suggested Citation: Ye, Jinwen; Pantuso, Giovanni; Pisinger, David (2024) : Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem, EURO Journal on Transportation and Logistics (EJTL), ISSN 2192-4384, Elsevier, Amsterdam, Vol. 13, Iss. 1, pp. 1-19, https://doi.org/10.1016/j.ejtl.2024.100132 This Version is available at: https://hdl.handle.net/10419/325206 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc-nd/4.0/ Contents lists available at ScienceDirect EURO Journal on Transportation and Logistics journal homepage: www.elsevier.com/locate/ejtl Order dispatching and vacant vehicles rebalancing for the first-mile ride-sharing problem Jinwen Ye a,∗, Giovanni Pantuso a, David Pisinger b aUniversity of Copenhagen, Copenhagen, Denmark bTechnical University of Denmark, Copenhagen, Denmark ARTICLE INFO Keywords: First-mile Ride-sharing Order dispatching Rebalancing Rolling horizon ABSTRACT Given a set of transport requests to a transit station and a set of homogeneous vehicle, both geographically dispersed in a business area, the First-Mile Ride-Sharing Problem (FMRSP) consists of finding least cost vehicle routes to transport passengers to the station by shared rides. In this paper we formulate the problem as a mathematical optimization problem and study the effectiveness of preventive movements of idle vehicles (i.e., rebalancing) in order to anticipate future demand. That is, we identify promising rebalancing locations based on historical data and give the model incentives to assign vehicles to such location. We then assess the effectiveness of such movements by simulating online usage of the mathematical model in a rolling-horizon framework. The results show that rebalancing is consistently preferable both in terms of profits and service rate. Particularly, in operating contexts where the station is not centrally located, rebalancing movements increase both profits and service rates by around 30% on average. 1. Introduction Ride-sharing services, which are linked to a reduction of the number of private cars on the road, emissions and congestion (Al-Abbasi et al., 2019), have emerged as a potential solution to the increase in road congestion and air pollution generated by growing urban areas and population (Taniguchi et al.,2014). Such services have yet significant potential for development. As an example, according to the NYC taxicab data (Commission and Limousine,2023), during January 2020 there were 363,874 taxi trips to the Pennsylvania Station, a fairly busy transit station in New York City see Fig. 1(a), that is, on average 12,129 taxis trips daily to the station. Of these, only 6% were shared by multiple passengers, see Fig. 1(b), which leaves significant margins for more efficient connections to the station. An effective implementation of ride-sharing services requires adequate responses to potentially frequent changes in demand patterns during the day that may determine geographical mismatches between demand as supply. Fig. 2 illustrates the location of the requests of transportation to Pennsylvania Station during January 2014, showing that the majority of the requests arrive from the North-East area, whereas much fewer requests arrive from the remaining zones of the city. This suggests implementing mechanisms that prepare the geographical distribution of the fleet in such a way to anticipate demand and perhaps reduce waiting and response times as well as service rate. ∗Corresponding author. E-mail addresses: [email protected] (J. Ye), [email protected] (G. Pantuso), [email protected] (D. Pisinger). The existing literature study various aspects of ride-sharing services, including pricing mechanisms (Bian and Liu,2019b,a;Bian et al., 2020;Chen and Wang,2018), integration with public transport (Shen et al.,2018), order dispatching and vehicle routes (Wang,2019;Chen et al.,2020). Conversely, strategies for anticipating demand through, e.g. preventive or rebalancing movements (Wen et al.,2018), remain, to a large extent, an open research question. Particularly, efficient ways to simultaneously determine both dispatching and rebalancing movements have, to the best of our knowledge, been neglected. We contribute to filling this gap by providing a mathematical programming model for joint order dispatch and rebalancing decisions in a first-mile ride-sharing service which transports passengers from their initial location to a common destination (e.g., a transit station). We will refer to this decision problem as the First-Mile Ride-Sharing Problem (FMRSP). In addition, we propose a strategy for identifying promising locations where to rebalance empty vehicles. The model and rebalancing strategies are tested in a rolling-horizon framework which simulates on-line usage. The rest of this paper is structured as follows. In Section 2we review the related literature and underline the contribution of this article. In Section 3we formally introduce the problem and the corresponding mathematical programming model. In Section 4we describe two methods for deciding where to relocate vehicles in anticipation of future https://doi.org/10.1016/j.ejtl.2024.100132 Received 9 March 2023; Received in revised form 13 March 2024; Accepted 26 March 2024 EURO Journal on Transportation and Logistics 13 (2024) 100132 Available online 28 March 2024 2192-4376/© 2024 The Author(s). Published by Elsevier B.V. on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ ). J. Ye et al. Fig. 1. Taxi trips to Penn Station. Data from Commission and Limousine (2023). Fig. 2. Distribution of trips to Penn Station. demand. In Section 5we describe the simulation framework and the numerical experiments we performed with the model and illustrate the results. Finally, we draw conclusions in Section 6. 2. Literature review The routing decisions considered in the FMRSP share similarities with those involved in well studied routing problems. Among these we find the Vehicle Routing Problem (VRP). Starting from the seminal paper of Dantzig and Ramser (1959), several exact and heuristics algorithms were proposed to solve VRPs (Bräysy and Gendreau,2005; Bertsimas et al.,2019;Toth and Vigo,2002) and several flavors of the problem have been studied, see e.g., the surveys (Kumar and Panneerselvam,2012;Pillac et al.,2013;Lin et al.,2014;Ritzinger et al., 2016;Braekers et al.,2016). One of the major differences between the FMRSP and the different variants of the VRP is that VRPs typically consist of designing tours returning to the depot, while the FMRSP designs open paths from the vehicle’s origins to a common destination. Arguably, a (variant of the) VRP would resemble more closely a lastmile ride-sharing problem where a vehicle departs and returns to the station visiting the destinations of a number of customers. Furthermore, FMRSPs focus on transporting customers from multiple locations to the destination (station) while VRPs are typically concerned with the delivery of goods to customers. This impacts the types of restrictions imposed on the routes. Particularly, the FMRSP shares features with the Dial-a-ride Problem (DARP) and the Pick-up-and-delivery Problem (PDP) (Cordeau and Laporte,2003;Ropke and Cordeau,2009;Berbeglia et al.,2010), which are generalizations of the VRP. A comprehensive review of DARP and PDP can be found in Ho et al. (2018). The goal of the DARP is to minimize the cost/time to transport a set of passenger by means of a fixed fleet of vehicles. Requests have different pickup and delivery locations, and the vehicles can pick up more than one passengers at a time. Also for the DARP different variants can be found, such as where the objective is to minimize the detour for the customers on board the vehicles (Pfeiffer and Schulz,2022). The DARP can be considered as a variant of the PDP. The PDP typically deals with the transportation of goods while the DARP deals with passenger transportation (Parragh et al.,2008). Thus, the difference between DARP and PDP is usually expressed in terms of additional constraints or objectives that explicitly take user (in)convenience into account (e.g., time window and vehicle capacity constraints). The FMRSP can be seen as a special case of DARP where passengers travel to a common depot (station) and with additional service-specific constraints. In particular, the FMRSP takes the desired arrival time of accepted customers as constraints. This, in turn, implicitly shapes feasible time window for the other customers on board the same vehicle and for the newly arrived customers in a rolling horizon optimization framework. Particularly, in this paper, we study on-line dispatch and rebalancing decisions. That is, we consider the allocation of customers requests to vehicles as they arrive and while vehicles are busy with other transportation requests. This entails dealing two types of customers. First, we find customers whose request has been accepted in previous decision epochs and have not yet picked up. These customers requests must be satisfied. Second, we find new customers whose request may or may not be accepted, similarly to a EURO Journal on Transportation and Logistics 13 (2024) 100132 2 J. Ye et al. Table 1 Summary of the available literature. Under ‘‘Decisions’’ we report the main decisions addressed by the article. Matching refers to the assignment of customers to vehicles. Rebalancing refers to the assignment of vehicles to zones. Under ‘‘Service’’ we use RS for a general ride-sharing service and FM for a first-mile ride-sharing service. Under ‘‘Model’’ a Yes or a No indicate whether the study provides an optimization model or not. Study Service Decisions Model Method Shen et al. (2018) FM Fleet size, matching, routing No Simulation Zhao et al. (2018) RS Matching Yes MILP, Heuristics Bertsimas et al. (2019) RS Matching Yes MILP, Heuristics Wang et al. (2018) RS Matching Yes MILP, Heuristics Chen et al. (2020) FM Matching Yes MILP Lotfi and Abdelghany (2022) RS Matching No Heuristics Santos and Xavier (2015) RS Matching Yes MILP Elting and Ehmke (2021) RS Matching Yes Constraint Satisfaction Problem Zheng and Pantuso (2023) FM Matching Yes MILP, Heuristics Fagnant and Kockelman (2018) RS Fleet size, matching No Simulation Lokhandwala and Cai (2018) RS Matching No Simulation Mao et al. (2020) RS Rebalancing Yes MILP, Reinforcement Learning Noruzoliaee and Zou (2022) RS Matching Yes MILP Beirigo et al. (2022) RS Matching Yes MILP Bongiovanni et al. (2022) RS Matching Yes MILP Wallar et al. (2018) RS Zone partition, rebalancing of idle vehicles Yes MILP, Poisson process Wen et al. (2018) RS Rebalancing of idle vehicles No Reinforcement learning Alonso-mora et al. (2018) RS Matching, rebalancing of idle vehicles NoaMILP Sayarshad and Chow (2017) RS Matching, rebalancing of idle vehicles Yes MINLP Ma et al. (2019a) RS Matching, rebalancing of idle vehicles No Queue theory aThe authors provide a verbal description of the mathematical model. price-collecting TSP (Balas,1989) where visiting customers is optional and provides a reward. Finally, empty vehicles may be moved to rebalancing centers in order to position for future demand. Due to the fast development of GPS technology and widespread use of smart-phones, ride-sharing services enabled by mobile applications have attracted broad attentions. Commercial companies such as Uber and Didi have implemented versions of the service (Xu et al.,2018; Lin et al.,2018). The attention of the research community has grown providing both optimization methods (Stiglic et al.,2015;Masoud et al.,2017;Masoud and Jayakrishnan,2017;Alonso-mora et al.,2018; Stiglic et al.,2018;Huang et al.,2014;Wang et al.,2018;Mourad et al., 2019) and reinforcement learning methods (Xu et al.,2018;Lin et al., 2018;Li et al.,2019;Tang et al.,2019;Qin et al.,2019). The FMRSP and, in general, ride-sharing problems are, however, a relatively new family of problems and the corresponding literature is somewhat sparse. In what follows we review the available literature before highlighting how our work extends the state-of-the-art. The literature is also summarized in Table 1 for the reader’s convenience. Shen et al. (2018) study the integration of a FMRS service based on autonomous vehicles (AVs) with public transportation. The idea is to preserve high demand bus routes while using shared AVs as an alternative for low demand routes. In a simulation framework they use simple heuristics to match passengers to vehicles and define routes. Chen et al. (2020) provide a mixed-integer linear programming (MILP) model to decide the assignment of request groups to AV in FMRS service. The objective is that of minimizing operational costs. The authors devise a cluster-based solution method to deal with large-scale instances. Zhao et al. (2018) address the joint problem of optimally matching passengers and vehicles and that of routing each vehicle. The problem is formulated as a PDP with the addition of space–time windows. Wang et al. (2018) consider a ride-share setting in which a ride-share provider receives trip requests over time from potential participants. A trip can be either a driver or a rider. This process generates two disjoint sets of trip requests. The authors focus on finding a stable match between the two sets. Bertsimas et al. (2019) study the problem of assigning customers to vehicles. The authors include service-specific constraints, including time windows and latest time for accepting or rejecting a transportation request. The authors address the problem via periodic re-optimization. Lotfi and Abdelghany (2022) consider a set of passengers requiring a ride and study the problem of assigning passengers to vehicles. This set of passengers is known at the time the problem is solved. Passengers are characterized by origin, destination, earliest pick-up time, latest drop-off time and willingness to share the ride. The authors consider two objectives, namely maximizing profit and maximizing passengers’ travel experience, measured in terms of transfers and travel times. The problem is solved by means of a heuristic. In the study of Santos and Xavier (2015) users decide whether to share either their own car or a taxi. They specify pickup and drop-off location, earliest pick-up time, latest drop-off time and the maximum cost tolerated. In addition, car owners also specify the departure time and the maximum accepted delay. The authors address the problem of matching users to vehicles and of determining the routes. Elting and Ehmke (2021) assess the economic potential of shared taxi services. Here a service operator collects requests from individual travelers. Based on every request’s origin and destination as well as the desired pick-up time, the service provider matches vehicles and travelers and builds a route plan for each vehicle. Zheng and Pantuso (2023) consider a FMRS service where passengers have to be transported to a common destination. The problem consists of assigning customers to vehicles and deciding vehicle routes. Transport requests may be rejected. The problem is formulated as a bi-objective MILP where the two conflicting objectives are travel costs and service rates. Fagnant and Kockelman (2018) consider an AV-based ride-sharing service. They use simulation to find the best fleet size. In their simulation they match passengers to AVs based on specific rules, such as assigning passengers to the nearest vehicle. Their study shares similarities with (Lokhandwala and Cai,2018) who also propose a simulation study for quantifying the environmental impact of ride-sharing with AVs over traditional taxis. In their simulation framework, passengers are assigned to vehicles based on a detailed algorithm which takes into account the preferences of the customer and looks for suitable AV routes. Noruzoliaee and Zou (2022) study the problem of assigning the multiple requests (from different origins and destinations) to shared AVs with the scope of avoiding undesired rider en-route transfers. Beirigo et al. (2022) also study the assignment of requests to vehicles in an AV-based ride-sharing system where users differ according to expectations in terms of responsiveness, reliability, and privacy. The authors assume possible that privately owned freelance AVs can be hired on short notice. They propose a multi-objectives MILP which optimizes vehicle occupancy, number of AVs used, service level violation, and the waiting times. Bongiovanni et al. (2022) also study the problem of assigning passengers to AVs. They propose a two-phase heuristic which assigns new requests AVs and subsequently re-optimizes such assignments through intraand inter-vehicle route moves. EURO Journal on Transportation and Logistics 13 (2024) 100132 3 J. Ye et al. A number of studies address the problem of rebalancing vehicles. Wen et al. (2018) propose a reinforcement learning method to move idle vehicles in a shared mobility-on-demand systems. They test their solution method on a first-mile ride-sharing service in the city of London. Mao et al. (2020) consider a taxi sharing systems with AVs. They study the problem of determining the number of AVs to send from a zone of the city to another in order to minimize the expected cost of repositioning AVs. They compare a reinforcement learning algorithm with an integer programming model that assumes full knowledge of future demand. Wallar et al. (2018) propose algorithms for partitioning the operating area into zones, estimating the real-time demand and rebalancing idle vehicles. Sayarshad and Chow (2017) propose a queuebased model for matching and rebalancing decisions. They assume that the number of idle vehicles is known in advance. Alonso-mora et al. (2018) design a matching algorithm for on-demand ride-sharing. The method incorporates rebalancing decisions for idle vehicles. The authors describe a MILP formulation for the problem and solve the problem via a specialized procedure that begins by assigning passengers to vehicles and finding feasible trips, and terminates by rebalancing idle vehicles. Ma et al. (2019a) study a more involved system in which a ride-sharing fleet is operated jointly with public transport services in order to arrange complete on-demand journeys for their customers. The authors consider also the rebalancing of idle vehicles. They propose a queueing-theoretic model for the problem. As it is evident in Table 1, the available literature has typically addressed matching decisions (i.e., the assignment of passengers to vehicles) and rebalancing decisions (i.e., the assignment of vehicles to zones) separately. Furthermore, when rebalancing decisions are addressed, they concern mainly idle vehicles, that is vehicles which have not been dispatched to customer requests. Thus, matching and rebalancing decisions have been understood as sequential decisions. First, vehicles match current requests, then the remaining ones may be rebalanced. Finally, it is possible to notice that not all articles that study rebalancing decisions provide an optimization model for that. We extend the state-of-the-art in the following ways: 1. We address matching, routing and rebalancing decisions simultaneously. This entails that we do not necessarily rebalance only idle vehicles. In our approach, vehicles may move to promising demand areas in advance, even if this entails giving up the profit of a current request. 2. We consider online optimization with binding acceptance of transportation requests. This entails that a subset of the customers (those whose request has been accepted in previous decision problems) must be serviced, while the remaining customers (those newly arrived) may be picked up if feasible and profitable. A side effect of this is that previously and newly accepted customers have an impact on the time window of the vehicle. 3. For this problem we provide an explicit mathematical model. The model includes service-specific constraints such as maximum waiting time, latest arrival time, and the necessity of fulfilling binding acceptance of transport requests. 4. We propose simple techniques to identify promising locations where to rebalance. 5. We test our model in a rolling-horizon simulation framework with periodic re-optimization based on randomly generated instances to assess the solutions delivered by the model and, particularly, the advantage provided by rebalancing activities. It must be noted that rebalancing decisions have been extensively studied in other emerging problems in shared mobility. These include carsharing (Illgen and Höck,2019;Folkestad et al.,2020;Pantuso, 2022), bike sharing (Faghih-Imani et al.,2017;Liu et al.,2016;Chemla et al.,2013), scooter sharing (Osorio et al.,2021). Nevertheless, the relocation problem involved is significantly different. In the ride-sharing problem, a vehicle has to drive (with its own driver) to a more promising location. In the other vehicle-sharing problems, vehicles have to be picked up by drivers or service vehicles to be moved to more promising locations. The amount of work in the latter is typically much higher and the relocation problem alone may involve complex optimization problems. Similarities may emerge in the methods used to predict demand occurrence. However, we believe the methods proposed are not immediately applicable due to the inherent differences in the systems and types of demand. 3. The first-mile ride-sharing problem In this section, we formally introduce the First-Mile Ride-Sharing Problem. We start, in Section 3.1, by providing a general introduction to the problem. Following, in Section 3.2, we introduce a mathematical model for the FMRSP. In addition, in Appendix A we provide a table that summarizes the notation and in Appendix B we provide a simple example that illustrates possible feasible solutions to the problem. 3.1. Problem statement We consider the operator of a fleet of vehicles 𝒦∶= {1,…, 𝐾} concerned with dispatch and relocation decisions in order to ensure a first-mile ride-sharing service. The fleet is homogeneous with capacity 𝑄. We assume the operator makes dispatch and relocations decisions periodically, e.g., every 5 or 10 min, as a result of the arrival of new transportation requests. We refer to these decision times as ‘‘(re)- optimization phases’’. At each re-optimization phase, the available customers can be partitioned in two sets, namely 𝒩𝑃∶= {1,…, 𝑁𝑃} which contains the customers whose transportation request had already been accepted during a previous optimization phase, and 𝒩𝐶∶= {1,…, 𝑁𝐶}which contains newly arrived customer requests which have not been considered in previous optimization phases. We assume that the customers in 𝒩𝐶may be either accepted (and thus assigned to a vehicles) or rejected, while the customers in 𝒩𝑃must be picked up (thus we assume acceptance decisions are binding). For convenience we set 𝒩𝑈∶= 𝒩𝐶∪𝒩𝑃. All customers travel to a common destination 𝑑located in position 𝑜(𝑑)(e.g., a transit station) and for each customer 𝑖, the operator knows the requested pick-up time 𝑇𝑃 𝑖, the requested arrival time 𝑇𝐴 𝑖and the origin 𝑜(𝑖). We let 𝛥be the maximum waiting time (i.e., difference between actual pick-up time and requested pick-up time). Similarly, at the beginning of the re-optimization phase, denoted 𝑇, each vehicle 𝑘is located at 𝑜(𝑘)as a result of previous deployment or relocation decisions. The vehicle is either idle in its location, or traveling between customers or to the station. In addition, vehicles might initially have customers on board. We denote 𝑉𝑘the number of customers on board of vehicle 𝑘at the beginning of the re-optimization phase and 𝑇𝑘the earliest arrival time of the passengers already on board vehicle 𝑘. The operator needs to ensure that vehicles with customers on board terminate their journey to the station. Conversely, vehicles with no customers on board may be sent to a rebalancing point or stay at their origin location 𝑜(𝑘). A set ℛ∶= {1,…, 𝑅}of potential rebalancing points in the operating area is available. For each rebalancing point 𝑟we let 𝐵𝑟denote an upper bound on the number of vehicles that can be dispatched to the rebalancing point. The operator bears transportation costs generated by vehicle movements. Particularly, we assume travel times are known, with 𝑇𝑖𝑗 being the travel time between locations 𝑜(𝑖)and 𝑜(𝑗)with 𝑖∈𝒦∪𝒩𝑈, 𝑗∈𝒩𝑈∪ℛ∪ {𝑑}and cost 𝐶is born for each unit of travel time. The operator collects a revenue 𝑃𝑖when picking up customer 𝑖, for 𝑖∈𝒩𝐶. Note that the revenue is collected only when picking up new customers as we assume the revenue for the customers in 𝒩𝑃has been collected during previous optimization phases. Furthermore, 𝐸𝑟denotes the expected revenue collected for each vehicle relocated to rebalancing center 𝑖∈ℛ. Parameter 𝐸𝑖is calculated as  𝑃𝑖−𝐶𝑇𝑖𝑑 , where  𝑃𝑖is the EURO Journal on Transportation and Logistics 13 (2024) 100132 4 J. Ye et al. expected revenue obtained from dispatching a vehicle to rebalancing center 𝑖∈ℛ. Expected future revenues from rebalancing activities are discounted using a parameter 𝛽that denotes the weight of the rebalancing reward. The decisions made by the operator can be formalized as follows. We let 𝑥𝑘 𝑖𝑗 take value 1if vehicle 𝑘moves directly between 𝑜(𝑖)and 𝑜(𝑗), 0otherwise, for all 𝑖∈ {𝑘}∪𝒩𝑈, 𝑗 ∈𝒩𝑈∪ℛ∪{𝑑}, 𝑘 ∈𝒦. Furthermore, we let 𝑡𝐴 𝑘denote the actual arrival time of vehicle 𝑘to the station, for 𝑘∈𝒦and 𝑡𝑃 𝑖denote the actual pick-up time of customer 𝑖, for 𝑖∈𝒩𝑈. Thus, we use a 3-index formulation of size 𝑂(|𝒩𝐶||𝒦||ℛ|). The FMRSP is NP-hard, as it contains the prize-collecting TSP (Balas,1989) as a special case. 3.2. Mathematical model Having defined all decision variables and parameters, we may formulate the problem as follows. max ∑ 𝑘∈𝒦 ∑ 𝑖∈𝒩𝐶 ∑ 𝑗∈𝒩𝑈∪{𝑑} 𝑃𝑖𝑥𝑘 𝑖𝑗 −∑ 𝑖∈{𝑘}∪𝒩𝑈 ∑ 𝑗∈𝒩𝑈∪ℛ∪{𝑑} ∑ 𝑘∈𝒦 𝐶𝑇𝑖𝑗 𝑥𝑘 𝑖𝑗 +𝛽∑ 𝑖∈ℛ ∑ 𝑘∈𝒦 𝑥𝑘 𝑘𝑖𝐸𝑖(1a) s.t. ∑ 𝑗∈𝒩𝑈∪{𝑑} ∑ 𝑘∈𝒦 𝑥𝑘 𝑖𝑗 ≤1 ∀𝑖∈𝒩𝐶 (1b) ∑ 𝑗∈𝒩𝑈∪{𝑑} ∑ 𝑘∈𝒦 𝑥𝑘 𝑖𝑗 = 1 ∀𝑖∈𝒩𝑃 (1c) ∑ 𝑖∈𝒩𝑈∪𝒦 𝑥𝑘 𝑖𝑑 ≤1 ∀𝑘∈𝒦 (1d) ∑ 𝑖∈𝒩𝑈∪{𝑘} 𝑥𝑘 𝑖𝑗 =∑ 𝑖∈𝒩𝑈∪{𝑑} 𝑥𝑘 𝑗𝑖 ∀𝑗∈𝒩𝑈, 𝑘 ∈𝒦 (1e) ∑ 𝑗∈ℛ∪𝒩𝑈∪{𝑑} 𝑥𝑘 𝑘𝑗 =∑ 𝑗∈𝒩𝑈∪{𝑘} ∑ 𝑖∈ℛ∪{𝑑} 𝑥𝑘 𝑗𝑖 ∀𝑘∈𝒦 (1f) ∑ 𝑖∈{𝑘}∪𝒩𝑈 ∑ 𝑗∈𝒩𝑈 𝑥𝑘 𝑖𝑗 +𝑉𝑘≤𝑄∀𝑘∈𝒦 (1g) ∑ 𝑘∈𝒦 𝑥𝑘 𝑘𝑗 ≤𝐵𝑗∀𝑗∈ℛ (1h) 𝑉𝑘≤𝑄(1 − ∑ 𝑗∈ℛ 𝑥𝑘 𝑘𝑗 ) ∀𝑘∈𝒦 (1i) 𝑉𝑘≤𝑄∑ 𝑗∈𝒩𝑈∪{𝑑} 𝑥𝑘 𝑘𝑗 ∀𝑘∈𝒦 (1j) 𝑡𝑃 𝑖+𝑇𝑖𝑗 ≤𝑡𝑃 𝑗+𝑇𝐿(1 − ∑ 𝑘∈𝒦 𝑥𝑘 𝑖𝑗 ) ∀𝑖, 𝑗 ∈𝒩𝑈 (1k) 𝑇+𝑇𝑘𝑗 ≤𝑡𝑃 𝑗+𝑇𝐿(1 − 𝑥𝑘 𝑘𝑗 ) ∀𝑗∈𝒩𝑈, 𝑘 ∈𝒦 (1l) 𝑡𝑃 𝑖−𝑇𝑃 𝑖≤𝛥∀𝑖, 𝑗 ∈𝒩𝑈 (1m) 𝑡𝐴 𝑘≤𝑇𝐴 𝑖+𝑇𝐿(1 − ∑ 𝑗∈𝒩𝑈∪{𝑘} 𝑥𝑘 𝑗𝑖) ∀𝑖∈𝒩𝑈, 𝑘 ∈𝒦 (1n) 𝑡𝐴 𝑘≤𝑇𝑘∀𝑘∈𝒦 (1o) 𝑡𝑃 𝑗+𝑇𝑗𝑑 𝑥𝑘 𝑗𝑑 ≤𝑡𝐴 𝑘+𝑇𝐿(1 − 𝑥𝑘 𝑗𝑑 ) ∀𝑗∈𝒩𝑈, 𝑘 ∈𝒦 (1p) 𝑥𝑘 𝑖𝑗 ∈ {0,1} ∀𝑖∈ {𝑘} ∪ 𝒩𝑈, 𝑗∈𝒩𝑈∪ℛ∪ {𝑑}, 𝑘 ∈𝒦 (1q) 𝑡𝐴 𝑘∈R+∀𝑘∈𝒦 (1r) 𝑡𝑃 𝑖∈R+∀𝑖∈𝒩𝑈 (1s) Objective function (1a) represents the profit for the operator. The first term represents the revenue generated by picking up customers, the second term the total cost born of the vehicles movements and, finally, the third term is the discounted expected profit obtained in the rebalancing centers. Constraints (1b) and (1c) state that new customers may be picked up at most once and customers already accepted must be picked up exactly once, respectively. Observe, in (1b) and (1c), that after visiting a customer 𝑖∈𝒩𝐶or 𝑖∈𝒩𝑃, the vehicle can only move to another customer 𝑖∈𝒩𝑃∪𝒩𝐶or to the station 𝑑. Constraints (1d) ensure that vehicles travel to the station at most once. Constraints (1e) state that whenever a vehicle arrives at a customer location, it must then move to another customer or to the station. Notice that a vehicle can arrive at a customer location 𝑗either from another customer or from the vehicle’s original location 𝑜(𝑘). We remind the reader that variable 𝑥𝑘 𝑘𝑗 must be understood as vehicle 𝑘moving from its original location 𝑜(𝑘)to the location 𝑜(𝑗)of customer 𝑗. Constraints (1f) state that, if a vehicle departs from its original location 𝑜(𝑘), i.e., 𝑥𝑘 𝑘𝑗 = 1 for some 𝑗, it must terminate its journey either at the station or at a rebalancing point. Also in this case, variables 𝑥𝑘 𝑘𝑗 must be understood as the vehicle moving from its origin, 𝑜(𝑘), see Section 3.1. Constraints (1g) ensure that the capacity of the vehicles is not exceeded, while constraints (1h) ensure that the total number of vehicles dispatched to a rebalancing center will not exceed the upper bound on the vehicles dispatchable at the rebalancing center. Constraint (1i) state that only empty vehicles may be dispatched to rebalancing centers. For instance, if vehicle 𝑘is dispatched to one of the rebalancing center, the right-hand-side becomes 0, and the constraints can only be satisfied when 𝑉𝑘is equal to 0. If vehicle 𝑘is not dispatched to any rebalancing center, the right-hand-side reduces to the capacity of the vehicle, and the constraint holds with any value of 𝑉𝑘. Notice that the movements between customer points 𝒩𝑈and rebalancing points are automatically forbidden by the absence of the corresponding 𝑥𝑘 𝑖𝑗 variables. Constraints (1j) state that the vehicles that already have customers on board at the beginning of the period must be dispatched (i.e., cannot stay idle). If 𝑉𝑘is strictly positive, the constraint forces the right-hand-side to be strictly positive as well, and thus to dispatch the vehicle. Constraints (1k) state that if customer 𝑗is picked up by vehicle 𝑘immediately after picking up customer 𝑖, then the actual picking up time of customer 𝑖plus the travel time between customer 𝑖and 𝑗 must be less or equal to customer 𝑗’s actual pick up time. Here 𝑇𝐿: =𝑚𝑎𝑥𝑖{𝑇𝐴 𝑖}for 𝑖∈𝒩𝑈is an upper bound on the requested arrival time. Similarly, constraints (1l) denote the pick-up time for the first customers in the route. Constraints (1m) ensure that the difference between the actual pick up time and the requested pick up time of the customer does not exceed the maximum waiting time 𝛥. Constraints (1n) ensure that the actual arrival time of vehicle 𝑘must be earlier than the requested arrival time of any of the customers on board of it. For instance, if customer 𝑖is picked up by vehicle 𝑘, the right-hand-side becomes 𝑇𝐴 𝑖enforcing that the actual arrival time of vehicle 𝑘is before 𝑇𝐴 𝑖. Constraints (1o) ensure that the actual arrival time of vehicle 𝑘 is earlier than the earliest requested arrival time 𝑇𝑘of the passengers EURO Journal on Transportation and Logistics 13 (2024) 100132 5 J. Ye et al. on board at the beginning of the re-optimization phase. Constraints (1p) state the relationship between pick-up time and arrival time. For example, if 𝑗is the last customer picked up by vehicle 𝑘before the station 𝑥𝑘 𝑗𝑑 takes value 1, the left-hand-side becomes 𝑡𝑃 𝑗+𝑇𝑗𝑑 , and the right-hand-side becomes 𝑡𝐴 𝑘, enforcing that the actual pick-up time of customer 𝑗plus the travel time between customer 𝑗and station be less than or equal to the actual arrival time of vehicle 𝑘. If 𝑗is not the last customer picked up by the vehicle 𝑘before arrive at the station, then the left-hand-side becomes 𝑡𝑃 𝑗, the right-hand-side becomes 𝑡𝐴 𝑘+𝑇𝐿, which always holds. Finally, constraints (1q)–(1s) define the domain of the decision variables. An illustrative example of possible solutions to the problem is provided in Appendix B. 4. Finding rebalancing centers Identifying where to rebalance in order to anticipate demand, and how many vehicles to send to each rebalancing point is currently an open research question. Any such prediction model could be used to feed rebalancing centers to model (1). In this section we introduce a clustering-based methods for identifying rebalancing centers. We refer to the method as the K-means Clustering (KC) method. The method identifies both the location and demand of the rebalancing centers, and this in turn allows us to determine the upper bound on the number of vehicles dispatchable to the different rebalancing centers. Given a number 𝑘of rebalancing centers to find, the KC method finds rebalancing centers by partitioning all requests received in the current re-optimization phase into 𝑘=|ℛ|clusters. Clusters are created in such a way as to minimize the total distance between the points allocated to the cluster and the centroid of the cluster. The centroids of the clusters will then be used as rebalancing centers. The expected demand (number of requests) of the rebalancing centers will be set equal to the number of requests in the corresponding cluster. We let 𝐷𝑟be the demand of rebalancing point 𝑟∈ℛ. The rational behind the clustering method is the following. Assume that the decision maker performs frequent re-optimizations and that the demand distribution changes slow enough. Then the geographical distribution of demand in the near future is approximately the same as the current demand. Current requests represent a sample from this (unknown) distribution. Thus, over many repetitions one expects to put rebalancing centers where there is actually more demand. We believe our assumption of frequent re-optimizations and demand changing slower than the re-optimizations is reasonable in real-life. However, clearly, the prediction accuracy of the KC method is expected to fall when either (i) there is no underlying pattern in the demand (we argue that any prediction method would probably fail in this case) and (ii) when the demand changes rapidly or re-optimizations are not performed sufficiently frequently. In the computational study we assess both cases. In Section 5we compare the KC method against two benchmarks, namely random selection and no rebalancing. The random selection method (hereafter named RS method) consists of randomly selecting |ℛ|points in the operating area as rebalancing centers. To each rebalancing center is assigned a demand equal to the number of customer requests of the current re-optimization phase within a certain distance (e.g., 1km) of the rebalancing center. No rebalancing entails ℛ= ∅. For both the KC and RS methods, the upper bound 𝐵𝑟of the number vehicles that can be dispatched to each rebalancing center 𝑟is defined as 𝐵𝑟=𝐷𝑟∕ 𝑄, where  𝑄denotes the average number of customer on board a vehicle during one trip. 5. Numerical experiments In this section we report the results of our numerical experiments. The scope of the experiments is to assess, in terms of profits and service rates, two different configurations of the service which we refer to as without rebalancing (woR) and with rebalancing (wR). The configuration woR refers to the situation where the service provider dispatches the vehicles only based on customer requests of the current re-optimization phase. For the model without rebalancing, we simplify our model in Section 3by having an empty set of rebalancing centers. In the configuration wR, the service provider makes the dispatching decision based both on current customer requests and on predicted demand using rebalancing centers. In this case, we test the model with two different method for finding rebalancing centers. In the first case, which we refer to as wRKC, the company use KC to obtain the location and demand of the rebalancing centers. In the second case, which we refer to as wRRS, the company uses the RS method to find the locations and demands of the rebalancing centers. Observe that the potential value of relocation activities in ondemand mobility has been the focus of other studies, such as Ma et al. (2019b), Jamshidi et al. (2021), Sayarshad and Chow (2017), Kash et al. (2022) and Danassis et al. (2022) for different configurations of the service. Particularly, our work shares similarities with Sayarshad and Chow (2017) who also explicitly model the decision of the service provider as an optimization model. However, with respect to Sayarshad and Chow (2017) we consider (i) binding previously accepted requests, (ii) customers desired arrival times and (iii) an upper bound on the maximum waiting time. We believe our study can provides evidences based on a more involved setup of the service. The different configurations are tested on a set of random instances introduced in Section 5.2. All problems are solved with the Python libraries of GUROBI 9.5.0 and a server equipped with Intel Core i5 and 16 GB of RAM. 5.1. Simulation framework We test our model in a simulation framework, based on rollinghorizon optimization, with a planning horizon of one hour. We assume online re-optimization happens every 5minutes. This means that every simulation requires the solution of 12 optimization problems (1). At each re-optimization we update the status of the system, and randomly generate (as explained in the next section) a number of new customers. Particularly, •At the initial optimization phase, say 𝑇= 0, we assume that the 𝒩𝑃is empty. This means that there is no customer whose request had already been accepted in a previous optimization phase. We generate a number of new customers 𝒩𝐶, rebalancing centers ℛ, and initial vehicle positions (as explained in the next section) and solve the resulting model (1). •We then step five minutes forward in time, say optimization phase 𝑇= 1, and assume the solution to the model for 𝑇= 0, has been implemented. This entails the vehicle followed the routes determined by the previous optimization model for five minutes, moving either to customers locations or to rebalancing centers. This provides their updated location for the new re-optimization phase. We then partition the customers of the previous optimization phase into three groups: 1. The first group contains those customers that had been assigned to a vehicle but have not yet been picked up in the five minutes interval between the two re-optimizations (i.e., the route of the vehicle assigned to the customer did not stop by the customer within the five-minute interval between re-optimizations). These customers form the set of mandatory customers 𝒩𝑃in the new re-optimization phase and must be picked up by some vehicle (possibly different from the one assigned in the previous re-optimization phase). EURO Journal on Transportation and Logistics 13 (2024) 100132 6 J. Ye et al. Fig. 3. Uniform and non-uniform distribution of customers with the station located in the center. 2. The second group contains those customers that had been assigned to a vehicle in the previous re-optimization phase and the route of the assigned vehicle stopped by the customer within the five-minute interval between re-optimizations. In the new re-optimization phase these customers represents occupied seats (𝑉𝑘) in the vehicles to which they were assigned. Therefore, these customers represent fulfilled requests and do not appear in 𝒩𝑃in the new re-optimization phase. 3. The third group contains those customers that had not been assigned to a vehicle in the previous re-optimization phase. These represent customers whose request has been rejected and will not show up in the new re-optimization phase. Observe, that in the new re-optimization phase, vehicles may find themselves into one of the following situations. (A) The vehicle is empty at a given position and was on the way to pickup customers or to a rebalancing centers. (B) The vehicle has passengers on board at a given position and was on the way to pick-up additional customers or to the station. In case (A), in the new re-optimization phase the vehicles may be assigned to new customers or to a rebalancing center, independently of the decision made in the previous re-optimization phase. That is, it is possible that the vehicle is assigned to a set of customers different from the ones previously assigned to the vehicle. In case (B) the vehicle cannot be sent to a rebalancing center but may be assigned to new customers or sent directly to the station. Following, we generate new customers 𝒩𝐶for the new re-optimization phase and resolve a problem (1). The procedure continues stepping five minutes forward in time until the end of the one-hour planning horizon. Thus, we are able to collect statistics on the performance of the service. Particularly, the profit is computed as follows. At the end of each re-optimization phase, we collect the fee for all the customers that have been accepted (i.e., a vehicle has been assigned to them) and picked up (i.e., the vehicle has arrived at their location during the five-minute interval between re-optimizations) and subtract the cost of the movements the vehicles have done during the five-minute interval between re-optimizations. The final total profit is then the sum of the individual profits made during the one-hour planning horizon. The procedure is explained by the following example. •Assume that at 𝑇= 0,𝒩𝑃is empty and 𝑉𝑘= 0 for all vehicles 𝑘∈ {𝐷1, 𝐷2, 𝐷3}. That is, there is no customer whose request had already been accepted in a previous optimization phase. We generate a number (say four) of new customers 𝒩𝐶∶= {𝐶0 1, 𝐶0 2, 𝐶0 3, 𝐶0 4}, rebalancing centers ℛ∶= 𝑅0 1, and initial vehicle positions 𝑜(𝐷1), 𝑜(𝐷2), 𝑜(𝐷3)and solve the resulting model (1). Assume that the solution determines the following routes for the three vehicles: 𝚁𝚘𝚞𝚝𝚎𝟷0∶= {𝐷1, 𝐶0 1, 𝐶0 3, 𝑑},𝚁𝚘𝚞𝚝𝚎𝟸0=∶ {𝐷2.𝐶0 2, 𝑑}, 𝚁𝚘𝚞𝚝𝚎𝟹0∶= {𝐷3, 𝑅0 1}and that customer 𝐶0 4is rejected. •The solution computed at 𝑇= 0 is implemented and the vehicle follow the respective routes for five minutes. This provides updated system information for optimization phase 𝑇= 1. That is, we updated the location of the vehicles {𝑜(𝐷1), 𝑜(𝐷2), 𝑜(𝐷3)}. We observe that, 1. For 𝚁𝚘𝚞𝚝𝚎𝟷0, the vehicle 𝐷1already picked up customer 𝐶0 1, and is still on the way to pickup 𝐶0 3, so we can delete 𝐶0 1from the system, update 𝑉𝐷1= 1 and move 𝐶0 3to mandatory customer set 𝒩𝑃∶= {𝐶0 3}. 2. For 𝚁𝚘𝚞𝚝𝚎𝟸0, vehicle 𝐷2already picked up customer 𝐶0 2 and is still on the way to station, so we can delete 𝐶0 2from the system and update 𝑉𝐷2= 1. 3. For 𝚁𝚘𝚞𝚝𝚎𝟹0, vehicle 𝐷3arrived at the rebalancing center 𝑅0 1, thus 𝑉𝐷3= 0. In the new optimization phase 𝑇= 1, since the vehicles 𝐷1, 𝐷2 already have customers on board, they cannot be sent to a rebalancing center but may be assigned to new customers or sent directly to the station. However, vehicle 𝐷3may be assigned to new customers or to a rebalancing center as it is still empty. Following, we generate new customers 𝒩𝐶∶= 𝐶1 1, 𝐶1 2, 𝐶1 3, 𝐶1 4for the new re-optimization phase 𝑇= 1 and resolve the problem (1). 5.2. Instance generation We generate a number of artificial and randomly generated instances that mimic real-life operating scenarios for the service. Particularly, we assume a fleet of homogeneous vehicles of capacity 𝑄= 4. The position of the vehicles for the first re-optimization phase is generated randomly in the business area (defined below) and initially vehicles are assumed to have no passenger on board. For the re-optimization phases other than the first, the position of the vehicles, and the number of EURO Journal on Transportation and Logistics 13 (2024) 100132 7 J. Ye et al. Fig. 4. Uniform and non-uniform distribution of customers with the station located in a corner. passengers on board is computed as the result of previous optimization phases. We consider two different geographies of the business area. In the first geography, depicted in Fig. 3, the station is located at the center of the business area, and the business area itself is represented by a circle of radius 𝑅= 4 km. In the second geography, see Fig. 4, the station is located in a corner and the business area is a quarter of a circle of radius of 𝑅= 8 km. The second geography is meant to represent urban contexts where the demand is concentrated only on one side of the station due to, e.g., physical barriers such as rivers or harbors. For each geography, and for each re-optimization phase, customer requests are generated in the following two different scenarios of demand distribution. In the first scenario, referred to as the uniform demand scenario, pickup locations are randomly scattered in the whole business area, see Figs. 3(a) and 4(a). In the second scenario, referred to as the non-uniform demand scenario, one third of the requests arrive, randomly, from inside the inner circle of radius 𝑅𝐼= 0.6𝑅(where 𝑅 is the radius of the outer circle), while the remaining requests arrive, randomly, from the outer portion of the circle, see Figs. 3(b) and 4(b). We obtain, in total, four configurations namely 1. station in the center and uniform demand (UCt), 2. station in the center and non-uniform demand (NUCt), 3. station in the corner and uniform demand (UCn), 4. station in the corner and non-uniform demand (NUCn). For each request, the requested pickup time (𝑇𝑃 𝑖) is randomly generated uniformly between 0and 3minutes after the beginning of the planning horizon, and the requested arrival time (𝑇𝐴 𝑖) is set as the sum of requested pickup time, 𝑇𝑃 𝑖, travel time between customer 𝑖and the station 𝑑, and a buffer time randomly generated between 5and 8 minutes. Travel time 𝑇𝑖𝑗 are calculated using Euclidean distances and assuming an average speed of 36 Km/h (Commission and Limousine, 2023). The unit transportation cost 𝐶is set to $11.25/h (English,2008) and trip revenues 𝑃𝑖are computed using a fare of $2.59 per Km traveled plus $0.74 per minute traveled, with a minimum fare of $8 following the setting in INSHUR (2022). We set the value of 𝛽to 0.1 in the objective function, unless otherwise specified. Observe that 𝛽determines the impact of rebalancing movements. High values will increase the potential benefit of rebalancing and might lead to rejecting current customers while low values might lead the model to provide myopic decisions. The impact of different values of 𝛽will be assessed through sensitivity analysis in Section 5.5. The expected revenue for rebalancing a vehicle to center 𝑖∈ℛ,𝐸𝑖, is calculated as  𝑃𝑖−𝐶𝑇𝑖𝑑 , where  𝑃𝑖is the revenue of dispatching a vehicle to rebalancing center 𝑖∈ℛ, and is calculated as  𝑃𝑖=𝑄 𝑃 𝐴 𝑖, where 𝑃𝐴 𝑖the average revenue for the requests in the cluster where 𝑖is the centroid and 𝑄is the capacity of the vehicles. 𝐶is the unit transportation cost, set as above, and 𝑇𝑖𝑑 is the distance between rebalancing point 𝑖and the station. To obtain the upper bound on the number of vehicles dispatchable to a rebalancing center (𝐵𝑟, see Section 4) we set the average number of customers on board during one trip of a vehicle  𝑄equal to half of the capacity 𝑄= 4. For each configuration, we generate different instances varying in the number of vehicles and customers that appear at each new re-optimization phase. Particularly, we create instance classes named 𝐶|𝒩𝐶|𝑉|𝒦|with number of customers |𝒩𝐶|∈ {6,7,8}, and number of vehicles, |𝒦|∈ {10,12,14}. As an example, 𝐶8𝑉10 indicates a class of instances with 8new customers in each re-optimization phase and 10 vehicles available for dispatching for the whole planning period. For each instance class we randomly generate 3different instances. Observe, however, that for each instance we solve 12 different optimization problems in our simulation framework. We set the number of rebalancing centers |ℛ|to 3in all instances (later we perform sensitivity analysis with respect to this parameter.) . This number is found using the Elbow Method (EM) and the Silhouette Analysis Method (SAM) (Mahendru,2019). Particularly, we use the instances with |𝒩𝐶|= 8 as a reference case to find a suitable value for 𝑘=|ℛ|. First we randomly generate 8customers in the operating area, then we use the EM approach to show the performance of the KC method for different values of 𝑘. For each 𝑘we consider the WithinCluster-Sum of Squared Errors (WSS). We then plot the WSS versus 𝑘, and choose the value of 𝑘for which the WSS flattens. This point is referred to as an ‘‘Elbow’’, see Fig. 5(a). Nevertheless, in some cases, the EM does not give precise answers as it is not always clear for which value of 𝑘the change of slope is significant. In such cases, we will use the SAM to make a decision. The silhouette score is a measure of how similar a customer request is to its own rebalancing cluster compared to other rebalancing clusters. To be more precise, the silhouette score of one customer request 𝑖can be calculate as below: 𝑠(𝑖) = 𝑏(𝑖) − 𝑎(𝑖) max{𝑎(𝑖), 𝑏(𝑖)} (2) EURO Journal on Transportation and Logistics 13 (2024) 100132 8 J. Ye et al. Fig. 12. Example problem in a scenario where rebalancing in not permitted. EURO Journal on Transportation and Logistics 13 (2024) 100132 15 J. Ye et al. Fig. 13. Example problem in a scenario where rebalancing is permitted. EURO Journal on Transportation and Logistics 13 (2024) 100132 16 J. Ye et al. Fig. 14. Illustration of capacity and arrival time constraints. Table 10 Service rate [%] in the simulations with |ℛ|= 4. C6V10 C6V12 C6V14 C7V10 C7V12 C7V14 C8V10 C8V12 C8V14 NUCt wRKC 91% 98% 98% 95% 97% 97% 93% 96% 98% wRRS 95% 94% 93% 91% 92% 91% 89% 93% 94% woR 94% 94% 94% 89% 94% 91% 90% 90% 92% UCt wRKC 97% 97% 96% 95% 96% 98% 94% 98% 99% wRRS 92% 94% 95% 92% 93% 94% 92% 94% 94% woR 91% 95% 94% 92% 95% 95% 91% 96% 92% NUCn wRKC 79% 84% 86% 79% 84% 86% 77% 84% 89% wRRS 59% 62% 77% 56% 63% 65% 62% 57% 72% woR 63% 66% 72% 48% 60% 62% 47% 48% 57% UCn wRKC 86% 87% 87% 81% 88% 87% 82% 87% 90% wRRS 67% 70% 72% 72% 72% 78% 64% 62% 70% woR 66% 69% 78% 63% 76% 68% 66% 72% 65% Table 11 Profit [$] in the simulations with |ℛ|= 5. C6V10 C6V12 C6V14 C7V10 C7V12 C7V14 C8V10 C8V12 C8V14 NUCt wRKC 55.59 58.84 57.78 68.43 67.63 70.83 76.62 81.41 82.31 wRRS 56.72 55.37 53.75 64.77 68.90 66.49 73.98 79.11 80.38 woR 56.37 56.61 56.42 63.96 67.08 65.72 74.71 77.52 78.71 UCt wRKC 54.50 51.97 56.89 64.16 64.61 63.51 67.93 74.05 72.42 wRRS 53.76 51.60 53.94 61.15 60.48 62.18 67.57 67.84 70.33 woR 50.88 55.03 54.35 61.46 61.68 65.22 66.79 71.78 68.77 NUCn wRKC 96.28 89.64 97.71 117.68 120.27 128.11 127.05 149.52 148.79 wRRS 73.74 79.37 87.74 86.42 77.28 97.84 91.69 103.02 115.89 woR 71.16 72.65 85.50 64.70 82.34 88.40 73.28 76.91 94.33 UCn wRKC 90.33 86.50 94.46 101.61 112.41 106.93 114.81 123.93 125.85 wRRS 61.13 84.17 81.85 72.83 78.28 91.78 86.65 88.83 103.16 woR 70.33 69.94 89.82 77.23 94.43 86.60 90.63 106.04 91.04 Table 12 Service rate [%] in the simulations with |ℛ|= 5. C6V10 C6V12 C6V14 C7V10 C7V12 C7V14 C8V10 C8V12 C8V14 NUCt wRKC 93% 99% 96% 94% 95% 97% 89% 95% 96% wRRS 93% 94% 91% 91% 94% 92% 90% 93% 93% woR 94% 94% 94% 89% 94% 91% 90% 90% 92% UCt wRKC 98% 94% 98% 95% 98% 95% 93% 99% 98% wRRS 94% 94% 97% 95% 93% 94% 92% 90% 95% woR 91% 95% 94% 92% 95% 95% 91% 96% 92% NUCn wRKC 78% 78% 81% 81% 83% 86% 78% 86% 84% wRRS 63% 68% 75% 61% 59% 70% 59% 63% 69% woR 63% 66% 72% 48% 60% 62% 47% 48% 57% UCn wRKC 81% 75% 82% 81% 87% 83% 77% 82% 85% wRRS 61% 78% 76% 62% 66% 76% 64% 68% 73% woR 66% 69% 78% 63% 76% 68% 66% 72% 65% EURO Journal on Transportation and Logistics 13 (2024) 100132 17 J. Ye et al. References Al-Abbasi, Abubakr O., Ghosh, Arnob, Aggarwal, Vaneet, 2019. DeepPool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Trans. Intell. Transp. Syst. 1–14. Alonso-mora, Javier, Wallar, Alex, Frazzoli, Emilio, Rus, Daniela, 2018. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. USA 115 (3), E555. Balas, Egon, 1989. The prize collecting traveling salesman problem. Networks 19 (6), 621–636. Beirigo, Breno A, Negenborn, Rudy R, Alonso-Mora, Javier, Schulte, Frederik, 2022. A business class for autonomous mobility-on-demand: Modeling service quality contracts in dynamic ridesharing systems. Transp. Res. C 136, 103520. Berbeglia, Gerardo, Cordeau, Jean François, Laporte, Gilbert, 2010. Dynamic pickup and delivery problems. European J. Oper. Res. 202 (1), 8–15. Bertsimas, Dimitris, Jaillet, Patrick, Martin, Sébastien, 2019. Online vehicle routing: The edge of optimization in large-scale applications. Oper. Res. 67 (1), 143–162. Bian, Zheyong, Liu, Xiang, 2019a. Mechanism design for first-mile ridesharing based on personalized requirements part I: Theoretical analysis in generalized scenarios. Transp. Res. B 120, 147–171. Bian, Zheyong, Liu, Xiang, 2019b. Mechanism design for first-mile ridesharing based on personalized requirements part II: Solution algorithm for large-scale problems. Transp. Res. B 120, 172–192. Bian, Zheyong, Liu, Xiang, Bai, Yun, 2020. Mechanism design for on-demand first-mile ridesharing. Transp. Res. B 138, 77–117. Bongiovanni, Claudia, Kaspi, Mor, Cordeau, Jean-Francois, Geroliminis, Nikolas, 2022. A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations. Transp. Res. E 165, 102835. Braekers, Kris, Ramaekers, Katrien, Van Nieuwenhuyse, Inneke, 2016. The vehicle routing problem: State of the art classification and review. Comput. Ind. Eng. 99, 300–313. Bräysy, Olli, Gendreau, Michel, 2005. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transp. Sci. 39 (1), 104–118. Chemla, Daniel, Meunier, Frédéric, Calvo, Roberto Wolfler, 2013. Bike sharing systems: Solving the static rebalancing problem. Discrete Optim. 10 (2), 120–146. Chen, Yiwei, Wang, Hai, 2018. Pricing for a last-mile transportation system. Transp. Res. B 107, 57–69. Chen, Shukai, Wang, Hua, Meng, Qiang, 2020. Solving the first-mile ridesharing problem using autonomous vehicles. Comput.-Aided Civ. Infrastruct. Eng. 35 (1), 45–60. Commission, New York City Taxi, Limousine, 2023. New York City Taxi and Limousine Commission. https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page. (Online; Accessed 10 October 2023). Cordeau, Jean François, Laporte, Gilbert, 2003. The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. 4OR 1 (2), 89–101. Danassis, Panayiotis, Sakota, Marija, Filos-Ratsikas, Aris, Faltings, Boi, 2022. Putting ridesharing to the test: Efficient and scalable solutions and the power of dynamic vehicle relocation. Artif. Intell. Rev. 55 (7), 5781–5844. Dantzig, G.B., Ramser, J.H., 1959. The truck dispatching problem. Manage. Sci. 6 (1), 80–91. Elting, Steffen, Ehmke, Jan Fabian, 2021. Potential of shared taxi services in rural areas–A case study. Transp. Res. Procedia 52, 661–668. English, Sandy, 2008. High fuel prices impoverish new york city taxi drivers. https: //www.wsws.org/en/articles/2008/09/taxi-s04.html. (Online; Accessed 10 October 2022). Faghih-Imani, Ahmadreza, Hampshire, Robert, Marla, Lavanya, Eluru, Naveen, 2017. An empirical analysis of bike sharing usage and rebalancing: Evidence from Barcelona and Seville. Transp. Res. A 97, 177–191. Fagnant, Daniel J., Kockelman, Kara M., 2018. Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in Austin, Texas. Transportation 45, 143–158. Folkestad, Carl Axel, Hansen, Nora, Fagerholt, Kjetil, Andersson, Henrik, Pantuso, Giovanni, 2020. Optimal charging and repositioning of electric vehicles in a free-floating carsharing system. Comput. Oper. Res. 113, 104771. Ho, Sin C., Szeto, W.Y., Kuo, Yong-hong Hong, Leung, Janny M.Y.Y., Petering, Matthew, Tou, Terence W.H.H., 2018. A survey of dial-a-ride problems: Literature review and recent developments. Transp. Res. B 111, 395–421. Huang, Yan, Bastani, Favyen, Jin, Ruoming, Wang, Xiaoyang Sean, 2014. Large scale realtime ridesharing with service guarantee on road networks. In: Proceedings of the VLDB Endowment. Illgen, Stefan, Höck, Michael, 2019. Literature review of the vehicle relocation problem in one-way car sharing networks. Transp. Res. B 120, 193–204. INSHUR, 2022. How much does an Uber driver make in New York City?. https:// inshur.com/blog/how-much-does-an-uber-driver-make-in-new-york-city/. (Online; Accessed 10 October 2022). Jamshidi, Helia, Correia, Gonçalo HA, van Essen, J Theresia, Nökel, Klaus, 2021. Dynamic planning for simultaneous recharging and relocation of shared electric taxies: A sequential MILP approach. Transp. Res. C 125, 102933. Kash, Ian A., Wen, Zhongkai, Zuck, Lenore D., 2022. Dynamic relocation in ridesharing via fixpoint construction. In: Cussens, James, Zhang, Kun (Eds.), Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence. In: Proceedings of Machine Learning Research, vol. 180, PMLR, pp. 980–989, URL https://proceedings.mlr.press/v180/kash22a.html. Kumar, Suresh Nanda, Panneerselvam, Ramasamy, 2012. A survey on the vehicle routing problem and its variants. Intell. Inf. Manage. 04 (03), 66–74. Li, Xihan, Zhang, Jia, Bian, Jiang, Tong, Yunhai, Liu, Tie-Yan, 2019. A cooperative multi-agent reinforcement learning framework for resource balancing in complex logistics network. In: International Foundation for Autonomous Agents and Multiagent Systems. AAMAS ’19, pp. 980–988. Lin, Canhong, Choy, K.L., Ho, G.T.S., Chung, S.H., Lam, H.Y., 2014. Survey of Green vehicle routing problem: Past and future trends. Expert Syst. Appl. 41 (4 PART 1), 1118–1138. Lin, Kaixiang, Zhao, Renyu, Xu, Zhe, Zhou, Jiayu, 2018. Efficient large-scale fleet management via multi-agent deep reinforcement learning. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 1774–1783. Liu, Junming, Sun, Leilei, Chen, Weiwei, Xiong, Hui, 2016. Rebalancing bike sharing systems: A multi-source data smart optimization. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 1005–1014. Lokhandwala, Mustafa, Cai, Hua, 2018. Dynamic ride sharing using traditional taxis and shared autonomous taxis: A case study of NYC. Transp. Res. C 97, 45–60. Lotfi, Sepide, Abdelghany, Khaled, 2022. Ride matching and vehicle routing for on-demand mobility services. J. Heuristics 28 (3), 235–258. Ma, Tai-yu Yu, Rasulkhani, Saeid, Chow, Joseph Y.J. J, Klein, Sylvain, 2019a. A dynamic ridesharing dispatch and idle vehicle repositioning strategy with integrated transit transfers. Transp. Res. E 128 (December 2018), 417–442. Ma, Ruimin, Yao, Lifei, Song, Lijun, Jin, Maozhu, 2019b. A novel algorithm for peer-to-peer ridesharing match problem. Neural Comput. Appl. 31 (s1), 247–258. Mahendru, Khyati, 2019. How to determine the optimal K for K-means?. https://medium.com/analytics-vidhya/how-to-determine-the-optimal-k-for-kmeans-708505d204eb. (Online; Accessed 10 October 2022). Mao, Chao, Liu, Yulin, Shen, Zuo-Jun Max, 2020. Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach. Transp. Res. C 115, 102626. Masoud, Neda, Jayakrishnan, R., 2017. A decomposition algorithm to solve the multi-hop Peer-to-Peer ride-matching problem. Transp. Res. B 99 (May), 1–29. Masoud, Neda, Lloret-Batlle, Roger, Jayakrishnan, R., 2017. Using bilateral trading to increase ridership and user permanence in ridesharing systems. Transp. Res. E. Mourad, Abood, Puchinger, Jakob, Chu, Chengbin, 2019. A survey of models and algorithms for optimizing shared mobility. Transp. Res. B 123, 323–346. Noruzoliaee, Mohamadhossein, Zou, Bo, 2022. One-to-many matching and section-based formulation of autonomous ridesharing equilibrium. Transp. Res. B 155, 72–100. Osorio, Jesus, Lei, Chao, Ouyang, Yanfeng, 2021. Optimal rebalancing and on-board charging of shared electric scooters. Transp. Res. B 147, 197–219. Pantuso, Giovanni, 2022. Exact solutions to a carsharing pricing and relocation problem under uncertainty. Comput. Oper. Res. 144, 105802. Parragh, Sophie N., Doerner, Karl F., Hartl, Richard F., 2008. A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. J. Betr. 58 (2), 81–117. Pfeiffer, Christian, Schulz, Arne, 2022. An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization. OR Spectrum 44 (1), 87–119. Pillac, Victor, Gendreau, Michel, Guéret, Christelle, Medaglia, Andrés L., 2013. A review of dynamic vehicle routing problems. European J. Oper. Res. 225 (1), 1–11. Qin, Zhiwei, Tang, Xiaocheng, Jiao, Yan, Zhang, Fan, Wang, Chenxi, Li, Qun, 2019. Deep reinforcement learning for ride-sharing dispatching and repositioning. In: IJCAI International Joint Conference on Artificial Intelligence. 2019-Augus, pp. 6566–6568. Ritzinger, Ulrike, Puchinger, Jakob, Hartl, Richard F., 2016. A survey on dynamic and stochastic vehicle routing problems. Int. J. Prod. Res. 54 (1), 215–231. Ropke, Stefan, Cordeau, Jean-François François, 2009. Branch and cut and price for the pickup and delivery problem with time windows. Transp. Sci. 43 (3), 267–286. Santos, Douglas O., Xavier, Eduardo C., 2015. Taxi and ride sharing: A dynamic dial-a-ride problem with money as an incentive. Expert Syst. Appl. 42 (19), 6728–6737. Sayarshad, Hamid R., Chow, Joseph Y.J., 2017. Non-myopic relocation of idle mobilityon-demand vehicles as a dynamic location-allocation-queueing problem. Transp. Res. E 106, 60–77. Shen, Yu, Zhang, Hongmou, Zhao, Jinhua, 2018. Integrating shared autonomous vehicle in public transportation system: A supply-side simulation of the first-mile service in Singapore. Transp. Res. A 113, 125–136. Stiglic, Mitja, Agatz, Niels, Savelsbergh, Martin, Gradisar, Mirko, 2015. The benefits of meeting points in ride-sharing systems. Transp. Res. B 82, 36–53. Stiglic, Mitja, Agatz, Niels, Savelsbergh, Martin, Gradisar, Mirko, 2018. Enhancing urban mobility: Integrating ride-sharing and public transit. Comput. Oper. Res. 90, 12–21. EURO Journal on Transportation and Logistics 13 (2024) 100132 18 J. Ye et al. Tang, Xiaocheng, Qin, Zhiwei Tony, Zhang, Fan, Wang, Zhaodong, Xu, Zhe, Ma, Yintai, Zhu, Hongtu, Ye, Jieping, Labs, A I, Chuxing, Didi, Tang, Xiaocheng, Qin, Zhiwei Tony, Zhang, Fan, Wang, Zhaodong, Xu, Zhe, Ma, Yintai, Zhu, Hongtu, Ye, Jieping, 2019. A deep value-network based approach for multi-driver order dispatching. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 1780–1790. Taniguchi, Eiichi, Thompson, Russell G., Yamada, Tadashi, 2014. Recent trends and innovations in modelling city logistics. Procedia Soc. Behav. Sci. 125, 4–14, URL https://www.sciencedirect.com/science/article/pii/S187704281401489X. Toth, Paolo, Vigo, Daniele, 2002. The Vehicle Routing Problem. SIAM. Wallar, Alex, Van Der Zee, Menno, Alonso-Mora, Javier, Rus, Daniela, 2018. Vehicle rebalancing for mobility-on-demand systems with ride-sharing. In: IEEE International Conference on Intelligent Robots and Systems. pp. 4539–4546. Wang, Hai, 2019. Routing and scheduling for a last-mile transportation system. Transp. Sci. 53 (1), 131–147. Wang, Xing, Agatz, Niels, Erera, Alan, 2018. Stable matching for dynamic ride-sharing systems. Transp. Sci. 52 (4), 850–867. Wen, Jian, Zhao, Jinhua, Jaillet, Patrick, 2018. Rebalancing shared mobility-on-demand systems: A reinforcement learning approach. In: IEEE Conference on Intelligent Transportation Systems, Proceedings. ITSC, 2018-March, (October), pp. 220–225. Xu, Zhe, Li, Zhixin, Guan, Qingwen, Zhang, Dingshui, Li, Qiang, Nan, Junxiao, Liu, Chunyang, Bian, Wei, Ye, Jieping, 2018. Large-scale order dispatch in ondemand ride-hailing platforms: A learning and planning approach. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD ’18, Association for Computing Machinery, New York, NY, USA, pp. 905–913. Zhao, Meng, Yin, Jiateng, An, Shi, Wang, Jian, Feng, Dejian, 2018. Ridesharing problem with flexible pickup and delivery locations for app-based transportation service: Mathematical modeling and decomposition methods. J. Adv. Transp. 2018. Zheng, Minyi, Pantuso, Giovanni, 2023. Trading off costs and service rates in a first-mile ride-sharing service. Transp. Res. C 150, 104099. EURO Journal on Transportation and Logistics 13 (2024) 100132 19