Samuel Vercraene

Fabien Lehuédé

Thibaud Monteiro

Olivier Péton

The Dial-A-Ride Problem with School Bell time Adjustment

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

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.

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 [START_REF] Anap | Améliorer la gestion des transports de personnes handicapées (improving the management of transportation for people with disabilities)[END_REF][START_REF] Yan | From data to decisions in urban transit and logistics[END_REF]. 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 [START_REF] Spada | Decision-aiding methodology for the school bus routing and scheduling problem[END_REF]. 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.

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 [START_REF] Doerner | Pickup-and-Delivery Problems for People Transportation[END_REF][START_REF] Sin | A survey of dial-a-ride problems: Literature review and recent developments[END_REF][START_REF] Molenbruch | Typology and literature review for dial-a-ride problems[END_REF]. The latest state of the art DARP algorithms [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] and [START_REF] Christiaens | Slack Induction by String Removals for Vehicle Routing Problems[END_REF]) 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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF]. 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 andKim 2010, Ellegood et al. 2020). According to [START_REF] Desrosiers | Transcol: A multi-period school bus routing and scheduling system[END_REF], 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 [START_REF] Samuel Raff | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF] and [START_REF] Desrosiers | Transcol: A multi-period school bus routing and scheduling system[END_REF]. 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. [START_REF] Fügenschuh | Solving a school bus scheduling problem with integer programming[END_REF] 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 [START_REF] Fügenschuh | A multicriteria approach for optimizing bus schedules and school starting times[END_REF], in [START_REF] Fügenschuh | A set partitioning reformulation of a school bus scheduling problem[END_REF] (set partitioning formulation), in [START_REF] Zeng | A Bounded Formulation for The School Bus Scheduling Problem[END_REF] and in [START_REF] Wang | Column generation-based stochastic school bell time and bus scheduling optimization[END_REF]. [START_REF] Banerjee | Incorporating equity into the school bus scheduling problem[END_REF] 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. [START_REF] Bertsimas | Optimizing schools' start time and bus routes[END_REF] 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 compat RtR t 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 [START_REF] Braca | A computerized approach to the New York City school bus routing problem[END_REF][START_REF] Spada | Decision-aiding methodology for the school bus routing and scheduling problem[END_REF][START_REF] Park | A post-improvement procedure for the mixed load school bus routing problem[END_REF]. A few additional papers are mentioned in the recent survey of [START_REF] Ellegood | School bus routing problem: Contemporary trends and research directions[END_REF], 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 [START_REF] Drexl | Synchronization in Vehicle Routing-A Survey of VRPs with Multiple Synchronization Constraints[END_REF]. It is related to the concept of dynamic time windows. According to [START_REF] Gschwind | Effective Handling of Dynamic Time Windows and Its Application to Solving the Dial-a-Ride Problem[END_REF]: "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 [START_REF] Hempsch | Vehicle routing problems with inter-tour resource constraints[END_REF]. This type of constraint has already been met in people transportation in the time-consistent VRP [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] or the time-consistent DARP [START_REF] Tellez | The time-consistent dial-a-ride problem[END_REF]. It is also met in goods distribution in the time window assignment VRP [START_REF] Spliet | The Time Window Assignment Vehicle Routing Problem[END_REF] and its discrete counterpart [START_REF] Spliet | The discrete time window assignment vehicle routing problem[END_REF]. 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. [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] and [START_REF] Tellez | The time-consistent dial-a-ride problem[END_REF] 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 papers 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.

The Dial A Ride Problem with School Bell Time Adjustment

(DARP-SBA)

Problem settings

We consider a set of schools denoted by E. The set of users is denoted by U. Each user u ∈ 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 S u and q W u 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 P = {p u |u ∈ U } the set of pickup nodes and D = {d u |u ∈ U } the set of delivery nodes. According to this notation, deliveries at the same school are represented by separate nodes in D. The set of nodes that model a delivery at school e ∈ E is denoted by D e . The depot is modeled by nodes o + and o -, which represent the departure and return of all vehicle routes, respectively. The set N of all nodes is defined as

N = P ∪ D ∪ {o + , o -}.
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 ∈ 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 δ e . This means that the bell time at school e has to be chosen within the set {a e + κ × δ e |κ ∈ N, a e + κ × δ e ≤ 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 ∈ P ∪ {o The service duration at any node i ∈ 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 ∈ N to j ∈ 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.

Representation of a solution

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

Figure 1 gives a graphical representation of a solution with two routes ω 1 and ω 2 visiting a school e.

route (in green) during which all visits to the school must be synchronized.

Mathematical formulation

To model the DARP-SBA we introduce the following variables: For each route ω ∈ Ω, the binary variable y ω is equal to 1 if ω is selected, 0 otherwise. Variable H e models the school bell time at school e ∈ E. To implement the discretization of the morning interval, we introduce the integer variable κ e ∈ N for all e ∈ E. It implements the relation H e = a e + κ e × δ. Finally, since waiting times may be introduced in a route to comply with school start times, we introduce variable h ω i ∈ [a i , b i ], which represent the time at which route ω starts serving node i ∈ N ω .

The DARP-SBA can be formulated as follows:

min f = ω∈Ω c ω y ω + C time ω (h ω ω[nω] -h ω ω[1] ) (1)
s.t.

ω∈Ω|pu∈N ω y ω = 1 ∀u ∈ U (2) h ω ω[i-1] + (s ω[i-1] + t ω[i-1],ω[i] )y ω ≤ h ω ω[i] ∀ω ∈ Ω, i ∈ {2, ..., n ω } (3) h ω du -h ω pu -s pu ≤ R u ∀ω ∈ Ω, u ∈ U ω (4) a i y ω ≤ h ω i ≤ b i y ω ∀ω ∈ Ω, i ∈ N ω (5) H e -W e ≤ ω∈Ω|i∈N ω h ω i ≤ H e ∀e ∈ E, i ∈ D e ( 6
h ω i ≥ 0 ∀ω ∈ Ω, i ∈ N ω (10) y ω ∈ {0, 1} ∀ω ∈ Ω (11)
The objective function (1) minimizes the sum of route fixed costs and travel time costs. The setpartitioning constraints (2) state that each user u ∈ U is picked up on exactly one route that visits pickup node p u . Constraints (3) determine the schedule of a route ω 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 ω[i-1] and the travel time t ω[i-1],ω [i] from the (i -1) th to the i th node of route ω. 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 ω associated with non-selected routes are set to 0. Constraints (6) represent the synchronization of all routes visiting school e ∈ 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 N ω and 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 δ. Constraints (8) to (11) define the nature and intervals for all decision variables.

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 Ω, 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 Ω ∈ Ω, 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 ∈ 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.

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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF]) 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 is replaced by a pre-processed value Θ ω i and a variable τ ω i for any route ω ∈ Ω and all nodes i ∈ N ω in this route. The value Θ ω i represents the earliest service time at node i in route ω. The variable τ ω i models the time lag that is added to Θ ω i 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 = Θ ω i + τ ω i .
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 ∈ E to find a feasible solution.

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

lex min(g, f ) (12) s.t. g = e∈E r e (13) f = ω∈Ω c ω y ω + C time ω (Θ ω ω[nω] -Θ ω ω[1] )y ω + C time ω (τ ω ω[nω] -τ ω ω[1] ) (14) ω∈Ω|pu∈N ω y ω = 1 ∀u ∈ U (15) Θ ω ω[i-1] + τ ω ω[i-1] + t ω[i-1],w[i] + s ω[i-1] ≤ Θ ω ω[i] + τ ω ω[i] ∀ω ∈ Ω, i ∈ {2, ..., n ω } (16) Θ ω du + τ ω du -Θ ω pu -τ ω pu -s pu ≤ R u ∀ω ∈ Ω, u ∈ U ω (17) a i ≤ Θ ω i + τ ω i ≤ b i ∀ω ∈ Ω, i ∈ N ω (18) H e -W e -r e ≤ Θ ω i + τ ω i ≤ H e ∀e ∈ E, ω ∈ Ω, i ∈ N ω ∩ D e ( 19
)

H e -W e = a e + δκ e ∀e ∈ E (20
)

H e ∈ [a e + W e , b e ] ∀e ∈ E (21) τ ω i ∈ R + ∀ω ∈ Ω, i ∈ N (22) κ e ∈ N ∀e ∈ E (23) r e ∈ R + ∀e ∈ E (24) y ω ∈ {0, 1} ∀ω ∈ Ω (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 time ω (Θ ω ω[nω] -Θ ω ω[1]
)y ω is accounted for in the objective function as soon as a variable y ω 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 ∈ 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 Ω 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 ∈ 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).

Matheuristic framework

The general solution method, called School Bell time Adjustment Matheuristic (SBAM), is described by Algorithm 1. 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 T L 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 Ω , 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 T L) 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 ε. 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 ε (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 T L/(R + 1) units of time. ] be the initial morning interval of school e (when SIt = 1). For a given e ∈ E, the shrink iteration process is initialized by determining the step by which a shrink iteration reduces the morning interval:

Shrinking 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

W idth = Step × (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:

T min = min i∈{1,...,K} h i T max = max i∈{1,...,K} h i Center =(T min + T max)/2 3. A first estimation a of a new e
is calculated according to the current value of a e , the center, the width and rounded to a multiple of the discretization step δ: With this mechanism, the time windows are gradually shrunk until they reach their minimal value, which happens during the last T L/(R + 1) time units of computation. In this final step, the problem becomes a DARP with no SBA consideration.

a = max{a e , Center -W idth/2} a = a /δ × δ.

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 feasiblility 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 andPisinger 2006b, Pisinger and[START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. This method has also proved its effectiveness for solving the DARP and several variants [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF][START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF], Lehuédé et al. 2013[START_REF] Masson | The Dial-A-Ride Problem with Transfers[END_REF]). 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 [START_REF] Masson | Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers[END_REF]) but maximum ride time constraints make the problem more complex [START_REF] Masson | The Dial-A-Ride Problem with Transfers[END_REF]). 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.

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 Ω (line 8) with the following heuristic filtering: If a route ω ∈ S visits the same users as a route ω ∈ Ω and f (ω) < f (ω ), then ω is not added to the set. Conversely, if ω have the same customers as ω and a strictly lower cost, then ω is replaced by ω in Ω . 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 g and 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 Ω 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 [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]), 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 ). 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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF]. 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.

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 i 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 Ω S . 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 e 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 ω of ω ∈ Ω S are known, the second objective consists in minimizing the sum of route durations

f = ω∈Ω S C time ω (h ω[nω] -h ω[1] ).
According to this notation, the lexicographical bi-objective MILP (26-37) models the timing problem of the r-DARP-SBA.

lex min(g, f ) (26) s.t. g = e∈E r e (27) f = ω∈Ω S C time ω (h ω[nω] -h ω[1] ) (28) h ω[i-1] + t ω[i-1],ω[i] + s ω[i-1] ≤ h ω[i] ∀ω ∈ Ω S , i ∈ {2, ..., n ω } (29) h du -h pu -s pu ≤ R u ∀ω ∈ Ω S , u ∈ U ω (30) a i ≤ h i ≤ b i ∀ω ∈ Ω S , i ∈ N ω (31) H e -(W e + r e ) ≤ h i ≤ H e ∀e ∈ E, i ∈ D e (32)
H e -W e = a e + δκ e ∀e ∈ E (33)

h i ∈ R + i ∈ N (34) H e ∈ [a e + W e , b e ] ∀e ∈ E (35) κ e ∈ N ∀e ∈ E (36) r e ∈ R + ∀e ∈ E (37)

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,

N (e, ω) =    d u ∈ N e | u ∈ ω ∈Ω\{ω} U ω    .
Note that if route w is the only route visiting e, then N (e, ω) = ∅. Let Θ - ω,i and Θ + ω,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 ω, respectively. Property Given a partial solution S, a user u ∈ U whose delivery location is school e, and a route ω ∈ Ω S , a necessary condition for the existence of a synchronized solution when inserting u ∈ U in route ω is that: (i) the user u can be inserted in route ω with respect to constraints ( 29) -( 31); (ii) all deliveries at school e on route ω must occur within the time window [a e , b e ], such that:

a e = max{a i , max i∈N (e,S,ω) {Θ - i } -W e } b e = min{b i , min i∈N (e,S,ω) {Θ + i } + W e }.
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 = Θ - i ∀i ∈ N (e, ω).
Suppose a new delivery to school e is inserted before max i∈N (e,ω) {Θ - 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∈N (e,ω) {Θ - 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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF]. 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 reevaluate insertions in the modified route ω. 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.

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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF] to solve our instances as a DARP.

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

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 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. For each vehicle type, Table 2 indicates the fixed cost C f (in €) of using the vehicle, the distance cost C d (in €/km) and the time cost C t (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 ).

Costs

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.

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 3: Recommended parameter values for the SBAMmatheuristic 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.

Parameter Value Meaning

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: Evaluation of the key components of the proposed matheuristic. Each gap is given in % to the best known solution.

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 * ) + ξ, with ξ = 1 hour and f (S ) < f (S * ) × (1 + ρ). 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 * ) × (1 + ρ) 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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF], derived from [START_REF] Grangier | A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking[END_REF]. 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 ε according to the performance of the solver (versus decreased only in [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF]). From these experiments we see that the SBAM pool management slightly dominates the strategy of [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF] 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-SBAreformulation 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.

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. 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.

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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF] 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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF] 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 ∈ 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. 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.

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.

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 ∈ E. 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. -5.38 100.51 15.25 105.00 -16.35 Table 8: Impact of SBA on the average ride times, the average duration of routes and the number of routes.

Impact on ride times, routes and vehicles

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.

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.

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 ∆ 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.

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 [START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF] 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.

Algorithm 1 :

 1 SBAM: School Bell time Adjustment Matheuristic Parameters: N : initial number of LNS iterations in one SBAM iteration, ε: constant positive multiplier for parameter N , T L 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 * := ∅ 2 Current solution: S := ∅ 3 MI := {[a e , b e ], e ∈ E} 4 Shrink iteration index: SIt := 1 5 while execution time < T L do /* LNS, see Section 5 */ 6 Ω , S * , S :=LNS(S * , S, N, M I) /* Solve the r-DARP-SBA model */ 7 Solve (12)-(25) with an MILP Solver, taking Ω = Ω ; {[a e , b e ], e ∈ E} = MI ; warm start with S * ; time limit T SCP 8 if S * has been improved by the MILP solver then 9 S := S * /* update N */ 10 if the r-DARP-SBA has been solved to optimality on two consecutive iterations then 11 N := N × (1 + ε) 12 else if optimality was not proven or S * was not improved on two consecutive iterations then 13 N := N/(1 + ε) /* Shrink schools morning intervals */ 14 if execution time reaches SIt × T L/(R + 1) then 15 ∀e ∈ E : {a new e , b new e } := shrinkMorningInterval(SIt, e, S * ) 16 SIt:=SIt+1 17 M I := {[a new e , b new e ], e ∈ E}; 18 end

  4. The left bound b new e is then positioned: b = min{b e , max{a + W idth, T max}} b new e = b /δ × δ. 5. Finally, the value of a new e is calculated from that of b new e : a new e =b new e -W idth/δ × δ.

Algorithm 2 :5Destroy8

 2 LNS(S * , S, N, MI ). Parameters: ρ record to record parameter (acceptance criterion). Input : S * best solution found so far, S current solution, N number of iterations, MI schools morning intervals. Result: pool of routes Ω , Best Solution S * 1 S := S (copy of the current solution) 2 Ω := ∅ (pool of routes) 3 n := 0 (iteration counter) 4 while n < N do /* Create DARP solutions */ Select a destroy quantity; a destroy operator; and a repair operator 6 Filter and append the routes of S to Ω 9 if f (S ) < f (S * ) then /* Evaluate the r-DARP-SBA timing constraints and objectives */ S , f , g:=timingProblem(S ) if g < g(S * ) or g = g(S * ) ∧ f < f (S * ) then S * := S n := 0 Ω := ∅ /* Record to record acceptance criterion */ if f (S ) < f (S * ) × (1 + ρ) then , Φ + ]. 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

  to shrinkMorningInterval. T SCP 10 sec Time limit to solve the r-DARP-SBA. N 20 Initial number of LNS iterations between two solving of the r-DARP-SBA. ε 1.25 Increasing/decreasing rate of N . Φ - 10% Minimal rate of requests removed by the LNS operators. Φ + 40% Maximal rate of requests removed by the LNS operators. ρ 5% Record-to-Record parameter in LNS.

  + , o -} have a time window [a i , b i ]. By abuse of notation, we also consider that a node i ∈ D that models a delivery at a school e ∈ E, has a time window [a i , b i ] = [a e , b e ].

  ω 1 Figure 1: Time space representation of two routes ω 1 and ω 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 . The horizontal axis represents the time scale. Route ω 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 ω 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

					a e	H e -W e	H e	b e
		o +	p 1	p 2	p 3	d 1	d 2	d 3	p 4	o -
	route ω 2	o +		p 5	p 6	d 5	d 6		p 7	o -

  The shrinkMorningInterval(SIt, e, S * ) function in line 15 of Algorithm 1 returns a reduced time interval [a new e , b new e ] for a school e ∈ E. [a new e , b new e ] 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 , . . . , h K } the set of of service times in S * for a given school school e. Let [a e , b e

Table 1 :

 1 . Set of users and schools

	Data set	|U| |E|
	S1-50-5	50	5
	S2-53-7	53	7
	S3-54-4	54	4
	S4-67-3	67	3
	S5-75-3	75	3
	S6-81-5	81	5
	S7-96-4	96	4
	S8-99-3	99	3
	M9-124-13 124 13
	M10-138-10 138 10
	M11-139-5 139 5
	M12-174-6 174 6
	L13-249-15 249 15
	L14-326-19 326 19
	F15-575-34 575 34

Table 2 :

 2 Features of the vehicle fleet. C

						Config 1		Config 2	Config 3
	Id	C f	C d	C t Seat Wheelchair Seat Weelchair Seat Wheelchair
	v1 13.23 0.14 27.39	4	0
	v2 13.92 0.16 27.39	6	0
	v3 19.02 0.18 27.39	2	1
	v4 19.87 0.21 27.39	7	0
	v5 21.13 0.19 27.39	4	1
	v6 22.48 0.26 27.39	7	1
	v7 23.72 0.22 27.39	8	0
	v8 21.06 0.24 27.39	6	0	5	1	4	2
	v9 21.24 0.23 27.39	5	1	3	3
	v10 21.74 0.24 27.39	5	2	3	3	2	4
	v11 22.63 0.25 27.39	5	2	4	3
	v12 25.52 0.24 27.39	7	1	6	2
	v13 26.84 0.27 27.39	5	3	4	4	3	5

f : fixed cost (in €), C d : distance cost (in €/km), C t : time cost (in €/h)

Table 4 :

 4

		Instance	SBAM -dTWrel -poolManagement -KC -reformulation -NC -MILP
	Average on 5 runs	S3-54-4-h S4-67-3 S5-75-3 S7-96-4-h M9-124-13 M12-174-6-h L13-249-15 Average	0.29 0.05 0.04 0.29 1.20 0.61 0.45 0.42	0.32 0.10 0.47 0.34 1.28 0.77 0.64 0.56	0.76 0.26 0.53 0.68 1.85 0.56 0.96 0.80	0.35 0.08 0.70 0.19 2.19 0.65 3.07 1.03	1.00 0.30 1.48 1.03 3.09 1.85 1.33 1.44	0.20 0.74 0.60 0.21 3.00 1.37 5.75 1.70	1.05 1.71 3.22 2.74 5.28 4.45 5.15 3.37
		S3-54-4-h	0.10	0.09	0.24	0.09	0.75	0.00	0.76
	Best of 5 runs	S4-67-3 S5-75-3 S7-96-4-h M9-124-13 M12-174-6-h	0.00 0.00 0.01 0.13 0.28	0.00 0.06 0.01 0.00 0.24	0.05 0.03 0.03 0.28 0.17	0.00 0.03 0.01 1.16 0.04	0.05 0.18 0.96 1.95 1.63	0.60 0.04 0.00 2.05 0.71	0.69 1.75 2.69 4.26 3.85
		L13-249-15	0.00	0.20	0.40	1.23	0.73	5.11	4.84
		Average	0.07	0.09	0.17	0.37	0.89	1.22	2.69

• 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 5 :

 5 Impact of the time windows shrinkage parameter R (

		Instance	R = 0	1	2 *	4	10	1
		S3-54-4-h	0.64 0.57 0.29 0.52 0.36 0.43
		S4-67-3	0.68 0.04 0.05 0.09 0.08 0.10
	Average	S5-75-3 S7-96-4-h M9-124-13	0.28 0.16 0.04 0.06 0.08 0.47 0.63 0.16 0.29 0.17 0.33 0.44 3.13 2.17 1.20 1.79 2.00 1.82
		M12-174-6-h	3.80 0.28 0.61 0.61 1.06 0.82
		L13-249-15	2.36 0.80 0.45 0.91 1.19 0.92
		Average	1.65 0.60 0.42 0.59 0.73 0.71
		S3-54-4-h	0.09 0.14 0.10 0.29 0.19 0.25
	Best of 5 runs	S4-67-3 S5-75-3 S7-96-4-h M9-124-13 M12-174-6-h	0.61 0.00 0.00 0.00 0.05 0.05 0.07 0.06 0.00 0.00 0.06 0.06 0.01 0.01 0.01 0.01 0.01 0.01 0.87 1.60 0.13 0.25 1.31 1.15 3.07 0.00 0.28 0.48 0.34 0.36
		L13-249-15	1.51 0.54 0.00 0.59 0.58 0.50
		Average	0.89 0.34 0.07 0.23 0.36 0.34

* : chosen parameter, gaps in % with respect to best known solutions)

Table 6 :

 6

		Delivery TW width: 20 minutes	Delivery TW width: 60 minutes
		BKS Best of 5 runs	Average	BKS Best of 5 runs	Average
			SBAM LNS SBAM LNS		SBAM LNS SBAM LNS
	Heterogeneous fleet
	S	8,485	0.00 0.01	0.01 0.15 7,582	0.06 0.04	0.23 0.45
	M	8,336	0.00 0.06	0.13 0.32 7,333	0.00 0.22	0.32 0.77
	L	8,290	0.00 0.34	0.31 0.50 7,076	0.01 0.30	0.53 1.07
	F	8,264	0.06 0.00	0.51 0.16 7,021	3.11 0.00	4.59 0.95
	Avg.	8,344	0.02 0.10	0.24 0.28 7,253	0.79 0.14	1.42 0.81
	Homogeneous fleet
	S	8,920	0.00 0.05	0.06 0.22 7,918	0.01 0.37	0.11 0.64
	M	8,706	0.07 0.27	0.18 0.58 7,619	0.00 0.29	0.34 0.82
	L	8,683	0.44 0.00	0.70 0.47 7,332	0.30 0.15	0.69 0.97
	F	8,647	0.00 0.32	0.19 0.51 7,281	0.68 0.00	4.09 0.51
	Avg.	8,739	0.13 0.16	0.28 0.44 7,538	0.24 0.20	1.30 0.73
	Average 8,541	0.07 0.13	0.26 0.36 7,395	0.52 0.17	1.36 0.77

Comparison between the LNS matheuristic of

[START_REF] Tellez | The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity[END_REF]

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).

  Table 7 shows the results of all scenarios aggregated by types of data set. The detailed results are available in Table 11 in Appendix.

		Impact of SBA		Gap to scenario 20 (%)
		0	20 20/60	60	0 20/60	60
	Heterogeneous fleet
	S	9,223 8,485 8,040 7,582	8.70	-5.25 -10.65
	M	9,223 8,336 7,743 7,333	10.64	-7.11 -12.03
	L	9,223 8,290 7,571 7,076	11.25	-8.68 -14.64
	Avg. 9,223 8,370 7,784 7,330	10.20	-7.01 -12.44
	Homogeneous fleet
	S	9,973 8,920 8,377 7,918	11.81	-6.09 -11.23
	M	9,973 8,706 8,031 7,619	14.56	-7.75 -12.48
	L	9,973 8,683 7,928 7,332	14.86	-8.69 -15.56
	Avg. 9,973 8,770 8,112 7,623	13.74	-7.51 -13.09
	Average				11.97	-7.26 -12.76

Table 7 :

 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 withing the morning interval (60).

  Table8details 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.

		Ride Time	Route duration	Nb Routes
		min Gap (%)	min Gap (%)	# Gap (%)
		20	20/60	20	20/60	20	20/60
	Heterogeneous fleet
	S	29.22	-4.68	98.48	12.04 109.00	-12.84
	M	29.34	-5.58 100.56	14.63 105.00	-16.19
	L	29.51	-7.59	98.48	18.62 107.00	-19.63
	Avg.	29.36	-5.95	99.18	15.09 107.00	-16.22
	Homogeneous fleet
	S	29.61	-3.41	99.78	13.28 106.00	-14.15
	M	29.91	-4.40 103.36	17.22 101.00	-17.82
	L	30.27	-6.45 101.65	15.55 102.00	-17.65
	Avg.	29.93	-4.75 101.60	15.35 103.00	-16.54
	Average 29.67

Table 9 :

 9 Number of routes visiting n schools

				Nb routes with n schools
		Scenario # routes n =1	2	3 4 5
	Heterogeneous fleet
	S	20	109	55 45	9 0 0
		20/60	95	40 38 16 1 0
	M 20	105	43 47 13 2 0
		20/60	88	21 45 21 1 0
	L 20	107	37 56 12 2 0
		20/60	86	14 41 25 5 1
	Homogeneous fleet
	S	20	106	52 46	8 0 0
		20/60	91	36 42 12 1 0
	M 20	101	34 47 19 1 0
		20/60	83	18 40 20 5 0
	L 20	102	33 50 18 1 0
		20/60	84	19 34 22 8 1
		∆				Gap to 5 min (%)
		1 sec 5 min 10 min 20 min 1 sec 10 min 20 min
	Heterogeneous fleet
	S	8,029 8,040	8,045	8,090 -0.13	0.07	0.62
	M	7,713 7,743	7,776	7,912 -0.39	0.43	2.19
	L	7,574 7,571	7,632	7,866		0.04	0.81	3.90
	Avg. 7,772 7,784	7,818	7,956 -0.16	0.44	2.24
	Homogeneous fleet
	S	8,374 8,377	8,406	8,489 -0.03	0.35	1.34
	M	8,010 8,031	8,048	8,172 -0.26	0.22	1.76
	L	7,904 7,895	7,962	8,052		0.11	0.86	1.99
	Avg. 8,096 8,101	8,139	8,238 -0.06	0.47	1.70
	Average					-0.11	0.46	1.97

Table 10 :

 10 Impact of the discretization step ∆

Acknowlegment

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

Impact of school bell time adjustment

Gap


The Jenin refugee camp (Palestine) became the setting for a significant military operation on September 6, which resulted in the arrest of Muhammad Naghnaghia (member of the Al Quds Brigades) by the Israeli army. There was, however, more to this operation than just an arrest. The Israeli forces seized control of the well-known Freedom Theatre in Jenin (where Adnan, Muhammad Nghanaghia's brother, serves as the head technician), using the structure as a defensive position against any resistance attempts to counter Israeli aggression. The recent developments in the Jenin camp are not isolated incidents. Between the 2nd and 3rd of July, the Israeli army attacked the camp and the city of Jenin by air and land (1000 soldiers and more than 150 bulldozers were reported to be employed). This marks the most severe assault by Israel since the infamous Jenin Battle of 2002, during which approximately 4000 camp inhabitants were made homeless. During this military offensive, The Freedom Theatre was also damaged. The outside yard of The Freedom Theatre was used as a military support point by the Israeli army, and the ceilings were compromised. Members of the staff were also personally affected by this offensive: they described their experiences and addressed more generally the invasion in a live stream on the 9th of July.

© Noor Shihadeh

The Freedom Theatre has been attacked several times over the years as a cultural institution. What is the history of this theatre and what is its role in the camp, and finally what are the implications of attacking a cultural institution?

The Freedom Theatre was created in 2006 by Juliano Mer Khamis, Jonatan Stanczak, and Zakaria Zubeidi. Still, its origins go back further than that and deserve to be remembered as an example of the complexity of Palestinian society and how, despite all difficulties, different people keep struggling to maintain, continue, and innovate Palestinian cultural heritage. As shown by Varghese, the roots of the theatre can be traced back to the first intifada, with Arna Mer (mother of Juliano Mer Khamis) playing a pivotal role. Born in 1929 in Rosh Pinna, a Zionist settlement in Palestine, Mer initially served in the Palmach brigade during the 1948 Arab-Israeli War. However, her perspective transformed over time. In the 1950s, she defied societal expectations by marrying Saliba Khamis, a Palestinian Christian who served as the secretary of the (Israeli) Communist Party. Mer fearlessly protested against the occupation, and in the 1980s, she extended her political commitment by establishing the Care and Learning Project. With this project, she provided additional after-school classes for children in Jenin, integrating creative approaches to help them cope with trauma. Thanks to this project, she earned the Right Livelihood Award (known as the Alternative Nobel Price), with whose reward she created, alongside her son Juliano Mer-Khamis, The Stone Theatre (named after the stones thrown during the intifada). The theatre began to decline after Arna Mer died in 1995. As shwon in the documentary Arna's childrens, several students who participated in Theater Stone projects died in armed resistance actions. It was out of the ruins of the battle of Jenin in 2002 that completely destroyed The Stone Theatre and under the influence of his late mother's legacy that Juliano Mer Khamis founded the Freedom Theatre with Jonatan Stanczak and Zakaria Zubeidi. The Freedom Theatre has nurtured a dynamic group of artists dedicated to advocating for equality, justice, and freedom. This artistic community has toured productions globally, drawing international attention to one of Palestine's most aggressively attacked refugee camps. In addition to a comprehensive three-year training program for actors, the Freedom Theatre also offers training and professional opportunities in film, photography, stand-up comedy, and writing. The Freedom Theatre serves as a crucial sanctuary for the population of the camp, specifically children and women, providing them with a space to play, create, and explore, away from the recurring traumas they endure due to Israel's military occupation.

Celebrative mural at the entrance © Noor Shihadeh However, the Freedom Theatre's productions denounce Palestinian society as well. Since its opening, the theatre has had to face criticism from some people of the Palestinian camp that accused it of corrupting morals and being a Zionist outpost. On the other hand, Israel was concerned about possible collaboration with armed resisters and the crossing of the green line by persons with Israeli citizenship (Mer Khamis and Stanczak). The Theatre's founders were acutely aware of the accusations of corrupting the youth of Palestinian society, as evidenced by an interview in which Juliano Mer Khamis predicts his death by stating that he will be killed by an outraged 'fucked-up' Palestinian ' who accuses him of 'corrupting the youth of Islam'. Eventually, Mer Khamis was indeed killed by a Palestinian in 2011. Following this event, the IDF continuously arrested the Theatre's staff members and students for a year under the guise of security operations. Despite all this, the Freedom Theatre continued its activities, and its executive board included Noam Chomsky, Judith Butler, Elias Khoury and Avraham Oz.

Photos of Juliano Mer Khamis posted at the entrance © Noor Shihadeh

What does it mean to do theatre in Palestine and why is it so contentious? Directors of various theatres say that their work is imperative because it shows the world the human face of Palestinians. In the case of The Freedom Theatre, productions arise from working with camp residents who can then give their perspective on living in their society under occupation. Moreover, the performances themselves are often participatory and openly call the audience to political reflection and how to organise themselves, thus offering a space for public reflection to a population, the Palestinian population, which is excluded from the domains of public debate. The practice of Freedom Theatre, Varghese points out, thus contributes to the creation of a counter-public that can create discursive strategies and gather oppositional resources. Attacks on cultural institutions, like The Freedom Theatre in Palestine, go beyond physical destruction. They are colonial tactics aimed at erasing the cultural heritage of the occupied, denying their existence. By targeting the Freedom Theatre in Jenin, assailants seek to erase its history, which represents people crossing boundaries made up by the colonial power and challenging the occupier-occupied division scheme. This erasure contributes to the denial of Palestinians' identity and their right to selfrepresentation and self-narration. The attack on the theatre is an act of cultural erasure, silencing Palestinian voices and preventing the authentic portrayal of their experiences. Such assaults perpetuate the systematic denial of Palestinian existence and underscore the importance of protecting their cultural heritage and spaces of self-expression. The Freedom Theatre is back in business and is now organizing the Feminist Theatre Festival and continues, even in the face of renewed attacks, to teach life.

Feminist theater festival poster © Noor Shihadeh

  • 5 MIN READPALESTINE THEATRE ART JENIN

  Photos on the entrance walls, on the top right Arna Mer smoking a cigarette © Noor Shihadeh

Mural near the entrance, The Freedom Theatre © Noor Shihadeh

NOOR SHIHADEH

Noor Shihadeh is a PhD student at L'Orientale University in Naples, her doctoral thesis focuses on Palestinian theatre.

She is a member and a translator of the French translation journal "Café".