Trading exibility for adoption: Dynamic versus static walking inride-hailingaS. Martin , S. J. Taylorb and J. Yanc,∗a Kellogg School of Business, Northwestern University, Evanston, IL, USA
sebastien.martin@kellogg.northwestern.edu

b Lyft, San Francisco, CA, USA
sjt@lyft.com

c Sauder School of Business, University of British Columbia, Vancouver, BC, Canadajulia.yan@sauder.ubc.ca∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 1, 2022

Keywords: walking, ride-hailing, exibility

1 INTRODUCTION
Ride-hailing is an on-demand, individual transportation service that can be appealing for its
convenience and comfort. By contrast, mass transit and microtransit services ask riders to beexible in time (waiting) and space (walking), enabling the services to operate more eciently
than purely on-demand systems. A key question, then, is whether on-demand ride-hailing canincorporate a degree of rider exibility into its operations. Cost savings from improved operations
in ride-sharing could be passed onto riders while also mitigating congestion and emissions.
Riders' exibility in time has been studied under the Vehicle Routing Problem with TimeWindows (Kolenet al., 1987), and their exibility in space has been studied under the Vehicle
et al., 2018, Zhang et al., 2020). In both

Routing Problem with Floating Targets (Gambellaproblems, riders are asked to accept a window of time or space for their pickup to occur, expanding the feasible region of the optimization problem relative to problems with xed pickup timesand locations. Driver assignments and routes are then optimized jointly within these windows
to nd higher-quality solutions. Riders' exibility in space has attracted relatively less attention
than their exibility in time. However, walking can shorten trips, bring riders closer to drivers
for faster pickup times, or coalesce demand for shared rides, especially when trac and one-way
streets restrict drivers' mobility (Stiglicet al., 2015).

In 2021, Lyft introduced a product that encouraged time-sensitive riders to accept a shortwalk to pickup locations that would enable faster travel times. A screenshot of Lyft's currentwalking user interface is shown in Figure 1a. As a rider selects the origin location with a pin, abubble with a short walking radius is shown around the pin, representing the oating target inthe Vehicle Routing Problem with Floating Targets (VRPFT). Riders are then asked via a toggle
switch whether they are willing to walk to a pickup location that could lie anywhere within thebubble.

TRISTAN XI Symposium

Original abstract submittal

S. Martin, S. J. Taylor, J. Yan

2(a) Floating/Dynamic Walk(b) Fixed/Static Walk

Figure 1  Two proposed user interfaces for walking.
The VRPFT is attractive for the exibility gained from the expansion of the feasible region,but it takes as given that riders are willing to accept theexibility.

uncertainty that comes with thisThe uncertainty arises from the joint optimization of riders' pickup locations anddrivers' assignments, which means that riders' pickup locations remain unknown until the solution
is computed. Rider opt-in is critical to realizing the benets of walking, motivating our interestin lessening the burden on riders while still leveraging their exibility.
We make the following contributions.

First, we formulate adynamic walking model.,which jointly determines riders' pickup locations and driver assignments as in Figure 1a. Second, we propose the newstatic walking paradigm, which alleviates uncertainty for riders byshowing a static, predetermined pickup location to the rider before asking for the opt-in andassigning a driver. A user interface is shown in Figure 1b; here, the rider is asked to walk along
the gray dashed line from the purple origin pin to the pink pickup pin. We propose algorithms todetermine static pickup locations and discuss network characteristics that make static walking
viable. Third, we provide detailed simulations quantifying thevalue of walking , dened

as the travel time savings for walking relative to no walking, in minutes per ride. The simulations are built using real Lyft data on drivers' locations and riders' origins and destinations in
Manhattan, and a detailed representation of the underlying road network. We show that despite
being more constrained, static walking performs competitively, achieving as much as 94% of thevalue of dynamic walking. Consequently, static walking can outperform dynamic walking if itachieves as little as a 6% relative increase in adoption rate. Finally, we provide empirical evi-dence of the value of static walking. Using a xed-eects model on hundreds of thousandsof Lyft rides, we show that riders who are very close to our static pickup locations see substantial
improvements in travel times.

2METHODOLOGY

Basic matching

A service region is represented on a directed graph G = (V, E). The functionc(u, v) returns the driving time from node u to node v . In each period, sets of riders andavailable drivers arrive; we use the random variables N and M to denote the number of riders
1and drivers arriving in a period, respectively. Each rider i is associated with origin-destination
1We will consider driver availability high enough that we can assume M ≥ N , which is usually true in practice.

TRISTAN XI Symposium

Original abstract submittal

S. Martin, S. J. Taylor, J. Yan

3(Oi , Di ) ∈ V 2 , and each driver j with location Lj ∈ V .
We use the binary variable xi,j to denote whether driver j is matched to rider i, and seek tominimize the total travel time (pickup/deadheading plus in-vehicle). The formulation is then:N X
MXminx∈X

N ×M |

where X = {x ∈ {0, 1}(c(Lj , Oi ) + c(Oi , Di )) xi,j ,(1)i=1 j=1PN

i=1 xi,j ≤ 1 ∀j ∈ [M ],PM

j=1 xi,j = 1 ∀i ∈ [N ]}. Problem (1) is abipartite matching problem, standard in the ride-hailing literature.

WalkingNow, consider that riders can walk from their origin to a nearby pickup location. To

this end, we use the function δ(u, v) to denote the walking time from node u to node v , anddene the set WΓ (u) to be the set of nodes within a walking radius Γ of node u.
We introduce the idea of awalking function f : V 3 → V , which maps an origin-destination

pair and driver location to a pickup location for the rider to walk to. For a given walking function

f , we can express the matching problem as:
J(S | f ) =minx∈XN XMXc̄ (Oi , Di , Lj , f (Oi , Di , Lj )) xi,j ,(2)i=1 j=1

where we use c̄(O, D, L, w) = max {c(L, w), δ(O, w)} + c(w, D) for the total travel time when arider for origin-destination pair (O, D) is picked up at w by a driver coming from location L. WeNM

use S = ({(Oi , Di )}i=1 , {Lj }j=1 ) as shorthand for the state of all riders and drivers in a period.
For

no walking and dynamic walking, we apply the following functions to Problem (2):f NO (O, D, L) = O,(3a)f DYN (O, D, L) = argmin c̄(O, D, L, w).

(3b)w∈WΓ (O)A

static walking function will assign a riders' pickup node based only on their origin and des-It therefore must satisfy the following conditions: (i) f (O, D, L) ∈ WΓ (O), and (ii)f (O, D, L) = f (O, D, L0 ) ∀L, L0 (L could of course be removed from the arguments). We use
F STAT to denote the set of walking functions that satisfy these conditions. Among the feasible
tination.

static walking functions, we are interested in achieving the best expected performance, namely:f STAT ∈ argmin ES [J(S | f )].

(4)

f ∈F STATIn the full paper, we will propose algorithms to solve (4). We can quantify their performance bycomputing the following values of walking:1 ES [J(S | f NO )] − ES [J(S | f DYN )] ,E[N ]
1 ES [J(S | f NO )] − ES [J(S | f STAT )] .
V STAT =E[N ]V DYN =As V

DYN ≥ V STAT , we have a convenient measure of the optimality gap when we solve (4).

3RESULTS

(5a)

(5b)

Here, we present a selection of simulated results and empirical analysis on historical Lyft data
in Manhattan. The road network was represented as a graph structure using the OSMnx package
in Python, with travel times from Uber Movement. On the Manhattan network, we simulated

TRISTAN XI Symposium

Original abstract submittal

S. Martin, S. J. Taylor, J. Yan

4arrivals of riders and drivers using internal Lyft data on riders and idle drivers. Our analysis
included both ashort walk setting that would ask riders originating on a road segment to simply
longwalk to one of the two intersections at either end of the origin road segment, as well as awalk setting that would ask riders to walk to any intersection within about a ve minute walk.

Table 1 shows results for dynamic and static walking. Naturally, dynamic walking has thehighest value, saving 1.69 minutes per ride for short walks and 3.47 minutes per ride for longwalks. But surprisingly, static walking performs competitively with dynamic walking, achieving
94% of the value for a short walk radius, and 85% of the value even for the long walk radius.

Table 1  Performance metrics on Manhattan simulation
Walk Radius

Short WalkLong WalkDesign

Walk Time

Value of Walking (min./ride)(min./ride)

Pickup

In-Vehicle

Total (%Dyn)

Dynamic

1.04

0.81

0.88

1.69 (100%)

Static

1.05

0.64

0.95

1.59 (094%)

Dynamic

2.98

1.27

2.20

3.47 (100%)

Static

3.24

0.46

2.48

2.94 (085%)

We also t a xed-eects model to data on hundreds of thousands of historical Lyft rides inManhattan to estimate the value of walking at dierent distances from our static pickup locations.
The estimates are plotted in Figure 2 and show that the value of walking can be substantial,with especially high value for shorter walks. These estimates give us condence that our static
pickup locations are indeed valuable, and that the value in our simulations would translate wellin practice.

Figure 2  Empirical estimates of value of walking for dierent bins of walking time.

References
Gambella, Claudio, Naoum-Sawaya, Joe, & Ghaddar, Bissan. 2018. The vehicle routing problem withoating targets: Formulation and solution approaches. INFORMS Journal on Computing, 30(3),554569.
Kolen, Antoon WJ, Rinnooy Kan, AHG, & Trienekens, Harry WJM. 1987. Vehicle routing with time
windows. Operations Research, 35(2), 266273.
Stiglic, Mitja, Agatz, Niels, Savelsbergh, Martin, & Gradisar, Mirko. 2015. The benets of meeting points
in ride-sharing systems. Transportation Research Part B: Methodological, 82, 3653.
Zhang, Wei, Jacquillat, Alexandre, Wang, Kai, & Wang, Shuaian. 2020. Geometric Optimization forRouting with Floating Targets. In: TSL Second Triennial Conference.
TRISTAN XI Symposium

Original abstract submittal