Staggered routing in autonomous mobility-on-demand systems
File(s)
Published version
Author(s)
Coppola, Antonio
Hiermann, Gerhard
Paccagnan, Dario
Schiffer, Maximilian
Type
Journal Article
Abstract
In autonomous mobility-on-demand systems, effectively managing vehicle flows to mitigate induced congestion
and ensure efficient operations is imperative for system performance and positive customer experience. Against
this background, we study the potential of staggered routing, i.e., purposely delaying trip departures from a
system perspective, in order to reduce congestion and ensure efficient operations while still meeting customer
time windows. We formalize the underlying planning problem and show how to efficiently model it as a mixed
integer linear program. Moreover, we present a matheuristic that allows us to efficiently solve large-scale
real-world instances both in an offline full-information setting and its online rolling horizon counterpart. We
conduct a numerical study for Manhattan, New York City, focusing on low- and highly-congested scenarios.
Our results show that in low-congestion scenarios, staggering trip departures allows mitigating, on average,
98% of the induced congestion in a full information setting. In a rolling horizon setting, our algorithm allows
us to reduce 82% of the induced congestion. In high-congestion scenarios, we observe an average reduction
of 60% as the full information bound and an average reduction of 30% in our online setting. Surprisingly, we
show that these reductions can be reached by shifting trip departures by a maximum of six minutes in both
the low and high-congestion scenarios.
and ensure efficient operations is imperative for system performance and positive customer experience. Against
this background, we study the potential of staggered routing, i.e., purposely delaying trip departures from a
system perspective, in order to reduce congestion and ensure efficient operations while still meeting customer
time windows. We formalize the underlying planning problem and show how to efficiently model it as a mixed
integer linear program. Moreover, we present a matheuristic that allows us to efficiently solve large-scale
real-world instances both in an offline full-information setting and its online rolling horizon counterpart. We
conduct a numerical study for Manhattan, New York City, focusing on low- and highly-congested scenarios.
Our results show that in low-congestion scenarios, staggering trip departures allows mitigating, on average,
98% of the induced congestion in a full information setting. In a rolling horizon setting, our algorithm allows
us to reduce 82% of the induced congestion. In high-congestion scenarios, we observe an average reduction
of 60% as the full information bound and an average reduction of 30% in our online setting. Surprisingly, we
show that these reductions can be reached by shifting trip departures by a maximum of six minutes in both
the low and high-congestion scenarios.
Date Issued
2025-12-16
Date Acceptance
2025-06-06
Citation
European Journal of Operational Research, 2025, 327 (3), pp.875-891
ISSN
0377-2217
Publisher
Elsevier
Start Page
875
End Page
891
Journal / Book Title
European Journal of Operational Research
Volume
327
Issue
3
Copyright Statement
/© 2025 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
License URL
Subjects
Autonomous mobility-on-demand
Business & Economics
COMPLEXITY
Management
MODEL
NETWORKS
Operations Research & Management Science
Routing
Science & Technology
Social Sciences
Technology
Trip-staggering
VEHICLES
Publication Status
Published
Date Publish Online
2025-06-19