A Scalable Logic-based Benders Decomposition to Optimize aDynamic Demand-Responsive Transport SystemL. Zigranda,b,∗ , R. Wolfler Calvob,c , E. Traversib and P. Alizadehd
a Padam Mobility, Paris, Francelouis@padam.iob LIPN (CNRS – UMR 7030), Université Sorbonne Paris Nord, Paris, Francezigrand@lipn.univ-paris13.fr, wolfler@lipn.univ-paris13.fr, traversi@lipn.univ-paris13.fr
c DIM, Università di Cagliari, Cagliari, Italyroberto.wolflerc@unica.itd Léonard de Vinci Pôle Universitaire, Research Center, Paris La Défense, Francepegah.alizadeh@devinci.fr∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 2, 2022
Keywords: Demand-Responsive Transport, Logic-based Benders Decomposition

1

Introduction

Demand Responsive Transport (DRT) defines shared transport systems where the vehicles adapt
their routes dynamically to the demand rather than using fixed routes and timetables. The
motivation of using such hybrid models is twofold: they straddle conventional public transport
and taxis, as their schedules and routes are quite flexible, and they constitute a viable alternative
to individual transport due to a lower cost of use.
Most of the time, such systems allow their users to make transport requests days before, as
well as during the day of the service. Consequently, if we put ourselves at the start of the service
and take a look at the demand, we can see two groups: the past ones that have already been
made, namely offline requests, and the future ones that have still to be made, namely online
requests. From there, a natural question can arise: is it possible to optimize the dispatching of
the offline requests while taking into account the online requests if we know them beforehand?
If so and to go a little bit further, is the gain in pooling of the service’s vehicles substantial incomparison to the usual planning optimization using myopic objective functions?
This work has been performed jointly with Padam Mobility, a well-established company thatprovides technological support to DRT companies. We first propose a generalization of the Diala-Ride Problem (DaRP) model to describe the previously presented situation. We then outline
a Logic-based Benders Decomposition method to solve our problem and show that this approachis efficient and adapted to the reality of an actual DRT service’s structure. Finally, we evaluate
the performance difference between a service where the offline requests have been organized withregards to a myopic objective function versus with regards to the online requests.
TRISTAN XI Symposium

Original abstract submittal

L. Zigrand, R. Wolfler Calvo, E. Traversi and P. Alizadeh22Problem Description

We consider a service where each agent k ∈ K has a vehicle with a capacity Qk ∈ IN⋆ , starts towork at Wk+ ∈ IR+ from depot Dk+ and finishes their shift at Wk− ∈ IR+ in depot Dk− . Regarding
the travel requests R associated to this service, we split them between the offline ROff and theonline ROn ones. In both cases, we describe a request r ∈ R with a pick-up Pr and a drop-off Dr
virtual nodes and we associate to each n ∈ {Pr ; Dr } a time-window of service [En ; Ln ] ⊂ IR+ , aload variation Qn as well as a service time Sn ∈ IR+ . Finally, each r ∈ R is given a maximum
ride time Mr ∈ IR+ and each r ∈ ROn has a probability of actually happening P (r).
Regarding the underlying graph of this Vehicle Routing Problem, we note N the set of all
the virtual nodes previously described and N= the pairs of virtual nodes associated to the same
physical node. Lastly, we note A ⊂ N × N the set of edges that can be crossed during the day
and, for each (n, n′ ) ∈ A, we define ∆tn,n′ the expected travel time between both nodes.
Based on this construction, we can consider the following decision variables of our problem:• xk,i,j : Binary variable equal to 1 if and only if agent k ∈ K is expected to cross (i, j) ∈ A.
• qk,i : Continuous variable equal to the load of agent k ∈ K when departing from i ∈ N .
• sk,i : Continuous variable equal to the time when agent k ∈ K arrives at i ∈ N .
Based on these definitions as well as the traditional three-index formulation (Cordeau, 2006),
we model our problem with the following Mixed-Integer Linear Programming formulation:
X Xmaxx,s,qX

X

X

xk,Pr ,j × P (r) , subject to:(1)r∈ROn k∈K {j∈N |(Pr ;j)∈A}

xk,i,j = 1∀i ∈ POff ∪ DOff(2)

xk,i,j ≤ 1∀i ∈ POn ∪ DOn(3)∀k ∈ K, ∀r ∈ R(4)∀k ∈ K(5)∀k ∈ K(6)∀k ∈ K, ∀i ∈ P ∪ D(7)sk,i + Si + ∆ti,j − sk,j − (1 − xk,i,j ) × Mi,j ≤ 0,
where Mi,j = max {0; Li + Si + ∆ti,j − Ej }∀k ∈ K, ∀ (i, j) ∈ A \ N=(8)sk,i − sk,j − (1 − xk,i,j ) × max {0; Li − Ej } ≤ 0∀k ∈ K, ∀ (i, j) ∈ A ∩ N=(9)sk,Pr − sk,Dr ≤ 0∀k ∈ K, ∀r ∈ R(10)sk,Dr − sk,Pr − SPr ≤ Mr

∀k ∈ K, ∀r ∈ R(11)

Ei ≤ sk,i ≤ Li∀k ∈ K, ∀i ∈ N(12)

Wk+ ≤ sk,D+ ≤ sk,D− ≤ Wk−kk∀k ∈ K(13)

qk,i + Qj − qk,j − (1 − xk,i,j ) × min {Qk ; Qk + Qi } ≤ 0∀k ∈ K, ∀ (i, j) ∈ A(14)

max {0; Qi } ≤ qk,i ≤ min {Qk ; Qk + Qi }∀k ∈ K, ∀i ∈ N(15)k∈K {j∈N |(i;j)∈A}XXk∈K {j∈N |(i;j)∈A}

X{j∈N |(Pr ;j)∈A}

X

X

xk,Pr ,j −xk,Dr ,j = 0{j∈N |(Dr ;j)∈A}

xk,D+ ,j = 1

Dk+ ;jk{j∈N |()∈A}X
xk,i,D− = 1k−{i∈N |(i;Dk )∈A}
X
X
xk,j,i −{j∈N |(j;i)∈A}

xk,i,j = 0{j∈N |(i;j)∈A}

TRISTAN XI Symposium

Original abstract submittal

L. Zigrand, R. Wolfler Calvo, E. Traversi and P. Alizadeh

3The objective presented in Equation (1) aims at maximizing the insertion rate of the online
requests. Then, Equations (2) to (4) define the assignment constraints of requests to agents.
The routing constraints are expressed by Equations (5) to (7) while the timing constraints aredescribed by Equations (8) to (13) and the load constraints are in Equations (14) and (15). In
particular, Equation (9) manages the dwell time computation with regards to the pairs of virtual
nodes that share the same physical location, which is a particularity of actual DRT services.

3Methodology

The problem described in Section 2 is actually complex to solve as it is. In the literature, various
approaches to solve the traditional DaRP model through the use of exact methods have been
proposed to tackle this scaling issue: Branch-and-Cut, Branch-and-Price and Branch-and-Priceand-Cut paradigms notably (Ho et al., 2018).
However, another way to look at this model is to decompose it as one assignment problem
per agent. This is the reason why we thought of applying a Logic-based Benders Decomposition(Hooker & Ottosson, 2003) approach to this problem. Furthermore, recent studies using thistechnique on similar problems have shown promising results (Riedler & Raidl, 2018).
We present in Algorithm 1 our optimization framework based on Benders Combinatorial Cuts.
The Master Problem assigns to each agent a set of requests to serve based on the already known
assignment constraints. On their side, the Sub-Problems check those assignments, give a feedback
to the Master Problem and try to repair heuristically the current assignment if necessary.
Algorithm 1: Logic-based Benders Decomposition AlgorithmInput: - Agents K- Offline and online requests R
Output: Best feasible assignment a ∈ P (R)K found during the optimization process
1 function LogicBasedBendersDecomposition(K, R)
2
master_problem ← MasterProblem (K, R)
3aBest ← ∅K
4
while OptimalityIsNotProven (master_problem, aBest ) do5(ak )k∈K ← GetNewAssignment (master_problem)
6
for each k ∈ K do
7ak,Off ← ComputeBCC (master_problem, k, (ak ∩ ROff ))
Sak,Off8a′k,Off← RepairAssignments (ak,Off )k∈K , ROff \k∈K9101112k∈Kfor each k ∈ K do
a′k ← ComputeBCC master_problem, k, a′k,Off ∪ [ak ∩ ROn ]S ′ifak,Off = ROff thenk∈K

S ′′′′a ← RepairAssignments K, a , R \akk∈K

13
14
15

if ObjectiveFunction (a′′ ) > ObjectiveFunction (aBest ) thenaBest ← a′′return aBest

In a few words, MasterProblem (l.2) initializes the Master Problem and builds heuristicallya set of initial constraints, ComputeBCC (l.7 and l.10) computes new Benders Combinatorial Cuts
and restricts the provided assignment to a feasible one if necessary, while RepairAssignments(l.8 and l.12) tries to insert the currently unserved requests into the current global assignment.
TRISTAN XI Symposium

Original abstract submittal

L. Zigrand, R. Wolfler Calvo, E. Traversi and P. Alizadeh

4

The initialization of the Master Problem plays a major role with regards to the convergenceof the optimization process. One of our core focus has thus been to design an efficient heuristic inorder to find Irreducible Infeasible Subsystems of requests to add to the initial pool of constraints.
We also worked on improving the existing heuristics used to compute new Benders Combinatorial
Cuts, to repair the broken assignments as well as to preprocess the underlying graph.

4Preliminary Results

We tested our optimization framework based on Logic-based Benders Decomposition on instancesfrom the literature (Cordeau, 2006, Riedler & Raidl, 2018) as well as on 25 real-world instances
provided by our industrial partnership. On the latter, ranging from small instances of 4 agents,
30 offline and 30 online requests up to 30 agents, 100 offline and 200 online requests, our solver
has been able to solve more than 80% of them to global optimality and obtain a gap of only a
few requests on most of the other instances in less than an hour.
In another experiment, we considered for each instance two ways to optimize the planningof the agents at the start of the service’s day: one where it is computed solely with the inadvance requests and the traditional objective function that minimizes the Total Duration of theRides, and another one where it is designed by maximizing the insertion rate of the expected
online requests using our solver. We then compared those initial schedules by simulating thearrival of the online requests during the service’s day using a classical greedy online insertion
module based on the Total Duration of the Rides minimization to answer the users. Our first
results show that the initial plannings computed with our non-myopic objective function insert
on average 11% more online requests than the ones computed with the traditional objectivefunction. Furthermore, while the initial routes of the agents are on average 17% longer with ourmethod, the final routes of the agents are only 7% longer on average. Those results show thepotential of working on new non-myopic optimization techniques.

5Conclusion

In this project, we first present a new Dial-a-Ride Problem-related model that describes moreaccurately real Demand Responsive Transport services than the existing models of the literature.
Then, we propose a new Optimization Framework based on Logic-based Benders Decomposition
to solve this problem and show that it scales well with actual instances, thanks to the structureof real services and newly designed heuristics. We also show encouraging results with regards tousing such a paradigm to optimize the routes of the agents at the start of their day.

6Acknowledgements

We thank Anh-Dung Nguyen from Padam Mobility for his precious support through this project.

References
Cordeau, Jean-François. 2006. A branch-and-cut algorithm for the dial-a-ride problem. Operations
Research, 54(3), 573–586.
Ho, Sin C, Szeto, Wai Yuen, Kuo, Yong-Hong, Leung, Janny MY, Petering, Matthew, & Tou, Terence WH. 2018. A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111, 395–421.
Hooker, John N, & Ottosson, Greger. 2003. Logic-based Benders decomposition. Mathematical Programming, 96(1), 33–60.
Riedler, Martin, & Raidl, Günther. 2018. Solving a selective dial-a-ride problem with logic-based Benders
decomposition. Computers & Operations Research, 96, 30–54.

TRISTAN XI Symposium

Original abstract submittal