This paper provides efficient solutions to maximize profit for commercial ridesharing services, under a pricing model with detour-based discounts for passengers. We propose a greedy heuristic for realtime ride matching and compare with other heuristics. We study the trade-offs between optimality and execution time that the solutions offer. Simulations on New York City (NYC) taxi trip data show that our heuristics are up to 93% optimal and 105 times faster than the exponential-time optimal algorithm. Commercial ridesharing service providers generate significant savings by matching multiple ride requests, which are typically shared between the service provider (increased profit) and the ridesharing passengers (discounts). It is not clear apriori how to split, since higher discounts would encourage more ridesharing, thereby increasing total savings, but the fraction of savings taken as profit is reduced. We simulate a scenario where the decisions of the passengers to opt for ridesharing depend on the discount offered by the provider. We provide an adaptive learning algorithm IDFLA that learns the optimal profit-maximizing discount factor for the provider. An evaluation over NYC data shows that IDFLA, on average, learns the optimal discount factor under 16 iterations.
Finally, we investigate the impact of imposing a detour-aware routing assuring sequential individual rationality which offers a better ride experience and increasing the provider’s market share, but at the cost of decreased average per-ride profit due to the reduced number of matched rides. We construct a model that captures these opposing effects, wherein simulations on NYC data show that 7% increase in market share would suffice to offset the decreased average per-ride profit.
This work was done when the authors were working with Xerox Research Center India (XRCI). 1
Ridesharing is a key initiative that can curb ever-increasing congestion on the urban transportation network and is an important means to move the world towards a sustainable future. While the term ridesharing has been used to include peer-topeer carpooling platforms as well, here we focus on commercial ridesharing service providers such as LyftLine and UberPool, that hold a significant share of the ridesharing population.
While ridesharing is undoubtedly appealing from a sustainability perspective, profit maximization is the primary goal of commercial providers. Given the emerging literature on detour-aware pricing and routing policies, e.g., [Jung et al., 2013; Gopalakrishnan et al., 2016] that enhance the ride experience, algorithms for profitable ride-matching should adapt to keep up. Such quality-enhancing policies encourage increased adoption of ridesharing, but perhaps at the cost of reduced average per-ride profit. We study three connected issues centered around profit optimization in commercial ridesharing.
First, it is unclear how to tune real-time ride-matching
algorithms to quickly find a near-optimal set of matches that
results in high profit under detour-based discounts
Second, ridesharing generates significant economic savings by reducing the driver-miles necessary to serve a set of passengers, which are split between the service provider (their profit) and the passengers (as discounts). It is not obvious how this split should be effected, since higher discounts encourage more ridesharing, increasing total savings, but the fraction of savings that constitutes the profit is smaller.
Third, in order to survive in an increasingly competitive market, ridesharing providers adopt additional qualityenhancing features which do not align fully with the goal of profit maximization, perhaps resulting in lower profit (due to the smaller feasible set of quality-compliant rides). It is important to understand the overall impact on profitability, and ensure that any resulting increase in market share can counter the reduced average per-ride profit.
The issues mentioned above are crucial for commercial ridesharing platforms; however, they are less explored. We address these issues, give solutions, and provide extensive evaluation on a real-world dataset.
Our Contributions: We investigate three important aspects of profit optimization in commercial ridesharing, resulting in the following contributions:
We provide an Integer Linear Program (ILP), and also an efficient greedy heuristic that quickly matches passengers to rides to approximately maximizes profit under a detour-based discount policy. We evaluate their performance experimentally (Section 3).
Under a model in which the likelihood of opting for ridesharing depends on the offered discount, we propose an adaptive algorithm that learns the profit-maximizing discount parameter (Section 4).
We additionally impose a detour-aware routing policy based on sequential individual rationality, introduced in [Gopalakrishnan et al., 2016]. Using simulations, we investigate the minimum increase in market share needed to offset the reduced average per-ride profit (Section 5). 2
There is a huge body of literature that studies several optimization problems related to ride sharing [Furuhata et al., 2013; Agatz et al., 2012; Pelzer et al., 2015], but the problem of pricing in ridesharing has been relatively less studied, with profit optimization rarely discussed. [Banerjee et al., 2015] characterizes the pros/cons of static versus dynamic pricing. [Jung et al., 2013] provides heuristics for maximizing profit subject to bounded detours. In contrast, we study profit maximization over a pricing model that incorporates a detour-based discount.
[Nguyen, 2013] proposes a dynamic, demand-responsive ridesharing system using auction mechanisms, where customers enjoy additive detour-based discounts. Our model considers multiplicative detour-based discounts; moreover, we also provide an algorithm to learn the profit-maximizing discount parameter under a suitable user choice model.
A closely related problem is that of cost sharing in peer-topeer ridesharing or carpooling, which, until recently, received little attention. Individual passengers are either asked to post what they are willing to pay in advance [Cao et al., 2015], to share the total cost proportionately among themselves according to the distances travelled [Geisberger et al., 2010; Agatz et al., 2011], or negotiate their shares on their own during/after the ride. Such methods ignore the real-time costs and delays incurred during the ride and are generally insensitive to the disproportionate delays encountered during the ride. Fair cost sharing in ridesharing has been studied [Bistaffa et al., 2015; Kleiner et al., 2011; Zhao et al., 2014; Kamar and Horvitz, 2009; Gopalakrishnan et al., 2016], but its impact on profitability is left unexplored. We fill this gap by studying the trade-off between average perride profits and market share. 3
Ridesharing generates significant profit to commercial platforms such as Uber and Lyft. The profit from a single cab is the difference between the fare paid by the passengers and the amount paid to the driver. When compared to assigning each user their own cab, ridesharing requires fewer cabs to serve the same set of users, leading to increased profit.
At the core of these platforms is a real-time matching algorithm that runs at regular time intervals, and generates a set of matched users from a set of waiting users (preprocessed to accommodate other spatio-temporal constraints). Such a system would maintain a pool of pending requests, and then invoke the matching algorithm every few minutes to determine optimal matches. We provide a matching heuristic that directly optimizes profit, under a detour-based discount scheme. Any unmatched requests left at the end of the algorithm either wait for another round, or, after a certain waiting time threshold elapses, are assigned fresh, empty cabs. Thus, it is important to provide a time-efficient matching algorithm for the larger dynamic ridesharing system to be sufficiently responsive to incoming user requests.
Moreover, under a detour-based discount policy, shared rides with smaller detours are more likely to be profitable. However, such a myopic observation could lead to suboptimal solutions, thus rendering the problem nontrivial.
In Section 3.1, we provide an Integer Linear Program (ILP) that matches n users to shared cabs (each with capacity ) to maximize profit, given a multiplicative detour-based discount fp( i; i), which is a linear function of the distance-wise ( i) and time-wise ( i) fractional detours experienced by user i. cb is the “base” (fixed) cost for a ride, cd and ct are the costs per unit distance and time, respectively. fd is the fraction of driver earnings taken by the service provider. 3.1
Each user i is associated with a source-destination pair (Si; Di). We consider n initially empty cabs and construct a complete directed graph G = (V; E) with 2n vertices that represent all the sources and destinations, that is, V = n fSi; Digi=1. Each directed edge e = (u; v) represents the best route from location u to v, and weights wd(e) and wt(e) denote the corresponding distance and time, respectively.
The ILP seeks values to assign to a set of optimization variables in order to maximize an objective function subject to a set of constraints.
Optimization Variables: Let xi;j;e 2 f0; 1g denote whether or not user i is served by cab j along edge e. Let yj;e 2 f0; 1g denote whether cab j travels along edge e while serving one or more users. Let zj 2 f0; 1g denote whether cab j serves at least one user. We set xi;j;(u;v) = 0 if (u; v) 2= E.
(a) Distance travelled, di = Pn
j=1 (b) Time in travel, ti = Pjn=1 Pe2E xi;j;ewt(e).
Pe2E xi;j;ewd(e). (c) Distance-wise fractional detour, i = diwdw(dS(iS; Di;iD)i) . (d) Time-wise fractional detour, i = tiwtw(tS(iS;Di;Di)i) . (e) Fare, Ci=(1 fp( i; i))(cb + cdwd(Si;Di)+ctwt(Si;Di)). yj;e yj;e zj zj xi;j;e 8i; j 2 f1; 2; : : : ; ng 8e 2 E n X xi;j;e 8j 2 f1; 2; : : : ; ng 8e 2 E i=1 yj;e 8j 2 f1; 2; : : : ; ng 8e 2 E X yj;e 8j 2 f1; 2; : : : ; ng e2E
(a) Distance traveled, j = Pe2E yj;ewd(e). (b) Time in travel, j = Pe2E yj;ewt(e). (c) Driver earnings, Ej = (1
fd)(cbzj + cd j + ct j).
Thus, the objective function to be maximized is the total profit, given by p = Pin=1 Ci Pjn=1 Ej.
Constraints: (i) yj;e = 1 if and only if xi;j;e = 1 for some i: (2) (3) (4) (ii) zj = 1 if and only if yj;e = 1 for some e: (iii) Each user is picked up by exactly one cab:
n X X xi;j;(Si;u) = 1 8i 2 f1; 2; : : : ; ng u2V j=1 (iv) Each user is dropped off by exactly one cab: n X X xi;j;(u;Di) = 1 8i 2 f1; : : : ; ng u2V j=1 (v) Each user is not served before pickup:
n X X xi;j;(u;Si) = 0 8i 2 f1; : : : ; ng u2V j=1 (vi) Each user is not served after dropoff:
n X X xi;j;(Di;u) = 0 8i 2 f1; : : : ; ng u2V j=1 (vii) Each user is served by a single cab, only between pickup and dropoff:
X xi;j;(u;v) = u2V
X xi;j;(v;u) 8v 2 V n fSi; Dig 8i 8j u2V (viii) Each cab serves at most users along any edge: n X xi;j;e 8j 2 f1; : : : ; ng 8e 2 E i=1 (ix) Each cab’s overall route is not disjoint, i.e., there are no gaps between serving users during which the cab is empty. Equivalently, if a cab serves a total of k 1 users, then it must do so using exactly 2k 1 edges: X yj;e
n 2 X
X xi;j;(Si;u) i=1 u2V ! 1 e2E
The inequality ( ) is to allow empty cabs (k = 0). Computing the optimal solution to the ILP takes a lot of time and memory, and is unsuitable for real-time ride matching, which requires fast, near-optimal techniques. However, it is a handy benchmark against which to experimentally evaluate the performance of our proposed methods (Section 3.3).
Given a set S of users matched to a cab, the driving distance and time for the best route for serving all the users i 2 S are denoted by d(S) and t(S), respectively. For each user i 2 S, di(S) and ti(S) denote the driving distance and time from Si to Di along that route, respectively. Thus, the profit from a cab serving a set of users S can be computed as follows: User Cost: The cost of the ride to user i 2 S,
Ci(S)=(1 fp( i(S); i(S))) (cb +cddi(fig)+ctti(fig)) ; (1) where i(S)= di(S) di(fig) , and i(S)= ti(S) ti(fig) .
di(fig) ti(fig) Driver Earnings: The earnings to the driver from the ride, E(S) = (1
fd) (cb + cdd(S) + ctt(S)) :
p(S) = X Ci(S) i2S
E(S): The incremental profit of merging two cabs (combining the users matched to two cabs into one and removing the other cab from the system), serving sets of users Sj and Sk is: p(Sj; Sk) = p(Sj [ Sk) p(Sj) p(Sk):
The above framework for real-time ride matching is more general than that of the ILP. A limitation of the ILP is that fp( ) is restricted to be a linear function. Moreover, it may not be possible for an ILP to explicitly incorporate additional detour-aware routing constraints and user preferences. However, during performance evaluation of our proposed methods, we limit the scope to the constraints listed in Section 3.1, in order to compare against the optimal ILP solution.
We now describe a greedy method for profit-maximizing realtime matching. We begin by assigning each of n input users to their “own” cab, i.e., no two users are assigned to the same cab.1 We maintain two collections of cabs, namely, a set of unavailable cabs U and a current pool of cabs A. We initialize A with the n single-user cabs and U = ;. We repeatedly perform the following steps until A is empty, at which point, we return U as the output: (a) For every two cabs j and k in A, if it is feasible to merge them subject to the capacity constraint (and any other optional constraints), compute the corresponding incremental profit pjk = p(Sj ; Sk). (b) Find two cabs j and k such that pj k is maximum. If pj k < 0, terminate and return U [ A as output. Otherwise, merge them and replace the individual cabs j and k in A with the merged cab. If the merged cab has passengers, move it from A to U .
Note that each iteration either terminates the method, or decreases the size of A by at least one; therefore, the method terminates after at most n 1 iterations. The time complexity of this method is O(n2 log n).
1We assume that all cabs are initially empty; however, our methods extend to a more general case where some cabs already have passengers in them with their own constraints to begin with. (a) Total profit by different methods with small-sized set of trip requests. (b) Time taken by different methods with small-sized set of trip requests. (c) Total Profit earned using various methods on a large dataset of about 19000 trip requests. In order to compare the performance of our proposed greedy method, we evaluate them against the optimal solution computed by solving the ILP of Section 3.1. Since the ILP takes more than 2 hours on an average (even with only 22 requests) to output the optimal solution, we first evaluate the nearoptimality of our methods using a small dataset, and then use a larger dataset for demonstrating the scalability and comparing the speed-optimality trade-off of our proposed heuristic and order-based greedy heuristics mentioned in [Biswas et al., 2017]2. To compare these order based methods with our proposed method, the orderings that we consider are: (a) Distance Order: Decreasing order of d(S). (b) Profit Order: Increasing order of p(S).
We evaluate our methods using publicly available New York City (NYC) taxi trip data [Whong and Monroy-Herna´ndez, 2013]. The 19GB dataset has logs for all NYC trips taken in 2013. Each trip in the dataset specifies pickup and dropoff coordinates, pickup time, dropoff time, trip distance and travel time. Each trip is considered as a “user” for our simulation. We assume that each cab serves at most = 3 users.
We discretize the underlying NYC map into grids of
100m2 area and select 2543 representative landmarks using
the methodology of [Rajasubramaniam et al., 2017]. We
precompute the inter-landmark distance and time using Open
Trip Planner [OTP, 2016]. For each user, we map their
source and destination coordinates to their nearest
representative landmarks and use the precomputed values for
comput2For completeness, we now briefly describe the greedy heuristics
which are parameterized by an order protocol
We select NYC taxi trips on randomly chosen days of 2013, between 7:45 - 8:00 pm. We intentionally choose the rush times, since many shared rides would be possible, and it would be interesting to see how our proposed heuristic performs. We run our method on several subsamples by considering a different number of users each time (5, 8, 10, 15, 20, and 22). We compare the total profit generated (Figure 1a) and the total time taken (Figure 1b) across each method, averaged over the small-sized subsamples of users. We observe that the total profit obtained by the Greedy-Max-Profit-Based method is up to 93% optimal and runs 105 times faster than the optimal algorithm on a machine with a quad Intel Core i7 processor with 32GB RAM. The optimal algorithm becomes intractable for instances where the number of users exceeds 25 (terminated after over 14:22 hours due to lack of memory).
Our proposed algorithm scales to a larger input set with 19000 users (obtained from a one-hour slot). The Greedy-Max-Profit-Based method takes 35 minutes while the Distance-Order-Based and Profit-Order-Based methods take 7 and 4 minutes, respectively.3 However, figure 1c shows that the performance of the former is significantly better than that of the latter methods in terms of the total profit. Thus, the speed-optimality trade-off becomes important in choosing the method that best suits the needs of a service provider. Finally, we also observe that the Greedy-Max-Profit-Based method matches 19000 users into 6701 cabs (reducing the operational cost significantly), obtaining a profit of $134; 500. 4
In the previous section, we laid out efficient ride-matching heuristics to maximize profit under a fixed detour-based discount for users. In this section, our goal is to learn the optimal detour-based discount policy, under a fixed ride-matching 3If the matching algorithm is invoked once per minute, in NYC, there are only 300 requests per minute on an average, for which all the greedy methods finish in less than a second. algorithm. For simplicity, we assume that the detour-based discount is a linear function of the fractional distance-wise detour. Thus, the discount to a user i 2 S is given by fp ( i(S)) = tan( ) i(S) + b; (5) where b is a constant denoting the minimum discount given to a user (to incentivize them to opt for ridesharing in the first place), and the discount parameter 2 [0 ; 90 ) governs how steeply the discount increases with the detour. Figure 2 plots (5) for various values of , assuming b = 10%.
Let P( ) denote the probability of a user opting to rideshare, a nondecreasing function of . A larger would lead to a larger population of users who are willing to rideshare, and potentially more shared rides; however, the profit from each shared ride would be smaller. Since the expected total profit depends on the number of users opting to rideshare, as well as the per-ride profit, it is important to find a value of that provides the optimal balance to maximize the expected total profit. We propose a method, which we call Iterative Discount Function Learning Algorithm (IDFLA), that learns such a over a period of time.
Each day, a value of is declared by the service provider. In response, the users who opt for ridesharing are then matched throughout the day using one of the heuristics from Section 3.2. The total profit earned is computed at the end of the day. IDFLA (Algorithm 1) learns the expected daily profit earned using different values of , and eventually converges to the best that maximizes this quantity. This kind of sequential decision making in stochastic environment can be categorized as a stochastic multi-armed bandit problem [Bubeck and Cesa-Bianchi, 2012], where the values are the arms, and the daily profit earned by using a certain is the reward earned by pulling the corresponding arm. IDFLA uses a popular technique for solving stochastic multi-armed bandit problems, called UCB1 [Auer et al., 2002]. Algorithm 1 IDFLA 1: Input: A finite number of values in an array 2: Ph stores the total profit with [h] 3: kh stores the number of days [h] is declared 4: for t 1 to j j do 5: Choose [t] on tth day and observe profit earned p; 6: Set Pt p; Set kt 1; 7: Find h = arg maxh
Ph + p2 ln j j ; 8: for t j j + 1; j j + 2; : : : do 9: Choose [h ] on tth day and observe profit earned p; 10: Update Ph Ph + p; Update kh kh + 1; Ph + q 2 ln t for (t + 1)th kh kh 11:
Find h = arg maxh day; 4.1
We evaluate our learning method IDFLA under the GreedyMax-Profit-Based ride-matching heuristic. We take = f10 ; 20 ; 30 ; 40 ; 50 ; 60 ; 70 ; 80 g, and run IDFLA to find near-optimal discount parameter, [h ]. The value of optimal discount parameter depends on P( ) which is the probability of opting rideshare. For simulating the user-behavior, we need to assume P( ) to be any non-decreasing function of . In practice, this probability P( ) is estimated while the optimal is learnt (step 14 of IDFLA). This corresponds to the fraction of times (k ) the users have opted for ridesharing whenever the discount parameter was . The P( ) function that we have assumed for our simulation, is shown in Figure 3.
Taxi trips in NYC between 7:45 - 8:00 pm of the 52 Wednesdays of 2013 were used to compare the performance of IDFLA with an “oracle” method (BDF) that knows the Best Discount Function apriori. Figure 4 shows the average daily profit obtained by declaring the same discount function everyday. We observe that the best discount function is obtained when = 40 ; therefore, BDF chooses = 40 everyday. Figure 5a shows that the discount parameter selected by IDFLA converges to that of BDF in 16 days.
We also observe (Figure 5b) that the average daily profit, that is, the cumulative total profit over t days divided by t, converges to that of the best discount function BDF. We show that after 52 days, the difference4 in average daily profit obtained by IDFLA and BDF is just $9:58, or 2:67%. Thus, IDFLA quickly learns the optimal discount parameter that can help the service provider maximize profit while keeping users sufficiently happy by providing suitable discounts.
In conjunction with desirable pricing schemes for ridesharing users, recent work has proposed detour-aware routing policies that impose upper bounds on the total detour [Jung et al., 2013] (static) or incremental detours [Gopalakrishnan et al., 2016] (dynamic). Such detour-aware routing policies work together with detour-based discount policies in order to enhance the quality of the ride experience for ridesharing users. This induces a similar trade-off as the one in Section 4: imposing additional quality-enhancing constraints into the ridematching process incentivizes greater adoption of ridesharing and increases the market share of the ridesharing population, but could result in reduced average per-ride profit. In this section, we consider the impact of one such detour-aware routing policy, based on the concept of Sequential Individual Rationality (SIR), introduced by [Gopalakrishnan et al., 2016].
SIR guarantees that the disutility to existing users (sum of the monetary cost and an “inconvenience cost” due to detours) in a shared ride is non-increasing as additional users are picked up. A parameterized version of SIR, called SIR, ensures that the incremental benefit (decrease in disutility) to an existing user upon picking up a new user is at least , where 0. Imposing SIR- results in a reduced set of feasible matched rides, leading not only to reduced average per-ride profit, but also a potential loss due to the “up-front discounts” (the parameter b in (5)) given to the passengers who opt for ridesharing, but end up being unmatched. However, the resulting detour-aware routing policy improves the quality of shared rides, thereby increasing the market share of ridesharing users, which could offset these negative effects. Unlike [Gopalakrishnan et al., 2016] that looks at the detour-aware routing policy from the user perspective (especially fairness), in this work we answer such a scheme’s impact on the service provider’s profit.
We investigate this phenomenon by performing experiments to address the following questions: (a) What is the trade-off between fewer matched rides and increased market share, compared to a scenario where no SIR- is imposed? How does this affect the profit? (b) How sensitive is the profit to the fraction of additional users who opt for ridesharing in response to the adoption of detour-aware routing by imposing SIR- ? 5.1
As before, we use the NYC taxi trip data for our experiments. We randomly select a weekday of 2013 and a one hour time 4The difference between the average reward of a learning algorithm to that of the optimal is called regret. An upper bound on the regret of UCB1 after T iterations is O(log T ) [Auer et al., 2002], when each arm’s reward is a bounded random variable. slot on that day. We then split the hour into 60 one-minute instances, and collect the sources and destinations for the users who initiated trips in each instance. The average number of users per instance is 210:85. While reporting our results, we take an average across these 60 instances.
The parameters cb, cd, ct, and fd are taken from publicly available Lyft user pricing and driver payment for NYC [LyftLine, 2016a; LyftLine, 2016b]. We select “detoursensitivities” i (higher values imply more aversion to detours) randomly from [$0; $5] per mile.We assume that each cab serves at most = 2 users, so that the profit maximization problem can be solved optimally in polynomial time using Edmond’s algorithm [Edmonds, 1965].5 The driving distance and time between locations are obtained by querying Open Trip Planner [OTP, 2016]. The parameters of the linear detour-based discount policy (5) are = 40 and b = 10%. To begin with, before imposing SIR- , we assume that the service provider’s initial market share is 60%, within which each user opts for ridesharing with a probability directly proportional to and b, and inversely proportional to i.
For each instance, we keep the following fixed: user origins, destinations, whether they are part of the initial market share, and if so, whether they opted for ridesharing. Then, we generate 30 realizations, where each user reacts to the adoption of a detour-aware routing policy (SIR- ), by flipping biased coins parameterized by cin, which is a measure of how strongly users value a quality-enhancing detour-aware routing policy. This participatory behavior is one of many that can be used. For any behavior model, our primary interest is the fraction of users who end up opting for ridesharing, and not the generative process itself. In the coin-flip-based process, the first group of users, who are in the initial market share but did not opt for ridesharing, flip with bias pin that is directly proportional to , b, and , and inversely proportional to i, with cin denoting the constant of proportionality. The second group of users, who are outside the initial market share, flip with bias 0:5pin (the factor 0:5 is hand-picked). The users who had already opted for ridesharing remain so. For consistency, we ensure that as we increase the value of , only users who have previously not opted for ridesharing flip again.
We calculate the profit obtained by matching users in the new market share. The parameter cin is varied from 100 and 1000, while is varied from 0 to 0:9. 5.2
Figure 6 shows profitability as increases for various values of cin. The baseline profit, without SIR- , is shown as a horizontal line. For any value of cin 200, there is a range of for which a higher profit can be obtained by imposing the appropriate SIR- policy. Moreover, when is high, the profit declines, because too many users remain unmatched.
Figure 7 shows a different visualization by plotting profitability as a function of cin, for different values of .
Figure 8 plots the minimum increase in market share that is necessary to meet a given lower bound on the profit, as 5The experiments can be carried out for > 2 as well, by using one of our proposed heuristics from Section 3.2 instead. a function of . For instance, to be 5% more profitable, a 13% increase is needed, as shown by the green curve. Alternatively, Figure 9 shows the maximum possible increase in profit (over all ), as a function of the increase in market share. The key takeaway here is that a 7% increase6 in market share is sufficient to recover from the negative effects (on the profit) of adopting a detour-aware routing policy.
In this paper, we adopt a profit-centric view of real-time ridesharing system design, and undertake an empirical investigation of three key elements that impact profit, namely 6A 7% increase in market share in response to a qualityenhancing policy is not unrealistic. Lyft’s market share increased by over 70% in 2016, owing in large part to better quality of service, resulting in Lyft’s customers being happier than those of their primary competitor, Uber [Swan, 2016]. (a) real-time ride matching, (b) user discounts, and (c) detouraware routing, by using NYC taxi trip data.
An optimal ride matching algorithm, even on a small set of 22 requests, can take up to 2 hours, however, our greedy heuristic generates near-optimal profit in less than 1=105 of the time, and scales well — it is able to match 18794 trip requests into 6701 cabs — while offering different trade-offs between optimality and running time. Our adaptive learning algorithm called IDFLA learns the optimal detour-based discount parameter that achieves the right balance between the number of passengers who opt for ridesharing and the portion of savings taken as profit from each shared ride, within 16 iterations. Finally, we demonstrate that even a small market share increase of 7%, in response to other restricted detouraware policies such as sequential individual rationality, is sufficient to counter the reduced per-ride profit due to the restricted constraints. Thus, one of our contributions is also a holistic treatment of the framework for detour-aware policies.
Given the encouraging empirical results of our proposed solutions for profit optimization, future work should provide approximation guarantees for the proposed greedy ridematching heuristics, and a formal mathematical analysis to characterize the dependence between profit under a detouraware routing policy. Another interesting direction to explore is the interplay between these different elements, e.g., how does a detour-aware routing policy affect the performance of the ride-matching heuristics and the convergence of the learning algorithm?