Addressing supply and demand heterogeneity: Trip order menus
in Ride-hailing platforms
Yue Yanga, , Mohsen Ramezania,∗
a The University of Sydney, School of Civil Engineering, Sydney, Australia

yyan2437@uni.sydney.edu.aumohsen.ramezani@sydney.edu.au
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

December 15, 2021
Keywords: Ride-hailing, Heterogeneity, Matching elasticity

1INTRODUCTION

In 2011, Uber first launched its ride-hailing service in San Francisco. The rise of Uber paved theway for more and more platforms (i.e. Didi Chuxing and Lyft) to provide ride-hailing services
all around the world, reshaping transportation systems in both urban and suburban areas. The
essential role of these platforms is ’service providers’ to offer value-added services for both demand(i.e., travelers) and supply (i.e., drivers). Ride-hailing platforms are a typical two-sided market,
so making matching proposals (Nourinejad & Ramezani, 2016) and setting pricing strategies(Nourinejad & Ramezani, 2020) are two critical components to connect demand and supplysides. In the context of order matching, much work (Zhan et al., 2016, Xu et al., 2018) has been
conducted recently assuming that all the drivers working in platforms are full-time employees andservice (accept) the dispatched orders unconditionally. After the matching process, the platformcharges a fare to travelers and pays a wage to drivers by withholding the commission, which isnormally between 15% and 30%, depending on the time, region, and company.
On the supply side in ride-sourcing platforms, drivers make working decisions (i.e. when andwhere to service) and have heterogeneous market-behavioural patterns (i.e. being full-time orpart-time) based on their income, waiting time, etc. Also, travel purpose, the value of time,
spatial location, and other factors result in the heterogeneity of the trip demand. Taking into
account the heterogeneity in the matching process, the platform can not ensure that a driver will
accept a dispatched trip order. To mitigate the uncertainty in one-to-one matching, we consider
a relaxed matching pattern that offering each driver a menu of trip orders to choose from. A key
issue then is to determine which orders should be listed in the menu of each driver. Such menus
are needed to be designed carefully to nudge the self-optimizing drivers’ behaviours toward adesirable collective outcome.
In this paper, the above problem is solved by combining modeling driver’s choice and designing order menus: i) we investigate the drivers’ choice behaviour and model the probability ofchoosing an order or ignoring the whole order menu. ii) We model the problem as many-to-many
matching and develop an algorithm to design order menus. Through numerical experiments on
the simulator based on the Manhattan road network, the proposed method could improve theplatforms’ efficiency and enhance drivers’ and travelers’ experience.
TRISTAN XI Symposium

Original abstract submittalYue Yang, Mohsen Ramezani

22Methodology

2.1

Modeling driver’s choice

Let D = {d1 , d2 , ..., dn } denote a set of drivers and O = {o1 , o2 , ..., om } be a set of trip orders.
For an arbitrary pair with a driver d ∈ D and an order o ∈ O, a utility function is defined as
ud,o .
ud,o = β0,d + β1,d · fo − β2,d · τ (loorg , ld ) + β3,d · V (lodest )(1)

where fo represents o’s fare (priced based on the travel distance and travel time), τ (loorg , ld )indicates the pick-up distance from driver’s location, ld , to order o’s origin, loorg . V (·) is thespatial-value function derived from demand statistics; higher V (·) indicates the place have ahigher probability of being matched to the subsequent passenger. There are three main factors
considered in the function: (i) order fare, an order with a higher fare will naturally attract
the driver (i.e. less probability of decline by the driver). (ii) Pickup distance, a longer pickup
distance undermines the driver’s willingness to choose an order. (iii) Order destination, an orderwhose destination is a passenger-hotspot region will be more probable to be selected.
Given an order menu Od and ’Decline’ option c for driver d, the probability of option o, ∀o ∈Od ∪ {c} is chosen by driver d:pd,o =eud,c +eud,oPo′ ∈Od eud,o(2)′where ud,c is a constant (i.e. the expected profit for serving an order) to represent the reserved
expectation of driver d by declining the current order menu Od and wait for the next instance ofmatching.

2.2

Designing menus

Suppose unserved orders O and idle drivers D are collected at each matching instance. Let xd,obe a binary decision variable that equals 1 if order o, ∀o ∈ O is listed in the order menus of driverd, ∀d ∈ D, and 0 if not. The probability Po of order o selected by at least one driver is:
Po = 1 −Y′[1 − pd,o ({xd,o′ |∀o ∈ O}) · xd,o ](3)d∈D′where pd,o ({xd,o′ |∀o ∈ O}) (abbreviated as pd,o in the sequel) is the choosing probability that dQ′′chooses o if the menu of d is known as {xd,o′ |∀o ∈ O}, and d∈D [1 − pd,o ({xd,o′ |∀o ∈ O}) · xd,o ]represents the probability that none of the drivers choose order o.
In this paper, the objective is maximizing the sum of Po over all orders in O so as to maximizethe number of orders being responded:maxXo∈OPo = maxXo∈O[1 −Y(1 − pd,o xd,o )](4)d∈DTo achieve the above goal, we abstract idle drivers d, ∀d ∈ D and unserved orders o, ∀o ∈ O
as two sets of vertices, and all valid pairs (if xd,o = 1, ∀o ∈ O, ∀d ∈ D) as the set of edges witha weight ud,o . After that, the optimization problem can be transformed into determining theoptimal edge configuration in the bipartite graph. Given a fully-connected graph X = {xd,o =1|∀o ∈ O, ∀d ∈ D}, we introduce an iterative edge cutting algorithms to achieve the best edge
configuration in the bipartite graph.
Once we cut off the edge between o and d and remove o from driver d’s orders menus, the′′choosing probabilities of choosing remaining existing orders o , o ∈ Od are updated. We candefine δd,o′ to capture the change of pd,o′ :TRISTAN XI Symposium

Original abstract submittalYue Yang, Mohsen Ramezani

3′

δd,o′ = pupdate− pd,o′ ; ∀o ∈ Od /{o}d,o′(5)′where pupdate
is a probability that driver d chooses o in the new graph (xd,o = 0).
d,o′Furthermore, δd,o′ leads to a change of Po′ :Pupdate− Po′ = δd,o′ ·o′Y′(1 − pd′ ,o′ xd′ ,o′ ); ∀o ∈ Od /{o}(6)′d ∈D/{d}where Pupdate
indicates the updated value of Po′ in the new graph (xd,o = 0).
o′On the other hand, Po also changes after cutting off the edge between o and d:Y(1 − pd′ ,o xd′ ,o ).
Pupdate− Po = −pd,o ·od′ ∈D/{d}Therefore, we can obtain the overall gain ∆ of the objective function:
X(Pupdate− Po′ ) + Pupdate− Po ,∆=oo′o′ ∈Od /{o}

(7)

(8)

positive ∆ indicates an improvement of our objective function.
To achieve the optimal edge configuration in the graph, the most straightforward way is tocompute ∆ for all the edges in the graph, and then cut off the ‘best’ edge (let xd∗ ,o∗ = 0) withthe maximal gain ∆max for the next iteration. The above process will be repeated until there isno edge with a positive ∆. We call the method Edge Cutting algorithm (see Algorithm 1).
Algorithm 1 Edge Cutting
Input: Unserved orders O, idle drivers D
Output: Order menus X ∗Initialize a graph X = {xd,o = 1|∀o ∈ O, ∀d ∈ D}
Find out the ‘best’ edge xd∗ ,o∗ with the maximal ∆max
while ∆max > 0 do
Cut off the edge between o∗ and d∗ (let xd∗ ,o∗ = 0)Update pd,o , ∀o ∈ O, ∀d ∈ D in the graphFind out the ‘best’ edge xd∗ ,o∗ with the maximal ∆max
end whileX∗ ← Xreturn X ∗3Experiment

In this section, we examine the performance of the proposed method. All the experiments areconducted in a simulation environment in which Manhattan island is considered. The demanddata used are Manhattan taxi datasets in December 2020 collected from Yellow Cab’s website1 .
The trip order data include order location (origin and destination) and order request time. Eachpassenger is assigned a matching patience time stochastically drawn from a truncated Gaussian
distribution in the range of 0.5 [min] to 1 [min] with a mean of 0.75 [min] and standard deviationof 0.15 [min]. An order will be canceled if not being matched or picked up within the matching
patience time. 300 drivers are initially generated in the road network at 07:00 AM randomly. The
number and location of new arriving drivers are considered to be stochastic and time-varying.
1

https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page

TRISTAN XI Symposium

Original abstract submittalYue Yang, Mohsen Ramezani

4Furthermore, drivers are assumed to be impatient; they will leave the network once they receive
no matching for 30 [min]. On the other hand, the platform kick out the drivers if they take morethan 10 [min] to choose a ride.
Every ten seconds, the platform provides an order menu to each idle driver. Drivers choose aride among the offered order menu (with the option decline) based on the utility and logit model(Eq. 1 and 2). Subsequently, the platform collects the drivers’ decisions and assigns the nearest
responded driver to each order. Note that Idle drivers are parked at the last drop-off location.
The performance of the following benchmark methods are evaluated: i) One-to-one: Thismethod is commonly employed in ‘Order Dispatching’ or ‘Ride Matching’ scenarios. ii) Global:
All orders are listed in the menus of idle drivers. iii) Local: An order is listed in the menu ofdrivers whose pick-up distance is less than 2 kilometers.
Table 1 – The matching results under different strategies to design order menus.
Avg.
Response

Avg.
Cancellation

Avg.
Response time [s]Avg.
Occupied rate4679.7 (63.6%)
3467.3 (47.1%)
5327.8 (72.5%)
5767.3 (78.5%)

2640.1 (35.9%)
3840.4 (52.2%)
1998.5 (27.2%)
1563.4 (21.2%)

13.1
17.7
12.4
11.5

47.2%
43.4%
51.3%
53.7%

MethodOne-to-one
GlobalLocal
Edge Cutting

Table 1 summarizes the outcomes of different methods implemented in the simulator. The
Global method leads to a worse platform efficiency due to the concentration of the drivers’ willingness on several attractive orders (over-competition on a few high-utility orders). Contrarily,
the Local and Edge Cutting methods can achieve more promising results. It is worth noticingthat though the Edge Cutting algorithm is designed for optimizing average response in our problem, it achieves the best performance on all evaluation metrics with 78.5% average response rate,
21.2% average cancellation rate, 11.5 [s] average response time and 53.7% average occupied rateof the vehicles.

4Conclusion

Considering the heterogeneity of both supply and demand in the matching process, we propose amethod to design the trip order menus in peer-to-peer ride-hailing platforms. Through extensive
experiments, the proposed method enhance both passengers’ and drivers’ experience and improve
platform efficiency

References
Nourinejad, Mehdi, & Ramezani, Mohsen. 2016. Developing a large-scale taxi dispatching system forurban networks. Pages 441–446 of: 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC). IEEE.
Nourinejad, Mehdi, & Ramezani, Mohsen. 2020. Ride-Sourcing modeling and pricing in non-equilibrium
two-sided markets. Transportation Research Part B: Methodological, 132, 340–357.
Xu, Zhe, Li, Zhixin, Guan, Qingwen, Zhang, Dingshui, Li, Qiang, Nan, Junxiao, Liu, Chunyang, Bian,Wei, & Ye, Jieping. 2018. Large-scale order dispatch in on-demand ride-hailing platforms: A learningand planning approach. Pages 905–913 of: Proceedings of the 24th ACM SIGKDD International
Conference on Knowledge Discovery & Data Mining.
Zhan, Xianyuan, Qian, Xinwu, & Ukkusuri, Satish V. 2016. A graph-based approach to measuring theefficiency of an urban taxi service system. IEEE Transactions on Intelligent Transportation Systems,17(9), 2479–2489.

TRISTAN XI Symposium

Original abstract submittal