A novel repositioning approach and analysis for dynamic ride-hailing problems

Ackermann, Christian; Rieck, Julia Article A novel repositioning approach and analysis for dynamic ride-hailing problems EURO Journal on Transportation and Logistics (EJTL) Provided in Cooperation with: Association of European Operational Research Societies (EURO), Fribourg Suggested Citation: Ackermann, Christian; Rieck, Julia (2023) : A novel repositioning approach and analysis for dynamic ride-hailing problems, EURO Journal on Transportation and Logistics (EJTL), ISSN 2192-4384, Elsevier, Amsterdam, Vol. 12, Iss. 1, pp. 1-16, https://doi.org/10.1016/j.ejtl.2023.100109 This Version is available at: https://hdl.handle.net/10419/325185 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/4.0/ EURO Journal on Transportation and Logistics 12 (2023) 100109 Available online 15 June 2023 2192-4376/© 2023 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 license (http://creativecommons.org/licenses/by/4.0/). Contents lists available at ScienceDirect EURO Journal on Transportation and Logistics journal homepage: www.elsevier.com/locate/ejtl A novel repositioning approach and analysis for dynamic ride-hailing problems Christian Ackermann∗, Julia Rieck University of Hildesheim, Institute for Business Administration and Information Systems, Operations Research Group, Universitätsplatz 1, 31141 Hildesheim, Germany ARTICLE INFO Keywords: Dynamic ride-hailing Repositioning Assignment Comparison ABSTRACT Mobility-on-demand services continue to grow in popularity and could provide a cheap and resource-saving alternative to private vehicles. However, to be truly attractive to the general public, these services must be thoroughly optimized. In this paper, we consider a ride-hailing problem where available vehicles have to be assigned to dynamically arising customer requests and, furthermore, vacant vehicles have to be repositioned to other parts of the service area to balance supply and demand. We propose a novel repositioning strategy based on dynamically created, overlapping zones that addresses identified weaknesses of previous repositioning approaches. While most other ride-hailing studies only consider one specific setting for which a suitable ridehailing strategy is developed, we further analyze which design decisions in the context of assignment and repositioning work best under different given problem characteristics. Our results show that the proposed repositioning approach outperforms the benchmark approaches in most of the relevant settings, independent of the underlying objective function. Additionally, we show that, especially for low-utilized fleets, the simple nearest-vehicle assignment strategy outperforms matching-based assignment approaches in many settings. The insights gained are analyzed and thoroughly discussed. 1. Introduction Mobility-on-demand represents a comfortable and flexible alternative to classic public transport or personal vehicles. Over the past decade, these services have continued to gain popularity among the public as well as researchers in the logistics area. When they are well-designed, they do not only minimize costs and emissions but can increase the willingness to relinquish the use of private vehicles due to improved service quality. In the extreme case, it could even be possible to replace all personal vehicles in big cities by fleets of autonomous—optimally electric—vehicles (Bischoff and Maciejewski, 2016). By that, resources would be used more efficiently due to higher vehicle utilization, inner-city parking areas could be utilized by other means, and individual mobility costs would decrease. In this paper, we are concerned with the ride-hailing problem, where a fleet of vehicles is centrally controlled by a fleet operator to pick up customers as quickly as possible and drop them off at their target destination. It has to be determined which vehicle to assign to which customer request (assignment) and whether the current vacant vehicles should be sent in an anticipatory fashion to other parts of the service area to balance future demand and supply (repositioning). For both problem parts, a sophisticated strategy has to be determined ∗Corresponding author. E-mail addresses: [email protected] (C. Ackermann), [email protected] (J. Rieck). in order to reach good solutions since both parts heavily affect the overall quality. For the repositioning part, we propose a new strategy based on the identified weaknesses in existing approaches from the literature. Regarding the selection of an appropriate assignment strategy, we realized that most of the papers in the literature that study this kind of problem only consider one very specific setting for which a solution method is presented (see Section 2). For example, the fleet size is fixed, there is a specific maximum waiting time, only idling vehicles are allowed to receive a new request assignment, and a specific number of requests is temporally uniformly distributed over the planning horizon. The proposed method is then only evaluated in this fixed setting, often without analyzing dependencies between these problem characteristics and the solution quality. Furthermore, many proposed assignment strategies share similarities in certain features and could therefore be applied in different problem settings. What is urgently missing, in our opinion, is a deeper analysis of which of the possible strategy features play a role in which problem setting since at least some of the features are highly dependent on the specific setting at hand. We want to close this research gap by means of an extensive discussion and computational study to be able to determine the best strategies for a given setting. https://doi.org/10.1016/j.ejtl.2023.100109 Received 21 December 2022; Received in revised form 9 May 2023; Accepted 30 May 2023 EURO Journal on Transportation and Logistics 12 (2023) 100109 2 C. Ackermann and J. Rieck Table 1 Classification of selected articles based on problem characteristics. Article Response Max WTaAvailable vehicles Objective SRbWTcProfit Other Bischoff and Maciejewski (2016) immediate ✗non-serving ✓ ✓ ✓ De Souza et al. (2020) immediate ✗non-serving ✓ ✓ ✓ Al-Kanj et al. (2020) immediate ✗non-serving ✓ Lu et al. (2012) immediate ✗non-serving ✓ ✓ Maciejewski and Nagel (2013) immediate ✗both ✓ ✓ Bailey and Clark (1992) immediate ✗both ✓ ✓ Maciejewski et al. (2016) delayed ✗non-serving ✓ ✓ Hyland and Mahmassani (2018) delayed ✗non-serving ✓ ✓ Dandl et al. (2019) delayed ✗non-serving ✓ ✓ ✓ Miao et al. (2016) delayed ✗non-serving ✓ ✓ Qin et al. (2021) delayed ✗non-serving ✓ Shi et al. (2021) delayed ✗non-serving ✓ ✓ Fagnant and Kockelman (2014) delayed ✓non-serving ✓ ✓ Gao et al. (2016) delayed ✓non-serving ✓ ✓ Guo et al. (2021) delayed ✓non-serving ✓ ✓ Lyu et al. (2019) delayed ✓non-serving ✓ ✓ Qin et al. (2020) delayed ✓non-serving ✓ Kullman et al. (2021) delayed ✓all ✓ Alonso-Mora et al. (2017) delayed ✓all ✓ ✓ Wallar et al. (2018) delayed ✓all ✓ This paper delayed (✓) both ✓ ✓ aMaximum waiting time constraint in place. bService rate maximization. cWaiting time minimization. The main contributions of this paper are threefold: •We evaluate the design decisions of assignment approaches for ride-hailing problems depending on various problem characteristics and derive which strategy should be used in which kinds of settings to achieve the best results. •We propose a novel repositioning strategy that, unlike comparable approaches from the literature, explicitly considers available parking lots for idling vehicles and given waiting time constraints to improve the service rate. Additionally, it uses dynamically created, overlapping zones and, by doing so, overcomes potential discretization issues. A previous version of our strategy won the ride-hailing track of the 12th DIMACS Implementation Challenge (DIMACS,2022). •We compare our repositioning strategy to strategies from the literature depending on various problem characteristics, derive which strategy should be used in which setting, and point out in which settings well-designed repositioning strategies are most important. With these contributions, we aim to advance the study of ridehailing problems by helping researchers as well as practitioners to find the most suitable approach for their specific problem settings, thus allowing easier further development of the existing approaches as well as the implementation of more efficient ride-hailing services in practice. The remainder of the paper is structured as follows: In Section 2, related literature is presented. In addition, we point out the different problem characteristics considered in the literature and classify the papers accordingly. In Section 3, the specific problem under consideration is introduced and formulated. Section 4describes in detail the relevant assignment approaches and their features considered in our study. In Section 5, we present the benchmark approaches for repositioning as well as our own repositioning strategy. The results of the experimental study are addressed and discussed in Section 6. Finally, Section 7 concludes the paper and summarizes the main findings. 2. Related literature and problem characteristics The ride-hailing problem can be considered part of the domain of dynamic vehicle routing problems. In this domain, it can be seen as a special case of the dynamic dial-a-ride problem. The main difference is that in the classic dial-a-ride problem, there are usually time windows associated with the dynamically arising customer requests, indicating when the customers want to get picked up and/or dropped off. With that, a sequence of pickup and drop-off nodes can be determined for each vehicle, which might be optimized later on based on new dynamic information. In most settings, it is additionally allowed that customers share their trip with other people, meaning that the pickup and dropoff nodes do not have to be visited directly after one another. For an overview of dial-a-ride literature, we refer to Ho et al. (2018). In the ride-hailing problem, however, customers want to be served as soon as possible. Therefore, the time window opens as soon as the request gets known to the system. Additionally, in most settings, there is a relatively short maximum waiting time of only a few minutes, leading to very tight time windows. Together with a significantly larger relative fleet size (i.e., fewer requests per vehicle compared to other vehicle routing problems), there are typically no long sequences of nodes to visit. In most cases, a vehicle has only planned its very next request since many settings do not allow sharing the vehicle with other customers. By that, the problem’s focus shifts towards quickly finding a feasible matching between open requests and available vehicles (request assignment). To improve the quality of future assignments, currently unused vehicles can be sent to different parts of the service area (repositioning) to balance supply and demand. In what follows, we first introduce different characteristics of the problems studied in the literature. Afterwards, we present approaches from the literature for assignment and repositioning. Please note that the approaches used in the experimental study will be discussed in more detail in Sections 4and 5. Table 1 shows articles dealing with assignment strategies. The order of the articles results from the classification made according to different relevant problem characteristics. The first important feature considered is whether customer requests have to be answered immediately or if the response can be delayed. An immediate response contains the decision for acceptance or rejection as well as the vehicle assigned to the request. When the response can be delayed, multiple requests can first be gathered before a decision has to be made. In some settings, the maximum waiting time (Max WT) of customers is limited. If it is not possible to pick up the customer within the time span of the maximum waiting time, the request gets rejected. Furthermore, problem settings differ in the vehicles considered to be available for assignment. While EURO Journal on Transportation and Logistics 12 (2023) 100109 3 C. Ackermann and J. Rieck most studies limit assignments to vehicles that are not currently serving a request (non-serving), other studies allow the assignment of all vehicles. Here, the current customer is first dropped off before the new customer is picked up. Two studies compare the quality of both versions with each other. The articles also use different objective functions. Most often, combinations of service rate (SR), customer waiting time (WT), and profit or costs have to be optimized. The table reveals that a maximum waiting time restriction is only applied in the listed studies when delaying the response is allowed. Additionally, delayed responses are considered more often, most likely due to the increased complexity of corresponding solution approaches. Finally, we observe that only in the studies of Kullman et al. (2021) and Maciejewski et al. (2016), it is taken into account that vacant vehicles cannot necessarily idle everywhere. Therefore, pre-defined parking lots are considered for vehicles to wait for their next request assignment. The real-world settings in which these ride-hailing problems occur are most often typical taxi services. In Alonso-Mora et al. (2017) and Wallar et al. (2018), sharing a trip with other customers is additionally possible. Car-sharing systems are examined in studies such as De Souza et al. (2020), Fagnant and Kockelman (2014), and Spieser et al. (2016), the first two of which use autonomous vehicles. Bischoff and Maciejewski (2016) go one step further and investigate the possibility of replacing all private cars in Berlin with autonomous taxis. In Kullman et al. (2021), Al-Kanj et al. (2020), and Lu et al. (2012), electric vehicles are used, extending the problem by adding charging decisions. When considering assignment approaches, significant differences can be seen between settings with immediate and delayed responses. For immediate responses, the strategies are rather simple. In Bailey and Clark (1992), a request is assigned to the closest vehicle. In their experiments, the authors examine if considering all or just non-serving vehicles for assignment leads to better results. Maciejewski and Nagel (2013) assign requests to their closest vehicle as well, but allow later reassignments in case the closest vehicle changes due to unexpected delays. Bischoff and Maciejewski (2016) use a strategy depending on the current supply–demand-ratio that either assigns a request to the closest available vehicle or assigns a vehicle to the closest open request. Lu et al. (2012) present similar strategies for electric vehicles. Here, the current battery load as well as the demand in the destination zone are considered in the assignment. When delayed responses are allowed, often variants of matching problems are solved to assign the gathered open requests to the available vehicles. The objective functions used in the matching can include, e.g., the service rate, the waiting time, or driving costs (Hyland and Mahmassani,2018;Maciejewski et al.,2016;Lyu et al.,2019). In Miao et al. (2016), fairness regarding similar service rates in different parts of the service area is also incorporated in the matching. Gao et al. (2016) consider additional assignment constraints due to heterogeneous vehicles and customer preferences. Qin et al. (2021) use a common matching approach as well, but learn a dynamic time interval between the matchings with reinforcement learning. Shi et al. (2021) and Xu et al. (2018) learn the cost matrix of the matching problem. By that, it can be taken into account that vehicles are differently profitable in different parts of the service area. Alonso-Mora et al. (2017) and Wallar et al. (2018) solve the sharing-variant of the problem by integrating information about the sharability of trips. Fagnant and Kockelman (2014) do not perform matching but assign gathered requests to the closest vehicles if they are in the same zone. Requests without an available vehicle in their zone receive a vehicle further away in subsequent steps. In Qin et al. (2020) and Shi et al. (2020), the complete assignment strategy is learned via reinforcement learning. Within the context of the repositioning approaches, Alonso-Mora et al. (2017) suggest sending vehicles to locations of previously rejected requests. In Fagnant and Kockelman (2014), vehicles are shifted between neighboring zones to balance supply–demand-ratios in these zones. In Spieser et al. (2016), all available vehicles are distributed in the same way as the demand is distributed. A solution is obtained by solving a corresponding matching problem. De Souza et al. (2020) and Wallar et al. (2018) use a similar idea but prevent further vehicles from repositioning when the expected demand is already met. In this way, they can reduce repositioning costs. In Jiao et al. (2021), reinforcement learning is applied for repositioning, maximizing the income per hour. Braverman et al. (2019), as well as (Zhang and Pavone,2016), investigate the repositioning problem from a queueing-theoretical perspective. They discretize the service area by considering a finite set of stations where vehicles can idle and customers enter and exit vehicles. Requests are rejected when a customer arrives at a station and there is currently no vacant vehicle available. Zhang and Pavone (2016) aim to balance demand and supply while minimizing the average number of repositioning vehicles. Braverman et al. (2019) maximize the revenue gained from serving requests. Both papers provide theoretically optimal solutions for their specific problem formulations. Lastly, there are some approaches that combine assignment and repositioning decisions into one single strategy. Kullman et al. (2021) present such a combined approach based on reinforcement learning. In Al-Kanj et al. (2020), approximate dynamic programming is used and pricing strategies are introduced to balance supply and demand. Guo et al. (2021) present a matching-integrated vehicle rebalancing model to optimize service rate and costs. A comparable approach is used in Dandl et al. (2019), where a matching problem for the assignment is solved while considering fleet unbalances introduced by the assignment. 3. Problem description The aim of our study is to evaluate our own repositioning approach as well as compare the quality of different solution approaches from the literature for varying common problem characteristics. To be able to include various settings, we keep the problem specification as flexible as possible. The basic setting is close to the setting of the ride-hailing track of the 12th DIMACS Implementation Challenge on Vehicle Routing Problems (DIMACS,2022) which was inspired by Kullman et al. (2021). The problem is to centrally control a fleet of homogeneous vehicles = {1,2,…, 𝑉 }that serve customer requests = {1,2,…, 𝑅}over the course of one day (24 h). Each customer submits a request 𝑖, which can be represented as a tuple (𝑡𝑖, 𝑝𝑖, 𝑑𝑖, 𝑟𝑖). The customer calls at time 𝑡𝑖 and provides the system with information about the desired pickup (𝑝𝑖) and drop-off (𝑑𝑖) location. Every customer wants to be served as soon as possible, and sharing a vehicle with other customers is not allowed. The fleet operator receives a reward 𝑟𝑖for serving this request. The reward consists of a fixed reward and a variable reward depending on the distance between pickup and drop-off. However, all vehicle movements (with and without customers) induce an additional negative reward proportional to the distance traveled. To limit customer inconvenience, a maximum waiting time 𝑇𝑊is introduced, requiring the designated vehicle to arrive at the pickup location no later than 𝑡𝑖+𝑇𝑊. If it is not possible to serve the request in time, the customer gets rejected by the system. To model problem settings without a maximum waiting time, 𝑇𝑊can be set to the length of the planning horizon (here: 86400 s). Please note that rejection of requests is just allowed, when there is a real maximum waiting time constraint in place. Additionally, there is a maximum notification time 𝑇𝑁until which the customer needs to be informed about the acceptance/rejection decision. In case of acceptance, this includes information about the assigned driver as well as the estimated arrival time. The notification constraint can be removed by setting 𝑇𝑁=𝑇𝑊. We model the problem as a Markov decision process (MDP), following the key modeling decisions by Kullman et al. (2021). A decision epoch is triggered by one of the three following events: 1. A new incoming request arrives. EURO Journal on Transportation and Logistics 12 (2023) 100109 4 C. Ackermann and J. Rieck 2. A vehicle drops off its current customer and has no follow-up job. Please note that a job is one single command, like the setup for a new request, the actual processing of a request, or a repositioning trip. 3. A maximum interdecision time of 𝑇𝐷seconds has passed since the last decision epoch. We describe each state as a tuple 𝑠= (𝑠𝑡, 𝑠𝑟, 𝑠𝑣). Here, 𝑠𝑡is the current time in seconds since the beginning of the current episode. Moreover, 𝑠𝑟is a tuple containing the pending requests. Each entry corresponds to one single pending request and holds the data about the request time, the pickup and drop-off locations as well as the reward, as described above. Lastly, 𝑠𝑣is a tuple where each entry holds the data of one single vehicle. Each vehicle has a current location, a state, and a set of already scheduled jobs. The vehicle state is one of the following: •Setup: The vehicle is vacant and on its way to pick up a customer. •Processing: The vehicle travels with a customer on board from the pickup to the drop-off location. •Repositioning: The vehicle is vacant and on its way to a designated parking lot for idling. •Idling: The vehicle is vacant and stationary in a parking lot, waiting for a new job. •Null: The vehicle just dropped off a customer at the drop-off location and is waiting for either a new job or a parking lot assignment for idling. Each action is given as a tuple 𝑎= (𝑎𝑟, 𝑎𝑣). Thereby, 𝑎𝑟is also a tuple representing the action related to each of the pending requests. Possible actions per request are reject,postpone, or assign to a vehicle, indicated by the ID of the assigned vehicle. If a request is rejected, it cannot be assigned in future epochs. Vehicles can only be assigned to at most one pending request at a time, provided that the vehicle is available for receiving a new request (see below) and the estimated time of arrival at the pickup location is within the maximum waiting time. In case such an assignment is feasible, the vehicle has to start setting up for this request immediately after a potential current customer is dropped off. Feasible assignments cannot be changed, retracted, or postponed. Furthermore, 𝑎𝑣is a tuple that represents the action associated with each of the vehicles. Possible actions per vehicle are continue or reposition to parking lot, indicated by the ID of the parking lot. Continuing means that the vehicle continues the planned jobs like setup, processing, or repositioning, or that it stays idling. If the vehicle is currently in state null and was not assigned to a pending request, a repositioning order has to be given since idling is only allowed at pre-defined, non-capacitated locations = {1,2,…, 𝐿}. The higher the number of parking lots 𝐿, the closer this setting is to ‘‘free-floating’’ scenarios, where vehicles are allowed to idle everywhere. Repositioning orders for vehicles are only executed if the vehicle was not assigned to a pending request in the same decision epoch or was not already busy setting up for or serving a request. Changing the destination of a repositioning trip before the vehicle reaches the previously assigned parking lot is allowed. We use different specifications to determine which vehicles are available for receiving a new request: •All vehicles: Vehicles are always available to receive a new request, except when they already have an open request assigned to them that has not yet been picked up. Repositioning jobs can be interrupted to pick up customers. This setting provides the most flexibility and the highest number of assignable vehicles. •All but repositioning vehicles: Here, the same vehicles are available as before, except for the vehicles that are currently repositioning. This setting ensures that the planned fleet repositioning is fully implemented and not affected by repositioning jobs being aborted half-way through to serve incoming requests. •Non-serving vehicles: Vehicles in states {repositioning,idling,null} are available for receiving a new request. In the literature, this is the most common setting. •Only idling vehicles: Just the vehicles in states {idling,null} are available. This is the same setting as the non-serving vehicles, while it ensures that repositioning jobs will be completed. In the context of the MDP formulation, performing an action 𝑎in state 𝑠leads to a reward 𝑅(𝑠, 𝑎). Different objectives are considered in the literature and in practical applications (see Table 1), with the most common being maximizing the service rate or number of served requests, minimizing customer waiting time, and maximizing overall profit. To enable the use of any of these as well as combinations of these, we formulate the reward function as follows: 𝑅(𝑠, 𝑎) = 𝛼⋅𝑅𝑆𝑅(𝑠, 𝑎) + 𝛽⋅𝑅𝑊 𝑇 (𝑠, 𝑎) + 𝛾⋅𝑅𝑅(𝑠, 𝑎).(1) 𝑅𝑆𝑅 calculates the reward related to the number of served requests. Here, only integer numbers are possible, indicating the number of feasible assignments of vehicles to pending requests, since these requests will be served. 𝑅𝑊 𝑇 computes the reward related to the waiting time of the customers. As we are considering deterministic travel times, the final waiting time of assigned customers can already be computed when the assignment happens. The reward is the negative sum of the waiting times for each assigned customer in seconds. Rejected requests receive a value equal to the maximum waiting time 𝑇𝑊.𝑅𝑅determines the monetary reward, which is calculated using the reward received for serving the assigned requests as well as the costs associated with all distances driven by all vehicles. All three objectives can be used at the same time and can be weighted via appropriately dimensionalized parameters 𝛼, 𝛽, and 𝛾. If only one objective is to be considered, the other weights can be set to 0. If a lexicographical order is preferred instead, the weights can be adapted accordingly. Note in this context that the number of served requests is limited by the total number of requests 𝑅per episode and the sum of waiting times over all requests is limited by 𝑇𝑊⋅𝑅. During the transition from state 𝑠to the following state 𝑠+ 1, the time is updated depending on the event that triggers the next decision epoch, the locations of the vehicles are updated with respect to the time passed, and the set of pending requests is updated as well. Feasibly assigned requests are removed from the set. Requests that have been pending for more than 𝑇𝑁seconds are automatically rejected and removed from the set. Potential new requests are added. We seek to find a policy 𝜋∗that maximizes the expected sum of rewards earned during the time horizon, starting from an initial state 𝑠0. The initial state 𝑠0is determined at random with 𝑡= 0, an empty set of pending requests, and all vehicles in random parking lots with no scheduled jobs. 4. Assignment strategies In this section, we present and explain the strategies included in our study for assigning available vehicles to open requests. The most used strategies are the nearest strategy and different variants of matching-based approaches. In the nearest strategy, an incoming request is processed immediately. All of the available vehicles are checked for their distance or travel time to the pickup location, and the nearest/fastest vehicle is selected, provided that it can reach the pickup location in time. While this is a very greedy strategy that can be suboptimal in various settings, it provides the customer with an immediate response. Thus, when customers demand a response immediately after requesting service (𝑇𝑁= 0), this strategy is usually chosen. Following this argumentation, it would make sense to also reject the customer immediately in case there is no feasible assignment possible. By that, we lose the option to find a feasible assignment at a later point. Bischoff and Maciejewski (2016) suggest an improved strategy for undersupply scenarios in which there are more open requests than EURO Journal on Transportation and Logistics 12 (2023) 100109 5 C. Ackermann and J. Rieck available vehicles. They assume that open requests will be queued in a first-come-first-serve (FCFS) fashion until they are answered. In this case, the next assignment will happen whenever the next vehicle becomes available for assignment. However, assigning this vehicle to the longest-waiting customer will most likely lead to bad assignments in terms of distance or travel time. To prevent this, they propose to switch from request-based to vehicle-based assignments and assign the nearest request to the first available vehicle. With that, the first-come-firstserve principle is disregarded (which can lead to fairness concerns), but the efficiency of the fleet is increased due to better assignments. This proves to be successful because efficiency is key in times of undersupply. Nevertheless, we do not consider this strategy in our study. The reason for that is that the strategy allows delayed responses, and matching-based approaches are expected to always provide superior results when the response may be delayed. The strategy can, however, be useful in very large practical applications where it is not possible to calculate the full distance matrix for the matching approaches in a reasonable amount of time (Maciejewski et al.,2016). If we do not require an immediate response, matching-based approaches are typically used in the literature. They gather incoming requests and available vehicles over a short timeframe 𝛿𝑀to then solve a matching problem, which assigns the open requests to the available vehicles. Because multiple assignments are made together (in contrast to the nearest strategy), the resulting solution is usually of higher quality. In most cases, the problem is formulated as a linear cost-minimum matching problem on a bipartite graph. The costs for each matching are usually the distance or the travel time between the current location of the vehicle and the pickup location of the respective request. Infeasible matchings can be prevented, e.g., by setting the associated costs to a sufficiently high value, so that the optimal solution will always contain as many feasible assignments as possible. The basic version of the assignment problem can be formulated as follows: min ∑ (𝑖,𝑗)∈𝐼×𝐽 𝑐𝑖𝑗 𝑥𝑖𝑗 (2) subject to ∑ 𝑗∈𝐽 𝑥𝑖𝑗 = 1 ∀𝑖∈𝐼(3) ∑ 𝑖∈𝐼 𝑥𝑖𝑗 = 1 ∀𝑗∈𝐽(4) 𝑥𝑖𝑗 ∈ {0,1} ∀𝑖∈𝐼, 𝑗 ∈𝐽(5) Here, 𝐼is the set of open requests and 𝐽the set of available vehicles, with 𝑐𝑖𝑗 ≥0representing the cost of the matching and 𝑥𝑖𝑗 indicating whether the matching is part of the solution or not. When |𝐼|≠|𝐽|holds, the set with fewer elements is extended with fictitious elements until |𝐼|=|𝐽|is satisfied. The costs associated with matches containing one fictitious element are set to a sufficiently large value. The problem can easily be solved to optimality in a very short time, even for very large instances, due to its polynomial solution time. Depending on the specific problem under consideration, variants can be found with additional constraints for sharing applications (Alonso-Mora et al.,2017) or heterogeneous fleets (Gao et al.,2016). In our study, we compare different matching approach variants that differ in the following characteristics: •Cost calculation: The costs 𝑐𝑖𝑗 of a matching (𝑖, 𝑗)are either the travel time of the vehicle 𝑗to the pickup location of request 𝑖or the total waiting time of the customer once the vehicle arrives at the respective pickup location. Therefore, the second version also includes the time the customer is already waiting. In cases where fairness towards customers is not a concern, two additional cost calculations could be used. If not all requests can be served, the number of served requests could be increased by prioritizing shorter requests since they require fewer resources. This could be achieved by using the distances or travel times for picking up and serving the customers while ensuring the maximum number of matches. A contrary idea is to maximize the total reward gained from the matching. Since longer requests have a larger total reward, they would be preferred in this setting. To that end, the costs 𝑐𝑖𝑗 of the matching (𝑖, 𝑗)are set to the negative reward 𝑟𝑖of request 𝑖plus the costs for the driving distance of vehicle 𝑗to reach the respective pickup location 𝑝𝑖. Please note that the objective function of the matching problem is always the sum of the costs of all selected matches. •Assignment interval 𝛿𝑀:Depending on the setting, the assignment interval 𝛿𝑀will have a significant impact on the strategy’s quality. Generally, longer intervals will lead to more possible combinations and, therefore, a more efficient solution. However, longer intervals also increase the notification time as well as the waiting time of the customers. When vehicles are already done serving the previous request, they will wait until the next matching happens instead of using this time to already travel to the pickup location. Therefore, the benefit of longer matching intervals in terms of travel time reduction per request has to be larger than the increase in time between two matching epochs. Furthermore, 𝛿𝑀should never be greater than the maximum notification time 𝑇𝑁, as we must ensure that every request is considered at least once in a matching epoch. Requests that did not receive an assignment in one matching epoch, while the next matching epoch would be after 𝑇𝑁, are rejected prematurely. •FCFS integration: In undersupply scenarios with more open requests than available vehicles, some of the requests will not receive an assignment. To increase fairness, Hyland and Mahmassani (2018) modify the purely cost-based matching approach by giving priority to earlier requests. Let us assume we have 𝑛 available vehicles but 𝑛+𝑐(with 𝑐 > 0) open requests. In this case, only the oldest 𝑛open requests are considered in the matching, resulting in an 𝑛×𝑛cost matrix, while the newest 𝑐requests are ignored in this decision epoch. By that, it can be guaranteed that no customer will be matched later than another one that requested service later. We consider this optional variation only in settings without a maximum waiting time restriction, as we have to ensure that all 𝑛requests will actually be matched. Although not used in our study, we want to point out the potential benefit of allowing voluntary rejections. In our paper, as well as most other articles in the literature, rejecting a customer is only allowed when a feasible assignment is not possible in time. However, each request has an individual explicit and implicit reward structure. Not only are the distances to the requests as well as the serving distances different, but also the destinations. A request with a drop-off location in an area of high demand is much more valuable than a request with a drop-off location in a remote area since the serving vehicle is much more likely to quickly receive a follow-up job. Therefore, it could be profitable (although unfair) to voluntarily reject servable requests to prevent resource commitment and wait for more valuable requests. This subproblem of voluntarily rejecting some requests could be considered a variant of the dynamic and stochastic knapsack problem (Kleywegt and Papastavrou,1998). Studies like (Ulmer et al.,2017) have already shown the potential benefits of voluntary rejections in dynamic vehicle routing problems. 5. Repositioning strategies The spare time of vehicles between serving two requests can be used to relocate them to spots where they are needed the most in order to balance supply and demand. This is especially important when the demand follows certain spatial patterns, like an increased number of trips from outer areas to the center in the morning hours and the other way around in the evening. Here, idling vehicles should take trips in the opposite direction to ensure the availability of vehicles where they are needed. In this section, we present the strategies used in our study to reposition vehicles to available parking lots when they do not serve EURO Journal on Transportation and Logistics 12 (2023) 100109 6 C. Ackermann and J. Rieck customer requests. In Section 5.1, we present the used strategies that were taken from the literature. In Section 5.2, we identify conceptual weaknesses of the benchmark approaches and introduce our own repositioning approach—originally designed for the DIMACS Implementation Challenge—which addresses these weaknesses by explicitly considering dynamically created, driving time-related, overlapping zones around the available parking lots. 5.1. Benchmark strategies In what follows, we describe selected benchmark strategies from the literature in more detail. Please note that most of these strategies had to be slightly adapted to work in settings where repositioning jobs have to end in pre-defined parking lots. Nearest parking lot. The first benchmark strategy is only used to create a feasible solution. This nearest parking lot strategy sends a vehicle that is currently in state null and has not yet received a request assignment to the parking lot closest to its current position, where it will stay idling until it receives a new request to serve. Therefore, no explicit supply–demand-balancing is done. This strategy would represent the no repositioning strategy in settings without fixed parking lots. While this is the simplest strategy tested in our study, we want to point out that there are cases in which the even simpler random parking lot strategy could actually lead to better results. While the nearest strategy will result in lower repositioning costs than the random strategy, where one of the lots is selected at random, there are two scenarios in which the random strategy could lead to more requests served. Keeping the vehicles as close as possible to the dropoff location of their last served request leads to a distribution of idling vehicles similar to the distribution of drop-off locations. However, to optimally serve the customer requests, the idling vehicles’ distribution should rather match the distribution of the pickup locations of future requests instead of the drop-off locations. As previously mentioned, in some realistic scenarios, very asymmetric travel patterns can occur with more people requesting a trip from 𝐴to 𝐵than from 𝐵to 𝐴, leading to significantly different distributions of pickup and drop-off locations. While the random strategy cannot completely resolve this problem, it distributes the vehicles at least evenly across all parking lots, which is already a step in the right direction. The second case in which random could be better than nearest results from the fact that a random repositioning does not evenly distribute the vehicles over the service area but over the given parking lots. Therefore, more vehicles will end up in areas with a higher density of parking lots. If, as it would make sense in real-world settings, there are more parking lots available in areas of high demand, the random strategy would actually implicitly prioritize these areas. This was the case in Kullman et al. (2021) and the challenge setting (DIMACS,2022), where locations of public charging stations for electric vehicles in Manhattan were used as parking lots. This led to the random strategy drastically outperforming the nearest strategy (Ackermann and Rieck,2022). These two cases should be kept in mind when comparing repositioning strategies against the nearest strategy as the only benchmark, especially for completely machine learning-based approaches, which usually start their training progress with the random strategy. In the remainder of this section, we present additional approaches that reposition the whole (non-serving) fleet in regular intervals of 𝛿𝑅. Since these approaches create a plan for the whole fleet, they are not used whenever a vehicle enters the null state. Here, unless otherwise stated, the vehicle is provisionally sent to its nearest parking lot until the next repositioning epoch occurs. Match missed requests. The match missed requests strategy is a slightly modified version of the one proposed by Alonso-Mora et al. (2017) for a ride-sharing application. In their study, it is possible that after an assignment epoch, there are still unmatched open requests and unassigned available vehicles. This happens due to matching constraints like maximum waiting time. Under some specific assumptions derived from their practical application, it is reasonable to still match the remaining vehicles and requests and send the vehicles to the locations of their respective matched requests. If, e.g., a customer decides to wait slightly longer than the maximum waiting time defined by the system, service could still be provided. Although we do not allow such a scenario in our setting, their approach can still be used in a modified way. Over the course of the day, every rejected request is logged. Rejecting a request happens whenever there are not enough vehicles in the vicinity of the open requests. Therefore, the locations of the rejected requests indicate areas with undersupply. Provided that the demand structure is not changing too quickly, this undersupply can be decreased in the short-term future by sending the available vehicles into these areas. The pickup location of each rejected request that occurred since the last repositioning epoch is mapped to its nearest parking lot, and the solution of a cost-minimum matching problem determines which vehicle is sent to which parking lot. In settings without a maximum waiting time, reducing the average waiting time is more often the aim of the assignment and repositioning strategies, as usually all requests can be served. For these settings, the strategy can be adapted by not only considering rejected requests but also requests that were served with a significantly higher waiting time because this would indicate an undersupply as well. The main disadvantage of this strategy is that it is purely reactive and not proactive. Since no explicit demand estimation is integrated, an imbalance in the fleet distribution has to happen and has to be noticeable in the results before the strategy can react to it and try to prevent it in the future. Iterative zone balance. The iterative zone balance strategy, introduced by Fagnant and Kockelman (2014), overcomes this issue by utilizing a short-term demand estimation for different parts (‘‘zones’’) of the service area. Here, for each zone 𝑘∈, a balance value 𝑏𝑘is calculated by taking the difference between the relative supply and the relative demand: 𝑏𝑘=supply𝑘 ∑𝑘∈supply −demand𝑘 ∑𝑘∈demand (6) Ideally, all zones are perfectly balanced (𝑏𝑘= 0,∀𝑘∈). In case of unbalanced zones, vehicles should be shifted between zones to reduce the imbalances. Positive values of 𝑏𝑘indicate a surplus of supply while negative values indicate a shortage of supply. The authors propose an iterative procedure, starting with the most unbalanced zone (largest |𝑏𝑘|), which pulls one vehicle from a neighboring zone (if 𝑏𝑘<0) or pushes one vehicle to a neighboring zone (if 𝑏𝑘>0). Which neighboring zone 𝑙∈𝑁(𝑘)is selected depends on their respective balances. If the neighboring zone should provide a vehicle, the zone with the largest 𝑏𝑙is selected, while for accepting an additional vehicle, the zone with the smallest 𝑏𝑙is chosen. The iterative procedure stops when all zone balances are within a certain threshold (|𝑏𝑘|≤𝛽, ∀𝑘∈). In our study, we use zones of size 1 × 1 km and edge-based neighborhoods, defining zones as neighbors only when they share an edge. In case there are multiple vehicles available for switching zones, the vehicle closest to the center of the destination zone is selected. For the destination, the parking lot in the destination zone closest to the selected vehicle is chosen. This follows the original idea by Fagnant and Kockelman (2014) to let vehicles just cross the zone border. In case there are no parking lots within the destination zone, the parking lot closest to the zone’s center is picked. While this repositioning strategy does reposition the fleet in an anticipatory fashion, it restricts the movements to a rather local area. Global matching. A more global and simultaneously intuitive repositioning approach is to distribute the fleet in the same way the demand is distributed without restricting vehicle movements to only neighboring zones. Based on the relative demand per zone and the fleet size, an optimal number of vehicles per zone can be calculated and the vehicle movements are determined by solving a cost-minimum matching problem. A similar idea is used, e.g., in Spieser et al. (2016). The downside of this approach is that the fleet is always repositioned to EURO Journal on Transportation and Logistics 12 (2023) 100109 7 C. Ackermann and J. Rieck match the demand distribution, even though a slightly imbalanced fleet would also be able to serve all requests in times of low demand. This unnecessarily increases the repositioning costs. An improved version to overcome this issue can be found, e.g., in De Souza et al. (2020) and Wallar et al. (2018). They use the same idea, but stop the repositioning when the absolute supply per zone equals the absolute expected demand. In De Souza et al. (2020), a matching problem is built to ensure that the actual supply in each zone is at least as big as a specified minimum supply while minimizing the travel time for repositioning. The minimum supply is calculated based on the expected demand for each zone. To ensure feasibility in times of undersupply, they scale the minimum supply linearly down from the expected demand until a feasible solution for the problem can be found. We implemented a slightly different version of this global matchingbased strategy. In a first step, the supply per zone is determined. Here, all vehicles that are either idling in this zone or have the destination of their last scheduled job in this zone are counted. Additionally, we keep track of the vehicles that can be repositioned in this epoch. This excludes the vehicles currently serving customer requests. The number of serving vehicles ending their jobs in the respective zone simultaneously forms the absolute minimum supply for that zone because these vehicles cannot be prevented from becoming available in that zone in the short-term future. This minimum supply is used as the initial solution. Since we have to distribute the existing supply in a ‘‘fair’’, proportional way among the zones with different demand, we make use of the Jefferson/D’Hondt method (Gallagher,1991), originally proposed by former US president Thomas Jefferson to distribute seats in the parliament to the different parties or states proportionally to their respective election results or population size. A quotient is calculated for each zone (‘‘party’’) by dividing the expected demand (‘‘votes’’) by the number of vehicles (‘‘seats’’) already assigned to this zone plus 1. The zone with the highest quotient will receive the next repositionable vehicle. After that, this zone’s quotient is updated, and the process repeats until all vehicles are assigned. An optional addition is to prevent more repositioning than necessary. For that, we set the quotient of a zone to 0, once the number of vehicles matches the expected demand. In case all zones are saturated, the procedure stops early. We refer to this addition as the restricted global matching strategy. After finishing this step, the current number of vehicles assigned to each zone (already including the absolute minimum supply) is called the target supply. By comparing the current supply with the target supply per zone, the surplus/shortage of vehicles per zone can be determined. The remaining repositioning problem can be formulated as a standard transportation problem. Zones with a surplus of vehicles form the supply nodes; zones with a shortage of vehicles form the demand nodes. In case the total supply is bigger than the target supply (i.e., in total there are more vehicles available than needed), a fictitious demand node is added. The costs for the transport are the distances between the zone centers. The costs associated with the edges connected to the artificial demand node are 0. Afterwards, for each zone serving as a real supply node, it has to be determined which of the vehicles are shifted to which of the designated demand nodes. This is done by solving a cost-minimum linear assignment problem with the available vehicles in the supply zone and the parking lots closest to the center of the associated demand zones. If more than one vehicle should be sent to the same demand zone, the respective parking lot is cloned as often as necessary in the assignment problem. We want to emphasize the importance of the length of the timeframe the demand estimation is done for. This plays a crucial role for the quality of the version where no more repositioning than necessary should be done. Is the timeframe too long, too many requests are estimated to arrive, and the demand might exceed the supply. In this case, no zone will be saturated and the benefit of the restricted repositioning vanishes. On the other hand, a timeframe that is too short will lead to even worse solutions since fewer requests are estimated and the restricted repositioning strategy will stop sending vehicles to demand zones too early, potentially resulting in unserved requests. From our point of view, this parameter should be set to the ‘‘cycle length’’ of a vehicle, which represents the average time between two requests served by the same vehicle. Results from preliminary experiments to find the optimal value for the timeframe support this assumption. 5.2. Proposed strategy The aforementioned demand estimation-based strategies share two big issues: •The supply–demand-balancing is done on the basis of more or less arbitrarily chosen zones, which are not directly connected to the objective function. Due to the simplified modeling, it is implicitly assumed that only vehicles within a certain zone can serve the requests that arise in that zone. •The approaches do not explicitly consider the locations of the parking lots. This can cause problems in settings where parking lots are, at least in some areas, only sparsely available. In this section, we present our own repositioning approach that overcomes both issues. The main idea is to create zones around each parking lot (referred to as parking lot zones), covering the area that can be reached by the vehicles in these parking lots within a specific timeframe. Later, we will also refer to this area as the range of a parking lot, a vehicle, or a request. By setting this timeframe to the maximum waiting time 𝑇𝑊and assuming that the incoming requests follow a Poisson distribution, we can calculate for each lot the probability of at least one missed request due to undersupply in this area. In the repositioning process, these probabilities can be minimized to maximize the number of served requests. We will refer to this strategy as the undersupply probability strategy. Since this strategy creates (overlapping) zones around each existing parking lot, we consider meaningful, problemrelated zones that explicitly integrate the information about the parking lot locations as well as the available time to respond to a request. By doing so, contrary to the other approaches, we also overcome potential discretization issues during zone creation. Preliminaries. The key element of the strategy is to determine how important or valuable an additional vehicle for a given parking lot would be. For that, we first determine the expected short-term future demand 𝑑in the respective parking lot zone as well as the supply 𝑠in this zone. Then, an undersupply probability for that lot zone is computed using a Poisson distribution: 𝑝undersupply = ∞ ∑ 𝑘=𝑠+1 𝑑𝑘𝑒−𝑑 𝑘!(7) Formula (7) gives the probability of more incoming requests in the short-term future than available vehicles in this lot zone. The higher this probability, the better it is to send an additional vehicle to this parking lot. Please note that for big instances, a slightly modified version of this formula has to be used because 𝑘!can grow beyond the limits of typical datatypes. The modified formula as well as its derivation can be found in Appendix A. This undersupply probability idea makes it possible to explicitly balance higher repositioning costs and increased rewards due to a higher service rate. In settings where, instead of the number of served requests, the overall profit of the system is the main objective (e.g., Kullman et al.,2021), it should be calculated whether repositioning orders are worth the additional travel costs. For that, we can estimate the expected reward per request in the lot zone under consideration based on historical data. Since the reward depends on the distance traveled, average requests in the city center might have different expected rewards than requests in outer areas. Multiplying the expected reward with the undersupply probability leads to an expected missed reward. This expected missed reward could be collected when an additional vehicle is sent to this parking lot. Therefore, a repositioning order is expected to be profitable if the travel costs for going to that parking lot are lower than the expected missed EURO Journal on Transportation and Logistics 12 (2023) 100109 8 C. Ackermann and J. Rieck reward. In settings where the repositioning costs can be ignored, this trade-off can simply be removed by ignoring the restriction to only perform the repositioning if the expected profit is positive. Handling overlapping zones. Since each lot has its own lot zone, these zones might overlap. While this is conceptually a benefit of this approach, it also increases computational complexity when calculating the expected demand and the current supply. All vehicles in a specific lot zone are considered the supply of this lot zone. However, not all of the vehicles are actually able to serve all requests arising in this zone. This is only true for those vehicles located in the parking lot in the center of the lot zone. Additionally, vehicles towards the border of a lot zone might be selected to serve a request that arose within their range but outside of the respective lot zone. This would reduce the supply without reducing the demand of this lot zone. Similarly, requests towards the border of a lot zone might be served by vehicles outside of the respective lot zone. Therefore, requests as well as vehicles are not necessarily counted as 1 for supply and demand but as the proportion of their individual range-zone (defined by the maximum waiting time 𝑇𝑊as well) overlapping with the lot zone under consideration. Details for calculating the overlapping area are given in Appendix B. On the demand side, an additional special case has to be taken into account: Requests in areas with few parking lots might have a total overlapping proportion of less than 1. Let us consider the simplest case with one request at the border of the service area and just one parking lot in proximity. The overlapping proportion might be, e.g., 20%. For the lot zone, this request would count as an additional demand of 0.2 because it is assumed that the vehicles from other lot zones could serve this request as well. But for this to be true, it would be necessary that the whole area of this request range is part of at least one parking lot zone. If this is not the case, the demand value of this request has to be increased so that it reaches 1. Considering our example with just one parking lot in proximity: Even though the overlap is only 20%, vehicles from this zone are the only ones able to serve this request. Therefore, it has to be counted as one full request with demand value 1. In case of more than one lot zone overlapping with a request range, the overlaps are scaled linearly. Putting everything together. We use the previously introduced calculations in two different situations: •Whenever a vehicle reaches the null state and needs a parking lot assignment, the best parking lot is determined by choosing the one that leads to the maximum profit (expected missed reward minus travel costs). Since, especially in settings with high demand, long repositioning jobs are often not finished but aborted to serve a new customer request, we only consider the parking lots within a certain radius of the vehicle’s location. •In regular intervals, the whole fleet needs to be repositioned. Unfortunately, due to the overlapping of the lot zones as well as the non-linear reward function for sending vehicles to specific lots, we cannot use a simple linear matching approach. Instead, we implemented an iterative, greedy approach. In each iteration, the profit for every vehicle-lot-combination is checked for the maximum profit. The lot with the highest profit is selected. The supply for this lot, as well as for all lots in proximity, is increased and the undersupply probabilities are updated. Lots can be selected multiple times. After each iteration, a cost-minimum matching problem is solved to determine which of the available vehicles will be repositioned to which lot. The unselected vehicles are then available for the profit calculation in the next iteration. Once all vehicles are repositioned or there are no more profitable repositioning orders possible, the process is stopped and the solution is executed. Please note that in both situations, vehicles that are available for repositioning are removed from the supply before the start of the calculations. Because of that, it is not necessary to consider the reduction in supply in a specific area when vehicles are sent to other areas. For the demand estimation timeframe, we use the same approach as described in the previous section. 6. Computational study & discussion The aim of this computational study is to analyze and compare the quality of the presented strategies and design decisions depending on varying problem characteristics. First, we describe in Section 6.1 the instances and configurations used in the study. Then, we perform the analysis of the assignment strategies in Section 6.2 and of the repositioning strategies in Section 6.3. 6.1. Instances and configuration For the instance generation and the execution of the implemented strategies, we use the pyhailing framework (Kullman,2021) with custom modifications to allow different problem settings. The general setting is close to the one used in Kullman et al. (2021). The considered service area is the district of Manhattan in New York City. Therefore, we use Manhattan distances instead of Euclidean distances. However, since the problem and our approach are time-based and not distancebased, the results should be generalizable to other distance metrics like Euclidean distances, as long as the corresponding formula for handling zone overlap (see Section 5.2 and Appendix B) is used. Requests are generated based on the real-world New York taxi cab dataset. For that, Manhattan is divided into 61 smaller neighborhoods, and for each 15minute time interval, the number of trips per origin–destination zone pair from the real-world dataset is counted. This data is subsequently used to generate new request arrival times (in the respective 15-minute interval) as well as new origin and destination locations (in the respective zone), as in Kullman et al. (2021) and Kullman (2021). For the driving time between origin and destination, we use the average speed of the trips from the dataset for this origin–destination combination in this time interval. By doing so, we achieve a very realistic dataset for the experiments. Fig. 1 shows the temporal distribution of requests over the course of the day. For every hour, the percentage of the daily requests arriving in this hour is depicted. As in Kullman et al. (2021), the planning horizon starts and ends at 2 a.m. to have the cut in times of low demand. We generated 𝐿= 300 uniformly distributed parking lots for the area of roughly 59 km2, leading to an average distance of less than 300 m between any given point and its nearest parking lot. Since the main goal of this computational study is to analyze the quality of the proposed strategies dependent on the given setting, key influence factors need to be varied over the course of the experiments. We identified the following factors for which different values are used in the study: •Fleet size, in relation to the service area •Demand-supply-ratio, as indication for overand undersupply •Maximum allowed customer waiting time before pickup or rejection •Vehicle availability (all or only non-serving vehicles) We consider three different fleet sizes, with 𝑉∈ {30,100,300}. The number of requests depends on the fleet size. We define the demandsupply-ratio (𝐷𝑆𝑅) as the number of requests per day per vehicle. We use 𝐷𝑆𝑅 ∈ {40,70,100}, representing fleets with low utilization, high utilization, and overloaded fleets. For the maximum waiting time 𝑇𝑊, we use three different settings: short waiting time, long waiting time, and no waiting time. Because the waiting time for the customers usually varies depending on the fleet utilization, we define different values for 𝑇𝑊for different 𝐷𝑆𝑅𝑠. To find reasonable values, we took the 50% and 90% quantiles of the customer waiting time for the 𝑉= 100 fleet without the maximum waiting time constraint, resulting in one very restrictive waiting time 𝑇𝑊1and one less restrictive waiting time 𝑇𝑊2. For 𝐷𝑆𝑅 = 40, we use 𝑇𝑊1= 103 s and 𝑇𝑊2= 218 s, and for 𝐷𝑆𝑅 ∈ {70,100}, we use 𝑇𝑊1= 271 s and 𝑇𝑊2= 1029 s. For each problem configuration under consideration, the framework simulates five different work days. When comparing different strategies EURO Journal on Transportation and Logistics 12 (2023) 100109 15 C. Ackermann and J. Rieck Fig. 10. Example of the spatial Perlin noise factor for artificial demand estimation error. Appendix B. Overlapping area calculations To handle the supply and demand calculations precisely, the overlaps of different zones have to be calculated. The radius of a zone is equivalent to the maximum waiting time 𝑇𝑊of the requests, so that all requests arising in a zone can be served by vehicles placed in the parking lot in the center of the zone within the time limit. Similar zones (with the same radius) can also be created around a vehicle or a request. In case of a request-based zone, a vehicle would have to be inside this zone to be able to reach this request in time. The shape of these zones depends on the used distance metric. For Euclidean distances, the zones form a circle with a radius of 𝑇𝑊(in terms of driving time). For Manhattan distances, however, the zones form a square standing on its corner, with the square’s diagonals having the length of 2⋅𝑇𝑊and the square’s side length being √2⋅𝑇𝑊. Because the overlap calculation differs completely depending on the used distance metric, we show the formula for both cases. B.1. Euclidean distances Fig. 7 shows the overlap of two zones for Euclidean distances. The overlapping area consists of two equally sized circular segments. Let 𝑑 be the distance between the center of both zones and ℎ=𝑇𝑊−𝑑 2be the segment’s height. Based on the general formula for the area of a circular segment (Weisstein,2002), the area of each of the segments can be calculated as follows: 𝐴segment =𝑇𝑊 2cos−1 (1 − ℎ 𝑇𝑊)− (𝑇𝑊−ℎ)√2𝑇𝑊ℎ−ℎ2(8) By doubling this value to get the full overlap area and putting this into relation to the total area of the zone, we get the overlap proportion by the following formula: overlap = 2𝐴segment 𝜋 𝑇𝑊2(9) B.2. Manhattan distances Fig. 8 shows the overlap of two zones for Manhattan distances. Here, the overlap always forms a rectangle. Because this has an angle of 45◦to the coordinate axes (similarly to the square zones themselves), we propose to rotate the coordinate system by 45◦to simplify the calculations. Fig. 9 shows the rotated version. The area of the rectangle can be calculated using the following formula: 𝐴rect =(√2𝑇𝑊−𝛥𝑥)⋅(√2𝑇𝑊−𝛥𝑦)(10) The new shift 𝛥in 𝑥and 𝑦direction after rotating the coordinate system by 45◦can be calculated based on the original shift 𝛥′as follows: 𝛥𝑥 =√2 2|||𝛥′𝑥2−𝛥′𝑦2|||(11) 𝛥𝑦 =√2 2|||𝛥′𝑥2+𝛥′𝑦2|||(12) Appendix C. Demand estimation error generation To test the influence of demand estimation errors, some noise has to be added to the exact demand estimation usually used in the repositioning approaches. This demand estimation is done by taking the real future demand sampled by the framework at the beginning of each planning horizon, mapping all requests to zones, and then counting the requests per zone for all 30 min intervals of the planning horizon. The zones correspond to the zones used in the respective repositioning approaches. Please note that these zones differ between the benchmark approaches and our proposed approach. Additionally, the zones in our approach are overlapping. Adding random, e.g., normally distributed noise to these zone values or multiplying them with a random factor does not work. First, using independent noise values for partially overlapping zones would not make sense since two very strongly overlapping zones should have roughly the same demand estimation. Second, because the zones have different sizes in different strategies, the strategies would be affected by the noise differently. To demonstrate that, let us consider a specific part of the service area. If this part is divided into several smaller zones, the random noise generated for each zone would be sometimes positive, sometimes negative. But the more zones there are, the closer the average noise would be to zero. Therefore, the total demand estimation for this part of the service area would not be greatly affected. If this part, however, only consists of one big zone, the noise for the whole part would be as big as the noise for each individual zone. In order to overcome this issue, we use the Perlin noise (Perlin, 1985). Here, a grid is used, with all points on intersections having a noise value of zero. A random gradient is generated for each intersection. All points between the grid intersections receive a noise value interpolated based on the gradients of the surrounding grid intersections. By that, a pseudo-random noise is generated where points close to each other have similar values. The noise can be configured regarding the amplitude (by scaling the interpolated values) as well as regarding the frequency (by changing the size of each grid cell). Using this approach, we create a noise factor for each estimated demand value depending on the spatial location as well as the current time. The average unsigned noise corresponds to the configured 10%, 25%, and 50%, while the maximum values are roughly three times as large. The noise is limited to ±100%.Fig. 10 depicts an example of the noise factor for one specific point in time for the whole service area. EURO Journal on Transportation and Logistics 12 (2023) 100109 16 C. Ackermann and J. Rieck References Ackermann, C., Rieck, J., 2022. A novel repositioning strategy for ride-hailing problems. In: 12th DIMACS Implementation Challenge: Vehicle Routing. http://dimacs. rutgers.edu/events/details?eID=2067. Al-Kanj, L., Nascimento, J., Powell, W.B., 2020. Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles. European J. Oper. Res. 284 (3), 1088–1106. Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., Rus, D., 2017. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc. Natl. Acad. Sci. 114 (3), 462–467. Bailey, W.A., Clark, T.D., 1992. Taxi management and route control: A systems study and simulation experiment. In: Proceedings of the 24th Conference on Winter Simulation. WSC ’92, pp. 1217–1222. Bischoff, J., Maciejewski, M., 2016. Simulation of city-wide replacement of private cars with autonomous taxis in Berlin. Procedia Comput. Sci. 83, 237–244. Braverman, A., Dai, J.G., Liu, X., Ying, L., 2019. Empty-car routing in ridesharing systems. Oper. Res. 67 (5), 1437–1452. Dandl, F., Hyland, M., Bogenberger, K., Mahmassani, H.S., 2019. Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets. Transportation 46, 1975–1996. De Souza, F., Gurumurthy, K.M., Auld, J., Kockelman, K.M., 2020. An optimizationbased strategy for shared autonomous vehicle fleet repositioning. In: Proceedings of the 6th International Conference on Vehicle Technology and Intelligent Transport Systems – VEHITS. pp. 370–376. DIMACS, 2022. DIMACS Center for Discrete Mathematics and Theoretical Computer Science, http://dimacs.rutgers.edu/programs/challenge/vrp/hailing. Fagnant, D.J., Kockelman, K.M., 2014. The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transp. Res. C 40, 1–13. Gallagher, M., 1991. Proportionality, disproportionality and electoral systems. Elect. Stud. 10 (1), 33–51. Gao, G., Xiao, M., Zhao, Z., 2016. Optimal multi-taxi dispatch for mobile taxi-hailing systems. In: 2016 45th International Conference on Parallel Processing. ICPP, pp. 294–303. Geng, X., Li, Y., Wang, L., Zhang, L., Yang, Q., Ye, J., Liu, Y., 2019. Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33. pp. 3656–3663. Guo, X., Caros, N.S., Zhao, J., 2021. Robust matching-integrated vehicle rebalancing in ride-hailing system with uncertain demand. Transp. Res. B 150, 161–189. Ho, S.C., Szeto, W.Y., Kuo, Y.-H., Leung, J.M., Petering, M., Tou, T.W., 2018. A survey of dial-a-ride problems: Literature review and recent developments. Transp. Res. B 111, 395–421. Hyland, M., Mahmassani, H.S., 2018. Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AV to immediate traveler demand requests. Transp. Res. C 92, 278–297. Jiao, Y., Tang, X., Qin, Z., Li, S., Zhang, F., Zhu, H., Ye, J., 2021. Real-world ridehailing vehicle repositioning using deep reinforcement learning. https://arxiv.org/ abs/2103.04555. Jin, G., Cui, Y., Zeng, L., Tang, H., Feng, Y., Huang, J., 2020. Urban ride-hailing demand prediction with multiple spatio-temporal information fusion network. Transp. Res. C 117, 102665. Kleywegt, A.J., Papastavrou, J.D., 1998. The dynamic and stochastic knapsack problem. Oper. Res. 46 (1), 17–35. Kullman, N.D., 2021. The pyhailing framework. https://pypi.org/project/pyhailing. Kullman, N.D., Cousineau, M., Goodson, J.C., Mendoza, J.E., 2021. Dynamic ride-hailing with electric vehicles. Transp. Sci. 56 (3), 775–794. Lu, J.-L., Yeh, M.-Y., Hsu, Y.-C., Yang, S.-N., Gan, C.-H., Chen, M.-S., 2012. Operating electric taxi fleets: A new dispatching strategy with charging plans. In: 2012 IEEE International Electric Vehicle Conference. IEVC, pp. 1–8. Lyu, G., Cheung, W.-C., Teo, C.P., Wang, H., 2019. Multi-objective online ride-matching. Available at SSRN: https://doi.org/10.2139/ssrn.3356823. Maciejewski, M., Bischoff, J., Nagel, K., 2016. An assignment-based approach to efficient real-time city-scale taxi dispatching. IEEE Intell. Syst. 31 (1), 68–77. Maciejewski, M., Nagel, K., 2013. A microscopic simulation approach for optimization of taxi services. In: Proceedings of the 3rd International Conference on Models and Technologies for Intelligent Transportation Systems. pp. 1–10. Miao, F., Lin, S., Munir, S., Stankovic, J.A., Huang, H., Zhang, D., He, T., Pappas, G.J., 2016. Taxi dispatch with real-time sensing data in metropolitan areas – a receding horizon control approach. IEEE Trans. Autom. Sci. Eng. 13 (2), 463–478. Perlin, K., 1985. An image synthesizer. ACM SIGGRAPH Comput. Graph. 19 (3), 287–296. Qin, G., Luo, Q., Yin, Y., Sun, J., Ye, J., 2021. Optimizing matching time intervals for ride-hailing services using reinforcement learning. Transp. Res. C 129, 103239. Qin, Z., Tang, X., Jiao, Y., Zhang, F., Xu, Z., Zhu, H., Ye, J., 2020. Ride-hailing order dispatching at DiDi via reinforcement learning. Informs J. Appl. Anal. 50 (5), 272–286. Shi, J., Gao, Y., Wang, W., Yu, N., Ioannou, P.A., 2020. Operating electric vehicle fleet for ride-hailing services with reinforcement learning. IEEE Trans. Intell. Transp. Syst. 21 (11), 4822–4834. Shi, D., Tong, Y., Zhou, Z., Song, B., Lv, W., Yang, Q., 2021. Learning to assign: Towards fair task assignment in large-scale ride hailing. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pp. 3549–3557. Spieser, K., Samaranayake, S., Gruel, W., Frazzoli, E., 2016. Shared-vehicle mobilityon-demand systems: A fleet operator’s guide to rebalancing empty vehicles. In: Transportation Research Board 95th Annual Meeting. Ulmer, M.W., Mattfeld, D.C., Köster, F., 2017. Budgeting time for dynamic vehicle routing with stochastic customer requests. Transp. Sci. 52 (1), 20–37. Wallar, A., Zee, M.V.D., Alonso-Mora, J., Rus, D., 2018. Vehicle rebalancing for mobility-on-demand systems with ride-sharing. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4539–4546. Weisstein, E.W., 2002. Circular segment, MathWorld – A Wolfram Web Resource, https://mathworld.wolfram.com/CircularSegment.html. Xu, Z., Li, Z., Guan, Q., Zhang, D., Li, Q., Nan, J., Liu, C., Bian, W., Ye, J., 2018. Largescale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD ’18, pp. 905–913. Zhang, R., Pavone, M., 2016. Control of robotic mobility-on demand systems: A queueing-theoretical perspective. Int. J. Robot. Res. 35 (1–3), 186–203.