Integrated School Bell Time Adjustment and Vehicle Routing forParatransit Optimization
Samuel Vercraene1 , Fabien Lehuédé2,∗ , Thibaud Monteiro1 and Olivier Péton2
1 Laboratoire DISP, INSA Lyon, Villeurbanne, France
2 IMT Atlantique, LS2N, UMR CNRS 6004, Nantes, France∗ Corresponding author

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

January 7, 2022
Keywords: vehicle routing, dial-a-ride problem, paratransit, matheuristic

1Introduction

In many countries, access to transportation for people with disabilities has become a major
equity and inclusion issue. Medical and Social Institutions (MSI) and specialized schools forstudents with disabilities use specialized transport services every day. As a result, paratransit
represents one of the main costs for specialized schools and is also expensive for public authorities(ANAP, 2016, Tellez et al., 2020, Bertsimas & Yan, 2020). To reduce the cost of transport, it
is possible to use a pooling approach between neighboring schools, i.e. to group users fromthe same area in a common vehicle, even if they have different destinations. We investigate
a practical case from France, where these establishments typically have around 80 % of theirusers benefiting from a specialized transportation service. In this study, the considered MSI andspecialized schools (called schools in the remaining of this abstract) are interested in studying
the benefits of pooling their transport. The organization of such transport systems requires
solving a Dial-a-Ride Problem (DARP) to design the best possible routes for vehicles that pickup their passengers at home and drop them off at their destination, provided they can sharepart of their route. In the case of people with disabilities, transports are usually performed bya heterogeneous fleet of vehicles, including wheelchair accessible minibuses. Particular attention
is paid to the quality of the service to passengers, with constraints on passenger’s ride times or
waiting times at destination.
When several schools have similar start times, it is hard to design feasible routes that canpick up passengers living in the same area and going to separate schools. Hence, modifying theschools’ start times, which is known as School Bell time Adjustment (SBA) in school bus routing(Park & Kim, 2010), facilitates transportation pooling. To address the optimization problem
which consists of simultaneously determining the school start times and vehicle routes:
1. We introduce and model the Dial-A-Ride Problem with School Bell time Adjustment(DARP-SBA).
2. We integrate operational constraints, including vehicles which can differ in their cost, size
and inner configuration (number of seats and wheelchair spaces).
3. To solve this problem, we present a matheuristic which combines a Large Neighborhood
Search (LNS) and a route-based model solved with a solver.
TRISTAN XI Symposium

Original abstract submittal

S. Vercraene, F. Lehuédé, T. Monteiro and O. Péton

24. The numerical experiments rely on instances generated from a set of 575 users and around
100 vehicles provided by the Synergihp Rhône-Alpes company in the area of Lyon, France.
On average, we show that in addition to the 10% of saving that can be expected bysharing vehicle routes between schools, 7% of additional savings can be achieved by schoolbell time adjustment. This cost saving also decreases user ride times and the number ofvehicles required, creating longer routes which are more attractive for driver services.

2The Dial-A-Ride Problem with School Bell Time Adjustment

We consider a set of schools denoted by E. The set of users is denoted by U. Each useru ∈ U has a transportation request from a pickup node pu to a delivery node du . This request
is associated with a maximal ride time Ru and loads quS and quW which represent the numberof seats and wheelchairs needed to transport the user in a vehicle, respectively. We denote byP = {pu |u ∈ U} the set of pickup nodes and D = {du |u ∈ U} the set of delivery nodes. According
to this notation, deliveries at the same school are represented by separate nodes in D. The setof nodes that model a delivery at school e ∈ E is denoted by De . The depot is modeled by nodeso+ and o− , which represent the departure and return of all vehicle routes, respectively. The set
N of all nodes is defined as N = P ∪ D ∪ {o+ , o− }.
Without loss of generality, we only present the case of morning transport. In practice, asimilar problem must be solved for return trips at the end of the day. Each school e ∈ E has amorning interval [ae , be ] during which all deliveries can be scheduled. Deliveries occur within aso-called dynamic time window (Gschwind & Irnich, 2015) of width We that ends at the school
start time. For practical reasons, the morning interval is discretized using a discretization stepδe . This means that the bell time He at school e has to be chosen within the set {ae + κ × δe |κ ∈N, ae + κ × δe ≤ be }. A vehicle may arrive before the actual opening of a school time window.
In this case, it has to wait for the opening of the school before any user can leave the vehicle.
Pickup or depot nodes i ∈ P ∪ {o+ , o− } have a time window [ai , bi ]. By abuse of notation,
we also consider that a node i ∈ D that models a delivery at a school e ∈ E, has a time window[ai , bi ] = [ae , be ]. The service duration at any node i ∈ N is denoted by si .
We consider a heterogeneous fleet of vehicles in which the number of vehicles of each type
is not limited. Vehicles have one or several configurations characterized by a number of seats
and a number of wheelchairs. These configurations can easily be changed en-route by folding
or unfolding some seats. Each vehicle type has a given fixed cost for its use, a traveling costassociated with the distance traveled, and a cost per hour. Although the fleet is heterogeneous,
all vehicles are considered to have similar speeds. Accordingly, the driving time from a nodei ∈ N to j ∈ N is denoted by tij for all vehicle types.
The DARP-SBA consists in determining a start time He for each school e ∈ E within its
morning interval, selecting a set of vehicles and designing the route of each selected vehicle suchthat: all transportation requests are served; all maximum ride times, pickup and depot time
windows are satisfied; all users can be dropped off at their school within its time window; thecapacities of the vehicles are satisfied; and the overall vehicle, traveling and route duration costs
are minimized.
Figure 1 gives a graphical representation of a solution with two routes ω1 and ω2 visiting aschool e. Note that nodes d1 , d2 , d3 , d5 and d6 represent the same physical location. One of the
key challenges of this problem is that routes should be synchronized at schools, where a dynamic
time window is fixed in time when determining the school bell time.

3

Matheuristic approach

To solve the DARP-SBA, we propose a matheuristic which iterates over the following steps until
a time limit T L is reached:
TRISTAN XI Symposium

Integrated School Bell Time Adjustment and Vehicle Routing

S. Vercraene, F. Lehuédé, T. Monteiro and O. Péton

ae H − Weroute ω1o+route ω2o+

p1

3

He

e

p2

p3

d1

d2

p5

p6

d5

d6

d3

beo−

p4

p7

o−

Figure 1 – Partial time space representation of two routes ω1 and ω2 visiting a school e. He
denotes the school bell time to be determined. [ae , be ] is the morning interval of school e and[He − We , He ] is the dynamic time window induced by He .
1. In each iteration, solutions are generated by running N iterations of an LNS algorithm
derived from Tellez et al. (2018). In this LNS implementation: the repair operator solves aDARP in which the schools time windows have been filtered thanks to a necessary condition
to remove values that cannot lead to routes that are correctly synchronized at schools.
The complete timing problem is solved by a MILP solver only for complete and promisingsolutions to validate their feasibility. All routes found in this process are collected in theset Ω′ , called route pool.
2. A relaxed, restricted route based model of the DARP-SBA is then solved with a MILP
solver on this route pool with a time limit T SCP (T SCP ≪ T L). It selects and combinesroutes generated at different LNS iterations. In this model: (i) the service time at eachvertex of a route can be adjusted to find synchronized solutions, and (ii) the dynamic time
windows at schools are relaxed and their violation is penalized to allow unfeasible solutions
to be explored.
3. If solution S ∗ has been improved by the MILP solver, then the current solution is updated.
Otherwise, the current solution is re-used as a starting point at the next iteration. When themodel is solved to optimality twice in a row by the solver, the number N of LNS iterations
is increased geometrically by a factor of ε. If, on the contrary, the solver has not certified
the optimality of the solution and has not improved the solution S ∗ twice consecutively, thenumber of LNS iterations performed between each model solving is decreased geometricallyby a factor of ε.
To intensify the search for synchronized solutions that are close to the best known solution, amechanism progressively shrinks the arrival time windows at each school. More precisely, theschool morning intervals are shrunk R times in this algorithm at regular run-time intervals.

4Experiments

Our experimental study considers a set of 34 schools in the area of Lyon and the 575 users
transported to these schools. Based on this data set, three types of instances have been produced:
Small, Medium and Large instances (S,M,L) are based on a division of the data set in eight, fourand two sub-problems, respectively. We also consider two fleets of vehicles (heterogeneous andhomogeneous).
The matheuristic components were thoroughly evaluated and tuned. The resulting matheuristic is competitive with a state-of-the-art meta-heuristic to solve static instances of the DARP.
To evaluate the potential impact of SBA and its role in the pooling of transportation between
several schools, we have considered four scenarios. In scenario 0, vehicles cannot visit more thanone school. This corresponds to the situation where there is no transportation pooling betweenschool. Scenarios 20 and 60 correspond to DARP instances where the delivery time windows areTRISTAN XI Symposium

Integrated School Bell Time Adjustment and Vehicle Routing

S. Vercraene, F. Lehuédé, T. Monteiro and O. Péton

4[8:20, 8:40] and [8:00, 9:00], respectively. Finally, scenario 20/60 corresponds to the DARP-SBA
with a dynamic time window of width We = 20 minutes and a morning interval [ae , be ] = [8:00,9:00] for each school e ∈ E. Table 1 shows the results of all scenarios aggregated by instancetypes.
Impact of SBA (cost)
020 20/60
60
Heterogeneous fleet
S9,223 8,485
M
9,223 8,336
L
9,223 8,290

Gap to scenario 20 (%)
0 20/60
60

8,040
7,743
7,571

7,582
7,333
7,076

8.70
10.64
11.25

-5.25
-7.11
-8.68

-10.65-12.03-14.64

8,370

7,784

7,330

10.20

-7.01

-12.44

Homogeneous fleet
S9,973 8,920
M
9,973 8,706
L
9,973 8,683

8,377
8,031
7,928

7,918
7,619
7,332

11.81
14.56
14.86

-6.09
-7.75
-8.69

-11.23-12.48-15.56

8,112

7,623

13.74-7.51-13.09

11.97

-7.26

-12.76

Avg.

Avg.

9,223

9,973

Average

8,770

Table 1 – Impact of SBA on transportation cost
From this table, a first observation is that the greatest savings can be achieved by poolingtransports between schools. Indeed, comparing scenarios 0 and 20, pooling achieve around 10%
savings on routing costs in the case of a heterogeneous fleet and up to 14% with a homogeneousfleet. The current practice of having a heterogeneous fleet of vehicles is validated with respect
to the cost of a standard eight-seater vehicle. Comparing lines S, M and L where schools aregathered in clusters of increasing sizes, we see that mixed loads allow for greater savings ininstances with large clusters. Second, scenario 20/60 shows that adjusting school bell times
enables additional cost reduction by 7% on average. This is also a non-negligible potential
saving for daily transportation operations. Finally we find that the unrealistic scenario 60 allows
for only 5.5% of additional savings with respect to SBA.

References
ANAP. 2016. Améliorer la gestion des transports de personnes handicapées (Improving the managementof transportation for people with disabilities). Tech. rept. Appui santé & médico social (Health &medico-social support).
Bertsimas, Dimitris, & Yan, Julia. 2020. The edge of optimization in large-scale vehicle routing
for paratransit. Tech. rept. https://dbertsim.mit.edu/pdfs/papers/2020-yan-transporation-scienceparatransit.pdf.
Gschwind, Timo, & Irnich, Stefan. 2015. Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem. Transportation Science, 49(2), 335–354.
Park, Junhyuk, & Kim, Byung-In. 2010. The school bus routing problem: A review. European Journalof Operational Research, 202(2), 311–319.
Tellez, Oscar, Vercraene, Samuel, Lehuédé, Fabien, Péton, Olivier, & Monteiro, Thibaud. 2018. The fleet
size and mix dial-a-ride problem with reconfigurable vehicle capacity. Transportation Research Part
C: Emerging Technologies, 91, 99 – 123.
Tellez, Oscar, Daguet, Laurent, Lehuédé, Fabien, Monteiro, Thibaud, Montoya, Geovanny Osorio, Péton,Olivier, & Vercraene, Samuel. 2020. A stakeholder oriented approach to the optimization of transportsof people with disabilities. Supply Chain Forum: An International Journal, 21(2), 93–102.

TRISTAN XI Symposium

Integrated School Bell Time Adjustment and Vehicle Routing