28 ISE Magazine | www.iise.org/ISEmagazine
Socially aware transit solutions focus on solving ‘first/last mile’ challenge
By Pascal Van Hentenryck
In the United States, car ownership is still the best pre-
dictor of upward social mobility. Indeed, the relationship
between transportation and social mobility is stronger
than that between mobility and several other factors, like
crime, elementary school test scores or the percentage of
two-parent families in a community (Transportation
Emerges as Crucial to Escaping Poverty,” Mikayla Bouchard,
The New York Times, May 7, 2015).
Those without a car are grievously disadvantaged in access-
ing jobs, healthcare and decent groceries. Millions of people
with health insurance cannot get to the doctor due to a lack of
mobility options. Tens of millions do not live within a mile of
a supermarket and often shop in convenience stores, with sig-
nificant consequences in the quality of their nutrition (The
Grocery Gap: Who Has Access to Healthy Food and Why
It Matters,” Sarah Treuhaft and Allison Karpyn, Policy Link).
Some children need to transfer buses twice before getting to
the school of their choice, limiting access to after-school pro-
grams and impacting their sleep patterns.
Advanced technologies have much to offer but improving
vehicles is only part of the solution. For instance, efficient elec-
tric vehicles cannot reduce congestion, which may cost $184
billion in 2030 for the United States alone (Beyond Traffic
2045,” U.S. Department of Transportation). Public transpor-
I
can ease commuters’ burdens
On-demand mobility systems
October 2019 | ISE Magazine 29
tation has the potential to mitigate
congestion and provide environmen-
tally friendly and cost-effective mobil-
ity. Existing systems, however, are of-
ten plagued with the infamous “first/
last mile” problem – the inability to
take travelers all the way from their
origin to their destination.
Indeed, in transit systems, fewer
than 10% of riders typically walk
more than a quarter of a mile. As a
result, the vast majority of travelers
prefer private vehicles if they can af-
ford them, often creating congestion
and emitting significant greenhouse
gasses.
New mobility services such as Lyft
and Uber have improved transporta-
tion for various population segments
by using information technology
to connect riders and potential drivers. Unfortunately, they
increase congestion and greenhouse gas emissions; some cit-
ies, including New York, have started to limit their numbers.
More importantly perhaps, they often serve the needs of an
affluent population and have widened inequalities in acces-
sibility by further draining the revenues of transit authorities
(Just a Better Taxi? A Survey-Based Comparison of Taxis,
Transit, and Ridesourcing Services in San Francisco,” Lisa
Rayle, Daniel Dai, Nelson Chan, Robert Cervero and Susan
Shaheen, Transport Policy, 2016).
Fortunately, ubiquitous connectivity and advances in arti-
ficial intelligence and operations research offer significant op-
portunities to design socially aware, on-demand mobility sys-
tems. These novel systems are capable of addressing the first/
last mile problem, reduce congestion and parking pressure and
decrease greenhouse gas emissions. They may transform mo-
bility for entire population segments and will benefit from au-
tonomous vehicles whenever they become available.
To illustrate the opportunities and the underlying tech-
nological challenges, we will review three such systems: on-
demand multimodal transit systems, community-based car
sharing and large-scale car sharing. It describes the motivation
behind these novel mobility systems, provides some pointers
to the technology powering them and describes case-studies
highlighting their potential benefits in cost and convenience.
On-demand multimodal transit systems
On-demand multimodal transit systems (ODMTS) (Arthur
Maheo, Philip Kilby, and Pascal Van Hentenryck, “Benders
Decomposition For The Design Of A Hub And Shuttle Public
Transit System,Transportation Science, January-February 2019)
aim at transforming public transit by simultaneously address-
ing accessibility and congestion issues. Being multimodal,
ODMTS combine on-demand mobility services to serve low-
density regions with high-occupancy vehicles (buses or trains)
traveling along high-density corridors. They differ from mi-
crotransit solutions by planning, operating and optimizing
transit systems holistically, using state-of-the-art optimization
technology and machine learning. As a result, they may trans-
form accessibility for entire population segments, decreasing
widening inequalities in transportation and providing a sus-
tainable transportation model for American cities and beyond.
Informally speaking, ODMTS are for transit systems what
Lyft and Uber are for taxi services: Their goal is to use arti-
cial intelligence and operations research, as well as information
and communication technologies, to transform public tran-
sit and improve accessibility and convenience. In its simplest
form, an ODMTS combines small, on-demand, ride-sharing
shuttles to address the ubiquitous first/last mile problem with
high-occupancy vehicles (e.g., buses) operating a network
of high-density corridors to mitigate congestion. The on-
demand shuttles are best viewed as feeders to and from the
high-occupancy network, although they also serve the local
demand.
Figure 1 illustrates this basic model. Large ODMTS may
feature multiple types of high-occupancy vehicles (e.g., trains
and buses), as well as various forms of small vehicles, which
may be shuttles, e-scooters or bicycles in appropriate settings.
An ODMTS forms a unique, integrated network that is de-
signed, planned and operated holistically. The network design
chooses the routes for the high-occupancy vehicles, sizes the
various fleets and produces the driver timetables. The OD-
MTS real-time operations decompose a trip in a series of legs
and solve generalized dial-a-ride problems over a rolling hori-
FIGURE 1
On-demand multimodal transit
An on-demand multimodal ride system from L1 to L4 with two shuttle legs around the bus leg
L2 to L3 in downtown Ann Arbor, Michigan.
30 ISE Magazine | www.iise.org/ISEmagazine
On-demand mobility systems can ease commuters’ burdens
zon to dispatch and route vehicles and
perform ride-sharing. The dial-a-ride
optimization minimizes the average
waiting time, while ensuring that any
ride does not exceed the time of the
shortest path too much (e.g., 15%).
The overall pipeline is depicted in
Figure 2.
Given that there is no range anxiety
in ODMTS, they could be operated
entirely by electrical vehicles. More-
over, ODMTS are also a natural path-
way to integrate autonomous vehicles
as they become available.
Simulation and pilot results on
small and medium transit systems
(e.g., 7.5 million riders a year) have
shown that an ODMTS can be priced
like a traditional transit system while
reducing wait times and/or improv-
ing accessibility. This is often pos-
sible due to a signicant reduction in
capital expenditures that compensate
for additional driver costs for the on-
demand shuttles. These simulations
were performed in a variety of set-
tings including the city of Canberra,
Australia, and the transit system of the
University of Michigan in Ann Arbor
that represent extremes in terms of
population densities.
The chart on Page 32 depicts the
benefits for Canberra: The ODMTS
improves convenience (trip time and
transfer) by a factor of two and cuts
the budget in half.
Figure 3 depicts some interesting
results for the ODMTS in Ann Arbor,
including the fact that almost all rides
take one or two legs and have short
waiting and trip times. The Rein-
venting Public Urban Transportation
and Mobility (RITMO) pilot at the
University of Michigan in spring 2018
has validated some of the simulation
results (“RITMO app introduces on-demand mass transit at
UM, with plans to expand,Concentrate, 2018).
Community-based car sharing
Parking occupies a significant portion of our cities. There are
at least 800 million parking spaces in the United States alone
and 14% of Los Angeles County is devoted to parking (The
Elephant In The Planning Scheme: How Cities Still Work
Around The Dominance Of Parking Space,” Elizabeth Tay-
lor, The Conversation, 2018). Parking also contributes to con-
gestion, as the average share of cruising to find a parking spot
is 30% in the United States (“Cruising For Parking,” Donald
Shoup, Transport Policy, 2006; “The High Cost of Free Park-
ing,” Shoup, American Planning Association, 2005).
FIGURE 2
Dial-a-ride optimization
The pipeline for designing and operating an ODMTS transit system that connects riders with
high-volume transit via the use of on-demand shuttle service.
Annual presentation, video offer
details on mobility solutions
Author Pascal Van Hentenryck presented his research on mobility
challenges and solutions during his keynote speech May 20 at the
IISE Annual Convention & Expo 2019 in Orlando, Florida.
You can watch portions of his speech plus a video interview afterward with IISE at
https://link.iise.org/Annual2019VanHentenryck.
FIGURE 3
Rides and waiting
Calculating trip times per number of legs for the ODMTS system at the University of Michigan.
October 2019 | ISE Magazine 31
Parking pressure is steadily increasing in corporate and uni-
versity campuses and cities. This second case study was mo-
tivated by parking pressure at the University of Michigan in
Ann Arbor, where the 15 most-used downtown parking lots
show typical parking usage: Cars arrive in the morning, park
in a lot for six to 10 hours and leave the lot in the evening.
Car pooling has long been proposed as a potential solution
for reducing peak-hour congestion and parking pressure. Its
adoption, however, is poor in general as 76.4% of American
commuters choose to drive alone (Who Drives to Work?
Commuting by Automobile in the United States,” Brian
McKenzie, American Community Survey Reports, U.S. Census
Bureau, 2015). Jianling Li and co-authors (Who Chooses
to Carpool and Why? Examination of Texas Carpoolers,” Li,
Patrick Embry, Stephen P. Mattingly, Kaveh Farokhi Sad-
abadi, Isaradatta Rasmidatta, Mark W. Burris, Transportation
Research Record: Journal of the Transportation Research
Board, 2007) identified the difficulty in finding peo-
ple with similar location and schedule as the main
reason for not car pooling. There is thus a unique
opportunity to build a matching platform based on
artificial intelligence and operations research for
boosting adoption of car pooling.
Community-based car pooling (“Community-
Based Trip Sharing For Urban Commuting,” M.
Haz Hasan, Pascal Van Hentenryck, Ceren Bu-
dak, Jiayu Chen, Chhavi Chaudhry, Proceedings of
the Thirty-Second AAAI Conference on Articial Intelli-
gence, 2018) is an embodiment of such a platform. Its
key idea is to organize pooling around commuting
communities, exploiting spatial and temporal local-
ity, i.e., the knowledge of when employees arrive
on a (corporate or university) campus in the morn-
ing and leave in the evening. It also guarantees a
ride back” in the evening, probably the most criti-
cal factor for adoption. This contrasts with the car
pooling platform Scoop, which only provides weak
guarantees for a ride back, with monthly limits on
how much auxiliary services can be used when a
ride back is not available.
To satisfy these three properties – spatial and tem-
poral locality and a guaranteed ride back – com-
munity-based car pooling proceeds in two steps.
First, it clusters commuters in communities, thus
ensuring spatial locality. In the second step, an opti-
mization algorithm selects drivers and matches rid-
ers to minimize the number of cars and the total
travel distance. Each driver is assigned a route for the
morning and evening commutes so that every rider
is guaranteed a ride back. The routes also guarantee
that each commuter will be served within requested
time windows, exploiting temporal locality in the
matching of drivers and riders.
The resulting optimization problem can be seen as two syn-
chronized dial-a-ride problems. In the model in Figure 4, Ω
+
and Ω
-
respectively represent a set of inbound and outbound
routes. A decision variable Xr denotes whether a route r is
included in the solution. The objective (1) minimizes the cost
of the routes, while constraints (2) and (3) ensure that a rider
is present in an inbound and outbound route (r,i is 1 if rider i
is serviced by route r). Constraints (4) express the “ride back
constraints (βr,i is 1 if rider i is the driver on route r). This
ensures that a driver in the morning is also a driver in the after-
noon and vice-versa. The routes can be generated on-demand
using a column-generation approach.
It would be ideal to have the same riders commute together
in the morning and the evening as well as every day of the
week. Unfortunately, one result of this study is the recognition
FIGURE 4
Formula for a fix
The master optimization solution for driver and route selection in ride-sharing.
32 ISE Magazine | www.iise.org/ISEmagazine
On-demand mobility systems can ease commuters’ burdens
that riders and drivers must be matched dynamically every day
and every morning and afternoon: It is only when riders are
matched dynamically that significant car-pooling occurs. This
important realization, which explains the poor adoption in
existing car-pooling programs, is illustrated in Figure 5. The
no sharing” column represents the number of cars with no
car-pooling. Columns WD-WIO, WD-DIO, DD-DIO and
DD impose progressively fewer constraints on the matching.
In particular, WD-WIO requires that the same routes and
drivers are used every day and that the same riders commute
together every morning and evening.
As can be seen, these constraints are too stringent. Car pool-
ing under these conditions reduces the number of cars on the
road only by 2%. In contrast, DD only requires that the drivers
are the same in the morning and in the evening in order to
satisfy the “ride back” constraint. It saves the number of cars
by 45% for the entire region and by more than 60% within the
city limit. The platform thus needs to match drivers and riders
every morning and every afternoon in real-time.
Moreover, it is desirable to adjust the afternoon dynamically
as riders update their schedules. Op-
timization algorithms based on route
generation are capable to meet these
requirements, primarily because they
exploit spatial and temporal locality.
The car-pooling platform must be
dynamic; while the morning and
evening shared routes are dense, their
intersection is rather sparse.
Large-scale ride sharing
The final on-demand mobility sys-
tem presented is a large-scale ride-
sharing platform. Ride-hailing
systems such as Lyft and Uber have
increased congestion in many cit-
ies. For instance, recent studies (“Do
Transportation Network Companies
Decrease Or Increase Congestion?
Gregory Erhardt, Sneha Roy, Drew Cooper, Bhargava Sana,
Mei Chen, Joe Castiglione, Science Advances, May 2019) have
shown that between 2010 and 2016, weekday vehicle hours of
delay increased by 62% compared to 22% in a counterfactual
2016 scenario without ride hailing.
Large-scale ride-sharing can change the equation. Authors
Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar,
Emilio Frazzoli, and Daniela Rus (On-Demand High-
Capacity Ride-Sharing Via Dynamic Trip-Vehicle Assign-
ment,” Proceedings of the National Academy of Sciences, 2017)
have shown that 98% of the riders using taxi and limousine
services in New York city can be served with 3,000 vehicles
and an average wait of 3.8 minutes (the city has about 12,000
taxis). Recent results using a bespoke column-generation ap-
proach have shown that all riders can be served with 2,000
vehicles, an average wait time of 2.2 minutes and an average
deviation of 0.62 minute compared to a direct trip (“Col-
umn Generation for Real-Time Ride-Sharing Operations,
Connor Riley, Antoine Legrain and Van Hentenryck, Inter-
national Conference on the Integration of Constraint Programming,
FIGURE 5
Out of the pool
A look at car reductions for various levels of flexibility in community-based car sharing.
‘Down Under’ upside
The potential benefits of ODMTS (BusPlus) in cost and convenience as calculated for Canberra, Australia:
BusPlus ACTION
Day IZI Buses ($) Cost ($) Time (s) IZI Cost ($) Time (s)
Monday 31 31,989.33 202,122.34 855.87 3,068 402,006.75 1,635.22
Tuesday 31 31,989.33 194,840. 42 848.96 3,068 402,006.75 1,635.10
Wednesday 33 33,135.41 205,814.09 849.01 3,068 402,006.75 1,620.79
Thursday 34 33,255.16 208,575.61 852.13 3,068 402,006.75 1,632.79
Friday 31 33,409.37 202,288.85 849.35 3,068 402,006.75 1,610.85
October 2019 | ISE Magazine 33
Articial Intelligence and Operations Research, 2019).
Figure 6 depicts some of these results and reports the aver-
age waiting times and average vehicle occupancy for vary-
ing numbers of customers and fleet sizes during peak hours.
Interestingly, the average occupancy is around 1.3 as soon as
there are more than 2,000 vehicles in the fleet. This indicates
that ride-sharing does not typically lead to overcrowded ve-
hicles.
Technology opens new opportunities
Mobility is a critical aspect of modern societies: It provides
access to jobs, healthcare, education, groceries and many
other social services. The current transportation infrastruc-
ture and systems, however, face signicant challenges in pro-
viding equitable access, as well as in decreasing congestion
and greenhouse gas emission.
Fortunately, the convergence of a number of technologies
opens new opportunities that may fundamentally change the
mobility landscape. In particular, information and commu-
nication technologies and progress in analytics driven by ma-
chine learning and optimization make it possible to imagine
entirely new mobility systems to meet these pressing chal-
lenges.
This article has presented three novel mobility systems
addressing different needs: on-demand multimodal transit
services, community-based car sharing and large-scale ride
sharing. It has shown that these mobility systems have the
potential to transform mobility by leveraging technology
enablers in communication and predictive/prescriptive ana-
lytics.
The mobility systems can be deployed immediately and
are sustainable from an economic and business standpoint.
Moreover, fleet electrification and autonomous vehicles
would amplify their benets. Electrification, combined with
renewable energy, would eliminate a substantial portion of
greenhouse gas emission due to transportation, since the pro-
posed mobility systems induce no range anxiety. Autonomy,
if properly priced, will further decrease costs, enabling to
further boost accessibility for entire population segments.
Pascal Van Hentenryck is the A. Russell Chandler III chair and
professor in the H. Milton Stewart School of Industrial and Sys-
tems Engineering at Georgia Tech in Atlanta. He previously was a
computer science professor at Brown University for 20 years, led the
Optimization Research Group at National ICT Australia and was
the Seth Bonder Collegiate Professor at the University of Michigan.
An author of five books published by MIT Press, Van Hentenryck is
the designer of several optimization systems that are widely used com-
mercially, including the constraint programming system CHIP (the
foundation of constraint programming languages) and the modeling
language OPL (now an IBM product). His current research focuses
on articial intelligence, data science and operations research with
applications in energy systems, mobility and privacy. He is an IISE
member, an INFORMS Fellow and a Fellow of the Association for
the Advancement of Articial Intelligence.
FIGURE 6
Large-scale ride-sharing in New York
The top picture shows the average wait times per number of
customers for various fleet sizes. The image at bottom reports the
average number of riders in a vehicle per number of customers for
various fleet sizes.