Structured-Learning-Based Fleet Control for Autonomous
Mobility-on-Demand Systems
K. Jungela,∗ , A. Parmentierb , M. Schiffera,c and T. Vidald,ea TUM School of Management, Technical University of Munich, Munich, Germany

kai.jungel@tum.de, schiffer@tum.deb CERMICS, École des Ponts, Marne-la-Vallée, Franceaxel.parmentier@enpc.fr
c Munich Data Science Institute, Technical University of Munich, Munich, Germanyd CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains, Department of Mathematics

and Industrial Engineering, École Polytechnique de Montréal, Canadathibaut.vidal@cirrelt.cae Department of Computer Science, Pontifical Catholic University of Rio de Janeiro, Rio deJaneiro, Brazil∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 4, 2022
Keywords: Autonomous Mobility-on-Demand, Structured Learning, online algorithm

1

INTRODUCTION

Autonomous Mobility-on-Demand (AMoD) systems constitute a viable alternative to mitigate
today’s mobility system’s externalities such as the rising traffic volume in urban areas andtransportation-related pollution. An AMoD system is a centrally controlled fleet of self-driving
vehicles serving on-demand ride requests. The central control of the MoD fleet allows the optimal
dispatching of vehicles to ride requests in an offline problem setting. The respective online problem setting causes the central control to dispatch vehicles to ride requests without information
about future ride requests, in hindsight leading to an optimality gap compared to the offline solution. To reduce this gap, some online approaches aim to anticipate future ride requests, e.g. via
sampling from known request distributions (Alonso-Mora et al. , 2017). However, the fleet control of sampling-based approaches is biased towards the predefined request distribution and tends
to misleading dispatching and rebalancing decisions in scenarios with inaccurate distributional
information.
We address this problem by proposing a structured-learning-based framework that allows
for prescriptive online dispatching learned from offline dispatching solutions. We derive thisframework in four steps: first, we show how to state the underlying dispatching problem in its
offline variant as a k-disjoint shortest paths problem, which allows to solve it in polynomial time.
Second, we introduce an extended problem representation for the online dispatching problem,
which allows to incorporate future ride requests in the graph representation of each online batch.
Third, we present a structured learning model (cf. Parmentier, 2021) which learns to predict thearc weights for this extended dispatching graph such that the solution of the extended dispatchingproblem incorporates prescriptive rebalancing decisions. This finally allows us to devise an online
dispatching algorithm for a centrally controlled MoD fleet that automatically adapts to different
scenarios. We benchmark our framework on the New York taxi data set and show that ourTRISTAN XI Symposium

Original abstract submittal

K. Jungel, A. Parmentier, M. Schiffer and T. Vidal

2approach outperforms existing MoD control approaches on scenarios with different numbers ofrequests per time interval and different vehicles to request ratios.

2PROBLEM SETTING

We consider an operator who has complete control over a MoD vehicle fleet V = {v1 , ..., vn }and dispatches vehicles to serve ride requests R = {r1 , ..., rm }. Each ride request has a pickup
location, dropoff location, start time, arrival time, and a revenue defining the value for theoperator to fulfill this ride request. Then, the operator’s objective is to maximize its reward by
dispatching vehicles to ride requests. A ride request can represent a solitary ride or pooled rides
as we assume pooling decisions to be taken at an upper planning level. Accordingly a vehicle canserve only one ride at a time, and a vehicle can fulfill two subsequent ride requests when theyare feasibly connectable in time and space.
Within this setting, we distinguish between an offline and an online problem variant. Anoffline system covers the complete planning horizon and contains full information about all riderequests. In the online problem, ride requests enter the system over time.

3METHODOLOGYOur algorithmic framework utilizes a novel offline imitation learning paradigm, see Figure 1.
The main rationale of this paradigm is to minimize the distance between an online solution andthe corresponding offline solution that could be obtained under full information. To reach thisgoal, we use an algorithm Ω to transform the online instance Γon , which represents the rolling
horizon online batch, into an extended online instance ΓextOn , and use an encoding algorithmϕΘ to parameterize ΓextOn . The encoding algorithm ϕΘ learns the parameterization of ΓextOn
from precalculated offline solutions, which allows to incorporate information about possible futuresystem states and the value of corresponding (rebalancing) decisions. We then solve the extended
online problem instance ΓextOn using algorithm A and denote the solution with xextOn .
Onlineprobleminstance ΓonϕΘ (Ω)
Alg + ML

Extended online
problem instanceΓextOn = ϕΘ (Ω(Γon ))AAlg.

SolutionxextOn = A(ϕΘ (Ω(Γon )))Figure 1 – The offline imitation learning paradigm
The crucial part in the offline imitation learning paradigm is to learn parameter vector Θ suchthat the solution xextOn = A(ϕΘ (Ω(Γon ))) imitates an optimal offline solution xof f . Successfully
applying this paradigm requires (a) an offline control algorithm that finds an optimal solution tothe offline problem, (b) an online control algorithm that is compatible with the offline problem,(c) the formulation of the online control problem as a structured-prediction problem, and (d) atractable structured-learning problem.
Offline control: We formulate our offline dispatching problem as a k-disjoint shortest paths
problem (cf. Schiffer et al. , 2021). We consider a weighted directed graph G = (V, A, W ) with aset of vertices V , a set of arcs A and a set of weights W with a weight w ∈ W for each arc a ∈ A.
The vertex set is V = {V 0 ∪ V v ∪ V r }, where V r denotes all ride requests, V v denotes theinitial positions of vehicles, and V 0 contains a dummy source and a dummy sink vertex. We thenconstruct this graph such that only ride request representing vertices that can be subsequently
served are connected by an arc. Further, we connect each vehicle vertex to all reachable riderequests, the dummy source to all vehicle vertices and all ride request vertices to the dummy
sink, see Figure 2a. Finally, we associate the weight of a ride request vertex’s incoming arc withthe ride request’s negative reward. This allows us to obtain a solution to the offline problem
TRISTAN XI Symposium

Original abstract submittal

K. Jungel, A. Parmentier, M. Schiffer and T. Vidal

3rolling horizon

V0
Vvrolling horizon

VrV r̂

(a) offline(b) online(c) extended online

Figure 2 – Comparison of offline, online, and extended online dispatching graphin polynomial time by solving a k-disjoint shortest path problem on this graph structure; here,each obtained path denotes a feasible vehicle schedule that is part of the optimal dispatchingstrategy. We refer to this algorithm as A.
Online control: To obtain an online control problem that is compatible with its offline
counterpart’s algorithm, we use a re-optimization approach (cf. Bertsimas et al. , 2019) in arolling horizon fashion. Here, we construct a dispatching graph that contains only the ride
request vertices representing ride requests that enter the system in between two time steps, see
Figure 2b. To make this dispatching graph compatible with its offline counterpart, we extend itwith artificial vertices V r̂ , see Figure 2c. To do so, the extension algorithm Ω splits the spatial
simulation area into square rebalancing cells of equal size and predicts a future ride demand
from a historical ride request distribution for every rebalancing cell. Each estimated future ride
demand is an artificial request vertex in the extended online batch graph representation andconstitutes a rebalancing location. Then, an offline solution with a vehicle fulfilling a futureride request coincides with a vehicle driving to an artificial request vertex in the extended onlinesolution.
Structured-prediction problem: The encoder algorithm ϕΘ calculates the weights on thegraph representation of the extended online instance. The encoder calculates the weights wj
on arc aj via a linear combination of parameters Θ and features φ(aj , ΓextOn ), e.g., location orrequest information, describing this arc:
wj = hΘ|φ(aj , ΓextOn )i ∀j ∈ {1, ..., m}.

(1)

This allows us to reformulate algorithm A as a minimization problem:
Xarg minhΘ|φ(y, ΓextOn )i with φ(y, ΓextOn ) =φ(aj , ΓextOn ).
y∈Y(2)aj ∈yStructured-learning problem: We formulate a structured learning problem,minnX

ΘL(Θ; yi , xi ),(3)i=1that learns parameters Θ such that the transformation from Γon to ΓextOn leads to a solution xextOn that minimizes the distance to xof f . We use a Fenchel-Young loss L(Θ; y, x) with
perturbations Z and excluded dual summand similar to Parmentier & t’Kindt (2021),
L(Θ; y, x) = EZ (minhΘ + Z|φ(y; x)i) − hΘ|φ(y; x)i,y∈Y(4)leading to a convex optimization problem that we solve with the BFGS algorithm.

4PRELIMINARY RESULTS

We apply our algorithmic framework on a real-world case study in Manhattan using the New York
City taxi data set. We compare our structured learning based algorithm (SLBA) against twobenchmarks, a naive online approach, and a sampling online approach. The naive approach, does
TRISTAN XI Symposium

Original abstract submittal

K. Jungel, A. Parmentier, M. Schiffer and T. Vidal

4Figure 3 – The x-axis describes different scenarios (left: different densities of request distributions, right: different amount of vehicles over a fixed amount of requests). The y-axis shows theperformance indicator (upper row: absolute profit of different benchmarks, lower row: the relative
improvement of our learning approach to the benchmark approach.
not consider information about future ride requests, whereas the sampling approach incorporates
artificial ride requests, sampled from a given distribution, into the dispatching .
Figure 3 compares these benchmarks with our approach. Besides the stable and superior
performance of our approach, the results show the pitfalls of both benchmarks: the naive approach outperforms the sampling approach for scenarios with sparse request distributions, wheresampling likely triggers suboptimal rebalancing decisions, and for scenarios with a high vehicles
to requests ratio, where the vehicle fleet can always fulfill all ride requests without additional
rebalancing. The sampling approach outperforms the naive approach on scenarios with a highrequest density, where sampling from the predefined distribution is a good indicator for future
requests, and in the case with a low ratio of vehicles to requests when wrong rebalancing decisions are unlikely. Our SLBA performs better or equally good than both benchmarks across all
analyzed settings, which shows the superiority of our imitation learning paradigm, which allows
for effective prescriptive rebalancing in various system states.
Acknowledgements: This work was supported by the German Research Foundation (DFG)
under grant no. 449261765.

References
Alonso-Mora, J., Wallar, A., & Rus, D. 2017. Predictive routing for autonomous mobility-on-demand systems with ride-sharing. Pages 3583–3590 of: 2017 IEEE/RSJ International Conference on Intelligent
Robots and Systems (IROS).
Bertsimas, D., Jaillet, P., & Martin, S. 2019. Online vehicle routing: The edge of optimization in largescale applications. Operations Research, 67(1), 143–162.
Parmentier, A. 2021. Learning to Approximate Industrial Problems by Operations Research ClassicProblems. Operations Research.
Parmentier, A., & t’Kindt, V. 2021. Learning to solve the single machine scheduling problem with releasetimes and sum of completion times. arXiv preprint arXiv:2101.01082.
Schiffer, M., Hiermann, G., Rüdel, F., & Walther, G. 2021. A polynomial-time algorithm for user-based
relocation in free-floating car sharing systems. Transportation Research Part B: Methodological, 143,
65–85.

TRISTAN XI Symposium

Original abstract submittal