# The Dial-a-ride problem with school bell adjustment

Samuel Vercraene Vercraene, Fabien Lehuédé, Thibaud Monteiro, Olivier Péton

<figure><img src="image_1.png" /></figure>

## To cite this version:

Samuel Vercraene Vercraene, Fabien Lehuédé, Thibaud Monteiro, Olivier Péton. The Dial-a-ride problem with school bell adjustment. 2nd International Workshop on Synchronization in Transport SynchroTrans 2019, Sep 2019, Nantes, France. 10.1287/trsc.2022.1160. hal-02285166

HAL Id: hal-02285166

https://hal.science/hal-02285166v1

Submitted on 25 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# The Dial-a-Ride Problem with School Bell Time Adjustment

Samuel Vercraene, Fabien Lehuédé, Thibaud Monteiro, Olivier Péton

► To cite this version:

Samuel Vercraene, Fabien Lehuédé, Thibaud Monteiro, Olivier Péton. The Dial-a-Ride Problem with School Bell Time Adjustment. Transportation Science, 2023, 57 (1), pp.156-173. 10.1287/trsc.2022.1160. hal-03771405

HAL Id: hal-03771405

https://hal.science/hal-03771405

Submitted on 19 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# The Dial-A-Ride Problem with School Bell time Adjustment

Samuel Vercraene Vercraene, Fabien Lehuédé, Thibaud Monteiro, Olivier Péton

► To cite this version:

Samuel Vercraene Vercraene, Fabien Lehuédé, Thibaud Monteiro, Olivier Péton. The Dial-A-Ride Problem with School Bell time Adjustment. 2021. hal-03327511

HAL Id: hal-03327511

https://hal.science/hal-03327511

Preprint submitted on 27 Aug 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# The Dial-A-Ride Problem with School Bell time Adjustment

Samuel Vercraene¹, Fabien Lehuédé², Thibaud Monteiro², Olivier Péton¹

¹ Laboratoire DISP, INSA de Lyon, 21 avenue Jean Capelle, 69621 Villeurbanne, France

² IMT Atlantique, Laboratoire des Sciences du Numérique de Nantes (LS2N, UMR CNRS 6004), Nantes, France

August 27, 2021

## Abstract

In this paper, we study a paratransit application in which children are transported every day from their homes to their schools or medical-social establishments. To optimize this transportation system, the establishments collaborate to propose a joint transportation plan. We propose a new algorithm to jointly build vehicle routes that visit several establishments and simultaneously set the establishments' opening hours. This algorithm combines a large neighborhood search, the resolution of a route-based model and the progressive shrinkage of the planning window. It is applied to a real case from the area of Lyon in France, including 34 schools and 575 heterogeneous users served by a heterogeneous fleet of reconfigurable vehicles. On average, we show that in addition to the 10% of saving that can be expected by sharing vehicle routes between schools, 7% of additional savings can be achieved by school bell adjustment. This cost saving also decreases user ride times and the number of vehicles required, creating longer routes which are more attractive for driver services.

*Keywords: vehicle routing; dial-a-ride problem; healthcare logistics, school bell time adjustment; large neighborhood search*

## 1 Introduction

In many countries, access to transportation for people with disabilities has become a major equity and inclusion issue. Medical and social institutions (EMS) and schools with disabled students use paratransit systems every day to provide their users with an adapted transportation service. As a result, paratransit represents one of the main costs for EMS and is also expensive for public authorities (ANAP 2016, Yan 2020). To reduce the cost of transport, it is possible to use a pooling approach between neighboring schools, i.e. to group users from the same area in a common vehicle, even if they go to different schools. The organization of such transport systems requires solving a Dial-a-Ride Problem (DARP). The DARP covers the set of optimization models that aim to define the best possible routes for vehicles that pick up their passengers at home and drop them off at their destination, provided they can share part of their route. In DARP, particular attention is paid to the quality of the service to passengers, which can be expressed in terms of several criteria to be optimized or constraints to be satisfied, such as adherence to pickup time windows, minimization of travel time, and regularity of schedules. In this paper, we consider a set of schools that have decided to pool their transportation services. This approach is more flexible than considering schools separately, in particular because mixed loads are considered (Spada et al. 2005). The arrivals of vehicles at each school must occur within a short time interval before the schools start times; this is how arrival time windows are defined. When several schools have similar start times, it is hard for a vehicle to carry together passengers living in the same area and going to these schools. Hence, modifying the schools' start times, which is known as School Bell time Adjustment (SBA), facilitates transportation pooling. The goal of this paper is precisely to study the impact of SBA while solving the DARP.

More precisely, we investigate the integration of School Bell time Adjustment (SBA) in a Fleet Size and Mix Dial-A-Ride Problem. This paper makes the following contributions:
1. We introduce and model the Dial-A-Ride Problem with School Bell time Adjustment (DARP-SBA).

2. We integrate operational constraints, since vehicles can differ in their cost, size and inner configuration (number of seats and wheelchair spaces). 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.

3. We propose a solution method called School Bell time Adjustment Matheuristic (SBAM). It is based on a Large Neighborhood Search (LNS) method coupled with the solving of a route-based model. A mechanism progressively shrinks the arrival time windows at each school.

4. On average, we show that in addition to the 10% of saving that can be expected by sharing vehicle routes between schools, 7% of additional savings can be achieved by School Bell Adjustment. This cost saving also decreases user ride times and the number of needed vehicles, creating longer routes which are more attractive for driver services.

The remainder of the paper is organized as follows. Section 2 reviews the main literature references on SBA practices in school bus routing and dial-a-ride problems. In Section 3, a mathematical model for the DARP-SBA is formally introduced. Section 4 introduces the SBAM framework. The vehicle routing component is solved with a Large Neighborhood Search matheuristic presented in Section 5. This method is evaluated in Section 6. Finally, Section 7 presents numerical experiments to assess the benefits of SBA.

## 2 Literature review

First of all, we introduce the DARP-SBA as an extension of the DARP. In the static version of the DARP, a set of transportation requests is known a priori. Each request is generally associated with an origin and a destination, a number of passengers, time windows at each location and a maximum ride time. The objective is to design the routes of a set of vehicles such that all requests are transported from their origin to their destination, respecting time windows constraints, maximum ride time constraints, vehicles capacities and minimizing the routing cost. Several recent surveys review the literature on passenger transportation optimization problems and the DARP (Doerner and Salazar-González 2014, Ho et al. 2018, Molenbruch et al. 2017). The latest state of the art DARP algorithms (Gschwind and Drexel (2019) and Christiaens and Vanden Berghe (2020)) rely on a large neighborhood search approach, which is also employed in this paper. The specific static DARP (without SBA) that motivates this study has been treated in Tellez et al. (2018). It is a Fleet Size and Mix version of the DARP, which integrates vehicle selection, heterogeneous passenger types (seat users and passengers with wheelchairs), reconfigurable vehicles and en-route reconfigurations.

SBA is a characteristic of the School Bus Routing Problem (SBRP) (Park and Kim 2010, Ellegood et al. 2020). According to Desrosiers et al. (1986), the SBRP can be decomposed into five steps: data preparation, bus stop selection (student assignment to stops), bus route generation, School Bell time Adjustment, and route scheduling. The idea of optimizing school bell times and bus routes starting times has been proposed in Raff (1983) and Desrosiers et al. (1986). In this problem, given separate routes to serve each school, school bell times can be adjusted so that buses that have visited a school can be reused to service another route. Fügenschuh (2009) consider the simultaneous determination of routes and school start times. School start times are required to be in discrete time slots of 5 minutes (7:30, 7:35, 7:40, etc.). The objective function is to minimize the number of buses necessary to serve all customers. The paper shows that the number of buses deployed can be decreased by 10 to 25% by properly setting start times. Similar problems are studied in Fügenschuh and Martin (2006), in Fügenschuh (2011) (set partitioning formulation), in Zeng et al. (2018) and in Wang and Haghani (2020). Banerjee and Smilowitz (2019) also combine the route scheduling problem with SBA and incorporate additional considerations related to equity and efficiency. Equity is sought by seeking to minimize the maximum disutility associated with changing start times across all schools. They propose an iterative lexicographic schedule improvement method consisting in iteratively solving
an ILP formulation. Bertsimas et al. (2019) point out that computing bus routes is a necessary component of bell time selection. Since there are too many possibilities to explore in practice, they propose an estimated compatibility cost $C_{RtR't'}^{compat}$ of using trips $R$ for school $S$ and trip $R'$ for school $S'$ with respective bell times $t$ and $t'$. The school bell time selection problem is then formulated as a Generalized Quadratic Assignment Problem, which is solved with simple local improvement heuristic. We note that mixing transportation requests with distinct destinations (*mixed loads* in the SBRP) is a common practice in medical transportation systems but few papers have considered it in the context of school bus routing (Braca et al. 1997, Spada et al. 2005, Park et al. 2012). A few additional papers are mentioned in the recent survey of Ellegood et al. (2020), but it also suggests that SBA and mixed load have not been considered simultaneously in the SBRP.

The DARP-SBA also shares some similarities with vehicle routing problems that involve synchronization of operations at some locations (Drexel 2012). It is related to the concept of dynamic time windows. According to Gschwind and Irnich (2015): *“a dynamic time window relates to two operations: both must be executed within a given time, meaning that the difference between the points in time when the two operations are performed is bounded from above.”* Typically the maximum ride time constraint in the DARP defines a dynamic time window for operations within a route. Adjusting school bell times together with vehicle routing defines a dynamic time window between routes, called inter-route synchronization (Hempsch and Irnich 2008). This type of constraint has already been met in people transportation in the time-consistent VRP (Feillet et al. 2014) or the time-consistent DARP (Tellez et al. 2021). It is also met in goods distribution in the time window assignment VRP (Spliet and Gabor 2015) and its discrete counterpart (Spliet and Desaulniers 2015). These problems involve finding routes to serve a passenger or a customer over several days. In time window assignment problems, this should be done together with the determination of a dynamic time window, the width of which is common to all visits. In the discrete case, a set of possible time windows is given for each customer. Feillet et al. (2014) and Tellez et al. (2021) aim at minimizing the number of dynamic time windows per passengers that are necessary to cover all his/her visits.

In this paper we solve a single-period problem. The routes should be synchronized at schools, where a dynamic time window is fixed in time when determining the school bell time. The proposed model can handle a continuous as well as a discrete set of possible values for the schools bell times.

In conclusion, this paper makes two main contributions with respect to the existing literature. First, we propose a solution method that simultaneously builds routes and sets school bell times. Second, we integrate mixed loads, allowing several users going to different destinations to share a vehicle. This results in the definition of the DARP-SBA and the description of a general methodology that can be combined with any DARP algorithm. To our knowledge, this is the first contribution that integrates school bell adjustment in a DARP context.

# 3 The Dial A Ride Problem with School Bell Time Adjustment (DARP-SBA)

## 3.1 Problem settings

We consider a set of schools denoted by $\mathcal{E}$. The set of users is denoted by $\mathcal{U}$. Each user $u \in \mathcal{U}$ has a transportation request from a pickup node $p_u$ to a delivery node $d_u$. This request is associated with a maximal ride time $R_u$ and loads $q_u^S$ and $q_u^W$ which represent the number of seats and wheelchairs needed to transport the user in a vehicle, respectively. Note that this definition of a user includes the case of a group of people having the same pickup and delivery nodes and the same maximal ride time.

We denote by $\mathcal{P} = \{p_u|u \in \mathcal{U}\}$ the set of pickup nodes and $\mathcal{D} = \{d_u|u \in \mathcal{U}\}$ the set of delivery nodes. According to this notation, deliveries at the same school are represented by separate nodes in $\mathcal{D}$. The set of nodes that model a delivery at school $e \in \mathcal{E}$ is denoted by $\mathcal{D}_e$. The depot is modeled by nodes $o^+$ and $o^-$, which represent the departure and return of all vehicle routes, respectively. The set $\mathcal{N}$ of all nodes is defined as $\mathcal{N} = \mathcal{P} \cup \mathcal{D} \cup \{o^+, o^-\}$.

In this paper, without loss of generality, we only present the case of morning transport. In practice, a similar problem must be solved for return trips at the end of the day. Each school $e \in \mathcal{E}$ has a
morning interval $[a_e, b_e]$ during which all deliveries can be scheduled. We reuse the *dynamic time window* concept, as defined in the literature review section: deliveries occur within a *dynamic time window* of width $W_e$ that ends at the school bell time. For practical reasons, the morning interval is discretized using a discretization step $\delta_e$. This means that the bell time at school *e* has to be chosen within the set $\{a_e + \kappa \times \delta_e | \kappa \in \mathbb{N}, a_e + \kappa \times \delta_e \le b_e\}$. 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 \in \mathcal{P} \cup \{o^+, o^-\}$ have a time window $[a_i, b_i]$. By abuse of notation, we also consider that a node $i \in D$ that models a delivery at a school $e \in \mathcal{E}$, has a time window $[a_i, b_i] = [a_e, b_e]$. The service duration at any node $i \in \mathcal{N}$ is denoted by $s_i$.

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 cost associated 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 node $i \in \mathcal{N}$ to $j \in \mathcal{N}$ is denoted by $t_{ij}$ for all vehicle types.

The DARP-SBA consists in determining a start time for each school within its morning interval, selecting a set of vehicles and designing the route of each selected vehicle such that: all transportation requests are served, satisfying maximum ride times, pickup and depot time windows; all users can be dropped off at their school within its time windows; the capacities of the vehicles are satisfied; and the overall vehicle, traveling and route duration costs are minimized.

## 3.2 Representation of a solution

We model the DARP-SBA with a route-based formulation. This formulation considers a set $\Omega$ of vehicle routes that satisfy the time windows, ride time and capacity constraints of the problem. A route $\omega \in \Omega$ is defined by a type of vehicle and an ordered set of nodes denoted by $\mathcal{N}^\omega = \{\omega[1], \dots, \omega[n_\omega]\}$, where $n_\omega$ is the number of nodes in the route, $\omega[1] = o^+$ and $\omega[n_\omega] = o^-$. Moreover, each route should contain at least one school and $\omega[n_\omega - 1]$ must be a school. $\mathcal{U}^\omega$ denotes the set of users on route $\omega$. The sum of fixed and traveling costs of the route $\omega \in \Omega$ is denoted $c_\omega$. The cost per time unit of the route $\omega$ is denoted $C_\omega^{time}$. Note that, due to time windows and possible waiting times, the latter cost can be calculated only once the route $\omega$ is scheduled.

Figure 1 gives a graphical representation of a solution with two routes $\omega_1$ and $\omega_2$ visiting a school *e*.

<figure><img src="image_3.png" /><figcaption>Figure 1: Time space representation of two routes $\omega_1$ and $\omega_2$ visiting a school *e*. $H_e$ denotes the school bell time to be determined. $[a_e, b_e]$ is the morning interval of school *e* and $[H_e - W_e, H_e]$ is the dynamic time window induced by $H_e$.</figcaption></figure>

The horizontal axis represents the time scale. Route $\omega_1$ picks up three users 1, 2, 3 at nodes $p_1, p_2$ and $p_3$. These users alight from the vehicle at the school, which is modeled by nodes $d_1, d_2$ and $d_3$. Route $\omega_2$ picks up users 5 and 6, who alight at the same school *e*. Hence, nodes $d_1, d_2, d_3, d_5$ and $d_6$ represent the same physical location which is visited by two distinct routes. This location has a fixed morning interval $[a_e, b_e]$ represented in red. The school bell time is denoted $H_e$. It corresponds to the
end of the dynamic time window of width $W_e$ (in green) during which all visits to the school must be synchronized.

## 3.3 Mathematical formulation

To model the DARP-SBA we introduce the following variables: For each route $\omega \in \Omega$, the binary variable $y_\omega$ is equal to 1 if $\omega$ is selected, 0 otherwise. Variable $H_e$ models the school bell time at school $e \in E$. To implement the discretization of the morning interval, we introduce the integer variable $\kappa_e \in \mathbb{N}$ for all $e \in \mathcal{E}$. It implements the relation $H_e = a_e + \kappa_e \times \delta$. Finally, since waiting times may be introduced in a route to comply with school start times, we introduce variable $h_i^\omega \in [a_i, b_i]$, which represent the time at which route $\omega$ starts serving node $i \in \mathcal{N}^\omega$.

The DARP-SBA can be formulated as follows:

$$ \min f = \sum_{\omega \in \Omega} \left( c_{\omega} y_{\omega} + C_{\omega}^{\text{time}} (h_{\omega[n_{\omega}]}^{\omega} - h_{\omega[1]}^{\omega}) \right) \quad (1) $$

s.t.

$$ \sum_{\omega \in \Omega | p_u \in \mathcal{N}^{\omega}} y_{\omega} = 1 \qquad \forall u \in \mathcal{U} \qquad (2) $$

$$ h_{\omega[i-1]}^{\omega} + (s_{\omega[i-1]} + t_{\omega[i-1],\omega[i]})y_{\omega} \leq h_{\omega[i]}^{\omega} \qquad \forall \omega \in \Omega, i \in \{2, \dots, n_{\omega}\} \quad (3) $$

$$ h_{du}^{\omega} - h_{pu}^{\omega} - s_{pu} \leq R_u \qquad \forall \omega \in \Omega, u \in \mathcal{U}^{\omega} \qquad (4) $$

$$ a_i y_{\omega} \leq h_i^{\omega} \leq b_i y_{\omega} \qquad \forall \omega \in \Omega, i \in \mathcal{N}^{\omega} \qquad (5) $$

$$ H_e - W_e \leq \sum_{\omega \in \Omega | i \in \mathcal{N}^{\omega}} h_i^{\omega} \leq H_e \qquad \forall e \in \mathcal{E}, i \in \mathcal{D}_e \qquad (6) $$

$$ H_e - W_e = a_e + \delta \kappa_e \qquad \forall e \in \mathcal{E} \qquad (7) $$

$$ H_e \in [a_e + W_e, b_e] \qquad \forall e \in \mathcal{E} \qquad (8) $$

$$ \kappa_e \in \mathbb{N} \qquad \forall e \in \mathcal{E} \qquad (9) $$

$$ h_i^{\omega} \geq 0 \qquad \forall \omega \in \Omega, i \in \mathcal{N}^{\omega} \qquad (10) $$

$$ y_{\omega} \in \{0, 1\} \qquad \forall \omega \in \Omega \qquad (11) $$

The objective function (1) minimizes the sum of route fixed costs and travel time costs. The set-partitioning constraints (2) state that each user $u \in \mathcal{U}$ is picked up on exactly one route that visits pickup node $p_u$. Constraints (3) determine the schedule of a route $\omega$ such that the service time of the $i^{th}$ node in this route is greater than the time of the visit at its $i-1^{th}$ node plus its service time duration $s_{\omega[i-1]}$ and the travel time $t_{\omega[i-1],\omega[i]}$ from the $(i-1)^{th}$ to the $i^{th}$ node of route $\omega$. These constraints are usually not included in route-based formulations. They model the fact that vehicles can wait for the opening of a school's dynamic time window. Constraints (4) set the maximum ride time $R_u$ associated with each user $u$. Constraints (5) set time windows for visiting every node. Variables $h^\omega$ associated with non-selected routes are set to 0. Constraints (6) represent the synchronization of all routes visiting school $e \in \mathcal{E}$. All these routes must arrive at $e$ in an interval of width $W_e$ finishing at start time $H_e$. Since there is a single route belonging to both $\mathcal{N}^\omega$ and $\mathcal{N}_e$, only one term of the sum has a non-zero value. Constraints (7) define the value of schools start times, discretized with a step value $\delta$. Constraints (8) to (11) define the nature and intervals for all decision variables.

## 4 Solution method

As a generalization of the DARP, the DARP-SBA is an NP-hard problem. Given the size of the set of feasible routes $\Omega$, we propose a matheuristic framework to solve the DARP-SBA. This solution method consists in iteratively generating solutions with a Large Neighbourhood Search (LNS) and solving an MILP formulation of the DARP-SBA on a restricted set of routes $\Omega' \in \Omega$, taken from the LNS solutions. We propose a reformulation of the DARP-SBA model that accepts intermediate solutions violating the dynamic time windows. This new model is solved both by the LNS and the
MILP solver. A second key feature of the algorithm is that the size of the morning interval $[a_e, b_e]$ of each school $e \in \mathcal{E}$ is progressively reduced to guide the search towards a feasible solution. The proposed MILP reformulation of the DARP-SBA is introduced in Section 4.1. Section 4.2 presents the School Bell time Adjustment Matheuristic, which uses LNS as a black-box to generate routes. The progressive shrinkage of the morning interval is explained in Section 4.3. The LNS method is detailed in Section 5.

## 4.1 MILP reformulation

In the model presented in Section 3, constraints (5) do not perform well in a MILP solver because of their poor linear relaxation. Hence, we introduce a new model that reinforces the DARP-SBA model. In addition, our approach is based on an efficient DARP algorithm (Tellez et al. 2018) which minimizes routing costs. Producing a good set of routes which respects the dynamic time window at each school is challenging for this algorithm. We found that relaxing the dynamic time windows enables one to take the best from the LNS algorithm and the solution of the MILP model. Accordingly, both components of the solution method use a relaxed formulation denoted r-DARP-SBA.

Compared with model (1)-(11), we introduce two major modifications: First, the service time decision variable $h_i^\omega$ is replaced by a pre-processed value $\Theta_i^\omega$ and a variable $\tau_i^\omega$ for any route $\omega \in \Omega$ and all nodes $i \in \mathcal{N}_\omega$ in this route. The value $\Theta_i^\omega$ represents the earliest service time at node $i$ in route $\omega$. The variable $\tau_i^\omega$ models the time lag that is added to $\Theta_i^\omega$ in order to respect the dynamic time windows and maximum ride time, and to minimize the route duration. Hence, the service time at a node $i$ can be computed as $h_i^\omega = \Theta_i^\omega + \tau_i^\omega$. Second, we introduce the possibility to explore solutions that do not respect the dynamic time windows at schools. This is modeled by positive real variables $r_e$ representing the time that must be added to the dynamic time window width $W_e$ of each school $e \in \mathcal{E}$ to find a feasible solution.

With these new variables, the problem is modeled as follows:

$$ lex \min(g, f) \tag{12} $$

s.t.

$$ g = \sum_{e \in \mathcal{E}} r_e \tag{13} $$

$$ f = \sum_{\omega \in \Omega} c_{\omega} y_{\omega} + C_{\omega}^{time} (\Theta_{\omega[n_{\omega}]}^{\omega} - \Theta_{\omega[1]}^{\omega}) y_{\omega} + C_{\omega}^{time} (\tau_{\omega[n_{\omega}]}^{\omega} - \tau_{\omega[1]}^{\omega}) \tag{14} $$

$$ \sum_{\omega \in \Omega | p_u \in \mathcal{N}^\omega} y_\omega = 1 \qquad \forall u \in \mathcal{U} \tag{15} $$

$$ \Theta_{\omega[i-1]}^{\omega} + \tau_{\omega[i-1]}^{\omega} + t_{\omega[i-1], w[i]} + s_{\omega[i-1]} \leq \Theta_{\omega[i]}^{\omega} + \tau_{\omega[i]}^{\omega} \qquad \forall \omega \in \Omega, i \in \{2, \dots, n_{\omega}\} \tag{16} $$

$$ \Theta_{d_u}^{\omega} + \tau_{d_u}^{\omega} - \Theta_{p_u}^{\omega} - \tau_{p_u}^{\omega} - s_{p_u} \leq R_u \qquad \forall \omega \in \Omega, u \in \mathcal{U}^{\omega} \tag{17} $$

$$ a_i \leq \Theta_i^\omega + \tau_i^\omega \leq b_i \qquad \forall \omega \in \Omega, i \in \mathcal{N}^\omega \tag{18} $$

$$ H_e - W_e - r_e \leq \Theta_i^\omega + \tau_i^\omega \leq H_e \qquad \forall e \in \mathcal{E}, \omega \in \Omega, i \in \mathcal{N}^\omega \cap D_e \tag{19} $$

$$ H_e - W_e = a_e + \delta \kappa_e \qquad \forall e \in \mathcal{E} \tag{20} $$

$$ H_e \in [a_e + W_e, b_e] \qquad \forall e \in \mathcal{E} \tag{21} $$

$$ \tau_i^\omega \in \mathbb{R}^+ \qquad \forall \omega \in \Omega, i \in \mathcal{N} \tag{22} $$

$$ \kappa_e \in \mathbb{N} \qquad \forall e \in \mathcal{E} \tag{23} $$

$$ r_e \in \mathbb{R}^+ \qquad \forall e \in \mathcal{E} \tag{24} $$

$$ y_\omega \in \{0, 1\} \qquad \forall \omega \in \Omega \tag{25} $$

This model has two objective functions that are minimized in a lexicographical way. The first function, $g$ in Equation (13), models the sum of dynamic time windows violations. The objective function $f$ in Equation (14) minimizes the sum of routing costs. It is mathematically equivalent to
(1) but this reformulation offers a better linear relaxation since a part of the route duration cost $C_{\omega}^{\text{time}}(\Theta_{\omega|n_{\omega}}^{\omega} - \Theta_{\omega|1}^{\omega})y_{\omega}$ is accounted for in the objective function as soon as a variable $y_{\omega}$ is strictly positive. Similarly, constraints (15) model demand satisfaction, constraints (16) determine the routes schedule, constraints (17) enforce a maximal ride time for each user, and constraints (18) set the time windows on nodes of selected routes. The variables $r_e, e \in \mathcal{E}$, are introduced in constraints (19) to express that the width of the dynamic time windows of some schools can be increased to find a set of routes in $\Omega$ that respect the other constraints. In addition, comparing constraints (19) with constraints (6), the reformulation requires one constraint to be set for each route that visits the corresponding school $e \in \mathcal{E}$. Constraints (20) model the discretization of the school bell times, and constraints (23)–(25) define the domains of the variables. A solution is feasible when $g = 0$. If $g = 0$, the formulation is equivalent to (1)–(11).

## 4.2 Matheuristic framework

The general solution method, called School Bell time Adjustment Matheuristic (SBAM), is described by Algorithm 1.

<caption>**Algorithm 1:** SBAM: School Bell time Adjustment Matheuristic</caption>

**Parameters:** $N$: initial number of LNS iterations in one SBAM iteration, $\varepsilon$: constant positive multiplier for parameter $N$, $TL$ time limit, $T^{SCP}$ time limit for the MILP solver, $R$ total number of shrink iterations.

**Result:** Best solution $S^*$

/* Initialization */
1 Best solution: $S^* := \emptyset$
2 Current solution: $S := \emptyset$
3 $MI := \{[a_e, b_e], e \in \mathcal{E}\}$
4 Shrink iteration index: $SI_t := 1$
5 **while** execution time < $TL$ **do**
6 | **/* LNS, see Section 5 */**
7 | $\Omega'$, $S^*$, $S := \text{LNS}(S^*, S, N, MI)$
8 | **/* Solve the r-DARP-SBA model */**
9 | Solve (12)-(25) with an MILP Solver, taking $\Omega = \Omega'$; $\{[a_e, b_e], e \in \mathcal{E}\} = MI$; warm start with $S^*$; time limit $T^{SCP}$
10 | **if** $S^*$ has been improved by the MILP solver **then**
11 | | $S := S^*$
12 | **/* update $N$ */**
13 | **if** the r-DARP-SBA has been solved to optimality on two consecutive iterations **then**
14 | | $N := N \times (1 + \varepsilon)$
15 | **else if** optimality was not proven or $S^*$ was not improved on two consecutive iterations **then**
16 | | $N := N/(1 + \varepsilon)$
17 | **/* Shrink schools morning intervals */**
18 | **if** execution time reaches $SI_t \times TL/(R+1)$ **then**
19 | | $\forall e \in \mathcal{E}: \{a_e^{new}, b_e^{new}\} := \text{shrinkMorningInterval}(SI_t, e, S^*)$
20 | | $SI_t := SI_t+1$
21 | **MI :=** $\{[a_e^{new}, b_e^{new}], e \in \mathcal{E}\}$;
22 **end**

First, the best solution $S^*$ and the current solutions are initialized as empty sets (line 1). Then the main loop (from line 5) iterates until the time limit $TL$ is reached. In each iteration, solutions are generated by running $N$ iterations of an LNS algorithm (line 6). All routes found in this process are collected in the set $\Omega'$, called *route pool*. The r-DARP-SBA model is then solved with a MILP
solver on this route set (line 7). A time limit $T^{SCP}$ ($T^{SCP} \ll TL$) is also given to each call to the MILP solver. For this reason, the solver may return no solution or may not be able to certify their optimality. If solution $S^*$ has been improved by the MILP solver, then the current solution is updated (line 9). Otherwise, the current solution is re-used as a starting point at the next iteration. When the r-DARP-SBA is solved to optimality twice in a row by the solver, the number $N$ of LNS iterations is increased geometrically by a factor of $\epsilon$. If, on the contrary, the solver has not certified the optimality of the solution and has not improved the solution $S^*$ twice consecutively, the value of $N$ is decreased geometrically by a factor of $\epsilon$ (lines 10–13). To intensify the search for synchronized solutions that are close to the best known solution, the school morning intervals are shrunk $R$ times in this algorithm (lines 14–15). This corresponds to a shrinkage every $TL/(R+1)$ units of time.

## 4.3 Shrinking Morning interval

The `shrinkMorningInterval`($SIt$, $e$, $S^*$) function in line 15 of Algorithm 1 returns a reduced time interval [$a_e^{new}$, $b_e^{new}$] for a school $e \in \mathcal{E}$. [$a_e^{new}$, $b_e^{new}$] will be the new morning interval of school $e$ for the next SBAM iterations. It is calculated according to the best known solution $S^*$ and the current shrink iteration index $SIt$. This reduction is done such that the morning interval of a school $e$ starting from a large time window [$a_e$, $b_e$], reaches a width $W_e$ after $R$ shrinkages. The new morning interval is centered on the middle of all service times of its school in the best known solution. The exact process is the following:

Let us denote by {$h_1, \dots, h_K$} the set of of service times in $S^*$ for a given school school $e$. Let [$a_e$, $b_e$] be the initial morning interval of school $e$ (when $SIt = 1$). For a given $e \in \mathcal{E}$, the shrink iteration process is initialized by determining the step by which a shrink iteration reduces the morning interval:

$$Step = (b_e - a_e - W_e)/R$$

Then, the $SIt^{th}$ reduction is done as follows:

1. The width of the morning interval at iteration $SIt$ is

$$Width = Step \times (R - SIt) + W_e$$

2. In order to position this interval in time, we first calculate the minimum and maximum current service times of $e$ in $S^*$ as well as the center of the interval:

$$Tmin = \min_{i \in \{1, \dots, K\}} h_i$$

$$Tmax = \max_{i \in \{1, \dots, K\}} h_i$$

$$Center = (Tmin + Tmax)/2$$

3. A first estimation $a''$ of $a_e^{new}$ is calculated according to the current value of $a_e$, the center, the width and rounded to a multiple of the discretization step $\delta$:

$$a' = \max\{a_e, Center - Width/2\}$$

$$a'' = \lfloor a'/\delta \rfloor \times \delta.$$

4. The left bound $b_e^{new}$ is then positioned:

$$b' = \min\{b_e, \max\{a'' + Width, Tmax\}\}$$

$$b_e^{new} = \lfloor b'/\delta \rfloor \times \delta.$$

5. Finally, the value of $a_e^{new}$ is calculated from that of $b_e^{new}$:

$$a_e^{new} = b_e^{new} - \lfloor Width/\delta \rfloor \times \delta.$$

With this mechanism, the time windows are gradually shrunk until they reach their minimal value, which happens during the last $TL/(R+1)$ time units of computation. In this final step, the problem becomes a DARP with no SBA consideration.
# 5 Vehicle routing component

In this section, we describe the metaheuristic used to build solutions to the r-DARP-SBA at each iteration of the SBAM algorithm. This metaheuristic has two goals: (i) improving the feasibility measure $g$ and the routing costs function $f$ of solutions, and (ii) creating good routes that can be recombined together by a set partitioning approach. We implement a Large Neighborhood Search (LNS) metaheuristic, which has proved its efficiency on a number of optimization problem related to vehicle routing problems and its extensions (Ropke and Pisinger 2006b, Pisinger and Ropke 2007). This method has also proved its effectiveness for solving the DARP and several variants (Gschwind and Drexel 2019, Tellez et al. 2018, Lehuédé et al. 2013, Masson et al. 2014). Moreover, it offers a good trade-off between the quality of the solutions found and the computational effort.

LNS is based on insertion heuristics which evaluate many insertions of requests at all positions on all routes. This evaluation is composed of a feasibility test and a cost calculation. Checking feasibility means scheduling routes and checking that the visit to every node satisfies the time constraints and the capacity constraints of the problem. In the DARP, routes can be scheduled independently of each other and efficient feasibility tests can be used at each insertion evaluation. In the DARP-SBA or its relaxed version, routes are made interdependent by the synchronization constraints (6) induced by the school bell time choice. In some cases, efficient feasibility tests can be found for vehicle problems with synchronization (Masson et al. 2013) but maximum ride time constraints make the problem more complex (Masson et al. 2014). In the proposed LNS implementation, we use the following strategy: the repair operator solves a DARP in which the schools time windows have been filtered to remove values that cannot lead to a synchronized solution. Insertions are based on cost. The complete timing problem is solved by a MILP solver only for complete and promising solutions to validate their feasibility.

In this section we first introduce the LNS framework. We present the underlying timing problem, which combines the determination of school bell times and route schedules in the r-DARP-SBA. We then introduced necessary conditions which are used to filter time windows in repair operators.

## 5.1 LNS framework

The LNS framework implemented in this paper is presented in Algorithm 2. It has two main steps: First, the current solution is iteratively destroyed and repaired by solving a DARP in which the time windows at destination of all requests are set to the morning interval of the corresponding school set in SBAM(lines 5–8). Second, promising routes are evaluated with respect to the r-DARP-SBA timing constraints and objectives (lines 10–14).

The algorithm starts with a copy $S'$ of the current solution $S$ (line 1). In each iteration, the LNS metaheuristics randomly removes a given percentage of users from $S'$ and reinserts them, using *destroy* and *repair* operators (lines 6-7). During this process, the problem is solved as a DARP, with reduced time windows, calculated as described in Section 5.3. The routes in $S'$ are appended to the set $\Omega'$ (line 8) with the following heuristic filtering: If a route $\omega' \in S'$ visits the same users as a route $\omega \in \Omega'$ and $f(\omega) < f(\omega')$, then $\omega'$ is not added to the set. Conversely, if $\omega'$ have the same customers as $\omega$ and a strictly lower cost, then $\omega$ is replaced by $\omega'$ in $\Omega'$. The cost of the DARP solution $S'$ is then compared to the best known solution $S^*$. If $f(S') < f(S^*)$, then $S'$ is rescheduled to minimize its degree of violation of the dynamic time windows at schools. This timing problem is solved as a linear problem, introduced in Section 5.2 (line 10). This rescheduling can improve the degree of violation of the dynamic time windows and, by doing so, increase route durations. The returned values of these two objectives are denoted $\tilde{g}$ and $\tilde{f}$, respectively. If the rescheduled solution $S'$ improves $S^*$ (line 11), it is saved as a new best solution (line 12), and the iteration counter and the route pool $\Omega$ are reinitialized (lines 13-14). The acceptance of the new solution $S'$ as the current solution $S$ for the next LNS iteration is a record-to-record acceptance criterion based on the solution cost (lines 15-18). The stopping criterion is defined as a number $N$ of LNS iterations without improving the best known solution (line 4).

The *destroy operators* used in this LNS are the *random removal* and *history removal* (Pisinger and Ropke 2007), selected at each iteration with the same probability. The percentage of users removed from the solution by the *destroy operators* is randomly selected with a uniform probability in the interval
<table><caption>**Algorithm 2: LNS(S*, S, N, MI).**</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>Parameters:</td><td>ρ record to record parameter (acceptance criterion).</td><td></td></tr><tr><td>Input</td><td>: S* best solution found so far, S current solution, N number of iterations, MI schools morning intervals.</td><td></td></tr><tr><td>Result:</td><td>pool of routes Ω', Best Solution S*</td><td></td></tr><tr><td>1</td><td>S' := S (copy of the current solution)</td><td></td></tr><tr><td>2</td><td>Ω' := ∅ (pool of routes)</td><td></td></tr><tr><td>3</td><td>n := 0 (iteration counter)</td><td></td></tr><tr><td>4</td><td>while n &lt; N do</td><td></td></tr><tr><td></td><td>/* Create DARP solutions</td><td>*/</td></tr><tr><td>5</td><td>Select a destroy quantity; a destroy operator; and a repair operator</td><td></td></tr><tr><td>6</td><td>Destroy a part of S'</td><td></td></tr><tr><td>7</td><td>Repair S'</td><td></td></tr><tr><td>8</td><td>Filter and append the routes of S' to Ω'</td><td></td></tr><tr><td>9</td><td>if f(S') &lt; f(S*) then</td><td></td></tr><tr><td></td><td>/* Evaluate the r-DARP-SBA timing constraints and objectives</td><td>*/</td></tr><tr><td>10</td><td>S', ſ, ſ̃:=timingProblem(S')</td><td></td></tr><tr><td>11</td><td>if ſ̃ &lt; g(S*) or ſ̃ = g(S*) &amp; ſ̃ &lt; f(S*) then</td><td></td></tr><tr><td>12</td><td>S* := S'</td><td></td></tr><tr><td>13</td><td>n := 0</td><td></td></tr><tr><td>14</td><td>Ω' := ∅</td><td></td></tr><tr><td></td><td>/* Record to record acceptance criterion</td><td>*/</td></tr><tr><td>15</td><td>if f(S') &lt; f(S*) &times; (1 + ρ) then</td><td></td></tr><tr><td>16</td><td>S := S'</td><td></td></tr><tr><td>17</td><td>else</td><td></td></tr><tr><td>18</td><td>S' := S</td><td></td></tr><tr><td>19</td><td>n:=n+1</td><td></td></tr><tr><td>20</td><td>end</td><td></td></tr><tr><td>21</td><td>return Ω', S*, S</td><td></td></tr></tbody></table>
[Φ⁻, Φ⁺]. The repair operators are *k-regret* insertion heuristics with *k* ∈ {1, 2, 3, 4}, where *k* = 1 is the classical cheapest insertion heuristic (Ropke and Pisinger 2006a). The value of *k* is chosen with uniform probability. A detailed description of these operators and comparisons with other operators from the literature for solving the DARP can be found in Tellez et al. (2018). In this algorithm, we allow for *incomplete solutions* to be accepted as the current or the best solutions when unserved users cannot be inserted. A solution with a lower number of unserved customers is always preferred in the acceptance tests of lines 9, 11 and 15.

## 5.2 Timing problem

The timing model is a simplification of the r-DARP-SBA model (13)–(25) where the selected routes are known. For the sake of clarity, it uses variables *h* from the DARP-SBA model, where *h*ᵢ denotes time of service at a node *i*. In this section the notation is simplified because each node belongs to a single route. Hence, there is no need to add an index to identify the route that visits node *i*.

Let *S* be a solution of the r-DARP-SBA and let us denote its set of routes by Ω<sup>S</sup>. The sequence of pickup and delivery nodes in each route is known, and feasible with respect to the maximal ride times, users' time windows and schools' morning intervals. The timing problem aims at synchronizing the deliveries at schools and minimizing the total route duration. For each school *e* ∈ E, variable *r*<sub>e</sub> measures the violation of the dynamic time window at *e* (see constraints 6). These variables introduce a relaxation of the synchronization constraints. The first objective of the timing problem is to minimize the sum of time window violations. As the fixed and traveling costs *c*<sub>ω</sub> of ω ∈ Ω<sup>S</sup> are known, the second objective consists in minimizing the sum of route durations *f*'<sub>ω</sub> = Σ<sub>ω∈Ω<sup>S</sup></sub> C<sub>ω</sub><sup>time</sup>(h<sub>ω[n<sub>ω</sub>]</sub> - h<sub>ω[1]</sub>).

According to this notation, the lexicographical bi-objective MILP (26–37) models the timing problem of the r-DARP-SBA.

$$ lex \min(g, f') \tag{26} $$

s.t.

$$ g = \sum_{e \in E} r_e \tag{27} $$

$$ f' = \sum_{\omega \in \Omega^S} C_{\omega}^{\text{time}} (h_{\omega[n_{\omega}]} - h_{\omega[1]}) \tag{28} $$

$$ h_{\omega[i-1]} + t_{\omega[i-1], \omega[i]} + s_{\omega[i-1]} \leq h_{\omega[i]} \quad \forall \omega \in \Omega^S, i \in \{2, \dots, n_{\omega}\} \tag{29} $$

$$ h_{du} - h_{pu} - s_{pu} \leq R_u \quad \forall \omega \in \Omega^S, u \in \mathcal{U}^\omega \tag{30} $$

$$ a_i \leq h_i \leq b_i \quad \forall \omega \in \Omega^S, i \in \mathcal{N}^\omega \tag{31} $$

$$ H_e - (W_e + r_e) \leq h_i \leq H_e \quad \forall e \in E, i \in D_e \tag{32} $$

$$ H_e - W_e = a_e + \delta \kappa_e \quad \forall e \in E \tag{33} $$

$$ h_i \in \mathbb{R}^+ \quad i \in \mathcal{N} \tag{34} $$

$$ H_e \in [a_e + W_e, b_e] \quad \forall e \in E \tag{35} $$

$$ \kappa_e \in \mathbb{N} \quad \forall e \in E \tag{36} $$

$$ r_e \in \mathbb{R}^+ \quad \forall e \in E \tag{37} $$

## 5.3 Necessary condition

Problem (26) – (37) can easily be solved with a MILP solver but it is not realistic to solve for all insertion evaluations in LNS. Hence, we check a necessary condition in all insertion evaluations and the timing problem is solved only when the solution is complete or no additional insertion is possible. This section presents the necessary condition. It relies on a reduction of the schools’ time windows according to the existing services at this school in the current partial solution.

Let us consider a partial solution of the r-DARP-SBA including a route ω that visits a school *e* and assume that *e* is also visited by at least another route *w'* ≠ ω. Let us denote by N(*e*, ω), the set
of delivery nodes at school e that are not on route w. More formally,

$$ \mathcal{N}(e, \omega) = \left\{ d_u \in \mathcal{N}_e \mid u \in \bigcup_{\omega' \in \Omega \setminus \{\omega\}} \mathcal{U}_{\omega'} \right\}. $$

Note that if route w is the only route visiting e, then $\mathcal{N}(e, \omega) = \emptyset$.

Let $\Theta_{\omega,i}^{-}$ and $\Theta_{\omega,i}^{+}$ be the service times of a node i in an as early as possible and an as late as possible scheduling of a route $\omega$, respectively.

**Property** Given a partial solution S, a user $u \in U$ whose delivery location is school e, and a route $\omega \in \Omega^S$, a necessary condition for the existence of a synchronized solution when inserting $u \in \mathcal{U}$ in route $\omega$ is that: (i) the user u can be inserted in route $\omega$ with respect to constraints (29) – (31); (ii) all deliveries at school e on route $\omega$ must occur within the time window $[a'_{e}, b'_{e}]$, such that:

$$ \left\{ \begin{array}{l} a'_{e} = \max\{a_{i}, \max_{i \in \mathcal{N}(e,S,\omega)}\{\Theta_{i}^{-}\} - W_{e}\} \\ b'_{e} = \min\{b_{i}, \min_{i \in \mathcal{N}(e,S,\omega)}\{\Theta_{i}^{+}\} + W_{e}\}. \end{array} \right. $$

**Proof 1** *Proof:* Suppose that all deliveries to school e in the other routes of the solution are set to their earliest time

$$ h_i = \Theta_i^{-} \quad \forall i \in \mathcal{N}(e, \omega). $$

Suppose a new delivery to school e is inserted before $\max_{i \in \mathcal{N}(e,\omega)}\{\Theta_i^{-}\} - W_e$. Then, this delivery cannot be performed within the same dynamic time window as the latest delivery to school e (i.e. $\arg\max_{i \in \mathcal{N}(e,\omega)}\{\Theta_i^{-}\}$). Symmetrically, a delivery at e scheduled after $b'_{e}$ cannot be synchronized with at least one visit in e. ■

This time window reduction is updated after each insertion for all schools during the repair process. Then, an insertion is evaluated using the DARP route scheduling algorithm of Tellez et al. (2018). If the scheduling is not feasible, the insertion cannot result in a synchronized solution. If it is feasible, this scheduling algorithm returns the cost of the insertion, calculating the minimum duration of the route, choosing the best vehicle to perform it, allowing for en-route reconfigurations of reconfigurable vehicles.

Concerning requests that remain to be inserted: without synchronization, it is sufficient to re-evaluate insertions in the modified route $\omega$. In our case, all insertions in all routes containing a school e for which $[a'_{e}, b'_{e}]$ has been modified have to be recomputed.

# 6 Experimental design

In this section, we first introduce the instances used in the numerical experiments (section 6.1). In Section 6.2, we evaluate the main components of the SBAM matheuristic, and give some insights on its tuning and on the impact of some parameter values. Section 6.3 presents a comparison of the method with the algorithm of Tellez et al. (2018) to solve our instances as a DARP.

The results show the performance of the proposed algorithm and validate its use in analysis.

## 6.1 Description of instances and experimental setting

All numerical experiments are based on data provided by the Synergihp Rhône-Alpes company, which is a major paratransit operator in the area of Lyon, France. The company operates a heterogeneous fleet of about 200 vehicles. These vehicles have one or several possible inner configurations that provide different numbers of seats and wheelchair spaces.

In this study, we have considered a set of 34 schools in the area of Lyon and the 575 users transported to these schools. This dataset is called F15-575-34, where F stands for Full size instance, 15 is the instance number, 575 is the number of users and 34 the number of schools. To create smaller instances, F15-575-34 has been partitioned three times. First it has been partitioned into two large-sized (L) subsets, called L13-249-15 and L14-326-19. Second, it has been portioned into 4 medium-sized (M9-124-13 to M12-174-6) instances. And the last partition gave 8 small-sized (S1-50-5 to S8-99-3) instances,
leading to a total of 15 data sets, from 50 to 575 users and from 3 to 34 schools. The decomposition was done using a k-means clustering of the set of schools with a minimal number of 3 schools per cluster. The distance metrics between schools is the length of a direct trip from one school to another. The data sets considered in this paper are presented in Table 1.

<table><caption>Table 1: Set of users and schools</caption><thead><tr><th>Data set</th><th>|U|</th><th>|E|</th></tr></thead><tbody><tr><td>S1-50-5</td><td>50</td><td>5</td></tr><tr><td>S2-53-7</td><td>53</td><td>7</td></tr><tr><td>S3-54-4</td><td>54</td><td>4</td></tr><tr><td>S4-67-3</td><td>67</td><td>3</td></tr><tr><td>S5-75-3</td><td>75</td><td>3</td></tr><tr><td>S6-81-5</td><td>81</td><td>5</td></tr><tr><td>S7-96-4</td><td>96</td><td>4</td></tr><tr><td>S8-99-3</td><td>99</td><td>3</td></tr><tr><td>M9-124-13</td><td>124</td><td>13</td></tr><tr><td>M10-138-10</td><td>138</td><td>10</td></tr><tr><td>M11-139-5</td><td>139</td><td>5</td></tr><tr><td>M12-174-6</td><td>174</td><td>6</td></tr><tr><td>L13-249-15</td><td>249</td><td>15</td></tr><tr><td>L14-326-19</td><td>326</td><td>19</td></tr><tr><td>F15-575-34</td><td>575</td><td>34</td></tr></tbody></table>

This decomposition of the full instance into large, medium or small clusters is useful to evaluate the proposed method on different instances. It also makes sense from the practical point of view as managing small subsets of schools is generally preferred for practical purposes.

The fleet is decomposed into two categories of vehicles, as shown on Table 2.

<table><caption>Table 2: Features of the vehicle fleet. C<sup>f</sup>: fixed cost (in €), C<sup>d</sup>: distance cost (in €/km), C<sup>t</sup>: time cost (in €/h)</caption><thead><tr><th rowspan="2">Id</th><th colspan="3">Costs</th><th colspan="2">Config 1</th><th colspan="2">Config 2</th><th colspan="2">Config 3</th></tr><tr><th>C<sup>f</sup></th><th>C<sup>d</sup></th><th>C<sup>t</sup></th><th>Seat</th><th>Wheelchair</th><th>Seat</th><th>Wheelchair</th><th>Seat</th><th>Wheelchair</th></tr></thead><tbody><tr><td>v1</td><td>13.23</td><td>0.14</td><td>27.39</td><td>4</td><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>v2</td><td>13.92</td><td>0.16</td><td>27.39</td><td>6</td><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>v3</td><td>19.02</td><td>0.18</td><td>27.39</td><td>2</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><td>v4</td><td>19.87</td><td>0.21</td><td>27.39</td><td>7</td><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>v5</td><td>21.13</td><td>0.19</td><td>27.39</td><td>4</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><td>v6</td><td>22.48</td><td>0.26</td><td>27.39</td><td>7</td><td>1</td><td></td><td></td><td></td><td></td></tr><tr><td>v7</td><td>23.72</td><td>0.22</td><td>27.39</td><td>8</td><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>v8</td><td>21.06</td><td>0.24</td><td>27.39</td><td>6</td><td>0</td><td>5</td><td>1</td><td>4</td><td>2</td></tr><tr><td>v9</td><td>21.24</td><td>0.23</td><td>27.39</td><td>5</td><td>1</td><td>3</td><td>3</td><td></td><td></td></tr><tr><td>v10</td><td>21.74</td><td>0.24</td><td>27.39</td><td>5</td><td>2</td><td>3</td><td>3</td><td>2</td><td>4</td></tr><tr><td>v11</td><td>22.63</td><td>0.25</td><td>27.39</td><td>5</td><td>2</td><td>4</td><td>3</td><td></td><td></td></tr><tr><td>v12</td><td>25.52</td><td>0.24</td><td>27.39</td><td>7</td><td>1</td><td>6</td><td>2</td><td></td><td></td></tr><tr><td>v13</td><td>26.84</td><td>0.27</td><td>27.39</td><td>5</td><td>3</td><td>4</td><td>4</td><td>3</td><td>5</td></tr></tbody></table>

For each vehicle type, Table 2 indicates the fixed cost C<sup>f</sup> (in €) of using the vehicle, the distance cost C<sup>d</sup> (in €/km) and the time cost C<sup>t</sup> (in €/h). Vehicle types v1 to v7 have fixed capacity, i.e. a fixed number of seats and a number of spaces for wheelchairs. Vehicle types v8 to v13 are configurable:
their inner configuration can be changed en-route by folding or unfolding some seats, allowing for more flexible capacity. For example, type v8 vehicles have a *Config 1* with 6 seats. When one seat is folded, this creates space for one wheelchair (*Config 2*). When one more seat is folded, this creates space for a second wheelchair (*Config 3*).

For each data set, we have created two instances: one instance with the heterogeneous fleet described in Table 2, and one instance with a homogeneous fleet with vehicles of type v7 only. In this case, no distinction is made between users. To differentiate between the two instances, we use the letter h for the heterogeneous case. For example, M9-124-13-h refers to the instance with 124 users and a heterogeneous fleet.

All algorithms were implemented in C++ on an Intel Xeon Gold 5118 at 3.2GHz. The MILPs were solved with IBM Ilog Cplex 12.10. Different run times are used to solve all instances depending on the size of the problem. Small- (S), Medium- (M), Large- (L) and the Full- (F) size instances are solved in 1, 2, 4 and 8 hours respectively.

## 6.2 Evaluation of the matheuristic components and parameter values

The choice of the matheuristic components and the choice of the parameter values have been validated through extensive experiments on a subset of seven representative instances. The objective of this section is to present some of these experiments in order to highlight the impact of the components and parameters of the method on its performance. For each experiment, each instance was solved five times with the SBAM algorithm. All traveling costs are presented in terms of gaps with respect the best known solutions to these instances (denoted BKS and given in Appendix A – Table 11 – Column “20/60”). We present the average and minimum gaps obtained over these five runs. Following these experiments, the recommended values for the method parameters are summarized in Table 3.

<table><caption>Table 3: Recommended parameter values for the SBAM matheuristic</caption><thead><tr><th>Parameter</th><th>Value</th><th>Meaning</th></tr></thead><tbody><tr><td>R</td><td>2</td><td>Number of calls to shrinkMorningInterval.</td></tr><tr><td>T<sup>SCP</sup></td><td>10 sec</td><td>Time limit to solve the r-DARP-SBA.</td></tr><tr><td>N</td><td>20</td><td>Initial number of LNS iterations between two solving of the r-DARP-SBA.</td></tr><tr><td>ε</td><td>1.25</td><td>Increasing/decreasing rate of N.</td></tr><tr><td>Φ<sup>-</sup></td><td>10%</td><td>Minimal rate of requests removed by the LNS operators.</td></tr><tr><td>Φ<sup>+</sup></td><td>40%</td><td>Maximal rate of requests removed by the LNS operators.</td></tr><tr><td>ρ</td><td>5%</td><td>Record-to-Record parameter in LNS.</td></tr></tbody></table>

In Section 6.2.1, we first evaluate the different components of the proposed matheuristic. In Section 6.2.2, we show the impact of the number of interval shrinkage on the quality of the solutions found.

### 6.2.1 Components evaluation.

Table 4 presents the evaluation of six key components of the SBAM matheuristic. Each column evaluates a variant of the SBAM. Column 2 corresponds to the full SBAM configuration whereas in columns 3 to 8, one of the components was deactivated. In each column, we indicate the gap (in %) with the BKS among all configurations. The upper part of the table provides the average gap over five runs. The lower part presents the best gap over five runs.

Regarding each column of Table 4:

* Column **SBAM** denotes experiments where all components of Algorithm 1 are activated with the parameter values of Table 3. A first finding based on the best results out of five runs is that this configuration has a very small gap to the BKS over all experiments. It gives the BKS most of the time and it is always less than 0.3% from the BKS. Comparing the average cost over five runs with the BKS of each instance, we also see that it is quite robust, with only instance
<table><caption>Table 4: Evaluation of the key components of the proposed matheuristic. Each gap is given in % to the best known solution.</caption><thead><tr><th>Instance</th><th>SBAM</th><th>-dTWrel</th><th>-poolManagement</th><th>-KC</th><th>-reformulation</th><th>-NC</th><th>-MILP</th></tr></thead><tbody><tr><td>S3-54-4-h</td><td>0.29</td><td>0.32</td><td>0.76</td><td>0.35</td><td>1.00</td><td>0.20</td><td>1.05</td></tr><tr><td>S4-67-3</td><td>0.05</td><td>0.10</td><td>0.26</td><td>0.08</td><td>0.30</td><td>0.74</td><td>1.71</td></tr><tr><td>S5-75-3</td><td>0.04</td><td>0.47</td><td>0.53</td><td>0.70</td><td>1.48</td><td>0.60</td><td>3.22</td></tr><tr><td>S7-96-4-h</td><td>0.29</td><td>0.34</td><td>0.68</td><td>0.19</td><td>1.03</td><td>0.21</td><td>2.74</td></tr><tr><td>M9-124-13</td><td>1.20</td><td>1.28</td><td>1.85</td><td>2.19</td><td>3.09</td><td>3.00</td><td>5.28</td></tr><tr><td>M12-174-6-h</td><td>0.61</td><td>0.77</td><td>0.56</td><td>0.65</td><td>1.85</td><td>1.37</td><td>4.45</td></tr><tr><td>L13-249-15</td><td>0.45</td><td>0.64</td><td>0.96</td><td>3.07</td><td>1.33</td><td>5.75</td><td>5.15</td></tr><tr><td>Average</td><td>0.42</td><td>0.56</td><td>0.80</td><td>1.03</td><td>1.44</td><td>1.70</td><td>3.37</td></tr><tr><td>S3-54-4-h</td><td>0.10</td><td>0.09</td><td>0.24</td><td>0.09</td><td>0.75</td><td>0.00</td><td>0.76</td></tr><tr><td>S4-67-3</td><td>0.00</td><td>0.00</td><td>0.05</td><td>0.00</td><td>0.05</td><td>0.60</td><td>0.69</td></tr><tr><td>S5-75-3</td><td>0.00</td><td>0.06</td><td>0.03</td><td>0.03</td><td>0.18</td><td>0.04</td><td>1.75</td></tr><tr><td>S7-96-4-h</td><td>0.01</td><td>0.01</td><td>0.03</td><td>0.01</td><td>0.96</td><td>0.00</td><td>2.69</td></tr><tr><td>M9-124-13</td><td>0.13</td><td>0.00</td><td>0.28</td><td>1.16</td><td>1.95</td><td>2.05</td><td>4.26</td></tr><tr><td>M12-174-6-h</td><td>0.28</td><td>0.24</td><td>0.17</td><td>0.04</td><td>1.63</td><td>0.71</td><td>3.85</td></tr><tr><td>L13-249-15</td><td>0.00</td><td>0.20</td><td>0.40</td><td>1.23</td><td>0.73</td><td>5.11</td><td>4.84</td></tr><tr><td>Average</td><td>0.07</td><td>0.09</td><td>0.17</td><td>0.37</td><td>0.89</td><td>1.22</td><td>2.69</td></tr></tbody></table>

M9-124-13 that is slightly more than 1% from the BKS on average. We see that this instance with 13 schools and 123 transportation requests is also challenging for other configurations.

* In column -dTWrel, we evaluate the effect of the relaxation of the dynamic time windows. To prevent this relaxation, the record-to-record acceptance criterion of the LNS is modified so that only solutions that do not strictly satisfy the dynamic time windows are accepted. The new solution $S'$ is accepted when $g(S') < g(S^*) + \xi$, with $\xi = 1$ hour and $f(S') < f(S^*) \times (1 + \rho)$. The impact of this mechanism is rather limited for two reasons. First, evaluating $g$ by solving a timing problem each time $f(S') < f(S^*) \times (1 + \rho)$ is time consuming. Hence, removing this operation allows the SBAM algorithm to perform more iterations.

* In column -poolManagement, we evaluate the impact of the proposed management of the pool of routes. We compare with the pool management strategy of Tellez et al. (2018), derived from Grangier et al. (2017). With respect to these strategies, SBAM introduces two features: (i) the route pool is cleared each time r-DARP-SBA is solved (versus only when the solver fails to prove the optimality of the found solution within the time limit); (ii) the number $N$ is decreased or increased by a factor $\epsilon$ according to the performance of the solver (versus decreased only in Tellez et al. (2018)). From these experiments we see that the SBAM pool management slightly dominates the strategy of Tellez et al. (2018) when looking at the best solutions out of five runs. The improvement reaches 0.38% when looking at averages over five runs, so this mechanism also brings some robustness to the algorithm. This improvement is small but consistently observed over most runs and instances.

* Column -KC: KC stands for “Keep Current” solution. In matheuristics involving the solution of a route-based model, the best solution $S^*$ is generally taken as the current solution every time the model is solved. In SBAM (Algorithm 1, line 9) a new mechanism is introduced: the current solution is modified only when solving the r-DARP-SBA improves $S^*$. As we can see, this mechanism induces an interesting improvement of 0.3% on best solutions and an improvement of 0.6% on average. Given the simplicity of the mechanism, it is interesting to note that it has more impact than the two previous mechanisms.

* Column -reformulation evaluates the impact of the r-DARP-SBA reformulation proposed in Section 4.1. In these experiments, the DARP-SBA model of Section 3 was solved instead of the r-DARP-SBA. The only adaptation to the DARP-SBA model is the relaxation of the dynamic
time windows. The impact of the r-DARP-SBA reformulation is strong: it improves the best solution found on five runs by 0.8% and the average results by 1%.

* In column **-NC**, the necessary condition proposed in Section 5.3 is disabled. This condition reduces the chances of creating solutions that violate the dynamic time windows at schools, thus preventing insertions that violate this constraint. Filtering morning intervals has a strong impact, with an increase of more than 1% of the quality of the best solution out of five runs. It is critical for instances M9-124-13 and L13-249-15, which have a significantly greater number of schools than the other instances.

* In column **-MILP**, the solving of the r-DARP-SBA model has been disabled. This means that solutions are produced exclusively by the LNS. Although the LNS is able to produce feasible, being able to re-assemble routes generated at different iterations and to re-schedule these routes seems to be crucial for all instances.

In conclusion, solving the r-DARP-SBA on regular intervals is critical for the performance of the algorithm. We recommend using the r-DARP-SBA reformulation of the model, which provides a stronger formulation. The necessary conditions proposed to propagate temporal constraints on the morning interval in repair operators also help significantly. Additionally, the simple enhancements of the pool management process in SBAM have a positive impact on the performance of the algorithm. Finally, relaxing the dynamic time windows and preserving the current solution when the solver does not improve the best one slightly improves the algorithm's performance but these are not critical features.

### 6.2.2 Morning interval shrinkage component.

In this section we provide a specific analysis for the `shrinkMorningInterval` procedure. Table 5 shows the impact of *R*, the number of morning interval shrinkage operations. *R* = 0 means that no shrinkage is applied during the process. Column 1' refers to a single and final shrinkage after the 2/3 of the execution time. It is equivalent to *R* = 2 but the first shrinkage after 1/3 of the execution time is not performed.

<table><caption>Table 5: Impact of the time windows shrinkage parameter *R* (*: chosen parameter, gaps in % with respect to best known solutions)</caption><thead><tr><th>Instance</th><th>R = 0</th><th>1</th><th>2*</th><th>4</th><th>10</th><th>1'</th></tr></thead><tbody><tr><td>S3-54-4-h</td><td>0.64</td><td>0.57</td><td>0.29</td><td>0.52</td><td>0.36</td><td>0.43</td></tr><tr><td>S4-67-3</td><td>0.68</td><td>0.04</td><td>0.05</td><td>0.09</td><td>0.08</td><td>0.10</td></tr><tr><td>S5-75-3</td><td>0.28</td><td>0.16</td><td>0.04</td><td>0.06</td><td>0.08</td><td>0.47</td></tr><tr><td>S7-96-4-h</td><td>0.63</td><td>0.16</td><td>0.29</td><td>0.17</td><td>0.33</td><td>0.44</td></tr><tr><td>M9-124-13</td><td>3.13</td><td>2.17</td><td>1.20</td><td>1.79</td><td>2.00</td><td>1.82</td></tr><tr><td>M12-174-6-h</td><td>3.80</td><td>0.28</td><td>0.61</td><td>0.61</td><td>1.06</td><td>0.82</td></tr><tr><td>L13-249-15</td><td>2.36</td><td>0.80</td><td>0.45</td><td>0.91</td><td>1.19</td><td>0.92</td></tr><tr><td><em>Average</em></td><td>1.65</td><td>0.60</td><td>0.42</td><td>0.59</td><td>0.73</td><td>0.71</td></tr><tr><td>S3-54-4-h</td><td>0.09</td><td>0.14</td><td>0.10</td><td>0.29</td><td>0.19</td><td>0.25</td></tr><tr><td>S4-67-3</td><td>0.61</td><td>0.00</td><td>0.00</td><td>0.00</td><td>0.05</td><td>0.05</td></tr><tr><td>S5-75-3</td><td>0.07</td><td>0.06</td><td>0.00</td><td>0.00</td><td>0.06</td><td>0.06</td></tr><tr><td>S7-96-4-h</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.01</td><td>0.01</td></tr><tr><td>M9-124-13</td><td>0.87</td><td>1.60</td><td>0.13</td><td>0.25</td><td>1.31</td><td>1.15</td></tr><tr><td>M12-174-6-h</td><td>3.07</td><td>0.00</td><td>0.28</td><td>0.48</td><td>0.34</td><td>0.36</td></tr><tr><td>L13-249-15</td><td>1.51</td><td>0.54</td><td>0.00</td><td>0.59</td><td>0.58</td><td>0.50</td></tr><tr><td><em>Average</em></td><td>0.89</td><td>0.34</td><td>0.07</td><td>0.23</td><td>0.36</td><td>0.34</td></tr></tbody></table>

First of all, these results show that selecting the *R* = 2 shrinkage operation gives the best performance. This is found both for average values and for the best over five runs for most instances. On instances where *R* = 2 is not the best value, the gap to the best value is small. We also find that the impact of the shrinkage component is average, with only 0.82% of improvement for the best solutions
and 1.23% on average. Nevertheless, the component is critical for instance M12-174-6-h, reducing the gap to the BKS by around 3% with respect to R = 2. In addition, we see that using a large value of R does not improve the algorithm performance. Column 1' also illustrates our finding that using *shrinkMorningInterval* on uneven intervals during SBAM does not have a significant impact.

## 6.3 Performance evaluation: FSM-DARP-RC benchmark

To the best of our knowledge, no instances have been proposed in the literature for the DARP with SBA. For this reason, we evaluated the performance of the SBAM algorithm by comparing it with the matheuristic presented in Tellez et al. (2018) to solve the Fleet Size and Mix DARP with Reconfigurable Vehicles (FSM-DARP-RC). As stated in Section 2, this matheuristic combines a LNS with the solution of a set covering problem at regular intervals during the application of the algorithm. The length of these intervals is adjusted reactively to maintain an appropriate route pool size. Note that this method has been proven to be competitive with state-of-the-art DARP methods on classical DARP instances, and that it outperforms other algorithms on the heterogeneous DARP with configurable vehicle capacity. The LNS matheuristic of Tellez et al. (2018) is denoted by LNS in the remainder of this section.

To perform this comparison we first transformed our DARP-SBA instances into FSM-DARP-RC instances by setting, for each school, a time window within the original morning interval $[a_e, b_e]$. For each DARP-SBA instance we created two instances: The first instance has a delivery time window width of 20 minutes, positioned at time [8:20, 8:40] for all schools. The second instance has a time window [8:00, 9:00] which is equal to the morning interval for all schools. The SBAM algorithm is run by setting the dynamic time window width $W_e$ equal to the delivery time window width $b_e - a_e$ ($H_e = b_e$ for all schools $e \in \mathcal{E}$). Each algorithm has been run five times on each instance, with the same run times.

Table 6 presents the results of this benchmark on the 60 generated instances. The results are synthesized for each size of instance (S,M,L,F) by summing up the costs of all instances of the same type. Columns 2 to 6 report the minimum and average relative gaps obtained when the time windows at schools are 20 minutes wide. In this case, SBAM behaves slightly better than LNS. Columns 7 to 11 present the results obtained when the time windows are 1 hour wide. Here, SBAM also has slightly better performances than LNS except for the full instance for which LNS is significantly better.

<table><caption>Table 6: Comparison between the LNS matheuristic of Tellez et al. (2018) and SBAM on DARP instances derived from the DARP-SBA instances. All SBAM and LNS results are expressed as gaps (in %) with respect to best known solutions (column BKS).</caption><thead><tr><th rowspan="3"></th><th colspan="6">Delivery TW width: 20 minutes</th><th colspan="6">Delivery TW width: 60 minutes</th></tr><tr><th rowspan="2">BKS</th><th colspan="2">Best of 5 runs</th><th colspan="2">Average</th><th rowspan="2">BKS</th><th colspan="2">Best of 5 runs</th><th colspan="2">Average</th></tr><tr><th>SBAM</th><th>LNS</th><th>SBAM</th><th>LNS</th><th>SBAM</th><th>LNS</th><th>SBAM</th><th>LNS</th></tr></thead><tbody><tr><td colspan="11"><em>Heterogeneous fleet</em></td></tr><tr><td>S</td><td>8,485</td><td>0.00</td><td>0.01</td><td>0.01</td><td>0.15</td><td>7,582</td><td>0.06</td><td>0.04</td><td>0.23</td><td>0.45</td></tr><tr><td>M</td><td>8,336</td><td>0.00</td><td>0.06</td><td>0.13</td><td>0.32</td><td>7,333</td><td>0.00</td><td>0.22</td><td>0.32</td><td>0.77</td></tr><tr><td>L</td><td>8,290</td><td>0.00</td><td>0.34</td><td>0.31</td><td>0.50</td><td>7,076</td><td>0.01</td><td>0.30</td><td>0.53</td><td>1.07</td></tr><tr><td>F</td><td>8,264</td><td>0.06</td><td>0.00</td><td>0.51</td><td>0.16</td><td>7,021</td><td>3.11</td><td>0.00</td><td>4.59</td><td>0.95</td></tr><tr><td>Avg.</td><td>8,344</td><td>0.02</td><td>0.10</td><td>0.24</td><td>0.28</td><td>7,253</td><td>0.79</td><td>0.14</td><td>1.42</td><td>0.81</td></tr><tr><td colspan="11"><em>Homogeneous fleet</em></td></tr><tr><td>S</td><td>8,920</td><td>0.00</td><td>0.05</td><td>0.06</td><td>0.22</td><td>7,918</td><td>0.01</td><td>0.37</td><td>0.11</td><td>0.64</td></tr><tr><td>M</td><td>8,706</td><td>0.07</td><td>0.27</td><td>0.18</td><td>0.58</td><td>7,619</td><td>0.00</td><td>0.29</td><td>0.34</td><td>0.82</td></tr><tr><td>L</td><td>8,683</td><td>0.44</td><td>0.00</td><td>0.70</td><td>0.47</td><td>7,332</td><td>0.30</td><td>0.15</td><td>0.69</td><td>0.97</td></tr><tr><td>F</td><td>8,647</td><td>0.00</td><td>0.32</td><td>0.19</td><td>0.51</td><td>7,281</td><td>0.68</td><td>0.00</td><td>4.09</td><td>0.51</td></tr><tr><td>Avg.</td><td>8,739</td><td>0.13</td><td>0.16</td><td>0.28</td><td>0.44</td><td>7,538</td><td>0.24</td><td>0.20</td><td>1.30</td><td>0.73</td></tr><tr><td>Average</td><td>8,541</td><td>0.07</td><td>0.13</td><td>0.26</td><td>0.36</td><td>7,395</td><td>0.52</td><td>0.17</td><td>1.36</td><td>0.77</td></tr></tbody></table>

This indicates some limits to the size of the problems that can be solved with the SBAM algorithm. However, this does not have any practical consequences since SBA is seldom considered by authorities
at the scale of a large city but rather for a subset of schools.

In conclusion, these experiments validate the use of SBAM on the S, M and L instances to solve problems with significant similarities to the DARP-SBA.

# 7 Managerial insights

In this section, we use SBAM on the S, M and L instances of the DARP-SBA to evaluate the potential impact of SBA on cost and quality of service aspects. Results are aggregated by instance type, providing a synthesized view for the same set of requests under the S, M and L partitions. We first analyze the potential of improvement in cost in Section 7.1. Section 7.2 then provides more insights into the resulting solutions, observing ride times, route durations and number of vehicles in solutions. In Section 7.4, we then examine whether modifying the time discretization step for the school bell start time has an impact on solutions costs.

All results are given for the best results out of 5 runs with the same run times as those used to validate the algorithm.

## 7.1 Impact on cost

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 than one school. This corresponds to the situation where mixed loads are not authorized. Scenarios 20 and 60 correspond to DARP instances where the delivery time windows are [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 $W_e = 20$ minutes and a morning interval $[a_e, b_e] = [8:00, 9:00]$ for each school $e \in \mathcal{E}$. Table 7 shows the results of all scenarios aggregated by types of data set. The detailed results are available in Table 11 in Appendix.

<table><caption>Table 7: Impact of SBA on transportation cost with respect to a DARP model with no mixed load (scenario 0), 20 minutes width delivery time windows (20), or free deliveries within the morning interval (60).</caption><thead><tr><th rowspan="2"></th><th colspan="4">Impact of SBA</th><th colspan="3">Gap to scenario 20 (%)</th></tr><tr><th>0</th><th>20</th><th>20/60</th><th>60</th><th>0</th><th>20/60</th><th>60</th></tr></thead><tbody><tr><td colspan="8"><em>Heterogeneous fleet</em></td></tr><tr><td>S</td><td>9,223</td><td>8,485</td><td>8,040</td><td>7,582</td><td>8.70</td><td>-5.25</td><td>-10.65</td></tr><tr><td>M</td><td>9,223</td><td>8,336</td><td>7,743</td><td>7,333</td><td>10.64</td><td>-7.11</td><td>-12.03</td></tr><tr><td>L</td><td>9,223</td><td>8,290</td><td>7,571</td><td>7,076</td><td>11.25</td><td>-8.68</td><td>-14.64</td></tr><tr><td>Avg.</td><td>9,223</td><td>8,370</td><td>7,784</td><td>7,330</td><td>10.20</td><td>-7.01</td><td>-12.44</td></tr><tr><td colspan="8"><em>Homogeneous fleet</em></td></tr><tr><td>S</td><td>9,973</td><td>8,920</td><td>8,377</td><td>7,918</td><td>11.81</td><td>-6.09</td><td>-11.23</td></tr><tr><td>M</td><td>9,973</td><td>8,706</td><td>8,031</td><td>7,619</td><td>14.56</td><td>-7.75</td><td>-12.48</td></tr><tr><td>L</td><td>9,973</td><td>8,683</td><td>7,928</td><td>7,332</td><td>14.86</td><td>-8.69</td><td>-15.56</td></tr><tr><td>Avg.</td><td>9,973</td><td>8,770</td><td>8,112</td><td>7,623</td><td>13.74</td><td>-7.51</td><td>-13.09</td></tr><tr><td>Average</td><td></td><td></td><td></td><td></td><td>11.97</td><td>-7.26</td><td>-12.76</td></tr></tbody></table>

Several conclusions can be drawn from Table 7. First, the greatest savings can be achieved by allowing mixed loads. If we compare scenarios 0 and 20, mixed loads achieve around 10% savings on routing costs in the case of a heterogeneous fleet and up to 14% with a homogeneous fleet. 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 are gathered in clusters of increasing sizes, we see that mixed loads allow for greater savings in instances 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.
## 7.2 Impact on ride times, routes and vehicles

Table 8 details the impact of SBA on three aspects: the users ride time, route durations and the total number of routes in solutions. The evaluation is performed by comparing scenario 20 to scenario 20/60.

<table><thead><tr><th rowspan="3"></th><th colspan="2">Ride Time</th><th colspan="2">Route duration</th><th colspan="2">Nb Routes</th></tr><tr><th>min</th><th>Gap (%)</th><th>min</th><th>Gap (%)</th><th>#</th><th>Gap (%)</th></tr><tr><th>20</th><th>20/60</th><th>20</th><th>20/60</th><th>20</th><th>20/60</th></tr></thead><tbody><tr><td colspan="7"><em>Heterogeneous fleet</em></td></tr><tr><td>S</td><td>29.22</td><td>-4.68</td><td>98.48</td><td>12.04</td><td>109.00</td><td>-12.84</td></tr><tr><td>M</td><td>29.34</td><td>-5.58</td><td>100.56</td><td>14.63</td><td>105.00</td><td>-16.19</td></tr><tr><td>L</td><td>29.51</td><td>-7.59</td><td>98.48</td><td>18.62</td><td>107.00</td><td>-19.63</td></tr><tr><td>Avg.</td><td>29.36</td><td>-5.95</td><td>99.18</td><td>15.09</td><td>107.00</td><td>-16.22</td></tr><tr><td colspan="7"><em>Homogeneous fleet</em></td></tr><tr><td>S</td><td>29.61</td><td>-3.41</td><td>99.78</td><td>13.28</td><td>106.00</td><td>-14.15</td></tr><tr><td>M</td><td>29.91</td><td>-4.40</td><td>103.36</td><td>17.22</td><td>101.00</td><td>-17.82</td></tr><tr><td>L</td><td>30.27</td><td>-6.45</td><td>101.65</td><td>15.55</td><td>102.00</td><td>-17.65</td></tr><tr><td>Avg.</td><td>29.93</td><td>-4.75</td><td>101.60</td><td>15.35</td><td>103.00</td><td>-16.54</td></tr><tr><td>Average</td><td>29.67</td><td>-5.38</td><td>100.51</td><td>15.25</td><td>105.00</td><td>-16.35</td></tr></tbody></table>

Table 8: Impact of SBA on the average ride times, the average duration of routes and the number of routes.

An important result is that, although it is not explicitly integrated into the DARP-SBA objective function, SBA saves some travel time for users, with an average ride time decreased by 5.95% on average for a heterogeneous fleet of vehicles.

Second, SBA achieve a significant decrease in number of vehicles, with longer routes. This is highly desirable in our application, where qualified drivers are hard to find, in particular because of part-time contracts.

## 7.3 Number of school services per route

Mixing users from different schools in vehicles implies that one vehicle route can serve several schools. When all schools have the same delivery time window, this potential is considerably reduced. Table 9 analyzes the impact of SBA on this aspect by comparing the number of routes with one to six school services in scenarios 20 and 20/60. The overall number of routes in solutions appears in the third column. The following columns show that the decrease achieved by SBA mainly concerns the routes visiting 1 or 2 schools. By contrast, the number of routes visiting more than 2 schools increases, which is also consistent with the previously observed increase in route duration. This confirms that SBA achieve some savings by a better pooling routes among schools.

## 7.4 Impact of time discretization for the school bell time

It is obvious that certain times are more desirable than others for school bell times. The DARP-SBA model offers an easy integration of time discretization. Table 10 measures the impact of the discretization step $\Delta$ on solution costs. The results are aggregated instance sizes. These experiments show that the impact of time discretization is rather limited on cost, provided it remains reasonable. Taking a school bell time that is a multiple of five or ten minutes has a nearly negligible impact. A larger time step of 20 minutes reduces the potential of cost reduction by reducing the pooling effect that is obtained on large instance sizes.
<table><caption>Table 9: Number of routes visiting *n* schools</caption><thead><tr><th rowspan="2">Scenario</th><th rowspan="2"></th><th rowspan="2"># routes</th><th colspan="6">Nb routes with n schools</th></tr><tr><th>n = 1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td colspan="9" style="text-align: left; font-style: italic;">Heterogeneous fleet</td></tr><tr><td rowspan="2">S</td><td>20</td><td>109</td><td>55</td><td>45</td><td>9</td><td>0</td><td>0</td><td>0</td></tr><tr><td>20/60</td><td>95</td><td>40</td><td>38</td><td>16</td><td>1</td><td>0</td><td>0</td></tr><tr><td rowspan="2">M</td><td>20</td><td>105</td><td>43</td><td>47</td><td>13</td><td>2</td><td>0</td><td>0</td></tr><tr><td>20/60</td><td>88</td><td>21</td><td>45</td><td>21</td><td>1</td><td>0</td><td>0</td></tr><tr><td rowspan="2">L</td><td>20</td><td>107</td><td>37</td><td>56</td><td>12</td><td>2</td><td>0</td><td>0</td></tr><tr><td>20/60</td><td>86</td><td>14</td><td>41</td><td>25</td><td>5</td><td>1</td><td>0</td></tr><tr><td colspan="9" style="text-align: left; font-style: italic;">Homogeneous fleet</td></tr><tr><td rowspan="2">S</td><td>20</td><td>106</td><td>52</td><td>46</td><td>8</td><td>0</td><td>0</td><td>0</td></tr><tr><td>20/60</td><td>91</td><td>36</td><td>42</td><td>12</td><td>1</td><td>0</td><td>0</td></tr><tr><td rowspan="2">M</td><td>20</td><td>101</td><td>34</td><td>47</td><td>19</td><td>1</td><td>0</td><td>0</td></tr><tr><td>20/60</td><td>83</td><td>18</td><td>40</td><td>20</td><td>5</td><td>0</td><td>0</td></tr><tr><td rowspan="2">L</td><td>20</td><td>102</td><td>33</td><td>50</td><td>18</td><td>1</td><td>0</td><td>0</td></tr><tr><td>20/60</td><td>84</td><td>19</td><td>34</td><td>22</td><td>8</td><td>1</td><td>0</td></tr></tbody></table>

<table><caption>Table 10: Impact of the discretization step Δ</caption><thead><tr><th rowspan="2"></th><th colspan="3">Δ</th><th colspan="3">Gap to 5 min (%)</th></tr><tr><th>1 sec</th><th>5 min</th><th>10 min</th><th>1 sec</th><th>10 min</th><th>20 min</th></tr></thead><tbody><tr><td colspan="7" style="text-align: left; font-style: italic;">Heterogeneous fleet</td></tr><tr><td>S</td><td>8,029</td><td>8,040</td><td>8,045</td><td>8,090</td><td>-0.13</td><td>0.07</td><td>0.62</td></tr><tr><td>M</td><td>7,713</td><td>7,743</td><td>7,776</td><td>7,912</td><td>-0.39</td><td>0.43</td><td>2.19</td></tr><tr><td>L</td><td>7,574</td><td>7,571</td><td>7,632</td><td>7,866</td><td>0.04</td><td>0.81</td><td>3.90</td></tr><tr><td>Avg.</td><td>7,772</td><td>7,784</td><td>7,818</td><td>7,956</td><td>-0.16</td><td>0.44</td><td>2.24</td></tr><tr><td colspan="7" style="text-align: left; font-style: italic;">Homogeneous fleet</td></tr><tr><td>S</td><td>8,374</td><td>8,377</td><td>8,406</td><td>8,489</td><td>-0.03</td><td>0.35</td><td>1.34</td></tr><tr><td>M</td><td>8,010</td><td>8,031</td><td>8,048</td><td>8,172</td><td>-0.26</td><td>0.22</td><td>1.76</td></tr><tr><td>L</td><td>7,904</td><td>7,895</td><td>7,962</td><td>8,052</td><td>0.11</td><td>0.86</td><td>1.99</td></tr><tr><td>Avg.</td><td>8,096</td><td>8,101</td><td>8,139</td><td>8,238</td><td>-0.06</td><td>0.47</td><td>1.70</td></tr><tr><td>Average</td><td></td><td></td><td></td><td></td><td>-0.11</td><td>0.46</td><td>1.97</td></tr></tbody></table>
# 8 Conclusion

In this paper we define the Dial-A-Ride Problem with School Bell time Adjustment. We integrate operational constraints related to paratransit: time windows and maximum ride times, passengers in wheelchairs and a heterogeneous fleet of vehicles with reconfigurable capacities. To solve this problem, we introduce the School Bell time Adjustment Matheuristic algorithm, which integrates a Large Neighborhood Search (LNS) metaheuristic and the periodic use of a MILP solver to solve a route-based formulation of the problem. This algorithm is enhanced by a mechanism which progressively shrinks arrival time windows. Adjusting school bell times creates synchronization constraints at schools, thus making routes interdependent. A key feature of the solution method is its ability to insert users in a route without checking the feasibility of all routes. This is done through a dedicated necessary condition evaluated to efficiently check insertion feasibility in LNS.

The performance of the proposed method is evaluated on real-life instances provided by a paratransit company in the area of Lyon, France. The numerical experiments first show the efficiency of the proposed method with respect to the state-of-the art algorithm of Tellez et al. (2018) on the DARP with reconfigurable vehicle capacity. Then, the main findings of this paper are:

* A pooling approach on transportation can generate 10 % savings on average on our case study;

* and SBA can decrease the transportation costs by approximately an extra 7 percent.

* SBA also improves the ride time for users by approximately 6 % on average.

* The DARP-SBA solutions have fewer vehicles and longer routes, which is appreciated in practice to design attractive timetables for drivers.

* The proposed model integrates a simple approach for the discretization of the school start time interval. We show that a reasonable discretization step has a low impact on cost.

For future work, it is clear that a column generation approach would be of interest for the exact solution of the DARP-SBA. Improving the efficiency of the method on large problems would allow SBA problems to be addressed for school bus routing with mixed loads. An application perspective would then be to extend the approach to review the assignment of users to schools in conjunction with transportation routes.

# Acknowledgment

We would like to thank the European Union through the European Regional Development Fund (ERDF) and the French Région Auvergne-Rhône-Alpes for their financial support for the NOMAd project.
A Additional results

<table><caption>Table 11: Detailed result for the DARP with school bell time adjustment</caption><thead><tr><th rowspan="2">Instance</th><th colspan="4">Impact of school bell time adjustment</th><th colspan="3">Gap to scenario 20 (%)</th></tr><tr><th>0</th><th>20</th><th colspan="2">SBA</th><th>0</th><th colspan="2">SBA</th></tr><tr><th></th><th></th><th></th><th>20/60</th><th>60</th><th></th><th>20/60</th><th>60</th></tr></thead><tbody><tr><td>S1-50-5-h</td><td>804.00</td><td>772.18</td><td>685.76</td><td>678.45</td><td>4.12</td><td>-11.19</td><td>-12.14</td></tr><tr><td>S2-53-7-h</td><td>690.30</td><td>555.48</td><td>502.89</td><td>478.89</td><td>24.27</td><td>-9.47</td><td>-13.79</td></tr><tr><td>S3-54-4-h</td><td>582.70</td><td>539.81</td><td>507.12</td><td>464.96</td><td>7.95</td><td>-6.06</td><td>-13.87</td></tr><tr><td>S4-67-3-h</td><td>1,282.00</td><td>1,190.91</td><td>1,177.51</td><td>1,089.57</td><td>7.65</td><td>-1.13</td><td>-8.51</td></tr><tr><td>S5-75-3-h</td><td>1,169.60</td><td>1,121.12</td><td>1,091.38</td><td>1,016.37</td><td>4.32</td><td>-2.65</td><td>-9.34</td></tr><tr><td>S6-81-5-h</td><td>1,408.50</td><td>1,269.41</td><td>1,178.43</td><td>1,128.25</td><td>10.96</td><td>-7.17</td><td>-11.12</td></tr><tr><td>S7-96-4-h</td><td>2,336.00</td><td>2,180.65</td><td>2,114.13</td><td>2,047.11</td><td>7.12</td><td>-3.05</td><td>-6.12</td></tr><tr><td>S8-99-3-h</td><td>950.30</td><td>855.94</td><td>783.12</td><td>678.52</td><td>11.02</td><td>-8.51</td><td>-20.73</td></tr><tr><td>M9-124-13-h</td><td>1,733.40</td><td>1,453.64</td><td>1,310.64</td><td>1,210.29</td><td>19.25</td><td>-9.84</td><td>-16.74</td></tr><tr><td>M10-138-10-h</td><td>2,312.70</td><td>2,081.58</td><td>1,899.15</td><td>1,791.60</td><td>11.10</td><td>-8.76</td><td>-13.93</td></tr><tr><td>M11-139-5-h</td><td>3,057.40</td><td>2,860.87</td><td>2,775.24</td><td>2,664.33</td><td>6.87</td><td>-2.99</td><td>-6.87</td></tr><tr><td>M12-174-6-h</td><td>2,119.90</td><td>1,940.02</td><td>1,758.17</td><td>1,667.23</td><td>9.27</td><td>-9.44</td><td>-14.06</td></tr><tr><td>L13-249-15-h</td><td>3,848.30</td><td>3,493.99</td><td>3,177.49</td><td>2,999.93</td><td>10.14</td><td>-9.06</td><td>-14.14</td></tr><tr><td>L14-326-19-h</td><td>5,375.20</td><td>4,796.63</td><td>4,393.73</td><td>4,076.76</td><td>12.06</td><td>-8.40</td><td>-15.01</td></tr><tr><td>Average</td><td></td><td></td><td></td><td></td><td>10.44</td><td>-6.97</td><td>-12.60</td></tr><tr><td>S1-50-5</td><td>886.70</td><td>843.80</td><td>713.77</td><td>706.12</td><td>5.08</td><td>-15.41</td><td>-16.32</td></tr><tr><td>S2-53-7</td><td>854.50</td><td>633.96</td><td>580.01</td><td>546.41</td><td>34.79</td><td>-8.51</td><td>-13.81</td></tr><tr><td>S3-54-4</td><td>661.30</td><td>594.05</td><td>538.81</td><td>505.21</td><td>11.32</td><td>-9.30</td><td>-14.96</td></tr><tr><td>S4-67-3</td><td>1,335.00</td><td>1,221.71</td><td>1,207.96</td><td>1,115.02</td><td>9.27</td><td>-1.13</td><td>-8.73</td></tr><tr><td>S5-75-3</td><td>1,211.20</td><td>1,117.87</td><td>1,078.40</td><td>1,017.62</td><td>8.35</td><td>-3.53</td><td>-8.97</td></tr><tr><td>S6-81-5</td><td>1,481.10</td><td>1,308.10</td><td>1,217.31</td><td>1,148.89</td><td>13.23</td><td>-6.94</td><td>-12.17</td></tr><tr><td>S7-96-4</td><td>2,490.00</td><td>2,289.49</td><td>2,185.86</td><td>2,119.58</td><td>8.76</td><td>-4.53</td><td>-7.42</td></tr><tr><td>S8-99-3</td><td>1,053.90</td><td>911.34</td><td>854.99</td><td>759.95</td><td>15.64</td><td>-6.18</td><td>-16.61</td></tr><tr><td>M9-124-13</td><td>1,985.60</td><td>1,585.31</td><td>1,403.29</td><td>1,310.68</td><td>25.25</td><td>-11.48</td><td>-17.32</td></tr><tr><td>M10-138-10</td><td>2,493.80</td><td>2,191.66</td><td>1,976.31</td><td>1,857.39</td><td>13.79</td><td>-9.83</td><td>-15.25</td></tr><tr><td>M11-139-5</td><td>3,229.30</td><td>2,967.28</td><td>2,850.29</td><td>2,744.06</td><td>8.83</td><td>-3.94</td><td>-7.52</td></tr><tr><td>M12-174-6</td><td>2,265.20</td><td>1,961.92</td><td>1,801.48</td><td>1,707.13</td><td>15.46</td><td>-8.18</td><td>-12.99</td></tr><tr><td>L13-249-15</td><td>4,102.60</td><td>3,626.82</td><td>3,245.63</td><td>3,071.77</td><td>13.12</td><td>-10.51</td><td>-15.30</td></tr><tr><td>L14-326-19</td><td>5,871.30</td><td>5,056.96</td><td>4,683.20</td><td>4,261.22</td><td>16.10</td><td>-7.39</td><td>-15.74</td></tr><tr><td>Average</td><td></td><td></td><td></td><td></td><td>14.07</td><td>-7.65</td><td>-12.88</td></tr><tr><td>Average</td><td></td><td></td><td></td><td></td><td>12.32</td><td>-7.30</td><td>-12.84</td></tr></tbody></table>
References

ANAP. Améliorer la gestion des transports de personnes handicapées (improving the management of transportation for people with disabilities). Technical report, Appui santé & médico social (Health & medico-social support), 2016.

Dipayan Banerjee and Karen Smilowitz. Incorporating equity into the school bus scheduling problem. *Transportation Research Part E: Logistics and Transportation Review*, 131:228–246, November 2019. ISSN 1366-5545. doi: 10.1016/j.tre.2019.08.006. URL http://www.sciencedirect.com/science/article/pii/S136655451831319X.

Dimitris Bertsimas, Arthur Delarue, and Sebastien Martin. Optimizing schools' start time and bus routes. *Proceedings of the National Academy of Sciences*, 116(13):5943–5948, March 2019. ISSN 0027-8424, 1091-6490. doi: 10.1073/pnas.1811462116. URL https://www.pnas.org/content/116/13/5943.

Jeffrey Braca, Julien Bramel, Bruce Posner, and David Simchei-Levi. A computerized approach to the New York City school bus routing problem. *IIE Transactions*, 29(8):693–702, Aug 1997.

Jan Christiaens and Greet Vanden Berghe. Slack Induction by String Removals for Vehicle Routing Problems. *Transportation Science*, 54(2):417–433, 2020. doi: 10.1287/trsc.2019.0914.

Jacques Desrosiers, J.A. Ferland, Jean-Marc Rousseau, G. Lapalme, and L. Chapleau. Transcol: A multi-period school bus routing and scheduling system. *TIMS Studies in the Management Sciences*, 22:47–71, 01 1986.

Karl F. Doerner and Juan-José Salazar-González. Pickup-and-Delivery Problems for People Transportation. In Paolo Toth and Daniele Vigo, editors, *Vehicle Routing*, pages 193–212. Society for Industrial and Applied Mathematics, Philadelphia, PA, November 2014.

M. Drexel. Synchronization in Vehicle Routing–A Survey of VRPs with Multiple Synchronization Constraints. *Transportation Science*, 46(3):297–316, March 2012.

William A. Ellegood, Stanislaus Solomon, Jeremy North, and James F. Campbell. School bus routing problem: Contemporary trends and research directions. *Omega*, 95:102056, 2020. doi: https://doi.org/10.1016/j.omega.2019.03.014.

Dominique Feillet, Thierry Garaix, Fabien Lehuédé, Olivier Péton, and Dominique Quadri. A new consistent vehicle routing problem for the transportation of people with disabilities. *Networks*, 63(3):211–224, 2014.

Armin Fügenschuh. Solving a school bus scheduling problem with integer programming. *European Journal of Operational Research*, 193(3):867–884, March 2009. ISSN 0377-2217. doi: 10.1016/j.ejor.2007.10.055. URL http://www.sciencedirect.com/science/article/pii/S0377221707010910.

Armin Fügenschuh. A set partitioning reformulation of a school bus scheduling problem. *Journal of Scheduling*, 14(4):307–318, August 2011. ISSN 1099-1425. doi: 10.1007/s10951-011-0234-0. URL https://doi.org/10.1007/s10951-011-0234-0.

Armin Fügenschuh and Alexander Martin. A multicriteria approach for optimizing bus schedules and school starting times. *Annals of Operations Research*, 147(1):199–216, October 2006. ISSN 0254-5330, 1572-9338. doi: 10.1007/s10479-006-0066-z. URL http://link.springer.com/10.1007/s10479-006-0066-z.

Philippe Grangier, Michel Gendreau, Fabien Lehuédé, and Louis-Martin Rousseau. A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking. *Computers & Operations Research*, 84:116–126, August 2017.

Timo Gschwind and Michael Drexel. Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem. *Transportation Science*, 53(2):480–491, April 2019. ISSN 00411655. doi: 10.1287/trsc.2018.0837. URL http://search.ebscohost.com/login.aspx?direct=true&db=a9h&AN=135968121&lang=fr&site=ehost-live. Publisher: INFORMS: Institute for Operations Research.

Timo Gschwind and Stefan Irnich. Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem. *Transportation Science*, 49(2):335–354, May 2015. ISSN 00411655. doi: 10.1287/trsc.2014.0531. URL http://search.ebscohost.com/login.aspx?direct=true&db=a9h&AN=111060812&lang=fr&site=ehost-live. Publisher: INFORMS: Institute for Operations Research.

Christoph Hempsch and Stefan Irnich. Vehicle routing problems with inter-tour resource constraints. In *The Vehicle Routing Problem: Latest Advances and New Challenges*, pages 421–444. Springer, 2008.

Sin C. Ho, W.Y. Szeto, Yong-Hong Kuo, Janny M.Y. Leung, Matthew Petering, and Terence W.H. Tou. A survey of dial-a-ride problems: Literature review and recent developments. *Transportation Research Part B: Methodological*, 111:395–421, 2018.

Fabien Lehuédé, Renaud Masson, Sophie N Parragh, Olivier Péton, and Fabien Tricoire. A multi-criteria large neighbourhood search for the transportation of disabled people. *Journal of the Operational Research Society*, 65(7):983–1000, 2013.
Renaud Masson, Fabien Lehuédé, and Olivier Péton. Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers. *Operations Research Letters*, 41(3):211–215, May 2013. ISSN 01676377. doi: 10.1016/j.orl.2013.01.007. URL https://linkinghub.elsevier.com/retrieve/pii/S0167637713000084.

Renaud Masson, Fabien Lehuédé, and Olivier Péton. The Dial-A-Ride Problem with Transfers. *Computers & Operations Research*, 41:12–23, January 2014. ISSN 03050548. doi: 10.1016/j.cor.2013.07.020. URL https://linkinghub.elsevier.com/retrieve/pii/S0305054813001998.

Yves Molenbruch, Kris Braekers, and An Caris. Typology and literature review for dial-a-ride problems. *Annals of Operations Research*, 259(1-2):295–325, December 2017.

Junhyuk Park and Byung-In Kim. The school bus routing problem: A review. *European Journal of Operational Research*, 202(2):311–319, April 2010. ISSN 0377-2217. doi: 10.1016/j.ejor.2009.05.017. URL http://www.sciencedirect.com/science/article/pii/S037722170900349X.

Junhyuk Park, Hyunchul Tae, and Byung-In Kim. A post-improvement procedure for the mixed load school bus routing problem. *European Journal of Operational Research*, 217(1):204 – 213, 2012. doi: https://doi.org/10.1016/j.ejor.2011.08.022.

David Pisinger and Stefan Ropke. A general heuristic for vehicle routing problems. *Computers & Operations Research*, 34(8):2403–2435, 2007. ISSN 03050548.

Samuel Raff. Routing and scheduling of vehicles and crews: The state of the art. *Computers & Operations Research*, 10(2):63 – 211, 1983. Routing and Scheduling of Vehicles and Crews. The State of the Art.

Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. *Transportation Science*, 40(4):455–472, 2006a.

Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. *Transportation Science*, 40(4):455–472, 2006b.

M. Spada, M. Bierlaire, and Th. M. Liebling. Decision-aiding methodology for the school bus routing and scheduling problem. *Transportation Science*, 39(4):477–490, 2005. doi: 10.1287/trsc.1040.0096.

Remy Spliet and Guy Desaulniers. The discrete time window assignment vehicle routing problem. *European Journal of Operational Research*, 244(2):379–391, July 2015. doi: 10.1016/j.ejor.2015.01.020.

Remy Spliet and Adriana F. Gabor. The Time Window Assignment Vehicle Routing Problem. *Transportation Science*, 49(4):721–731, November 2015. ISSN 0041-1655, 1526-5447. doi: 10.1287/trsc.2013.0510.

Oscar Tellez, Samuel Vercraene, Fabien Lehuédé, Olivier Péton, and Thibaud Monteiro. The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity. *Transportation Research Part C: Emerging Technologies*, 91:99 – 123, 2018.

Oscar Tellez, Samuel Vercraene, Fabien Lehuédé, Olivier Péton, and Thibaud Monteiro. The time-consistent dial-a-ride problem. *to appear in Networks*, 2021. doi: 10.1002/net.22063.

Zhongxiang Wang and Ali Haghani. Column generation-based stochastic school bell time and bus scheduling optimization. *European Journal of Operational Research*, 286(3):1087 – 1102, 2020. ISSN 0377-2217. doi: 10.1016/j.ejor.2020.03.071.

Julia Yan. *From data to decisions in urban transit and logistics*. PhD thesis, Massachusetts Institute of Technology, 2020.

Liwei Zeng, Sunil Chopra, and Karen Smilowitz. A Bounded Formulation for The School Bus Scheduling Problem. arXiv:1803.09040 [cs, math], March 2018. URL http://arxiv.org/abs/1803.09040. arXiv: 1803.09040.