An Online Mechanism for Ridesharing in Autonomous Mobility-on-Demand Systems

1 Introduction

The rise of private car ownership and use has brought many social and environmental challenges, including traffic congestion, increased greenhouse gas emissions [Poudenx, 2008]. One possible solution to address the challenges is to promote ridesharing [Furuhata et al., 2013; Caulfield, 2009; Levofsky and Greenberg, 2001] among passengers by providing incentives (e.g., lower fares for the shared trips than individual trips) to them. In such a scenario, a limited number (depending on the seat capacity of the vehicle) of passengers who have similar itineraries share a ride and split the fares. Ridesharing (as shown in Figure 1) increases the occupancy of vehicles during traveling, making it possible to transport more passengers with fewer vehicles running on the roads.

Rideshare experiences can be significantly improved as autonomous vehicle technologies mature. This is because AMoD systems have the potential to provide safe, convenient, and affordable mobility solutions for passengers, Jacob W. Crandall Masdar Institute of Science and Technology Abu Dhabi, PO Box 54224, UAE jcrandall@masdar.ac.ae while reducing greenhouse emissions and private car ownership [Mitchell, 2010; Chong et al., 2013; Shen and Lopes, 2015; Spieser et al., 2014]. Unlike traditional mobility-ondemand systems (e.g., taxis, shuttles), an AMoD system is equipped with a fleet of self-driving, electric cars with no drivers needed. This enables seamless cooperation between the information center and the autonomous vehicles (AVs).

Several mechanisms [Kleiner et al., 2011; Kamar and Horvitz, 2009; Cheng et al., 2014; Zhao et al., 2015] have been introduced to promote ridesharing in traditional mobility-on-demand systems. These mechanisms require passengers to directly reveal the valuation of the rides. While interesting and insightful from a theoretical perspective, they may not work well in practice since they require passengers to reveal the exact value of their rides, which could be problematic [Naor et al., 1999; Larson and Sandholm, 2001; Babaioff et al., 2015]. In this case, posted-price mechanisms are more appealing because passengers only need to accept offers with value greater than the posted price, without revealing their actual valuations to service providers.

Some of the mechanisms require additional constraints (e.g., dual ride shares only, linear in commitment) to satisfy desirable properties such as strategy-proofness and budgetbalance [Kleiner et al., 2011; Zhao et al., 2015]. Besides, many mechanisms assume that passengers are only motivated by monetary incentives (i.e., lower fares) [Kleiner et al., 2011; Kamar and Horvitz, 2009; Cheng et al., 2014; Zhao et al., 2015]. They neglect the fact that non-monetary factors such as time, comfortability and privacy, are also important, or even critical when people make decisions on whether to use the service or not.

Another drawback of these mechanisms is that they process the ride requests in batch and do not work in online environment [Kleiner et al., 2011; Kamar and Horvitz, 2009; Cheng et al., 2014; Zhao et al., 2015]. In AMoD systems, service providers are committed to offering an immediate response to each request sent by passengers via a smart device. Besides, they assume that the demand is fixed without consideration of the dynamic nature of demand responsive systems.

A desirable mechanism is expected to be truthful and online [Parkes and Singh, 2004; Gallien, 2006; Nisan et al., 2007]. It should be able to provide a fare quote immediately after the submission of a request. It needs to consider major non-monetary factors (e.g., latest departure time) as well as the dynamic nature of demand-driven systems. However, such a mechanism is yet to be designed. To bridge the gap and transcend conventional transport models like private car ownership, we introduce a truthful online mechanism called IORS for AMoD systems. We implement a simple, abstracted, yet powerful simulator that enables efficient modeling of ridesharing in AMoD systems. Numerical results show that the IORS mechanism outperforms the cutting-edge auction-based mechanism for last-mile mobility systems [Cheng et al., 2014] substantially. It has a very close performance compared to the optimal solution, but requires a shorter time to compute and requires no future knowledge about the demand.

2 Ridesharing in AMoD Systems

An AMoD system (see Figure 2) can be viewed as a multiagent system consisting of an information center, a fleet of autonomous vehicle agents, and self-interested passengers who dynamically enter and exit the system. The working principle of the AMoD system is straightforward: when a passenger needs a ride, she sends the ride request to the information center using a smart device. This initiates the demand for mobility. The information center next computes a fare quote and sends it to the passenger. If the passenger accepts the fare estimate, the information center then calculates an assignment. As long as a plan has been calculated, it will be sent to both the AV assigned and the passenger who has just submitted the request. Both the passenger and the AV are committed to executing it. Otherwise, the passenger will be subject to penalties.

3 The Online Mechanism

3.1 Preliminaries

In our work we consider discrete time T = ¶0↪ 1↪ 2↪ ▷▷▷♦, with passengers that arrive and depart over time. Without loss of generality, we assume that the AVs never exit the AMoD system. The information center has full knowledge of the AVs at each time. However, passengers' demand information is private and hidden from the center. The mechanism designer should incentivize passengers to truthfully reveal their demand for better system-wide optimization.

In our model we make a realistic assumption that the passengers are impatient [Horn, 2002]. They will leave the AMoD system and switch to other alternatives if the pickup time is later than their latest departure time.

Let I t denote a group of passengers who have mobility demand at time t 2 T . At each time, a passenger i 2 I t submits a request rt i 2 Rt to the information center. The request rt i can be represented as a tuple (oi↪ di↪ ti↪ ¯ ti), where oi, di, ti and ¯ ti are passenger i's origin, destination, arrival time and latest departure time, respectively. Here, ti = t. To quantify the transport demand, we introduce the effective demand `i, which indicates the minimum distance from passenger i's origin oi and destination di. Assuming that the effective demand is independent of request submission time, we have:

Equation 1 indicates that the effective demand of passenger i 2 I t will not change if the passenger delays its request submission from time t to time t + 1.

Once a passenger i has sent her request rt i , the system needs to provide a fare estimate qrt i to the passenger immediately, which enables the passenger to make a prompt decision on whether to accept the quote or not. It is important to note that the quote is the upper bound of the fare rather than the final payment. The passenger only accepts the service if the quote is lower than the amount that she is willing to pay. If the passenger accepts the quote and if the system is able to provide the service given the time and routing constraints, she will be serviced with an assignment provided. A final payment prt i will be calculated upon the completion of the ride. Otherwise, the request will be rejected.

In our model we make the passengers who use the ride service split the operational cost of the vehicles. This enables the AMoD system to provide service without seeking for external subsidies. The mechanism designer's goal is to minimize the cost per unit effective demand. Since the operational cost is split by all the passengers, this objective reflects the social welfare. The mechanism needs to collect truthful information about the requests from passengers. However, passengers are selfish and motivated to minimize their own cost for the rides. For instance, they may delay their request submissions, or claim a shorter waiting time to reduce their cost. Therefore, incentives should be provided to counter the manipulations. Let C t denote the total cost of the system incurred up to now from t = 0, and I 0t ✓ I t be the set of passengers been serviced at t. We have the cost per demand of the system:

Let W = 1◁W 0 , the mechanism designer's goal is equivalent to maximizing the social welfare W. Initially, the total cost is zero. That is, C 0 = 0. We assume that the total cost of the systemC t is non-decreasing. It quantifies theminimumoperational cost that the system needs to transport the passengers. Since the total cost is independent of the time and the orders of the request submissions, the following inequation holds:

If the requests are delayed from t to t + 1:

Let δrt i denote the increase on the operational cost if passenger i is serviced when she submits the request rt i at time t, the following equation always holds for every t 2 T :

Equation 5 shows that the increase on the total operational cost from time t to time t+1 always equals to the summation of the marginal cost that is incurred by the requests being served at time t + 1.

Let V denote the set of vehicles in operation and V t ✓ V be the set of vehicles that have at least one seat available at time t. Initially, we divide the vehicles into N groups (or coalitions), where N = ♣V♣. At each time, a request r 2 Rt is added into a group X t v ✓ Xt according to the mechanism policy, where Xt is the set of all groups at time t. At time t, all passengers in a group share the same fare rate (cost per unit demand). Let ⇢ denote the cost per unit demand, we have:

3.2 IORSMechanism

The IORS mechanism consists of three parts: fare estimation, pickup assignment and payment calculation. In the fare estimation process, the mechanism calculates a quote for each request. In the pickup assignment phase, the mechanism computes an optimal plan that minimizes the cost per unit demand. Finally, the mechanism provides payments immediately after successful completion of the rides.

Fare Estimation

As the passengers arrive and depart dynamically, the mechanism can only rely on the known information to compute the upper bound of the fare. The fare estimation process is described as follows (as shown in Algorithm 1): for each request rt i at time t, the mechanism first checks if a vehicle v (with vacancies) satisfies the passenger's latest departure time. If such a vehicle is found, then the mechanism compares the cost per unit demand before and after adding the request rt i into the coalition, respectively. If the cost per unit demand decreases, then the fare is calculated and stored in a set Q0 . The mechanism selects the maximum fare in the set as the quote. Otherwise, the system rejects the request. Note that the mechanism picks the highest (instead of the lowest) cost per unit demand as the upper bound of the fare estimate. This is because the mechanism needs to adjust the assignments so that the system can produce the lowest cost per unit demand in general. Besides, it is a necessary condition for individual rationality and incentive compatibility. The algorithm takes O(n3 ) time in the worst case.

Algorithm 1: The Fare Estimation Algorithm

Pickup Assignment

Let nvt denote the number of seats available in vehicle v at time t. Each vehicle can only service at most Nv passengers, where N is the seat capacity of the vehicle. That is, 0  nvt  Nv. When there are multiple requests that decrease the cost per unit demand of a coalition, the coalition selects the one that produces the lowest cost per unit demand. If there is a tie, the mechanism breaks it by choosing the one with the highest demand at random. The pickup assignment procedure is shown in Algorithm 2. The mechanism selects the nt requests that produces the lowest cost per unit demand, where nt is determined as following: nt = min¶nvt ↪ nRt♦, where nRt is the number of requests submitted. The time complexity of Algorithm 2 is O(n2 log n).

Payment Calculation

When a passenger accepts a fare quote and is not assigned with a vehicle, her request will be added to time t + 1 if the threshold ¯ t satisfies. In this process, the mechanism assumes that all the passengers accept the fare estimate. This is because if a passenger rejects the quote, the mechanism simply ignores the request and assumes that the passenger never submits it. We assume that the system can calculate the marginal cost and the optimal routes as quickly as necessary, although it might be time-consuming in real-world application due to limited computational power and the complexity of the traffic

Algorithm 2: The Pickup Assignment Algorithm

1 function assign (t↪R0t ); Input : t - Time; R0t - A set of requests from passengers I t who accept the fare quotes at time t. Output : ⇧t -The set of assignment. 2 ⇧t ;; 3 A ;; 4 while v 2 V t do 5 while r 2 R0t do /* t0 is the estimated pickup time needed to service passenger it using vehicle v */ 6 Compute t0 ; 7 if t0  ¯ ti then 8 Compute ⇢X t-1 v [¶r♦ ; 9 if ⇢X t-1 v [¶r♦ < ⇢X t-1 v then 10 c0 ⇢X t v ; 11 A A[ ¶(v↪ c0 )♦; 12 end 13 end 14 end 15 end 16 V V t ; 17 I ¶i ♣ ri 2 Rt ♦; 18 while A 6= ; and V 6= ; and I 6= ; do /* sort in ascending order of c0 */ 19 A quicksort(A); /* ties are broken by selecting the one with the highest unit demand ` */ 20 (v↪ c0 ) argmin (v↪c0 )2A c0 ; 21 ⇧t ⇧t [ ¶(ˆ v↪ ˆ r) ♣ ˆ v = v↪ cˆ r = c0 ♦; 22 A A∩ ¶(v⇤ ↪ c⇤ ) ♣ v⇤ = v↪ (v⇤ ↪ c⇤ ) 2 A♦; 23 if nv < 1 then 24 V V ∩ ¶v♦; 25 end 26 I I ∩ ¶i ♣ cri = c0 ↪ ri 2 R0t ♦; 27 end 28 return ⇧t .

dynamics. However, it can be computed with meta heuristics [Hansen and Zhou, 2007]. At time t, the cost per unit demand for all requests assigned to vehicle v under the assignment of ⇡v 2 ⇧t is determined as following:

Therefore, the final payment of passenger i at time t is calculated as following:

where pti can be calculated in O(n2T log n) time.

Ex-post Incentive Compatibility

We show that the IORS mechanism satisfies ex-post incentive compatibility.

Lemma 3.1. A passenger can not decrease her cost by delaying the submission of the request, provided that all other passengers report their demand truthfully and do not change their decisions on fare quotes. That is, for all ⌧1↪ ⌧2↪ t 2 T and submissions R and R0 , where 0  ⌧1 < ⌧2  t, R = ¶R0 ↪ ▷▷R⌧1 ↪ R⌧2 ↪ ▷▷▷↪ Rt ♦, and

We have:

Proof. Depending on whether ri is serviced or not, we distinguish two cases:

• ÷ The request is not serviced: if the passenger delays her request from ⌧1 to ⌧2, then her latest departure time ˆ¯ ⌧1 = ¯ ⌧1 - 1 < ¯ ⌧1. If the pickup time t = ¯ ⌧1, then she will not be serviced at time ⌧2, which is obviously less favorable than being serviced. Another situation is that the addition of the request at time ⌧2 does not decrease the cost per unit demand of the coalitions at time ⌧2, or the new cost per unit demand is less than the threshold determined by Algorithm 2.
• ÷ The request is serviced: If the passenger delays her request from ⌧1 to ⌧2. Assuming that,

We prove the theorem by contradiction. If 0  ⌧ < ⌧1, we have R0 (⌧) = R(⌧). By equation 1 and 4, the operational cost and the total unit demand are independent of the request submission time. That is, C 0 = C, P `0 = P `. By equation 5, 7 and 8, we have ptR(⌧) = ptR0 (⌧) . Thus, inequation 11 does not hold. This is also true if ⌧2 < ⌧  t. If ⌧1 < ⌧  ⌧2, since R0 (⌧) = R⌧1 ∩ ¶r⌧1 i ♦, we have the cost per unit demand ⇢R(⌧1)  ⇢R⌧1∩¶r⌧1 i ♦ , and the total demand `R(⌧1) < `R⌧1∩¶r⌧1 i ♦ . By multiplying the left and right sides of the two inequations, we get ⇢R(⌧1)`R(⌧1)  ⇢R⌧1∩¶r⌧1 i ♦ `R⌧1∩¶r⌧1 i ♦ . That is, ptR(⌧)  ptR0 (⌧) . Hence, inequation 11 does not hold when ⌧2 < ⌧  t. Therefore, the assumption is invalid and inequation 10 holds.

By incorporating the above cases, we prove the lemma.

Lemma 3.2. The passenger can not decrease her cost by misreporting its latest departure time, provided that all other passengers report their demand truthfully and do not change their decisions on fare quotes. That is,

Proof sketch. If passenger claims an earlier latest departure time (i.e., ˆ¯ t < ¯ t), according to Algorithm 1 and 2, the search space of the vehicles may be reduced and the request might be rejected. If ˆ¯ t > ¯ t, the search space will be increased. However, a passenger will reject the assignment if the pickup time exceeds the ¯ t according to the assumption made in section 3.1. By equation 1, 4, 5, 7 and 8, the fare ˆ¯ p does not increase in either scenario.

Theorem 3.3. The IORS mechanism is ex-post incentive compatible provided that all other passengers report their demand truthfully and do not change their decisions on fare quotes.

Proof sketch. A passenger i can not lie about her origin oui and destination di. She is unable to claim an earlier arrival ti. According to Lemma 3.1, she will not benefit from delaying the request submission provided that all other passengers report their demand information truthfully and do not change their decisions on whether to accept the quotes or not. The passenger will not gain from misreporting the latest departure time according to lemma 3.2.

Discussion

Note that the IORS mechanism does not require passengers to specify the deadlines for the latest delivery to their destinations. This is because passengers are likely to misreport the deadlines to rule out potential ridesharing assignments (e.g., by claiming an earlier deadline). However, mechanism designers may set constraints (e.g., the longest time, the maximum number of passengers, and the maximum rate) on a shared ride if necessary.

The IORS mechanism also satisfies other properties such as individual rationality and budget balance. For example, it is individual rational because passengers' final payments never exceed their quotes. The budget balance property is met for the reason that the total cost is split by the passengers who are provided with the ride services. Due to space limitations, we omit the poofs for these properties.

4 Benchmark

For evaluation purposes, we compute the optimal assignment as a benchmark to evaluate the efficiency of the IORS mechanism. The goal of the optimal assignment is to minimize the overall cost per unit demand (equivalent to maximizing W) under the constraints in the AMoD system. This is a minimum maximal matching problem, which is NPhard [Hopcroft and Karp, 1973], and cannot be solved in polynomial time. We use a linear programming solver LpSolve solver [Berkelaar et al., 2004] for optimization in the experiment.

Auction-based mechanisms have been proven to be efficient in some of the existing ridesharing systems such as carpooling and shuttles [Kleiner et al., 2011; Cheng et al., 2014; Coltin and Veloso, 2013; Kamar and Horvitz, 2009]. Some of them even have very close performance compared with the optimal solution [Cheng et al., 2014]. In our work, we compare the performance of the IORS with the state-of-theart, offline, auction-based mechanism (bottom-up) described in [Cheng et al., 2014]. The auction-based mechanism can not be solved in polynomial time.

5 Experimental Results

To evaluate the performance of the IORS mechanism, we developed an AMoD simulator to model the transportation system of a grid city with 101 ⇥ 101 blocks (a scenario similar to Figure 2).

5.1 Experimental Settings

In the experiment, we assumed that the number of AVs in the system is fixed. We set the number N = 1000. For each simulation, the system ran for 500 rounds unless specified otherwise. For each round, we generated a random number of requests Rt 2 R. We initialized R with a set of N = 500 integers randomly drawn from a normal distribution with mean θ = 1000 and standard deviation 100 (see Figure 3a). We assumed that each AV can transport up to four passengers at the same time.

We then generated the Rt requests respectively using the following method: the request time is the current round number; the waiting time is randomly drawn from the range 10 to 100; both the origins and destinations are randomly selected within a radius of 50 blocks in the grid. The operational cost per unit distance (block) is 1. The speeds for all vehicles are the same: 0.5 block per unit time (round). Initially, all the AVs depot at the center of the grid city. At time t = 0, the AVs become available for servicing passengers.

To be fair for evaluation and in the interest of saving time, we calculated the shortest paths between any two vertices in the city grid using the A⇤ algorithm [Hart et al., 1968] and saved it into a dictionary for further use in all the simulations

We ran all the simulations on a 2.9GHz quad-core machine with a 32GB RAM.

5.2 Results and Discussion

We performed simulations using the IORS mechanism. For comparison purposes, we computed the optimal assignment under the same experimental settings as a benchmark. we also conducted experiments on an AMoD system with the offline, auction-based mechanism described in section 4. To counter the effect of the fluctuations caused by the randomization techniques used, we ran all the experiments 20 times and calculated the mean and the standard deviation of the metrics evaluated.

We computed the social welfare scores over time for the systems using one of the following mechanisms: IORS mechanism, auction-based mechanism and the optimal assignment solution. The result (see Figure 3b) clearly shows that the IORS mechanism performs significantly better (with a 95% confidence interval) than the auction-based mechanism, with an increase of 22▷73%. Although it is a little inferior to the optimal solution, it performs fairly well (with a score equals to 93▷62% of the optimal solution) with 79.35% less computational time on average (see Figure 3c ) and no future knowledge of demand required.

The IORS mechanism adds a request only if this addition decreases the cost per unit demand of a group. However, it might suffer from local minima and produce suboptimal solutions due to a myopic view of the demand. The auctionbased mechanism, on the other hand, processes the aggre-

1

gated requests at once. It removes the requests with the lowest ranks. Although the mechanism might make better plans than the IORS mechanism at processing time because they have a better knowledge of demand distributions, it performs worse than the IORS at all the other time.

The revenue of IORS system is slightly lower than the optimal system, and much higher than the auction-based system (see Figure 4a). The effective demand of the system with the IORS mechanism fluctuates around 0▷7, while the demand for optimal solution first increases and then drops down to a level very close to that of the IORS system. This is due to the increased demand from passengers. As shown in Figure 4b, the demand for auction-based system keeps increasing and then reaches a plateau. For each time measured, the scores of the auction-based system are the lowest.

When the demand is high, obviously, it is effective to increase the supply (i.e., number of vehicles) at first. However, once the number of the AV fleet reaches some point, it will not help to improve the social welfare (i.e.,W) (see Figure 4c).

In summary, the IORS mechanism outperforms the offline, auction-based mechanism overwhelmingly in promoting ridesharing in AMoD systems. Although it is still inferior to the optimal solution, it can achieve a very close performance with substantially less computational time needed and no future knowledge of demand required.

6 Conclusions

To promote ridesharing in AMoD systems, we introduce a posted-price, integrated online mechanism, namely IORS. We show that IORS is ex-post incentive compatible. Simulation results demonstrate its competitiveness compared with the optimal assignment solution and the offline, auctionbased mechanism. Although IORS is tailored for AMoD systems, it is applicable to traditional demand responsive transport systems such as taxis and shuttles, provided that the dispatchers have full control over the vehicles. Besides, IORS can be applied to distributed scenarios by dividing a city into multiple zones where each zone has a control center individually processing the requests.

Future directions include coalition structure generation for optimal groups of shared riders, mechanism design to address ethics and privacy problems in ridesharing. Another direction is to develop more complex and realistic simulation platforms as benchmarks for future evaluation.

Acknowledgments

This work was supported in part by the National Science Foundation under grant CCF-1526593. The authors wish to thank anonymous reviewers for their helpful comments and suggestions.