Oscar Augusto

Tellez Sanchez

Ecole Sigle

Doctorale

Renée El

Melhem Bât

Pascal Blaise

R Gourdon

M Stéphane

ÉLECTROTECHNIQUE E E A Électronique

M Gérard Scorletti
email: gerard.scorletti@ec-lyon.fr

M Philippe
email: philippe.normand@univ-lyon1.fr

Mme Emmanuelle
email: emmanuelle.canet@univ-lyon1.fr

M Luca

Jean-Yves Buffière
email: jean-yves.buffiere@insa-lyon.fr

Stéphanie Cauvin

M Jocelyn Bonjour

Véronique Guichard

J Y Toussaint

M Christian Montes

Samuel Vercraene

Fabien Léhuhédé

Olivier Péton

Directeur Thibaud
email: directeur@edchimie-lyon.fr

Optimizing the daily transport for people with disabilities By

.

For Medico-Social Institutions (MSI), transport costs often represent the second-largest expense after that of the staff. Despite this, few MSIs have the means to effectively manage the transport to provide high-quality service and keep the costs down. With little expertise, MSIs are often led to adopt sub-optimal practices that impact costs, quality of service or the environment.

In the medico-social sector, transport is no longer considered merely a painful or non-valueadded activity. It is generally integrated into the life project of People With Disabilities (PWD).

Transportation allows the inclusion of the PWD to school or work life. It can be a lever for the autonomy of PWD. Transport demands in the medico-social sector are mostly regular and very often known in advance. This anticipated knowledge of needs can be used to jointly improve: the quality of service for users, and the efficiency of the resources used. This thesis is part of the project "Numérique et Optimisation pour une Mobilité Adaptée" (NOMAd). This project aims to improve the daily transport service for people with disabilities between their homes and the MSIs. To this end, we suggest the transport pooling between several MSIs on one side and a global optimization strategy for building the annual transport planning on the other side. The construction of the annual transport planning is a complex problem that has not been completely solved in the scientific literature. Following the current practice, we can assume that the annual transport plan is composed of a pattern of identical weekly schedules.

To solve the weekly problem, we first work on the planning of the half-day transport problem. This problem is modeled as a mixed-integer program called the fleet size and mix dial-a-ride problem with multiple passenger types and with a heterogeneous fleet of reconfigurable vehicles.

In this new variant of the dial-a-ride problem, en-route modifications of the vehicle's inner configuration are allowed. The main consequence is that the vehicle capacity is defined by a set of configurations and the choice of vehicle configuration is associated with binary decision variables. Vehicle reconfiguration is a lever to efficiently reduce transport costs, but the number iii

of passengers and vehicle fleet setting make this problem intractable for exact solution methods.

A large neighborhood search matheuristic combined with a set covering component and a reactive mechanism to automatically adjust its parameters is therefore proposed.

Once we solve the half-day transport problem, we conduct a weekly integration of solutions.

However, the simple juxtaposition of half-day transport schedules give cost-efficient transport planning but a very inconsistent service time for each passenger. This situation is uncomfortable for PWD, or even unacceptable for some people with mental disabilities. These service time requirements together with traditional route planning define a new variant of the multi-period dial-a-ride problem that we denote the time consistent DARP. This problem is modeled as a route based mathematical modeling considering two objectives: the transport cost and the service time consistency.

A perfectly consistent schedule, defined for each passenger a single service time during the planning horizon. However, this transport solution is very expensive for MSIs. With a lexicographic definition of the solution time-consistency, we are able to produce a large variety of less consistent but affordable solutions that fits better to the needs of MSIs. The problem is solved with a matheuristic framework based on a master set partitioning problem and routes generated from a large neighborhood search procedure.

Currently, the pooling of transport between MSIs is not a common practice. Instead, each MSI manages its transport independently. This way of working has technical and administrative advantages in terms of optimization, contracting and negotiation. On the contrary, dealing with multiple MSIs at a time supposes a simultaneous negotiation process, and requires a specialized mechanism for pricing users individually. Despite the advantages of the current policy, there is a major economic drawback that must be weighed against its benefits. An assessment against two other policies is presented in the context of both economic and service aspects. Alternative policies consider transport pooling between several MSIs. The service quality indicator for this study is the user ride time.

The transport pooling between MSIs is both a research and managerial challenge. Currently, transport management is mainly carried out independently in each MSI. The pooling of transport increases the size of the problem and therefore its complexity. It also implies having, on the one hand, economic interest and, on the other hand, a common mechanism of effective management and communication between the two parties. The objective of this study is to evaluate the impact of transport pooling on the costs and the ride time of the users. From an optimization point of view, this solving approach is known as "clustering first route second" for large scale routing problems. A comparison is made between a scenario without transport pooling and other scenarios allowing transport pooling shows that up to 30% of transport costs can be saved. iv Résumé D ans la plupart des pays développés, le transport des personnes en situation de handicap est subventionné avec des fonds publics. En 2017, le coût de ce transport en France était d'environ 500 M€ soit 10% du coût total du transport médical [START_REF] Gonzalez | Les dépenses de santé en 2017 -résultats des comptes de la santé -Édition 2018[END_REF].

Entre 2006 et 2014, ce coût a augmenté de 40% [START_REF] Wahl | Les transports sanitaires -revue de dépenses 2016[END_REF] et le nombre de personnes transportées de 18% de 2006 à 2008 [START_REF] Laurent | Établissements et services pour personnes handicapées offre et besoins, modalités de financement[END_REF]. Pour les Établissements Sociaux et Médico-Sociaux (ESMS), les coûts de transport représentent souvent la deuxième dépense en importance après celle du personnel. Malgré cela, peu d'ESMS ont les moyens de gérer efficacement le transport afin de fournir un service de haute qualité et de réduire les coûts. Avec peu d'expertise, les ESMS sont souvent amenés à adopter des pratiques peu performants ayant un impact sur les coûts, la qualité de service ou l'environnement.

Dans le secteur médico-social, le transport n'est plus considéré comme une simple activité pénible ou sans valeur ajoutée. Il est généralement intégré au projet de vie des Personnes en Situation de Handicap (PSH). Le transport permet l'inclusion des PSH à l'école ou au travail, ce qui favorise leur autonomie. La demande de transport dans le secteur médico-social est généralement régulière et très souvent connue à l'avance. Cette connaissance anticipée des besoins peut être utilisée pour améliorer conjointement la qualité de service pour les utilisateurs et l'efficacité des ressources utilisées.

Dans ce contexte, cette thèse réalisée dans le cadre du projet «Numérique et Optimisation pour une Mobilité Adaptée» (NOMAd) vise à améliorer le service de transport quotidien des personnes en situation de handicap entre leur domicile et les ESMS. À cette fin, nous proposons la mutualisation du transport entre plusieurs ESMS et nous proposons une stratégie d'optimisation globale de la planification annuelle du transport.

La construction de la planification annuelle des transports est un problème complexe qui n'a pas été complètement résolu dans la littérature scientifique. Conformément à la pratique actuelle, nous pouvons supposer que le plan de transport annuel est composé d'un ensemble d'horaires hebdomadaires identiques.

Pour résoudre le problème hebdomadaire, nous travaillons d'abord à la planification d'un problème de transport d'une demi-journée. Ce problème est modélisé comme un programme à nombres entiers mixtes appelé "the fleet size and mix dial-a-ride problem", Dans ce problème, nous prenons en compte plusieurs types de passagers et un parc hétérogène de véhicules reconfigurables. Dans cette nouvelle variante du problème dial-a-ride, les modifications de la v configuration interne du véhicule sont durant le trajet sont autorisées. La conséquence principale est que la capacité du véhicule est définie par un ensemble de configurations dont le choix est associé à des variables de décision binaires. La reconfiguration des véhicules est un levier pour réduire efficacement les coûts de transport, mais le nombre de passagers et l'hétérogénéité du parc de véhicules rendent ce problème insoluble pour des méthodes de résolution exactes.

Nous proposons donc une matheuristique de recherche de grand voisinage combinée à un set partitioning problem doté d'un mécanisme réactif pour ajuster automatiquement ses paramètres.

Une fois que nous avons résolu le problème de transport d'une demi-journée, nous procédons à une intégration hebdomadaire des solutions. Cependant, la simple juxtaposition d'horaires de transport d'une demi-journée peut permettre une planification très efficace du transport en terme de coûts, mais peut conduire à un service horaire très irrégulier pour chaque passager.

Cette situation est inconfortable pour les PSH, voire inacceptable pour certaines personnes souffrant de certains handicaps mentaux. Ces exigences de régularité de service, combinées à la planification traditionnelle, définissent une nouvelle variante du problème multi-period DARP.

Ce problème, nommé le time-consistent DARP prend en compte deux objectifs: le coût de transport et la régularité du temps de service.

Une planification parfaitement cohérente définit pour chaque passager une seule heure de service pendant l'horizon de planification. Cependant, cette solution de transport est très coûteuse pour les ESMS. Avec une définition lexicographique de la régularité des horaires, nous sommes en mesure de produire une grande variété de solutions moins régulières mais plus économiques et mieux adaptées aux besoins des ESMS. Le problème est résolu avec une matheuristique basée sur un master set partitioning problem et des routes générées à partir d'une procédure de recherche de grand voisinage.

La mutualisation du transport est à la fois un défi de recherche et un défi managérial.

Actuellement, la gestion du transport est principalement réalisée intra-établissement c'est-à-dire sans mutualisation. La mutualisation du transport augmente la taille du problème et donc sa complexité. Elle suppose également d'avoir d'une part, un intérêt économique et d'autre part, un mécanisme commun de gestion et de communication efficace. L'objectif de cette étude est d'évaluer l'impact de la mutualisation sur les coûts de transport et le temps de trajet des usagers. En termes mathématiques, ce problème correspond à l'approche clustering first route second pour la résolution des problèmes de transport de grande taille. Sur un jeu de données issue du terrain, une comparaison est réalisée entre le transport sans mutualisation et deux scénarios avec différents niveaux de mutualisation. vi [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] instance "A" scenario (iii) without groups . . . . A.5 Benchmark [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] instance "B" scenario (iii) without groups . . . . A.6 Benchmark [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] For social and Medico-Social Institutions (MSI), this cost represents the second biggest expense after that of the wages. In this context, this thesis as part of the NOMAd project aims to improve the daily transport service for people with disabilities between their home to MSIs. To this end, we suggest the transport pooling between several MSIs on one side and a global optimization strategy on the other side. This strategy makes possible to group and optimize routes on a given geographical area. The challenge is then to improve economic performance while maintaining social and environmental goals. A decision aiding tool for transport optimization is proposed for this purpose.

Table of Contents

Page

List of Tables xvii

List of Figures xviii 1 Introduction

A.4 Benchmark

Keywords

Context

The medico-social sector

In 2010, medical transportation became one of the top ten priorities of the risk management plan of the French insurance scheme due to the increasing cost of these transports ANAP (2013). In France, the «transport sanitaire» includes both the medical transportation and the medico-social transportation. This sector serves both elderly and people with disabilities.

The report "Establishments and services for disabled people -Offers and needs, financing modalities", published by the General Inspectorate of Social Affairs & General Inspection of Finance estimates the transportation cost for all medico-social institutions at 10% of the total cost of medical tansportation [START_REF] Laurent | Établissements et services pour personnes handicapées offre et besoins, modalités de financement[END_REF].Thus, in 2017, the medico-social transportation cost represents 500 million euros, at the national level, for all medico-social institutions [START_REF] Gonzalez | Les dépenses de santé en 2017 -résultats des comptes de la santé -Édition 2018[END_REF]. There are few details on the evolution of this cost. Between 2006 and 2014, this cost has increased by 40% [START_REF] Wahl | Les transports sanitaires -revue de dépenses 2016[END_REF]. There are few statistics on the evolution of this cost.

Medico-Social Institutions

For Medico-Social Institutions (MSI), transport costs often represent the second largest expenditure after that of the staff (ANAP, 2016b). Despite this, few MSIs have the skills and means to effectively manage the transport, provide high quality service and keep the costs down (ANAP, 2016b). With little expertise, MSIs are often led to adopt sub-optimal practices that impact costs, quality of service or the environment. Unlike medical transportation, medico-social transportation is generally integrated into the life project of People With Disabilities (PWD) (ANAP, 2016c). Transportation is no longer considered merely a painful or non-value-added activity. It allows, the inclusion of PWD to the school or work life. It can be a lever for the autonomy these people (ANAP, 2016b).

Transportation demands in the medico-social sector are mostly regular and very often known in advance. This anticipated knowledge of needs can be used to jointly improve: the punctuality, quality of service for users, and the efficiency of the resources mobilized. The success of such a project requires the mobilization of all stakeholders in order to consider the different concerns of the parties involved. We must indeed meet the needs of people with disabilities and family carers, accompanying persons and mobility centers, MSIs and professional carers.

The following sections are organized as follows: Section 1.2 presents the NOMAd project.

Then, Section 1.3 describes the field study in three parts: the stakeholders, a needs analysis drawn from a survey conducted in the fall of 2017 and a summary of the special features of the transport for PWD. Section 1.4 illustrates where this thesis is positioned within the general transportation process. Section 1.5 presents the road map and contributions of this thesis.

Finally, the conclusions of this chapter are presented in Section 1.6.

1.2. The NOMAd project

The NOMAd project

The project called "Numérique et Optimisation pour une Mobilité Adaptée1 " (NOMAd) is a 3-year project supported by the European Union through FEDER Founds. Deployed in the Auvergne Rhône-Alpes region, NOMAd aims to develop a web service to facilitate exchanges among all the stakeholders of adapted transport: transporters, families of PWD and MSIs. The aim is to build the transport solution by jointly integrating the points of view of the different actors (see https://nomad.disp-lab.fr/). Three objectives are targeted:

• Optimization of the transportation costs by reducing the number of kilometers traveled and the number of vehicles needed.

• Improvement of the quality of service for passengers and establishments by reducing travel times and provide time-consistent schedules.

• Reduce the environmental impact by reducing CO2 emissions linked to the number of kilometers traveled.

These objectives are interlinked and have been considered conjointly. As proposed in [START_REF] Zhu | Lean six sigma and environmental sustainability: a hospital perspective[END_REF], to be sustainable, the environmental impact reduction has to be associated with a cost improvement.

This project is carried out by a group of researchers from the DISP2 laboratory in collaboration with researchers from LS2N3 laboratory and two strategic partners of the medico-social sector:

Ressourcial: a cooperative structure specialized in information systems for the medico-social sector. Created as an association, it is intended to share management practices and IT tools to non-profit MSIs. GIHP Service Adapté: a transportation company specialized in the management and realization of paratransit services. GIHP intervenes particularly in the agglomeration of Lyon.

To give an order of magnitude, this structure carries up to 1500 people per day. One of the benefits of GIHP is that its stakeholders are the MSIs, which implies that making profit is not the only objective nor priority.

Field study

During the interaction with different stakeholders involved in the transportation for PWD we could understand the needs of the sector. In this section we present first the role of stakeholders, then a needs analysis study drawn from a survey conducted in the fall of 2017 and finally a summary of the special features found in the transportation for PWD. Each category can include the coordination of multiple stakeholders.

Health authorities

Health authorities play the role of regulators and very often finance the transport itself. In France, most of MSIs are financed with public funds. This founds come from different sources, named: the National Solidarity Fund for Autonomy (CNSA) and health insurance (Assurance Maladie), and in a smaller proportions the State and Department councils.

Medico Social Institutions (MSIs)

MSIs accompany PWD daily in the construction of a life project that will allow PWD develop their autonomy. Some PWDs may stay in boarding house the whole week, but the majority come back home daily. Each MSI receive a global budget to finance all its expenses, including transportation. Thus, there is an incentive to optimize costs without compromising the service quality. The transportation activity can be so cumbersome for MSIs that outsourcing is often seen as a promising solution. However, with an external transporter the coordination can be difficult and the quality of service may be compromised.

Transporters

The transportation activity can be internally organized by the MSI themselves or outsource to a specialized provider. In both cases, the transporter must follow strict regulations regarding safety measures, driving competences and vehicle specifications. The two main tasks for a 1.3. Field study transporter are: the construction of the annual transport planning and the daily operation of the transportation itself taking into account unforeseen events.

The transportation planning is a complex task that requires decision support tools. However, the available solutions in the market are scarce and do not completely adapt to the needs of the medico-social sector. Currently, complex tasks like route optimization are performed manually, as in GIHP, based on field experience only. The project NOMAd is meant to fill these needs on in comprehensive manner.

Users

Users are PWD and their families who are very often the spokesperson. Families facilitate the transport of their relatives and stay in direct contact with MSI and the driver. In a certain way, families verify that the transportation is done with the expected quality.

Survey: needs analysis

In 2017, we conducted a survey with 30 managers of MSI (12 urban, 10 suburban and 8 rural)

and 35 users (33 parents and 2 PSW) from the Auvergne Rhône-Alpes Region in France. This survey provides us an overview of the current situation of the adapted transportation from two different angles, from the users perspective and from the service provider's perspective. The service providers are MSIs that can outsource the transportation activity. Nearly half of the MSIs surveyed outsource the transport.

Service provider's perspective

Figure 1.2 shows how MSIs perceive the quality of their transport and the resources they deploy in the transportation management. On one side, 77% of MSIs think they provide a good quality transport (yes + rather yes). This perception shows the importance given to the transportation activity. On the other side, this attention is confirmed with the resources deployed in the transportation management: 68% of MSIs put a great effort in the management of transport (significant + high levels) as shown in the graph on the right.

For MSIs, the transportation activity is not just a logistics service, but it is integral part of the life project of PWD. The main resource required by the transportation activity is the staff necessary to the reception and departure; the realization of the transport itself, if it is not outsourced; and the staff for transportation management, gathering needs, planning routes and managing interactions with family caregivers on a daily basis. The last activities are often perceived as highly time-consuming and without real added value.

MSIs were also asked about the approximate distance of users to MSIs.

Users' perspective

Figure 1.3 shows the users view point regarding service quality on the left side and how users perceive their current ride time on the right side. Note however, that most of the responses come from parents as a spokesperson of PWDs. The perception of the service quality is very good 94% ("yes" + "rather yes"). However, there is a 6% of users completely unsatisfied. This situation is reflected in the graph of the ride side with 15% of users unsatisfied with their current ride time ("no" + "rather no"). This result shows us that one way to improve the quality of service is by reducing long ride times.

Users were asked to give a level of importance to different improvement directions. Figure 1.4

presents the results sorted from the most to the least important aspect. The most important aspect for users (parents) is to stay informed about modifications such as driver or scheduling changes (69% very important). Users give more importance to the service punctuality than to have prior information about the vehicle arrival. Time-consistency, which is having the same service time every day, seems to be a bit more important than driver consistency which is having the same driver every day.

Open questions

In the survey to MSIs, we also address open questions regarding difficulties and possible actions to improve the transportation system. Regarding the main difficulties found in the transportation activity, managers of MSI point out the elements already seen above, ride times and transportation costs. They mention several other topics of concern:

• First, the need to take into account the specificity of this type of transport by adapting it to the PWD's needs. The necessity to manage behavioral problems in PWD like potential crises during transport.

• Secondly, the subject of communication and coordination especially for the management of unforeseen events, changes and delays. The coordination among 3 or more stakeholders and the need of real-time information about the transportation is a real concern for managers.

Chapter 1. Introduction

• Finally, managers evoke the human dimension of this transport. The need of a considerable number of staff in order to ensure the service quality and the safety. The specific driver training with respect to the qualifications and stability.

In regard of the actions to improve transportation, we found that 16% of the MSIs had integrated transport-related objectives into their long-term contract with the heath authorities (in France known as CPOM). MSI leaders mention the following objectives:

• To transform the transportation into a lever of autonomy for PWDs.

• To reduce operating costs, particularly those related to vehicle maintenance.

• To reduce ride times by the transport pooling among multiple MSIs.

• To adequately treat all the transport demands in the territory.

• To transform the transportation activity into an enabler of the PWD life project rather than a hurdle to his/her personal life project. This field survey allowed us to define the three main objectives of the NOMAd project. It is about controlling costs, the quality of service and the ability to communicate and coordinate actions among multiple MSIs.

A multidimensional problem

The management and optimization of the transportation for PWD is a complex task. It requires taking into account a set of variables and features related to people, vehicles and the organizational scheme.

Beneficiaries

Beneficiaries are the PWD transported. They can be in a wheelchair or in a seat. PWD have a certain degree of autonomy but some have to be accompanied by a third party. From a quality of service perspective, the time dimension is very important. Users have availability constraints that must be respected. These constraints are expressed in the form of time windows with an earliest and latest arrival time. A maximum ride time of transport for each person is taken into account. Furthermore, in the design of routes a consistent schedule must be taken into consideration. Indeed, despite the variability of demand during the week, it is better to give a single time of service in the morning (afternoon) when they are present several days during the week.

Transportation management processes

Vehicles

Vehicles used in the transport for PWD are specifically designed. Each vehicle can receive a limited capacity for people in wheelchair and/or seated. Additionally, one vehicle may have different layouts that can be configured before the departure or during the routing. These configurations are made with retractable seats, for example, to swap a wheelchair space with a conventional seat. Figure 1.5 shows four different layouts of a reconfigurable vehicle. This vehicle can have spaces for seats, wheelchairs and electric wheelchairs(in black).

Co-organization

Stakeholders are characterized for having different, even antagonistic, objectives. A transport management based solely on a financial criterion will tend to reduce the number of vehicles mobilized and to offer rather long routes, which is a sub-optimal policy from quality point of view. Conversely, an organization of a transport seeking only to offer the best quality of service will tend to increase the number of vehicles and to offer direct-route transport for each person.

Thus, it seems necessary to find a compromise solution. A multi-criteria approach is therefore required to take into account together cost reduction, environmental impact and quality of service criteria.

Transportation management processes

There are multiple processes involved in the management of transport for PWD. Figure 1.6 shows the Business Process Modeling (BPM) of the main transportation activities. In it, we model the interaction among the MSI, the transporter and users in order to perform 3 main

Road map and contributions

This thesis is structured in 5 chapters. The first four chapters are focused on the construction of the long-term transportation planning while the last one is dedicated to the assessment of transport pooling policies.

Construction of the long-term transportation planning

The construction of the long-term transportation planning is a complex problem that has not been completely solved in scientific literature. A literature review about the transportation problems in the health sector is presented in Chapter 2. The long-term planning is defined for one academic year. In accordance with practice, we assume that this transport plan is constructed from a pattern of identical weekly transportation plans.

Defining a weekly schedule is a complex task that needs to decomposed into several subproblems. First, we work in the planning of each sub-problem called the half-day transport problem. Secondly, we focus on building the weekly schedule from the sub-problems that compose it. Figure 1.7 illustrates the process. The rectangle M 1 corresponds to one sub-problem related to the half-day problem. The dotted rectangle specifies the perimeter of the weekly morning or afternoon schedule. We therefore assume the problem of the morning and the afternoon can be solved independently.

Monday Thuesday Wednesday Thursday Friday

Morning Vehicle capacity constraints are also integrated. The problem of on-demand transport for PWDs is already covered in the scientific literature (Toth and Vigo, 1997;[START_REF] Parragh | Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem[END_REF][START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF]. However, our problem considers specific transport elements such as the typology of transported people (wheelchairs or seated) and the typology of adapted vehicles that can be reconfigured en-route.

Afternoon A 1 A 2 A 3 A 4 A 5 M 1 M 2 M 3 M 4 M 5

Road map and contributions

The transport optimization of the half-day problem is based on a cost objective that incorporates vehicle depreciation, hourly costs (eg driver wages), and mileage costs. The respect of pickup and delivery time windows and maximum ride time is expressed as timing constraints. reconfigurable vehicle can perform a given route with a maximum number of reconfigurations.

Weekly transport problem

Once we solved the half-day transport problem, we conduct a weekly solving. Indeed, not PWD need to be transported every day. The simple juxtaposition of half-day transportation schedules can give a very cost-efficient transport planning. However, in this plan, users may have a different service time every day. This situation is uncomfortable for PWD, or even unacceptable for some people with mental disabilities. Thus, from a global approach this weekly schedule aims to optimize both transport costs and time-consistency throughout the week.

The problem of time-consistency has already been treated in the scientific literature for a transportation problem close to ours but simpler called "Time-consistent Vehicle Routing

Problem". It is characterized by a fleet of homogeneous vehicles, a common destination place,

13

Chapter 1. Introduction and no service time constraints [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]. The time-consistency for one user is defined by the number of different time slots during the week. In this approach, one time slot can hold several service times within 10 minutes to each other. If one user has a different time slot each day, he has therefore 5 time-classes. A perfectly consistent transportation plan is characterized by a single time-class for each PWD. This condition is very convenient for the user but very expensive for MSIs. Considering a consistency objective in addition to the cost objective to build the weekly schedule is another contribution of this thesis that is presented in Chapter 4.

This problem is denoted the time-consistent DARP.

Figure 1.9 illustrates the proposed solving approach for the time-consistent DARP. We begin by solving the sub-problem of each half-day described in Section 1.5.1. The union of these solutions is the starting point for the construction of the weekly transportation plan. This first plan is economically efficient, but highly inconsistent. During this first step, we collect the routes obtained in the different iterations to constitute a pool of routes useful for the improvement of time-consistency. Then, using an optimization MILP solver, a time-consistent DARP is solved using a different subset of routes from the pool at each iteration. This process is repeated until the desired pattern is achieved. A Pareto front is constructed using an epsilon-constraint approach. Each new solution of the front is found by relaxing the cost of the previous solution by an epsilon quantity to gradually improve the time-consistency.

Assessment of transport pooling policies

The transport pooling between MSIs is both a research and a managerial challenge. Currently, the transport operation is managed independently for each MSI. In contrast, the management of multiple MSI at a time in addition to increasing the size of the problem (complexity),

presupposes among other things: to have an economic interest to be shared and to have a common mechanism of management and communication between partners.

Conclusion

At the strategic level, the study of Chapter 5 aims to evaluate the marginal gain of interinstitutional transport pooling. Alternative policies with different pooling levels are proposed.

The management objective of this study is to provide the elements to open up a serious discussion between managers of MSIs in order to go further in the development of this strategy.

At the operational level, this problem corresponds to a clustering approach for solving large scale routing problems. One of the challenges in the clustering step is to define a relevant measure to determine the proximity between user demands. Different metrics from the literature will be tested in order to identify which one works better in each way of clustering.

Conclusion

The transportation management and optimization for PWD is a complex task. It requires taking into account a set of variables and particularities related to people, vehicles and organizational schemes. For MSIs, transportation management is a highly demanding task and very often requires a lot of human resources to ensure the expected quality and safety. Knowing that this transport is characterized by a strong geographical dispersion of users, there is a real economic interest in optimizing and pooling this service. This must be done without degrading the quality of service. To this end, we propose a comprehensive approach for developing a transport planning that is both cost-effective and time-consistent for each PWD.

There are five chapters in this thesis corresponding to five major contributions. In this chapter, we have presented a characterization of the transport sector for PWD, the needs in transportation and the global approach for optimizing the long-term transportation planning.

Chapter 2 presents a literature review of the non-emergency transport of patients and PWD in the context of healthcare transport. Chapter 3 focused the modeling and solving approach of the half-day transport problem. Chapter 4 presents the modeling and solving approach of the weekly transport problem. Finally, Chapter 5 addresses the question of transport pooling between several MSIs. A comparison between different pooling policies is presented in regard to transport costs and service quality.

T

he transport for people with disabilities is commonly studied outside of a medical transport context. However, in practice, it is usually part of the public medical transport or home care services. Healthcare transport is usually related to emergency medical transport. However, a large percentage of patient transport is of non-urgent nature [START_REF] Hains | Non-emergency patient transport: what are the quality and safety issues? a systematic review[END_REF]. In this chapter, we present a demand-based classification for healthcare transport services. A literature review about the optimization problems in the context of non-emergency transport of patients & passengers is carried out with a focus on the decision problems found at the strategic, tactical, operational and real-time levels.

Keywords: healthcare, non-emergency transport, patients transport, optimization, dial-a-ride problem 2013). More generally, health transport includes the transport of patients, passengers with disabilities, medical-related supplies and professionals in the case of home care services. In this chapter, patients and passengers with special transport needs will be referred to as P&P.

Healthcare transport

Healthcare transport can be divided into emergency and non-emergency transport. The first case is when the life of a person is in danger and the second one is, for example, the transport of patients between hospitals, the daily transport of PWD and home care. Non-emergency cases

Chapter 2. Literature review manage both short term patients with temporal illness (occasional) and long term patients with chronic illness or disability (regular).

Transport of staff, supplies, and patients & passengers

Healthcare transport continuously moves staff, medical supplies, and P&P all along the supply chain. Although the different type of flows is interrelated, each type of flow is so different that needs to be studied independently.

Staff: the transport of professionals to the patient's residence place for support services is known as home care. This service is provided for patients (i.e. elderly, disabled) needing assistance for daily living or managing health issues. There are three types of home care services:

(i) non-medical care to support everyday activities such as bathing, dressing, household, shopping, etc.; (ii) long term nursing care to support patients with chronic illness, injury or disability.

(iii) short term care or home health care which is physician-directed care designed to help a patient prevent or recover from an illness, injury, or hospital stay. In-home care services, a caregiver takes care of multiple patients during the day. The sequence of patient visits can be optimized to reduce transport costs. Moreover, home care routing should consider the patient's preferences and the nurse working shift. Recent developments in the optimization of home care routing and scheduling are presented in [START_REF] Fikar | Home health care routing and scheduling: A review[END_REF].

Healthcare transport

Supplies: Hospitals manage a complex distribution network of supplies such as food for patients, sterilization, patient's specimens, pharmaceuticals, and medical records. On a daily basis, vehicles, supply carts, personnel move between storage areas and points of care to continuously supply the demand of healthcare facilities [START_REF] Landry | Supply chain forum: An international journal[END_REF]. From a logistics point of view, supplies need being transported with the right quality at the right time and place. Medicine shortages and improper use of pharmaceuticals can not only lead to financial losses but also have a significant impact on patients (Uthayakumar and Priyan, 2013). The coordination of stakeholders around inventory management is a key component for attaining these objectives effectively [START_REF] Kelle | Pharmaceutical supply chain specifics and inventory solutions for a hospital case[END_REF].

Patients & Passengers (P&P): the transport of patients in hospitals, commonly known as intrahospital transport, include medical transfers between healthcare facilities specialized in diagnostics or medical treatment. Patients have fixed appointments, such as x-ray, ultrasonic, blood testing or surgery. For medical reasons some patients are not able to go on their own, and need to be escorted by trained staff (Turan et al., 2011). Hence, the transport for going and return needs to be scheduled for these patients. In campus-based hospitals, intrahospital transport is provided by appropriate vehicles, generally, ambulances, which several patients often share [START_REF] Hanne | Bringing robustness to patient flow management through optimized patient transports in hospitals[END_REF]. Some PWD living at home or in boarding schools need specialized transport for moving to different places such as school centers or workplaces. They usually go every day from home to Medico Social Institutions (MSI) in the morning and go back home in the afternoon [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF].

The following section defines the types of transport for P&P in a general context before detailing in the non-emergency transport of P&P which is the focus of this chapter.

Emergency and non-emergency transport for patients & passengers

Healthcare transport of P&P differentiates from both emergency and non-emergency cases.

The first case is when the life of a person is in danger and the second one is, for example, the transport of patients between hospitals, the daily transport of PWD or home care. Over the past years, much attention has focused on the emergency transport of acute and critical-care patients [START_REF] Hains | Non-emergency patient transport: what are the quality and safety issues? a systematic review[END_REF]. However, a large percentage of patient transport are of a non-urgent nature [START_REF] Robinson | Inter-facility patient transfers in ontario: Do you know what your local ambulance is being used for?[END_REF][START_REF] Hains | Non-emergency patient transport: what are the quality and safety issues? a systematic review[END_REF].

Emergency transport in the healthcare context is commonly known as emergency medical transport. Emergency transport is usually referred to the transport of patients whose conditions are life-threatening or time-critical [START_REF] Huggins | Non-emergency patient transport in victoria: An overview[END_REF]. It is mainly performed by ambulances after emergency calls due to an accident or a malfunction of the body. Emergencies are highly unpredictable in magnitude or location. The response time must be as short as possible because the person's life is in danger. There are two emergency management systems, Chapter 2. Literature review the Franco-German and the Anglo-American systems. In the Franco-German system, most patients are treated on the scene because care providers are medical doctors supported by paramedics [START_REF] Dick | Anglo-american vs. franco-german emergency medical services system[END_REF]. In the Anglo-American system, however, very few patients are treated on-scene as care providers are paramedics with medical oversight. The Anglo-American model, ambulances should be located in strategic places to be able to arrive quickly to the incident site. This model is known as "scoop and run" because the aim is to rapidly bring patients to the hospital with less pre-hospital interventions [START_REF] Al-Shaqsi | Models of international emergency medical service (ems) systems[END_REF]. In both cases, the expected level of service is very high and therefore very expensive. Thus, the transport cost is more of a budget constraint than a goal by itself. A review of the recent developments in the optimization of emergency medical services can be found in [START_REF] Saghafian | Operations research/management contributions to emergency department patient flow optimization: Review and research prospects[END_REF]; [START_REF] Bélanger | Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles[END_REF].

Non-emergency transport However, a wider view of non-urgent transport concerns also the daily transport for PWD and seniors to and from specialized centers. Reports from several countries show that non-urgent transport is continuously growing at significant levels (ANAP, 2016b;[START_REF] Hains | Non-emergency patient transport: what are the quality and safety issues? a systematic review[END_REF]. Unlike emergency transport, non-emergency cases can be scheduled at a later time depending on the needs and resources' availability. In some contexts, demands are known in advance. This anticipated knowledge can be used to optimize transport costs by pooling demands and increasing vehicle utilization. This is at the cost of a longer response and ride times. In other context, demands arrive in an on-going fashion and dispatchers should propose quickly a schedule or reject the request if there is not available schedules with the current status of the system. The non-emergency transport for P&P covers a wide variety of applications from the leisure transport for PWD to the long term transport of chronically ill patients. Non-emergency transport can be divided into subcategories according to the frequency of demand. The following section presents the characteristics of non-emergency occasional and regular transport.

2.1. Healthcare transport

Occasional and regular transport for patients & passengers

Non-emergency services can differ depending on the frequency of demands. The transport of a patient with temporal illness is called "occasional" while the transport for patients with long term care is called "regular". Occasional transport concerns non-recurrent P&P while regular transport concerns P&P with frequent and periodic demands.

Occasional transport refers to the transport of non-recurring patients. It is usually the case of punctual medical appointments for patients or the transport of extra-curricular activities for PWD. On a wider scope, this transport type is known as Transport On Demand (TOD).

Demands are called "static" if they are known before the scheduling phase or "dynamic" if demands are scheduled as they arrive [START_REF] Pillac | A review of dynamic vehicle routing problems[END_REF]. Static cases allow higher cost optimizations but usually take longer solving time. Dynamic solutions rather look for quick and cheap feasible schedules based on the current status of the system. However, real-life TOD systems manage both static and dynamic cases at a time.

TOD systems are characterized by having three often conflicting objectives: maximizing the number of requests served, minimizing operating costs and minimizing user inconvenience [START_REF] Cordeau | Transportation on demand[END_REF]. In the context of patient transport, these objectives have different names.

In healthcare transport, three common objectives are the number of patients served, transport costs and individual/collective preferences. Sometimes one objective can prevail over the others depending on the application. [START_REF] Rasmussen | The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies[END_REF] for example, in an application to the Danish home care service for seniors and disabled citizens, consider as a primary objective the number of served patients, the visit preferences as secondary and lastly the operating costs. For PWD, preferences are usually expressed in terms of the desired pickup and delivery time [START_REF] Jaw | A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows[END_REF].

Regular transport concerns recurrent demands of patients during a planning horizon. Most of PWD are transported daily to medico-social institutions or twice a week for those in boarding houses. Patients with a long-term illness such as dialysis, tracheotomy or ventilator care that is treated on a regular basis at home or in the hospital. The planning horizon for regular transport is long, the school year for PWD. With demand information well in advance, transporters can optimize costs by pooling resources. However, regular transport often assumes additional objectives such as staff-consistency and time-consistency.

Staff-consistency in a medical context refers to the fact that patients expect to be followed up by the same caregiver [START_REF] Allaoua | Routage et planification des personnels pour l'hospitalisation à domicile[END_REF]. In the transport of PWD it is known as driverconsistency [START_REF] Braekers | A multi-period dial-a-ride problem with driver consistency[END_REF]. PWD with autism, for example, hardly supports the change of driver. At most, they tolerate a reduced pool of drivers acknowledged beforehand.

Time-consistency refers to having a similar service time every time. For regular patients is highly desirable to have consistent visit schedules. For children with disabilities, families are

Chapter 2. Literature review not ready to accept highly inconsistent schedules during the week [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]. Some PWD cannot tolerate irregular time schedules.

Optimization problems in the non-emergency transport of patients & passengers with disabilities

Different types of problems are found in the optimization of non-urgent transport of P&P. Some problems deal with the whole transport system while other problems only a part of it.

For example, the selection of the vehicle fleet can greatly influence the transport costs in the long-term. However, the re-scheduling of transport routes concern a small group of patients during a short time period. Healthcare systems differ from production systems in having constraints and objectives related to the service quality of patients. There are four decision problems in the transport optimization of patients: strategic problems concerning long-term decisions usually at the scale of years; tactical problems for medium-term decisions at the scale of months; operational problems for short-term decisions at the scale of days; and real-time problems concerning dynamic decisions. Table 2.3 shows the main characteristics found in applications for the literature review of non-emergency transport of P&P. The following parts describe the research problems found at each decision level.

Optimization problems in the non-emergency transport of patients & passengers

with disabilities

Strategic problems

Strategic problems concern long-term decisions such as depot location, fleet size or opening hours for MSI. Healthcare institutions locate depots next to facilities in order to reduce response times that are critical in urgent cases. Depots are then located at the same time as health care facilities. Facility location problems in a non-emergency context are very often solved independently of the routing design [START_REF] Ahmadi-Javid | A survey of healthcare facility location[END_REF]. However, some applications consider simultaneously location and routing to improve the service access in applications for developing countries [START_REF] Doerner | Multicriteria tour planning for mobile healthcare facilities in a developing country[END_REF]ur Rahman and Smith, 2000).

The vehicle fleet for P&P is highly varied due to a large number of possibilities of combining wheelchair, seats or stretchers. Hence, the choice of vehicles and the fleet dimensioning is a real concern for transporters. [START_REF] Fu | Fleet size and mix optimization for paratransit services[END_REF] proposed a method to estimate the fleet size and mix for a given application. A case study for the weekday paratransit service in Canada is presented considering low-demand of 460 trips and high-demand of 682 trips scenarios. This study confirms the intuition that the larger the vehicles, the higher the average vehicle productivity and the smaller the required fleet size. Moreover, under high-demand applications is more advantageous to use larger vehicles. Clearly, there exists a critical point beyond which additional capacity would not improve the system performance.

In the paratransit context, the opening hours of MSIs impact the possibilities of transport

Tactical problems

Tactical decisions consider medium-term choices about the routes design and service-oriented considerations such as time-consistency and driver-consistency for regular P&P. In scientific literature, the routing problem that better adapts to the characteristics of paratransit is the Dial-A-Ride Problem (DARP). Unlike classic routing problems, DARPs include constraints and objectives related to the services offered to passengers [START_REF] Parragh | Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints[END_REF]. Tactical decisions mostly concern multi-period transport problems (i.e multiple days for a week).

The concepts of time-consistency and driver-consistency have been presented in the previous section. The relationship between time-consistency and transport costs is studied in a vehicle routing problem (VRP) context which is a DARP without time constraints and with a single delivery point (MSI). The majority of contributions on this field are developed for the transport of goods [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF]Kovacs et al., 2015a). However, [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] proposed a new

Chapter 2. Literature review consistency measure adapted to the transport of people. This measure is defined for each user and is based on time slots of fixed width (i.e. 10 minutes). Thus, service times within 10 minutes to each other will be considered in the same class. The user time-consistency is therefore equal to the number of different time-classes. This problem is called the time-consistent VRP. To the best of our knowledge, the time-consistency aspect has not been investigated in a DARP context.

The impact of driver-consistency on transport costs is examined in [START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF]

Operational problems

Operational problems concern the design of vehicle routes for a single time period (i.e one day).

In the occasional transport of patients, new requests are generally collected during the day, so that the next day's itineraries are scheduled at the end of the day. The majority of applications in the literature concern operational routing problems considering different transport features.

Toth and Vigo (1997) solved a DARP with heterogeneous users (seat and wheelchair) for the paratransit service in the city of Bologna. This problem was later extended to include heterogeneous vehicles [START_REF] Borndörfer | Telebus berlin: Vehicle scheduling in a dial-a-ride system[END_REF][START_REF] Parragh | Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem[END_REF] and multiple depots [START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF][START_REF] Detti | A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare[END_REF]. [START_REF] Borndörfer | Telebus berlin: Vehicle scheduling in a dial-a-ride system[END_REF] and [START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF] studied a paratransit service in Germany and Belgium respectively while Parragh (2011) a broader transport service including the transport of patients in stretchers for the Austrian Red Crox.

The DARP with heterogeneous users and vehicles is called Heterogeneous DARP (H-DARP).

It is quite common in paratransit vehicles to have different inner configurations of seats and wheelchair spaces to be able to adapt to the different needs of demand. Configurations may be done at depots [START_REF] Rekiek | Handicapped Person Transportation: An application of the Grouping Genetic Algorithm[END_REF][START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] or en-route (Tellez et al., 2018b).

En-route reconfigurations are only possible for easy layout modifications like (un)folding seats without significant changeover time. Higher flexibility of vehicles favors greater utilization of the vehicles and transportation pooling. The DARP with en-route reconfigurations is a contribution of this thesis and will be presented in Chapter 3 (Tellez et al., 2018b).

The DARP assumes a full driver availability. However, in practice, drivers are subject to regulatory rules. The DARP with driver-related constraints is studied in Xiang et al. (2006a); [START_REF] Parragh | Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints[END_REF]; [START_REF] Zhang | A memetic algorithm for the patient transportation problem[END_REF]. [START_REF] Zhang | A memetic algorithm for the patient transportation problem[END_REF] and elderly patients from one healthcare location to another. This problem is modeled as a multi-trip dial-a-ride problem which requires designing several routes for each ambulance in order to maximize driver availability. Some patients present preferences about drivers or incompatibilities with other patients for reasons of health or behavior [START_REF] Detti | A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare[END_REF].

Some healthcare applications consider service quality not as a constraint but as an objective in itself. [START_REF] Paquette | Measuring quality of service in dial-a-ride operations: the case of a canadian city[END_REF] proposed some quality measures for evaluating the service of dial-a-ride systems. And, for a case study in the paratransit transport of a Canadian city the authors combine objectives related to costs, waiting time and user ride time using dynamic weights for generating non-dominant solutions [START_REF] Paquette | Combining multicriteria analysis and tabu search for dial-a-ride problems[END_REF]. [START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF] proposed a multi-criteria approach for combining cost and patient-oriented objectives within a preference model based on the choquet integral. For an application in the transport of patients in Belgium, [START_REF] Molenbruch | Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation[END_REF] proposed a bi-objective modeling to evaluate the trade-off between the operational efficiency and the service quality measured by total ride time.

The Aeromedical Airlift Wing of the United States Air Force is responsible for transporting personnel in need of specialized medical treatment to and from military hospitals. Non-emergency patients may be transferred before the actual consultation date for increasing vehicle utilization and reduce transport costs. This problem is modeled as a route based pickup and delivery problem with the objective of minimizing the number of nights at the hospital before consultation [START_REF] Ruland | A model for aeromedical routing and scheduling[END_REF]. Other applications consider service oriented criteria into a single weighted objective function using suitable coefficients [START_REF] Fu | Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time[END_REF][START_REF] Fu | Scheduling dial-a-ride paratransit under time-varying, stochastic congestion[END_REF][START_REF] Ruland | A model for aeromedical routing and scheduling[END_REF][START_REF] Aldaihani | Hybrid scheduling methods for paratransit operations[END_REF][START_REF] Detti | A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare[END_REF].

Door-to-door transport systems may be combined with other application-related problems. [START_REF] Aldaihani | Hybrid scheduling methods for paratransit operations[END_REF] studied the integration of the transport on-demand with fixed bus lines in the transport for disabled or elderly individuals at Lancaster, California. The aim of the integration is to reduce the vehicle miles of the transport on-demand which is more expensive. [START_REF] Dikas | Scheduled paratransit transport systems[END_REF], on the contrary, considered the case in which buses operating in public transport routes may diverge from its nominal path to pick-up passengers and drop them off at their destination. This service is particularly relevant for people with limited mobility that can not easily reach bus stops. Two objectives in a lexicographic order were considered: first the maximization of requests served; and then the total ride time in order to select the solutions with lower ride times for the rest of passengers. [START_REF] Coppi | A planning and routing model for patient transportation in health care[END_REF] modeled the healthcare timetable of non-urgent patients for a hospital in the city of Tuscany (Italy), in such a way that the transportation costs for patients going to hospitals is minimized.

Most routing problems applications assume deterministic and time-unvarying travel times.

However, traffic congestion in an urban environment can significantly modify these times [START_REF] Fu | On-line and off-line routing and scheduling of dial-a-ride paratransit vehicles[END_REF]. [START_REF] Fu | Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time[END_REF] studied the disabled adult transportation system in the city of Edmonton (Canada) under dynamic and stochastic travel times. Travel times may differ at different hours of the day (dynamic) and can be altered by external events like traffic (stochastic).

Chapter 2. Literature review

His study showed that there are several negatives consequences from ignoring the dynamic and stochastic variation of travel times such as a high percentage of trips that may not be served during their desired time windows and a decline in vehicle productivity due to the dynamic aspect [START_REF] Fu | Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time[END_REF].

The previous problems conceive solutions for occasional transport services. Regular transport problems are modeled with additional patient requirements into a DARP system. Fleischmann et al. ( 2009) for example consider a desired pick-up and drop-off service times beside the DARP time windows. The objective of this problem is to minimize the transport cost as well as deviations to the desired service time. Some patients may be absented one day for different reasons. In those cases, transport planners should adjust vehicle routes so that the inconvenience to the rest of passengers is minimized. To our knowledge, this problem has not been studied in the literature. A closer problem in the transport of goods seeks to minimize planning discrepancies with the original schedule in relation to service times. This problem is known as the vehicle re-scheduling problem [START_REF] Spliet | The vehicle rescheduling problem[END_REF].

Real-time problems

Real-time problems treat decisions mainly about accepting new transport requests, canceling or reprogramming existing ones. Very often, new transport requests arrive with the desired service for the same day time, while vehicles are already in service with operational schedules.

The dispatcher usually has to give an immediate answer providing a pickup and drop-off times if the transport is feasible. Routing problems with on-line decisions are usually known as dynamic problems. In these problems, real-time technological support is needed to inform vehicles en-route about schedule modifications [START_REF] Pillac | A review of dynamic vehicle routing problems[END_REF].

Most of the paratransit applications combine a dynamic version of the DARP (Dyn-DARP)

dealing with on-line requests with classic planning dealing with off-line requests from the day before [START_REF] Madsen | A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives[END_REF][START_REF] Fu | Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time[END_REF][START_REF] Xiang | A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints[END_REF][START_REF] Schilde | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports[END_REF]. However, patient transfers between hospitals are mainly dynamic as on-line requests account for around 90% of cases [START_REF] Hanne | Bringing robustness to patient flow management through optimized patient transports in hospitals[END_REF][START_REF] Beaudry | Dynamic transportation of patients in hospitals[END_REF]. Dyn-DARPs are based on fast heuristics to quickly find a suitable schedule of the incoming request. Scheduling in paratransit services might be influenced by traveling time fluctuation or external events such as traffic congestion. This problem, known as the dynamic dial-a-ride problem under time-dependent and stochastic events, is studied in [START_REF] Fu | On-line and off-line routing and scheduling of dial-a-ride paratransit vehicles[END_REF] for the paratransit service in the city of Edmonton (Canada). Then, it was extended to include other stochastic events, such as new requests, absences, vehicle breakdowns, and cancellations [START_REF] Schilde | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports[END_REF]. Results showed that dynamic problems under stochastic events provide more reliable and realistic transport schedules to customers.

Transport requests can sometimes be anticipated with the help of historic data. A patient regularly transported from home to a hospital for dialysis, consumes a predictable amount of time before going back home. An application of the daily operations in the Austrian Red

Cross studied the impact of adding prior information about inbound requests. With a certain probability, each outbound request causes a corresponding inbound request on the same day. The result is a Dynamic and Stochastic DARP (Dyn-S-DARP) showing that models with stochastic information can outperform myopic dynamic models under certain circumstances [START_REF] Schilde | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports[END_REF]. Real-time problems are mainly occasional. Similarly, to operational problems, regular applications would imply on-line planning modifications that minimize deviations to the original schedule.

Chapter 2. Literature review

Conclusions

In healthcare transport, there are different operating modes according to the nature of the demand. The two main transport types are emergency and non-emergency transport. A lot of attention has been focused on the evolution of emergency medical systems. However, a large percentage of patient transport is non-urgent. Non-emergency transport concerns a wide range of applications in-home care, transport for PWD and intra-hospital transport.

Depending on the frequency of demands of recurrent P&P, non-emergency transport can be occasional or regular. Both transport types differ to each other in their objectives and characteristics. This thesis examines long-term transport planning for people with disabilities that, according to this classification, falls into the category of non-emergency regular transport.

Contributions in the non-emergency transport of patients can impact the system's performance at a strategic, tactical, operational or real-time level. There are numerous contributions in this area, especially at the operational and real-time levels.

Reviewed applications at the strategic level are very few and do not distinguish regular and occasional P&P. Regular transport problems are mostly studied at the tactic level. However, the needs of time-consistency in a DARP context, which is a characteristic of regular transport systems, has not been studied in the literature. The definition and solution of this problem is a contribution of this thesis that will be studied in Chapter 4.

At the operational level, en-route reconfiguration of vehicles is a novelty contribution of this thesis which will be presented in Chapter 3.

Finally, we point out that although the decisions about the opening hours of MSIs are out of reach of transporters. It is to the interest of both MSIs and transporters to negotiate these hours that can lead to a possible transport pooling among MSIs. Transport pooling is not a common practice in the medico-social sector. However, there is an economic intensive to share resources. The impact of transport pooling in the daily transport of PWD will be studied in Chapter 5. for a recent survey on PDP). The main applications concern door-to-door transportation of people, particularly elderly or disabled people.

In this chapter, we propose a generalization of the heterogeneous PDP with configurable vehicle capacity introduced by [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF]. This problem includes both heterogeneous fleets of vehicles and heterogeneous users. We consider several types of users who do not occupy the same space in the vehicle (e.g. passengers using seats or wheelchairs). The vehicle capacity depends on the chosen configuration. A configuration is characterized by a multidimensional capacity vector indicating the maximum number of users of each type allowed in the vehicle.

Figure 3.1 presents three configurations of a vehicle with two types of users (passengers using seats or wheelchairs). The configuration has a capacity of 1 wheelchair and 7 seats, including 5 folding seats (the driver's seat is not available for passengers). In the second configuration, one folding seat has been lifted and replaced by a wheelchair space. This configuration has a capacity of 2 wheelchairs and 6 seats. Adding one more wheelchair requires two additional seats to be folded. This is represented by the third configuration, which has a capacity of 3 wheelchairs and 4 seats.

Vehicle reconfiguration is as simple as folding or unfolding a foldable seat. This operation is performed manually by the driver, when the vehicle is parked. It takes only a few seconds, while service times take several minutes (including the time necessary to park the vehicle, install the car ramp, help passengers get in/off the vehicle, etc.). Although reconfigurable vehicles lead to higher vehicle investments, neither extra time nor cost is associated with the operation of en-route reconfiguration.

Note that there is no linear correspondence between the number of seats and wheelchairs.

Moreover, the total number of passengers can be either 7 or 8, depending on the chosen configuration.

Qu and Bard (2013) integrate the choice of the initial vehicle configurations as a decision variable in a PDP dedicated to the transport of people with reduced mobility. In such services, it is actually possible to switch en-route from one configuration to another to serve additional transportation requests. As a result, we propose a generalization to the problem presented by [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF], by assuming the possibility of en-route reconfiguration. This extension From Mondays to Fridays, users are picked up at home in the morning and driven to their MSI.

In the afternoon, they are transported back home. For MSIs, transportation is often considered the second-biggest expense after wages. Optimizing transport is therefore a priority. In this chapter, without loss of generality, we present the case of morning trips. Every year, the company defines the fleet mix as well as the vehicles' itineraries. In addition, routing planners re-assess decisions daily, if required. All decisions are currently made without vehicle routing software.

In order to design routes, route planners have to use simplifying assumptions, e.g. considering each MSI separately and ignoring the possibility of en-route vehicle reconfiguration. These assumptions lead to an over-constrained problem and consequently, to sub-optimal solutions.

One aim of this chapter is to solve the problem of having to stop at several MSIs on the same route. Using reconfigurable vehicles furthermore increases the possibility to pool routes between MSIs. Another aim of this chapter is to assess the impact of en-route reconfiguration.

The chapter is organized as follows: Section 3.2 reviews related problems. Section 3.3 presents the problem settings and the mathematical formulation for the FSM-DARP-RC. Section 3.4

1 www.gihp-sa.com

Chapter 3. Half-day transport problem is dedicated to the solution method. In particular, we detail the Large Neighborhood Search (LNS) operators and the set covering component. The capacity check and the minimization of the number of reconfigurations are detailed in Section 3.5. We report extensive computational results and management insights in Section 3.6. Finally, Section 3.7 gives the conclusions and prospects.

Literature review

In this section, we first review some related work on DARP. We then present papers regarding the design and the routing of a fleet of heterogeneous vehicles with a special focus on DARP applications. Finally, we discuss how configuration and reconfiguration have been considered in the Vehicle Routing Problem (VRP) literature.

The dial-a-ride problem

The DARP is related to the optimization of a multi-occupancy, door-to-door transport service for people [START_REF] Doerner | Pickup-and-delivery problems for people transportation[END_REF]. Most commonly, this problem consists in designing the routes of a homogeneous fleet of vehicles to satisfy a set of transportation requests.

The objective is to minimize the sum of route costs, satisfying constraints on vehicle capacity, time windows at origins and destinations of requests, and limits on the ride time of each passenger. Due to the combinatorial nature of the problem, exact methods (see for instance [START_REF] Gschwind | Route Feasibility Testing and Forward Time Slack for the Synchronized Pickup and Delivery Problem[END_REF]). The latest contribution in this area is [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF], which proposes an incremental algorithm to evaluate, in constant time, the feasibility of request insertions in routes. The minimization of route duration is considered in Cordeau and Laporte 2003). This algorithm has been used and extended in many papers such as [START_REF] Parragh | Variable neighborhood search for the dial-a-ride problem[END_REF] and [START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF].

3.2. Literature review (

Routing a heterogeneous fleet of vehicles

In the FSM-DARP-RC, a heterogeneous fleet of vehicles has to be constituted to transport several types of users. In the VRP context, the routing of a heterogeneous fleet of vehicles was recently surveyed in [START_REF] Koç | Thirty years of heterogeneous vehicle routing[END_REF]. Problems of this class fall into two main variants: (i) the

Configurable vehicle capacity

Finally, the FSM-DARP-RC extends the notion of vehicle configuration, which implies having multiple capacity options for some vehicles. To our knowledge, this notion was first introduced by Qu and Bard (2013) who define the heterogeneous PDP with configurable vehicle capacity.

The problem could actually be called a DARP since it integrates considerations related to passenger transportation such as ride time minimization. These authors consider a limited and heterogeneous fleet of configurable vehicles that serve transportation requests coming from a heterogeneous set of passengers. In addition to routing decisions, one configuration must be chosen for each vehicle. Hence, this problem differs from the FSM-DARP-RC since a vehicle is assumed to keep the same configurations for its entire route. The authors propose a multi-start ALNS. The assignment of configurations for a given set of routes is done in a feasibility check either by a heuristic or by solving a general assignment problem when the heuristic fails. A branch-and-price algorithm for this problem was also proposed in [START_REF] Qu | A Branch-and-Price-and-Cut Algorithm for Heterogeneous Pickup and Delivery Problems with Configurable Vehicle Capacity[END_REF] for instances with up to 30 requests.

Chapter 3. Half-day transport problem

Choosing a vehicle configuration can be compared to determining compartment sizes in the flexible multi-compartment VRP described in [START_REF] Derigs | Vehicle routing with compartments: applications, modelling and heuristics[END_REF]. In this chapter, compartment sizes are determined together with a set of routes for vehicles with flexible compartments. The goal is to deliver various types of goods, given that some goods cannot be transported in the same compartment. Compartments can be continuously flexible as presented in [START_REF] Koch | A genetic algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes[END_REF]; [START_REF] Derigs | Vehicle routing with compartments: applications, modelling and heuristics[END_REF], or discretely flexible if compartment options are defined beforehand as in [START_REF] Henke | The multi-compartment vehicle routing problem with flexible compartment sizes[END_REF]. The difference with our problem is twofold: first, in the FSM-DARP-RC, the total capacity changes from one configuration to another, in a non-linear way, whereas in multi-compartment problems, the sum of compartment sizes is assumed to remain constant.

Second, we consider a PDP. Hence, a vehicle's load can increase and decrease along its route and en-route reconfiguration may be advantageous. In a VRP, a single configuration is needed since all goods are delivered at once. To our knowledge, the PDP with flexible compartment sizes has not been studied.

Contributions with respect to the literature

Regarding the literature, the main contributions of this chapter are the following. First, we introduce the FSM-DARP-RC and propose a mathematical model for this problem. Second, we propose a matheuristic framework that combines a LNS with a reactive set covering component to solve this problem. This matheuristic is proven to be competitive on benchmark instances for the DARP and the heterogeneous PDP with configurable vehicle capacity. This matheuristic integrates innovative components related to the use of reconfigurable vehicles: (i) the vehicle selection procedure, which efficiently determines the minimum cost of a reconfigurable vehicle that is feasible for a given route, and (ii) the reconfigurable vehicle capacity test, which determines if a given vehicle can perform a given route together with its minimum number of reconfigurations.

We also show that, when it is combined with a set covering component in a matheuristic, the ALNS framework introduced in Pisinger and Ropke ( 2007) can be simplified. Finally, we present some managerial insights based on our experiments on the real instances provided by the GIHP.

These instances will be made available to the community.

Problem settings and mathematical model

In this section, we start by providing an example of en-route reconfiguration. Then in Section 3.3.2 the FSM-DARP-RC problem is formally described, and is modeled in Section 3.3.3.

Example

The example represented in Figure 3.2 illustrates the potential benefits of vehicle reconfiguration.

We consider a single vehicle which starts and terminates its routes at depot D. This vehicle has two possible configurations, denoted as c 1 and c 2 respectively. Configuration c 1 consists of Without an en-route reconfiguration policy, the only solution is to leave the depot D with configuration c 1 , which is the only one that includes a wheelchair space. The optimal solution for this policy is represented with dashed lines in Figure 3.2.

However, with en-route reconfiguration policy, the vehicle can be configured with configuration c 2 at the depot D and reconfigured with configuration c 1 after visiting M SI 1 . This solution is represented with solid lines in Figure 3.2. This strategy reduces the length of the route by the value of the detour ∆ p 4 ,M SI 2 + ∆ MSI 2 ,p 5 -∆ p 4 ,p 5 , where ∆ i,j represents the value of the shortest path from i to j.

Problem settings

The FSM-DARP-RC is modeled on a graph G = (V, A). The set V of nodes contains the set O + of starting depots, the set O -of arrival depots, the set P of pickup locations and the set D of delivery locations. We consider a large (potentially infinite) heterogeneous fleet of vehicles.

We denote by K the set of vehicle types. Without loss of generality, we consider in this section that there is a single vehicle of each type, so that K also represents the set of vehicles. Each

(o + k , i) where k ∈ K, i ∈ P. Arcs (i, j) where i, j ∈ P ∪ D, i = j. Arcs (i, o - k ) where k ∈ K, i ∈ D.
Every arc (i, j) represents the fastest path from nodes i to j. It is associated with a travel time t ij and a distance ∆ ij .

The set of transport requests is denoted by R. These requests concern passengers who may require various types of spaces in vehicles (e.g. seat, wheelchair). By extension, the type of Chapter 3. Half-day transport problem space required by a passenger in a vehicle is called a user type and the set of user types is denoted by U. Each request r ∈ R is characterized by a pickup node p r ∈ P, a delivery node d r ∈ D, a maximum ride time T r and a quantity q r,u of users of each type to be transported from p r to d r . Note that even though each request is modeled by pair of pickup and delivery vertices, in practice, different nodes can refer to the same geographical location. We define the following notations to represent the load variation at the pickup node and the delivery node of each request respectively: φ pr,u = q r,u and φ dr,u = -q r,u . This modeling implies that one request can include many users at a time if they share the same transport requirements (pickup and delivery locations, time windows and maximum ride time). For instance, if a passenger with a wheelchair and another passenger traveling on a regular seat have the same transport requirements,they can be considered in the same request r with load q r,0 = 1 and q r,1 = 1 thus sharing the same vehicle.

Each node i ∈ V is associated with a service duration s i and a time window The set of configurations is defined by a set of capacity vectors

Q k = {Q k1 , . . . , Q k ck } with Q kc = (Q kc 1 , . . . , Q kc |U| ), where Q kc u represents the maximal number of users of type u ∈ U that can be carried by vehicle k ∈ K in configuration c ∈ C k . Example 1. Let us consider the vehicle k ∈ K represented in Figure 3.1. We have C k = {1, 2, 3} and Q k = {Q k1 , Q k2 , Q k3 } = {(4, 3), (6, 2), (7, 1)}.
The sequence of nodes visited by a vehicle forms a route. A route is characterized by a vehicle k ∈ K (and its associated depots

o + k ∈ O + and o - k ∈ O -
) and a sequence of pickup and delivery nodes. The maximal allowed route duration is denoted by T . The GIHP's experience shows that reconfigurable vehicles allow fast and easy reconfigurations. So, in this work, for a given vehicle k ∈ K, switching from a configuration c ∈ C k to another configuration c ∈ C k can be done at no cost and within negligible time. However, to limit the inconvenience for the driver, related to this task, we introduce the parameter R, which denotes the maximum number of reconfigurations allowed within a route. For each driving hour, there is a cost α related to the driver wages.

The FSM-DARP-RC consists in selecting a set of vehicles, designing their pickup and delivery routes, determining the time of service at each node and selecting the configuration used on each arc of the solution. The problem solutions must satisfy the vehicle capacity for all selected configurations, the maximum number of reconfigurations for each route, the time window constraint for each node and the maximum ride time constraint of each request.

As a generalization of the vehicle routing problem, the FSM-DARP-RC is NP-hard.

Problem settings and mathematical model

Mathematical model

Let us introduce the following variables:

x kc ij is a binary variable which is equal to 1 if vehicle k ∈ K uses arc (i, j) ∈ A
with configuration c ∈ C k , and 0 otherwise,

z k i is a binary variable which is equal to 1 if vehicle k ∈ K is reconfigured at node i ∈ P ∪ D,
and 0 otherwise.

l k i,u
is an integer variable representing the number of users of type u ∈ U in vehicle k ∈ K after visiting node i ∈ V,

w k i is a continuous variable representing the time of service of vehicle k ∈ K at node i ∈ V.
The FSM-DARP-RC can then be formulated with the following mixed integer program:

min k∈K f k i∈P c∈C k x kc o + k i + α k∈K (w k o - k -w k o + k ) + k∈K c∈C k (i,j)∈A γ k ∆ ij x kc ij (3.1) s.t. c∈C k (pr,j)∈A x kc prj - c∈C k (j,dr)∈A x kc jdr = 0 ∀r ∈ R, k ∈ K (3.2) c∈C k k∈K (j,pr)∈A x kc jpr = 1 ∀r ∈ R (3.3) c∈C k (j,i)∈A x kc ji - c∈C k (i,j)∈A x kc ij = 0 ∀i ∈ P ∪ D, k ∈ K (3.4) c∈C k i∈P x kc o + k i - c∈C k i∈D x kc io - k = 0 ∀k ∈ K (3.5) w k j ≥ w k i + t ij + s i -M ij (1 - c∈C k x kc ij ) ∀(i, j) ∈ A, k ∈ K (3.6) a i ≤ w k i ≤ b i ∀i ∈ V, k ∈ K (3.7) w k pr + s pr + t prdr ≤ w k dr ∀r ∈ R, k ∈ K (3.8) l k j,u ≥ l k i,u + φ ju -Qk u (1 - c∈C k x kc ij ) ∀(i, j) ∈ A, u ∈ U, k ∈ K (3.9) l k i,u ≤ c∈C k (i,j)∈A Q kc u x kc ij ∀i ∈ P, u ∈ U, k ∈ K (3.10) c ∈C k /{c} (j,i)∈A x kc ji + (i,j)∈A x kc ij ≤ 1 + z k i ∀i ∈ P ∪ D, k ∈ K, c ∈ C k (3.11) i∈P∪D z k i ≤ R ∀k ∈ K (3.12) w k dr -w k pr -s pr ≤ T r ∀r ∈ R, k ∈ K (3.13) w k o - k -w k o + k ≤ T ∀k ∈ K (3.14) x kc ij ∈ {0, 1} ∀(i, j) ∈ A, k ∈ K (3.15) Chapter 3. Half-day transport problem l k i,u ∈ Z + ∀i ∈ V, u ∈ U, k ∈ K (3.16) w k i ∈ R + ∀i ∈ V, k ∈ K (3.17) z k i ∈ {0, 1} ∀i ∈ P ∪ D, k ∈ K. (3.18)
The objective function (3.1) to be minimized is the total transportation cost, including fixed costs associated with each selected vehicle, time-related costs proportional to the total route duration (which may include some waiting time), and distance-related costs proportional to the total distance traveled. Constraints (3.2) and (3.3) ensure that every transportation requests is

M ij = b i + s i + t ij .
Constraints (3.7) set time windows for variables w k i . Constraints (3.8) assure that for each request r ∈ R in each route the pickup node is visited before its corresponding delivery node.

Constraints (3.9) propagate the load along the route in each type of user each time the arc (i, j) ∈ A is crossed by a vehicle k. The constraint linearization requires to define a big-M value denoted as Qk u = max c∈C k {Q kc u }, the maximum capacity of type u ∈ U among all configurations. Constraints (3.10) correspond to the vehicle capacity for each type of user. Note that, as the quantity of users cannot increase during deliveries, those constraints can be defined for pickup nodes only.

Constraints (3.11) and (3.12) concern the reconfiguration of vehicles. In constraints (3.11), the variable z k i is set at value 1 when the vehicle k ∈ K is reconfigured at node i. Constraints (3.12) limit the number of reconfigurations to be less than R for each vehicle. Constraints (3.13) limit the total ride time (including waiting and service times) of request r ∈ R to be less than T r . Constraints (3.14) states that the duration of each route should be less than T . Finally, the last constraints define the decision variables.

Solution method

In this section, we describe the solution method that we propose to solve the FSM-DARP-RC.

It relies on a combination of two components: a Large Neighborhood Search (LNS) and the solution of a Set Covering Problem (SCP) using a layer with a Reactive adjustment of SCP parameters (denoted RSCP). The framework is denoted LNS-RSCP. This section is structured as follows: Section 3.4.1 presents the general framework of LNS-RSCP. LNS removal and repair operators are detailed in Section 3.4.2 and the RSCP is presented in Section 3.4.3.

Solution method

Matheuristic framework (LNS-RSCP)

LNS was first proposed by [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF] in a constraint programming context and introduced under the name ruin and recreate in [START_REF] Schrimpf | Record breaking optimization results using the ruin and recreate principle[END_REF]. In LNS, the current solution is improved by following an iterative process of destroying it (i.e. removing a part of it) and repairing it. This process is repeated until a stopping criterion is reached. In our case, the stopping criterion is either a maximum number of iterations or a maximum computational time.

The potential of LNS for solving a large variety of vehicle routing problems was revealed by Ropke and Pisinger who proposed an Adaptive version of LNS, known as ALNS, consisting of multiple search operators adaptively selected according to their past performance (see e.g. [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF] and [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]). LNS was successfully applied to many variants of vehicle routing problems. In particular, it remains one of the best-known approaches to solve PDPs.

The RSCP component acts as a long-term memory. Given that routes that appear together in optimal or near-optimal solutions can be generated at distinct LNS iterations, it aims at reassembling these routes. Let us consider two routes ω and ω , with respective costs Π(ω) and Π(ω ). Route ω is said to dominate ω if both routes visit the same nodes and Π(ω) ≤ Π(ω ).

All non-dominated routes collected through LNS iterations are stored in a set Ω = {1, . . . , |Ω|} called the pool of routes. The RSCP component is based on a route-based formulation of the FSM-DARP-RC built from this pool. An SCP is solved with an MILP solver at regular intervals.

The number of iterations between each SCP solution is adjusted in a reactive way, as described below. The solver is given a time limit to solve this problem.

The LNS-RSCP framework is described in Algorithm 1.

The algorithm requires a set of repair and removal operators denoted as Σ + , Σ -respectively.The initial solution is created using a repair operator, denoted as σ + init ∈ Σ + , from a totally destroyed solution. At every iteration, the proportion of requests to be removed, called Φ, is randomly determined according to a continuous uniform distribution on the interval between parameters Φ -and Φ + , where 0 < Φ -< Φ + < 1 (line 7). A removal operator σ -∈ Σ -and a repair operator σ + ∈ Σ + are selected according to a discrete uniform distribution in line 8. The operator σ -removes max{1, Φ • |R| } requests from the current solution s (line 9). These requests are placed in a set of unsatisfied requests called Request Bank (B). From the request bank B, they are reinserted into the partially destroyed solution using the repair operator σ + (line 10). If the solution cannot be completely repaired, its total cost is increased by the value penalty for each unsatisfied request. Once the solution s is repaired, it can be either accepted or rejected as the next current solution using an acceptance criterion (line 11). We use the recordto-record acceptance criterion proposed by [START_REF] Dueck | New optimization heuristics[END_REF]: if objective(s ) ≤ (1 + χ).objective(s * ), then s is accepted as the new current solution where χ is a small positive value. We refer to [START_REF] Santini | A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic[END_REF] cheaper than s * is found (lines 13-14). Finally, lines 15 to 22 describe the RSCP component of the algorithm. Every η iteration (line 16), SCP is solved with a MILP solver to find the best combination of routes generated during the previous iterations (line 15). A parameter t limit is used to limit the time allocated to the solver. When the SCP cannot be solved to optimality within the time limit, the pool of routes Ω is cleared and reinitialized with the routes of the best-known solution s * (line 19). The reactive layer of the RSCP readjusts parameter η every time the solver fails to optimally solve the SCP twice consecutively (line 20).

LNS operators

The sets of removal and repair operators are major components of the LNS method. Hence, many LNS operators have been developed. [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]

Removal operators

These operators determine the set of requests to be removed from the current solution according to a given criterion. The following operators have been used:

• Random removal: This operator removes a proportion Φ of randomly selected requests from the current solution.

• Historical node-pair removal: This operator consists in removing a proportion Φ of requests from the current solution that were "better placed" in previous solutions. The LNS algorithm calculates a score for each arc (i, j) ∈ A. The initial score of each arc is set to infinity. It is then updated at each iteration with the value of the best solution found so far that includes arc (i, j). The removal heuristic calculates the cost of a request r ∈ R from pickup node i to delivery node j by summing the score of the arcs that are incident to i and j in the current solution. It then removes requests according to a probabilistic rule used in [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF]: Consider the list R of requests sorted by non-increasing costs. The operator iteratively removes the request at position ξ p × |R|, where 0 ≤ ξ < 1 is a random number and p ∈ Z is a deterministic parameter.

This probabilistic choice gives higher probability to the requests with the highest cost to be removed.

Chapter 3. Half-day transport problem

We also implemented the following operators, that were not kept in the final version of the LNS: worst removal, which removes the request responsible for the longest detour in the solution; distance-related removal which removes the nearest nodes, based on a distance-related indicator; and time-related removal, which removes requests that are similar from a time point of view. For a full description of these operators, we refer to [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF].

Repair operators

Removed requests are stored in the request bank B. Repair operators are intended to take them out of the request bank and to re-insert them into the current partial solution. We implemented the two most common repair operators: best insertion and k-regret insertion.

• Best insertion: At each iteration, the best insertion position is calculated for each request r ∈ B, in each route of the current solution. The request with the minimal insertion cost is then inserted at its best position. This process is repeated until the request bank is empty or no more feasible insertion exists.

• K-regret: This operator generalizes Best insertion with more looking-ahead information.

At each iteration, the best insertion position of each request r ∈ B is calculated for each route of the current solution. Let ∆f j r designate the insertion cost of a request r ∈ R in its j th best route at its best position. ∆f 1 r denotes the insertion cost (min additional cost) of inserting request r ∈ R in its best route, ∆f 2 r is the insertion cost for the same request in its 2 nd best route, etc. The request r selected for insertion at its best position is: r = arg max r∈B k j=2 ∆f j r -∆f 1 r . The heuristic stops when the request bank is empty or when no more requests can be inserted. In this chapter, we consider K-regret heuristics with values of K between 2 and 4 and regard them as 3 independent operators.

Set covering problem (SCP)

The use of heuristic approaches for generating routes to solve a set covering or set partitioning formulations of the VRP was first proposed by [START_REF] Foster | An integer programming approach to the vehicle scheduling problem[END_REF]: several routes, called petals are first generated and a set partitioning problem is then solved to build a VRP solution.

This approach was then extended to multiple applications. In particular, it has been combined with local search methods in [START_REF] Rochat | Probabilistic diversification and intensification in local search for vehicle routing[END_REF] and [START_REF] Subramanian | A hybrid algorithm for a class of vehicle routing problems[END_REF] for the VRP, and has been combined with LNS-based heuristics in [START_REF] Parragh | Hybrid column generation and large neighborhood search for the dial-a-ride problem[END_REF] and [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] for the DARP. Note that, whereas [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] solve a single SCP at the very end of their algorithm, the matheuristic of [START_REF] Parragh | Hybrid column generation and large neighborhood search for the dial-a-ride problem[END_REF] uses reduced costs from the SCP solution to guide a variable neighborhood search that can possibly generate new routes. In the survey of [START_REF] Archetti | A survey on matheuristics for routing problems[END_REF] for VRP matheuristics, this approach is classified under the name of column generation based heuristics.

Solution method

The name is naturally chosen because of the similarity with set partitioning formulations in branch-and-price algorithms. More precisely, this method falls into the class of restricted master heuristics according to the same survey.

The proposed approach is based on the framework of [START_REF] Grangier | A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking[END_REF] for a VRP with cross-docking. According to this framework, a solver is called every η iterations to solve the SCP on a pool Ω containing all non-dominated routes found by LNS in the previous iterations.

When the number of routes in Ω makes the SCP intractable for the solver within a given time limit t limit , Ω is cleared and reinitialized with the routes of the best solution found so far.

In the following sections, we detail the mathematical formulation of the SCP and the pool management process. We also develop a reactive version denoted RSCP where parameter η is automatically adjusted from one SCP solving to another.

Formulation of the SCP

Note that Ω = {1, . . . , |Ω|} is the set of routes collected through LNS iterations, and π ω ∈ R + denotes the cost of route ω ∈ Ω. Let ρ rω be a parameter equal to 1 if request r ∈ R is served by route ω ∈ Ω, and 0 otherwise.

The SCP aims at building a new solution by selecting a subset of independent routes in Ω.

The SCP model uses binary variables y ω , that are set at value 1 if route ω ∈ Ω is part of the solution and 0 otherwise. The SCP can be defined by the following integer linear program.

min ω∈Ω π ω y ω (3.19) s.t. ω∈Ω ρ rω y ω ≥ 1 ∀r ∈ R (3.20) y t ∈ {0, 1} ∀ω ∈ Ω. (3.21)

SCP solving

As introduced before, the SCP is solved by a MILP solver with a run time limited to t limit . To improve the solver performance and guarantee that a feasible solution is returned, the solver is initialized with the current routes of s * using a so-called warm-start function.

Given that constraints (3.20) of the SCP model allow request duplication, a request may appear in more than one route in the optimal solution of the SCP. In this case the request is left only in the route that yields the best cost (line 21, Algorithm 1).

Chapter 3. Half-day transport problem

Management of the pool of routes Ω

At each iteration of the LNS-SCP, the non-dominated routes in the current solution are added to the pool of routes Ω (line 15, Algorithm 1), possibly dominating some routes in the pool.

Hence, the size of the pool generally increases after each iteration. Eventually, the pool becomes so large that the MILP solver cannot optimally solve the SCP within the time t limit . When this happens, the pool Ω is cleared and reinitialized with the routes of s * . This strategy used in [START_REF] Grangier | A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking[END_REF] allows for the route pool to be maintained at a reasonable size. Of course, this strategy heavily depends on the solving time left to the MILP solver.

Reactive adjustment of SCP parameters (RSCP)

The combination of the run time t limit and the frequency η determine the overall computational effort spent in solving the SCP. Thus, one issue in tuning the SCP component is to define a common policy to set the values of parameters t limit and η in all instances.

In our numerical experiments we observe that, for a given value of η, the run time necessary to optimally solve the SCP is considerably longer on larger instances. Moreover, this time is longer at the beginning of the LNS execution than at the end. This has already been observed

by [START_REF] Subramanian | A hybrid algorithm for a class of vehicle routing problems[END_REF] in a VRP context. The authors developed a reactive strategy to limit the number of routes in the SCP. Their approach requires setting 5 parameters. Moreover, a threshold mechanism eliminates bad solutions even if they contain good routes. Thus, we propose a reactive layer RSCP that allows a simpler and automatic adjustment of parameter η, reducing its value geometrically such that η ← η/ψ (Algorithm 1, line 20). This mechanism uses a single real parameter ψ > 1 and assures that every dominant route will be considered at least once in a SCP solving. Unlike the re-initialization of Ω which is done when the solver cannot solve the SCP optimally, the automatic adjustment of η is performed only when the solver cannot solve the SCP optimally twice consecutively.

Evaluation of the insertion of requests

In each iteration of the framework LNS-SCP (Algorithm 1), the repair operator checks the potential insertions of all unplanned requests in all routes at all positions. This represents a large number of insertion attempts. In practice, for every unplanned request, only the best insertion is performed. Repair operators therefore evaluate the feasibility and the performance of a very large number of unnecessary insertions, which has a major impact on the performance of the SCP-LNS algorithm. This section describes the core algorithms involved in the insertion of unplanned requests.

Let ω denote a feasible route with N nodes. Without loss of generality, let us denote by 1, ..., N the set of nodes visited by this route, where nodes 1 and N are the initial and the final depot of this route. Inserting request r ∈ R consists in inserting pickup node p r ∈ P

Evaluation of the insertion of requests

between nodes i ∈ ω and i + 1 ∈ ω and inserting delivery node d r ∈ D between nodes j ∈ ω and j + 1 ∈ ω. We call ω the route resulting from this request insertion, as represented in Figure 3.3

1 i i + 1 j j + 1 N 1 i p r i + 1 j d r j + 1 N ω ω Figure 3.3: Insertion of request r into route ω
The feasibility evaluation of ω has two parts: The Capacity evaluation checks that at least one vehicle type can serve all requests in ω with at most R reconfigurations. The Schedule evaluation computes the minimal route duration and checks if there is a departure time for route ω that complies with all users time windows and maximum ride times.

Let us denote by time(ω ) the minimal duration of route ω , K(ω ) the set of vehicle types compatible with route ω , k(ω ) ∈ K(ω ) the cheapest vehicle type compatible with route ω , and dist(ω ) the total length of route ω . Note that dist(ω ) can be computed in constant time with an incremental approach:

dist(ω ) = dist(ω) +    ∆ i,pr + ∆ pr,i+1 -∆ i,i+1 + ∆ j,dr + ∆ dr,j+1 -∆ j,j+1 if i < j, ∆ i,pr + ∆ pr,dr + ∆ dr,i+1 -∆ i,i+1 if i = j.
Remember that α and γ k represent the unitary costs related to the route duration and length respectively. Then, if route ω is feasible regarding the Capacity evaluation and the Schedule evaluation, the minimal cost Π(ω ) of route ω is determined by

Π(ω ) = α time(ω ) + min k∈K(ω ) f k + γ k dist(ω ) , = α time(ω ) + f k(ω ) + γ k(ω ) dist(ω ). (3.22)
Note that in our application, all vehicles travel at the same speed. Hence, the time feasibility and the duration of a route can be evaluated without knowing the vehicle that travels that route.

Algorithm 2 shows how the Schedule evaluation and the Capacity evaluation algorithms are organized. Since these algorithms are mutually independent, they can be executed in any order.

Although this order may impact computational times, there is no general rule to define which one should be placed first because the performance always depends on the considered data. Schedule evaluation (line 11) is performed first because our instances are mostly constrained by time windows and ride times. Accordingly, the Capacity evaluation (line 4) is run only on the resulting feasible routes. The algorithm returns the cost of an insertion, and the value -1 if the insertion is not possible.

Sections 3.5.1 and 3.5.2 detail the Schedule evaluation and the Capacity evaluation respectively.

Chapter 3. Half-day transport problem

Algorithm 2: Evaluation of a route ω Input: Routes ω and ω Output:

Total insertion cost (-1 if infeasible) 1 time(ω ) ← ScheduleEvaluation(ω ) /* Algorithm 11 */ ; 2 if time(ω ) > -1 then 3 k(ω ) ← CapacityEvaluation(ω, ω ) /* Algorithm 4 */ ; 4 if k(ω ) > -1 then 5 Π(ω ) = α time(ω ) + f k(ω ) + γ k(ω ) dist(ω ); 6 return Π(ω )
7 return -1

Schedule evaluation

The scheduling of a route first consists in determining if the user time windows and maximum ride time are respected on the route. Second, it determines a minimal duration schedule. The Schedule evaluation is the most time-consuming operation in the algorithm due to the large number of evaluations performed each time a request insertion is evaluated.

The route scheduling for our problem is performed by Algorithm 11. It is based on Tang et al. ( 2010) as presented in [START_REF] Gschwind | Route Feasibility Testing and Forward Time Slack for the Synchronized Pickup and Delivery Problem[END_REF]. We add forward time slack calculations from [START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a-ride problem[END_REF] in order to determine the minimum route duration. Note that some simple classical and necessary conditions are checked before running this algorithm.

These are well summarized in [START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF].

Let us consider a route ω = {1, ..., N }. For each node i ∈ ω, Algorithm 11 determines the beginning of service w i in such a way that route duration is minimized. This algorithm has three phases. In the first phase, the earliest possible schedule is computed for every visited node (lines 5 to 9). At the same time, we calculate the forward time slack of node 1, denoted by F 1 , and the total waiting time H on the route. The second phase minimizes the route duration by shifting the first node w 1 by F 1 units. Consequently, the beginning of service in all other nodes i = 2, . . . , N is updated (lines 11 to 13). Once the route duration is minimized, the maximum route duration constraint is verified in line 14.

The third phase checks ride-time constraints for every request (lines 16 to 27), starting from the end of the route. For any pickup node i, we denote as r ∈ R the request to which it belongs. Consequently, d r is the corresponding delivery node and i is equal to p r . The ride-time associated with this request is then w dr -w pr + s r . If the value (w dr -w pr + s r ) -T i is positive, then the max ride-time constraint associated with pickup p r is violated. In this case, the beginning of service w pr is shifted by the value of this violation (line 25). This may lead to infeasibility on time windows, which is checked in lines 26 to 29. Finally, since the beginning of service w pr may have been changed, the ride-time constraint for request r is checked again in line 30. If no infeasibility is detected, the minimal route duration w N -w 1 is returned (line 29).

w i ← max{a i ; w i-1 + s i-1 + t i-1,i } if w i > b i then return -1 H ← H + max{0; a i -(w i-1 + t i-1,i + s i-1 )} F 1 ← min{F 1 ; H + max{0; b i -w i }} /* Phase 2: optimize route duration */ w 1 ← w 1 + F 1 for i = 2, . . . , N do w i ← max{w i-1 + s i-1 + t i-1,i ; a i } /* Check route duration constraint */ if (w N -w 1 ) > T then return -1 /* Phase 3: check ride time constraints */ for i = N -2, . . . , 1 do if i ∈ P then r ← request of pickup i /* Implies i = p r */ δ ← (w dr -w pr + s r ) -T r if (δ > 0) then 21 w pr ← w pr + δ 22 if w pr > b pr then return -1 23 for j = p r + 1, . . . , N do 24 w j ← max{a j ; w j-1 + s j-1 + t j-1,k } 25 if w j > b j then return -1 26 if T r -(w dr -w pr + s r ) < 0 then 27 return -1 return w N -w 1
Chapter 3. Half-day transport problem

Capacity evaluation

The objective of this section is to complete the evaluation of a route by determining the cheapest vehicle type that satisfies capacity constraints as well as the constraint on the maximal number of reconfigurations. Section 3.5.2.1 presents the procedure that assigns a vehicle to a given route.

Section 3.5.2.2 details the subroutine that checks if a given reconfigurable vehicle is feasible for a given route.

Vehicle type selection

We consider the resulting route ω after the insertion of a request r ∈ R in route ω. A first observation is that the set of vehicle types that can perform route ω is included in the set of vehicles that can perform route ω: K(ω ) ⊂ K(ω). Thus, the Capacity evaluation of ω can be limited to the vehicle types in K(ω).

A second observation is that it is sufficient to check the capacity only over a smaller subset of key nodes of the route. This leads to the following definitions:

Definition 1. We call the load profile of a route the list of vectors representing its load at every node of this route. The load profile for route ω is {l 1 , . . . , l N }, where l i = {l i,u , i ∈ 1, . . . , N ; u ∈ U}, and l i,u represents the load of user type u ∈ U at node i ∈ ω .

Load l i,u results from the accumulation of load variations of the route from node 1 to node i, i.e. l i,u = i j=1 φ j,u .

Definition 2. The set of pickup nodes of a route that are immediately followed by a delivery node is called the kernel of this route. The restriction of the load profile {l 1 , . . . , l N } to the nodes of its kernel is denoted by L.

Theorem 1. A vehicle type k ∈ K can be assigned to a route ω if, and only if

• each load l ∈ L is compatible with at least one configuration of vehicle type k,

• the number of reconfigurations required to carry every load l ∈ L is less than or equal to the maximum number of allowed reconfigurations R.

Proof. If i is the delivery node of some request r ∈ R. Then, l i,u ≤ l i-1,u for all user types u ∈ U. Thus, if the capacity is satisfied at node i -1, it is also satisfied at node i. If i is a pickup node followed by another pickup node, then l i,u ≤ l i+1,u and the capacity at i is satisfied if it is satisfied at i + 1.

Regarding the number of reconfigurations, it is trivial to note that reducing the number of loads to test can not increase the number of reconfigurations. However, we shall prove that reducing the number of test to the set of pickups followed by a delivery node do not reduce the number of reconfigurations. First, note that it is not necessary to reconfigure before a Because the load is increasing, the second pickup requires a configuration from the subset S 2 such that S 2 ⊂ S 1 . Finally, given that the configuration for the first pickup should be chosen from S 2 to minimize the number of reconfigurations, we can therefore limit the test to the second pickup and by extension to every pickup followed by a delivery.

By definition, for each node i in a route, there exist a node j in the route kernel that has a greater load (ie such that ∀u ∈ U : l i,u ≤ l j,u ). Let k be a vehicle type. If there exists a configuration c ∈ C k such that ∀u ∈ U : Q kc u ≥ l j,u , then the load l i is also compatible with configuration c. As a result, checking the vehicle capacity in every node of the route kernel is equivalent to check the vehicle feasibility of the entire route. Then, in order to save computation time, the capacity evaluation of route ω can be restricted to its kernel. Considering that k can be reconfigured and that several types of users are considered, this evaluation is non-trivial and is detailed in Section 3.5.2.2.

Algorithm 4: Capacity evaluation

Input: Routes ω and ω , list K(ω) of vehicle types compatible with ω, distance dist(ω ) Output: Cheapest vehicle type for the route ω (- Given that vehicles type k ∈ K(ω) are tested one by one in non-decreasing order of values λ k , as soon as ω is feasible for a given k ∈ K(ω ), we have k = k(ω ).

1 if infeasible) 1 /* Estimate partial route costs */ 2 forall k ∈ K(ω) do 3 λ k = f k + dist(ω )v k

Vehicle type feasibility

In this section, we focus on solving the question: given a vehicle type k ∈ K and a load profile L, can this vehicle carry this load? (see line 13, Algorithm 4)

Evaluation of the insertion of requests

Recall that Q k is the set of all configuration vectors for a vehicle type k ∈ K, represented by the |C k | × |U | matrix:

Q k =        Q k1 . . . Q k|C k |        =        Q k1 1 . . . Q k1 |U | . . . . . . . . . Q k|C k | 1 . . . Q k|C k | |U |       
, where Q kc represents the c th configuration (c ∈ C k ) of vehicle k and Q kc u the capacity of vehicle type k in configuration c for user u ∈ U.

Example 2. Let us consider the vehicle type k described in Figure 3.1. Figure 3.5 represents According to these notations, we can state that a route ω is feasible for a given vehicle type k if: (i) for each load l in the route kernel L, there is a capacity vector in Q k that is greater than l; and (ii) if the minimum number of reconfigurations of k to operate L is less than R.

Q k1 , Q k2 , Q k3 . Seats Wheelchairs 0 1 2 3 4 5 6 7 1 2 3 Q k1 Q k2 Q k3
The efficiency of these two checks is increased by computing a priori the list of feasible configurations for each possible load vector and for each vehicle type. The envelope set of possible load vectors is defined by

T k = {0, . . . , max c∈C k Q kc 1 } × • • • × {0, . . . , max c∈C k Q kc |U| }.
Mathematically, we define S k (l) as the function that maps the set of feasible configurations of vehicle type k for a given load l.

S k : T k → P(C k ),
where P(.) is the power-set function of set C k , i.e. the set of all subsets of C k , including the empty set and C k itself.

Chapter 3. Half-day transport problem

The function S k (.) can be pre-processed and written as a matrix with |U| dimensions. Each vector of feasible configuration in this matrix is encoded using a bitset. This guarantees a limited size in memory and a O(1) access to the list of configurations able to carry any element of T k .

Table 3.1 details the value of function S k (.) in the case described by Example 2 and Figure 3.5. For each possible load value, this table returns the list of configurations that are compatible with this load. For example, for a load of 4 seats and 2 wheelchairs, configurations 1 and 2 are feasible. For a load of 6 seats and 3 wheelchairs, there is no feasible configuration.

Seats Wheelchairs 3 {1} {1} {1} {1} {1} ∅ ∅ ∅ 2 {1, 2} {1, 2} {1, 2} {1, 2} {1, 2} {2} {2} ∅ 1 {1, 2, 3} {1, 2, 3} {1, 2, 3} {1, 2, 3} {1, 2, 3} {2, 3} {2, 3} {3} 0 {1, 2, 3} {1, 2, 3} {1, 2, 3} {1, 2, 3} {1, 2, 3} {2, 3} {2, 3} {3} 0 1 2 3 4 5 6 7
Table 3.1: Matrix representation of S k for the vehicle presented in Figure 3.1.

Algorithm 5 presents the procedure for evaluating the feasibility of vehicle k in route ω .

The algorithm initializes the number nr of necessary reconfigurations to 0 (line 1) and the set

ListConf ig with all admissible configurations (line 2). It then iteratively goes through the nodes of the entire route kernel L. If the current node is not compatible with any vehicle configuration (line 4), vehicle k is infeasible and the value -1 is returned. Otherwise, the list ListConf ig is updated with the set of feasible configurations common to this node and ListConf ig (line 6).

If the load of the current node l requires a configuration not previously stored in ListConf ig, a reconfiguration is needed. Thus, nr is increased by 1 and the ListConf ig is initialized with the set of feasible configurations of the current node (line 11). If nr exceeds the maximum value allowed, R, vehicle k is infeasible and the value -1 is returned. Finally, if every load in the nodes of the kernel are compatible with vehicle k the number of reconfigurations nr is returned.

Proposition 2. Algorithm 5 finds the minimal number of reconfigurations.

Proof. We define the graph G = (V, A) in which nodes v 1 , . . . , v |L| represent the ordered set of elements of the kernel. We define an arc between any pair of nodes which can be connected without reconfiguring the vehicle. So, if an arc (v i , v j ) exists, then all arcs of the form (v i , v j ),

where i ≤ i < j ≤ j, also exist.

With all arcs weighted by 1, finding the minimum number of reconfigurations is equivalent to finding a shortest path between v 1 and v |L| .

Given a node v i ∈ V , we define the farthest neighbor of v i as the node v j , such that the arc (v i , v j ) exists and the arc (v i , v j+1 ) does not exist. Algorithm 5 starts from v 1 and iteratively looks for the farthest neighbor of the current node. Let v 1 , v opt(2) , . . . , v |L| be an optimal path from v 1 to v |L| . We shall prove by contradiction that if some node v i is the farthest neighbor of v 1 , then it belongs to an optimal path.

Computational experiments

Algorithm 5: Feasibility of vehicle type k and number of necessary reconfigurations Input: route ω , with the load profile L of its kernel Input: vehicle k, with preprocessed values for S k (.) and T k Output: number nr of necessary reconfigurations

1 nr ← 0 2 ListConf ig ← C k 3 forall l ∈ L do /* capacity test */ 4 if l ∈ T k or S k (l) = ∅ then 5 return -1 /* number of reconfigurations test */ 6 ListConf ig ← ListConf ig ∩ S k (l) 7 if ListConf ig = ∅ then 8 nr ← nr + 1 9 if nr > R then 10 return -1 11 ListConf ig ← S k (l) 12 return nr Assume that (v 1 , v i ) is not in the shortest path from v 1 to v |L| . Because (v 1 , v j ) ∈ A, ∀j > i,
it is not possible to go from l 1 to any successor of v i with a weight of 1. So, v opt(2) < i and

v opt(3) > i. By construction, if arc (v opt(2) , v opt(3)
) exists and has weight 1, then arc (v i , v opt(3) ) also exists and has the same weight. Thus, the cost of path

v 1 → v i → v opt(3) is 2. Hence, (v 1 , v i )
is also an optimal solution.

Computational experiments

The matheuristic described in Section 3.4.1 was coded in C++ and run on a CPU Intel Xeon E5-1620 v3 @3.5Ghz. The SCP was solved with CPLEX 12.6 running on a single thread.

The matheuristic was evaluated using real and benchmark data. The parameters shown in This section is structured as follows: First, we introduce the instances used to evaluate the algorithms. In Section 3.6.2 we present the experiments that determine the choice and calibration of the main components of the proposed matheuristic. The proposed algorithms are compared to state-of-the-art algorithms on benchmarks from [START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a-ride problem[END_REF] and [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF], which correspond to particular cases of our problem. Finally, we provide managerial insights, mainly regarding vehicle fleet aspects.

Description of instances

The real data comes from the GIHP Company2 . An instance set of 14 instances is made from a bank of 576 requests decomposed into smaller subsets of three sizes. There are 8 small instances containing from 60 to 80 requests, 4 medium-size instances containing from 120 to 160 requests, and 2 large instances containing from 280 to 295 requests. We consider 2 different user types: users occupying seats and users with wheelchairs. Each type of user occupies dedicated spaces in vehicles. Travel times and distances are obtained from the Open Source Routing Machine3 (OSRM) by [START_REF] Luxen | Real-time routing with openstreetmap data[END_REF]. Common characteristics for the instances are: 1) maximum ride times are defined according to direct travel time (t pr,dr ) by the formula RT = 15 × (t pr,dr + 15)/15 ; 2) time windows at medico social institutions are 30 minutes wide; and 3) the service time for users using seats is 2 minutes at the pickup location and 1 minute at the delivery location. For users in a wheelchair, it is 5 minutes at pickup locations and 2 minutes at delivery locations.

The characteristics of vehicles considered in experiments are summarized in Table 3.4. There are four vehicle types, including one that is not configurable (V 0 ). Vehicles V 1 and V 2 have two 3.6. Computational experiments possible configurations, while vehicles V 3 have three configurations. Costs for each vehicle type can be found in Table 3.4. Note that in terms of capacity, vehicle V 0 is a restricted case of vehicle V 3 . It is nevertheless an interesting choice as its fixed cost is considerably lower (€50 against €63). The fixed cost corresponds to the estimated vehicle ownership cost per day. The time-related cost corresponds to the driver's wages, and the distance-related cost corresponds to the fuel consumption and vehicle use.

V 0 4 3 - - - - V 1 3 5 4 4 - - V 2 2 1 4 0 - - V 3 4 3 6 2 7 1
Table 3.4: Vehicle types -configurations

Evaluation of the metaheuristic components

Table 3.5 compares several LNS settings in order to evaluate the main components of the proposed matheuristic. These experiments are performed on the presented real instances with the four vehicles described in Table 3.4.

The first column specifies the different LNS variants considered in this experiment. 5 runs of the full instance-set are computed for each variant. A time limit was set for each instance according to its size. For small instances (60-80 request), this time is 16 minutes. For mediumsize instances (120-160 request) and large instances (280-295 request) the time is 40 and 100 minutes respectively. The following columns show average values over the full instance set.

Please refer to A.2 for detailed results. Columns "Avg" correspond to the average cost over 5 runs of the instance set. The "Best" column corresponds to the average cost of the best run of each instance. The Gap for every instance is computed as (value -BKS)/BKS × 100. The "Nb BKS" column is the number of best known solutions found by the heuristic (there are 14 instances in the instance set).

Chapter 3. Half-day transport problem

The first variant is a classic implementation of LNS which implements operators k-regret, best insertion, random removal, historical node-pair removal, worse removal, time-related removal and distance related removal, as described in [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. This variant is denoted by LNS(5) because it implements 5 destroy operators. The second metaheuristics ALNS(5) adds-up the adaptive layer of [START_REF] Ropke | An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows[END_REF] the reactive layer fail to improve the solution significantly. This is because the SCP parameters are not adapted to this instances and the SCP is probably never solved optimally. Variants with the reactive layer perform better since the number of iterations between two calls to the SCP is reduced. This approach proves efficient in large instance as shown in the figure.

Performance evaluation on benchmarks from the literature

To evaluate the performance of LNS(2)-RSCP, we apply it to two sub-problems of the FSM-DARP-RC on benchmark instances. The first benchmark is made of the DARP instances of [START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a-ride problem[END_REF] for which many elaborate methods were designed. In a second step, LNS(2)-RSCP is compared to the algorithm of [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] that was designed to solve a heterogeneous DARP with configurable vehicle capacity. This benchmark considers a limited fleet of vehicles that can be configured at the depot.

For the sake of conciseness, given our objective to solve large instances, we compare our algorithm to state-of-the-art metaheuristics. All these metaheuristics can easily and efficiently solve instances for which optimal solutions are known (refer to [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] for the DARP and [START_REF] Qu | A Branch-and-Price-and-Cut Algorithm for Heterogeneous Pickup and Delivery Problems with Configurable Vehicle Capacity[END_REF] for the HDARP-C).

Performance evaluation on the DARP

The instances of [START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a-ride problem[END_REF] are still a reference point to evaluate the efficiency of algorithms on the DARP. Table 3.6 compares the results of the LNS(2)-RSCP, after 50,000

Iterations, to the latest heuristics of the literature that have been designed specifically to solve instances of [START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a-ride problem[END_REF]. Detailed results of each instance can be found in A.3.

Gap values are computed in relation to the best known solutions (BKS) found in [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] and have been found either by the cited meta-heuristics, or during the parameter tuning of [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF]. Looking at the average gap (Avg Gap) we note that our matheuristic competes with those three dedicated methods. LNS(2)-RSCP has the second-best average gap of 0.72% with 8 solutions among the best known (Nb. BKS), just after the ALNS of proposed by [START_REF] Chassaing | An ELS-based approach with dynamic probabilities management in local search for the Dial-A-Ride Problem[END_REF].

Note that LNS(2)-RSCP is executed without any parameter tunning other than the one of the

Performance evaluation on the heterogeneous DARP with configurable vehicle capacity

Another relevant benchmark was proposed by [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] for the heterogeneous dial-a-ride with configurable vehicle capacity (HDARP-C). The three main differences between this problem and the FSM-DARP-RC are: (i) a limited fleet of heterogeneous vehicles with configurable capacity; (ii) the vehicle configuration is decided at the depot, not en-route; and

(iii) the presence of users with walkers in some instances, which means that two seats or one seat and half a wheelchair space are occupied.

These differences were integrated into our algorithm to run [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF] instances.

The SCP was adapted in a simple manner to consider a limited fleet of vehicles as follows: first, every route was explicitly assigned the vehicle type for which it was generated, and second, a constraint limiting the number of vehicles for each vehicle type was added to the SCP model.

In this benchmark, two instance sets of 100 requests each are proposed. A first set "A" is characterized by integrating various proportions of appointment requests (between 5% to 25%

). The second instance set "B" instead differentiates the proportion of users with walkers.

According to [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF], we denote by C total , the total transport cost computed as a sum of the vehicle ownership cost, the time cost related to driver wages, and the penalty cost related to the passengers ride time. In Table 3.7 the LNS(2)-RSCP is compared to the multi-start ALNS (MSALNS) of [START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF]. Each row corresponds to a different scenario. In all experiments LNS(2)-RSCP uses the same parameter tuning proposed in Table 4.5 with 3 runs per instance and a stopping criteria of 1 hour.

The first scenario, corresponding to the first row, considers the instance-set "A". In "Gap

Avg" column we observe an average total cost improvement of 1.02% over 3 runs. Column Gap(*) refers to the best average total cost improvement of the best solution found among Chapter 3. Half-day transport problem the 3 runs. In Gap(*), we obtain 1.34% improvement on average with respect to the MSALNS best solution. 6 new best solutions are found out of the 10 instances of the benchmark. These results demonstrate the good performance and stability of LNS(2)-RSCP from an experimental point of view.

A second scenario, corresponding to the second row, is performed on instance-set "B". The main difference between set "B" and set "A" is the presence of very few time windows. Looking at the average gap (Gap Avg), we find more clearly that LNS( 2

Managerial insights

Having shown the efficiency of our matheuristic, we performed simulations in order to provide some general insights regarding, in particular, the relevance of en-route reconfiguration of vehicles. First, we measured the impact of en-route reconfiguration for two variants of the DARP. We then varied the fixed cost of reconfigurable vehicles to determine under which conditions it is worth buying the vehicles.

Vehicle fleet insights

In this section we analyze the gain of enabling en-route reconfigurations. Two variants of the DARP are compared with the real instance set, as shown in Table 3.8. Both variants employ the vehicle fleet of Table 3.4. The first variant, denoted as FSM-DARP-C, consist in allowing vehicles to be configured only once: at the depot, before starting their respective routes.

The second variant, denoted FSM-DARP-RC, allows vehicles to be reconfigured en-route.

Strictly speaking FSM-DARP-RC is a relaxed problem of FSM-DARP-C, which explains why gains in the last column are always greater than 0. Cost reductions can go up to 2.45% of the total cost, depending on the instance. Regarding the structure of solutions, let us consider the best solution (Best) found among the 5 runs for each instance. The next columns (Routes, Rec, RR) refer to some characteristics of these Best solutions. Passing from FSM-DARP-C to FSM-DARP-RC, we observe that the number of routes (Routes) is similar for most instances. However, in some instances, like I14-280, cost savings are related to a reduction in the number of routes (from 37 to 36).

The maximum number of performed reconfigurations among the solution routes (Rec) shows that en-route reconfiguration is usually performed once or twice inside a route. The number of routes performing en-route reconfiguration (RR) indicates how many configurable vehicles are actually reconfiguring en-route in the whole solution. For example, in instance I02-60, we find that 3 out of 8 routes actually reconfigure en-route, this is 37.5% of the vehicle fleet. In average this proportion is 10.28% for small instances, 21.43% for medium-size and 26% for large instances.

Fixed cost analysis

So far, we have seen that reconfigurations can allow cost reductions; however, the resulting gain is correlated to the cost of buying reconfigurable vehicles rather than standard ones. Figure 3.8 pictures how, for the instance in I13-280, the percentage of reconfigurable vehicles decreases when their cost increases compared to the cost of standard vehicles. In this figure, the point with coordinates (2%;12%) means that re-configurable vehicles are 2% more expensive than standard vehicles, and in the cheapest solution found, 12% of the vehicles are reconfigurable. In the same way, when reconfigurable vehicles are 20% more expensive than standard vehicles, they are completely excluded from the solution.

The set of vehicle types considered in these experiments can be found in Table 3.9 and their

V 4 7 1 - - - - V 5 6 2 - - - - V 6 4 3 - - - - V 7 4 3 6 2 7 1
Table 3.9: Characteristics of vehicle types for fixed cost analysis

Conclusion

In this chapter, we investigated a new variant of the dial-a-ride problem characterized by enroute reconfiguration of vehicle capacity. This feature was studied in the context of door-to-door transportation of children with disabilities, considering heterogeneous users and vehicles. We variants. Experiments show that the SCP component increases not only solution quality but also convergence speed. LNS-RSCP was also tested on literature instances that achieved competitive results for the classic DARP and outstanding results in the heterogeneous DARP with configurable vehicle capacity. Although en-route reconfiguration is not a usual practice in companies, companies often own configurable vehicles, as in the case study. Yet route designers do not plan routes considering this extra degree of flexibility. In this study we show that companies can easily save up to 2.5% in the total cost just by allowing vehicles to use en-route reconfiguration. Finally, we show that the utilization of reconfigurable vehicles is strongly dependent on the vehicle ownership cost (fixed cost). For the evaluated instance, supposing that all operations are the same on each day, we found that reconfigurable vehicles are advantageous for companies when their cost are no more than 20% of the cost of standard non-reconfigurable vehicles. Further research includes the extension of the problem studied in this chapter with operational features. First, we plan to study passengers time consistency in a multi-periodic transportation framework (see, e.g. Kovacs et al. (2014a); [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]).

Then, incorporating real-time information (traffic, variable demand) may require the use of state-space-time networks with a fine time discretization (see, e.g. [START_REF] Mahmoudi | Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations[END_REF] and specific optimization algorithms such as the Dynamic Discretization Discovery [START_REF] Boland | The continuous-time service network design problem[END_REF].

C h a p t e r 4

Weekly transport problem:

The time-consistent dial-a-ride problem

In the context of door-to-door transportation of people with disabilities, service quality considerations, such as maximum ride time and service time consistency, are critical requirements. These requirements together with traditional route planning define a new variant of the multi-period dial-a-ride problem called the time-consistent DARP. A perfectly consistent planning defines for each passenger the same service time all along the planning horizon. This planning can be too expensive for Medico-Social Institutions that it is necessary to find a compromise solution between costs and timeconsistency objectives. The time-consistent DARP is solved using an epsilon-constraint approach to illustrate the trade-off between these two objectives. In this chapter, the time-consistency is defined by the number of different timetables for each user. Each solution of the Pareto Front is computed using a matheuristic framework based on a master set partitioning problem and a large neighborhood search procedure. This approach is benchmarked in the context of time-consistent vehicle routing problem with instances from the literature. The context of door-to-door transportation for people with disabilities is also experimented by using real data provided by GIHP Company. Those experiments allow us to propose some managerial insights regarding the interaction between costs and service quality.

Keywords: Dial-a-ride problem, consistency, set partitioning, large neighborhood search, inconsistency

Introduction

The design of efficient para-transit systems relies both on minimizing operational costs and providing users with an adequate quality of service. In the operations research literature, the Dial-A-Ride Problem (DARP) is a well-known optimization problem that consists of designing minimal cost vehicle routes to fulfill a set of transportation requests while satisfying several quality service requirements. Common applications concern door-to-door transportation of elderly people or people with disabilities. In Medico-Social Institutions (MSI) in France, transportation is considered as the main expense after wages ANAP (2016a). Transportation plans are defined every year and partially revised several times a year whenever necessary. Due to the high pressure on expenses, minimizing costs is often the main objective function of MSIs.

The DARP formulation considers a single period, typically half a day. Passengers are generally subject to ride time constraints: they must not travel longer than a predefined duration. In this chapter, we address the case of para-transit systems for people who need to be transported regularly, for example, handicapped workers or scholars. The DARP formulation is extended over multiple periods and each period has a known set of transportation demands coming from passengers. Most passengers emit the same transportation demand every day but it is common to observe variations (attendance, pickup or destination modifications according to medical appointments...). A passenger demand variation may impact the schedule of other passengers in its route. As a result, a need for regularity (or consistency) of service times is expressed from passengers and MSIs: for medical, cognitive or convenience reasons, it is desired that a passenger who has the same demand on several week-days has the same pickup/drop off time these days. This chapter aims at designing an algorithm to be integrated into a dial-a-ride application for passengers with regularity requirements. This work has been motivated by a real-life case study in the area of Lyon, France. The transportation in the area is mainly operated by a single carrier1 who works for multiple MSIs with a fleet of adapted vehicles. Every morning, from Monday to Friday, disabled children from the region are transported from their home to one MSI. In the afternoon, they are driven back home. Without loss of generality, this chapter presents the result of our research for morning trips. Thus, we address a multi-period dial-a-ride problem and study the trade-off between service time consistency and transportation costs. As this problem introduces time consistency within a DARP setting, we call this new variant the Time-Consistent DARP (TC-DARP). This research has been conducted in tight cooperation with SMIs and the passenger transportation company.

The chapter is organized as follows: Section 4.2 presents how the TC-DARP is related to the existing literature in operations research. In Section 4.3, we give a formal definition of the TC-DARP and formulate it as a mixed-integer linear program (MILP). Sections 4.4 presents a general approach for solving the TC-DARP. Sections 4.5 detailed the algorithm used 4.2. Literature review for generating the routes. In Section 4.6, computational results and management insights are reported.

Literature review

The mono-period DARP of our application has been presented in Tellez et al. (2018b). We focus our literature review on the consistency aspects that appear in the multi-periodic version of the problem.

The integration of time consistency has appeared recently in the vehicle routing problem (VRP) literature. Applications were first identified in the context of fast parcel delivery [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF] and rapidly extended to passengers transportation [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]. Readers interested in an extensive review of vehicle routing with consistency considerations can refer to Kovacs et al. (2014a). Consistency is very routing problems that can be divided into three main categories: service time consistency, driver consistency or territory consistency. Service time consistency refers to visiting regular customers at approximately the same hour during the planning horizon. As the main focus of our chapter, the service time consistency will be detailed in the next section.

Driver consistency consists in minimizing the of different drivers assigned to each passenger during the planning horizon. This aims at reinforcing the relationship between drivers and passengers to improve the quality of service. [START_REF] Braekers | A multi-period dial-a-ride problem with driver consistency[END_REF] computed the average cost of a solution where each passenger is served by one, two and three drivers, respectively, showing that a solution with two drivers can be near-optimal whereas solutions with one driver are 10% costlier on average. Other approaches using soft constraints result in similar conclusions (see [START_REF] Smilowitz | Workforce Management in Periodic Delivery Operations[END_REF]; [START_REF] Milburn | Multi-objective home health nurse routing with remote monitoring devices[END_REF]). In [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF], drivers are assigned to routes a posteriori, so that service time consistency and drivers consistency are considered as independent problems in a lexicographical way.

Territory consistency aims at increasing drivers' efficiency through their knowledge of the geographical area where they operate. A common way of addressing territory consistency is to design independent districts in advance where independent routing problems are solved every day. This approach was studied in [START_REF] Lei | Districting for routing with stochastic customers[END_REF]; [START_REF] Zhong | Territory Planning and Vehicle Dispatching with Driver Learning[END_REF]; [START_REF] Smilowitz | Workforce Management in Periodic Delivery Operations[END_REF]; [START_REF] Schneider | Territory-Based Vehicle Routing in the Presence of Time-Window Constraints[END_REF]. This chapter focuses on service time consistency applied to a Dial-a-Ride Problem (DARP).

In contrast to the VRP, the DARP considers one origin and destination for each user and maximum ride time. The main applications of the DARP concern door-to-door transportation of people, particularly elderly or disabled people [START_REF] Ho | A survey of dial-a-ride problems: Literature review and recent developments[END_REF][START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF].

Service time consistency models

Service time consistency consists in serving regular needs at approximately the same hour during the whole planning horizon. This is either modeled by hard constraints, that is, imposing an acceptable level of service time variation, or by soft constraints, that is, penalizing service time variations in the objective function. [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF] defined the maximum arrival time variation as the difference between the latest and earliest service times during the whole planning horizon for each customer. This consistent VRP (conVRP) is an extension of the multi-period VRP where the maximal arrival time variation is bounded above by a constant value L max . However, this measure, initially proposed for the small package shipping industry, has some practical drawbacks in the context of people transportation. Nevertheless, there is one limitation related to using objective C max . It is the larges number 4.2. Literature review of time-classes in the solution overall passengers. Hence, a solution with 99% of users having C max time-classes is equivalent to another solution having only 1% of users in the same situation.

To overcome this limitation, we propose a lexicographic optimization. We first minimize the number of passengers from the highest to the lowest number of time classes: first passengers with C max time-classes, then C max -1, C max -2 and so forth.

To the best of our knowledge, this approach is a new refinement of the [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] model. Still, according to the passenger transportation company, many good trade-off solutions fit between the cost-optimal solution with C max = 2 and the cost-optimal solution with C max =1. According to the fair optimization literature [START_REF] Ogryczak | Fair optimization and networks: A survey[END_REF], the proposed model corresponds to a lexicographic minimax refinement of the min-max model, using counting functions. We show that this lexicographic objective adapts well to the context of passenger transportation.

Solution approaches for time-consistent routing problems

In the conVRP model introduced by [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF], the objective is to optimize service time consistency (L max ) without compromising a perfect driver consistency (1 driver per customer).

The authors proposed a record-to-record travel algorithm and developed benchmark instances for up to 100 customers.

The consistency measure L max has been used in several subsequent papers (i.e. Sungur et al. (2010);Tarantilis et al. (2012); [START_REF] Kovacs | A template-based adaptive large neighborhood search for the consistent vehicle routing problem[END_REF]Kovacs et al. ( , 2015a)); [START_REF] Luo | On service consistency in multi-period vehicle routing[END_REF]; [START_REF] Xu | Variable neighborhood search for consistent vehicle routing problem[END_REF]). The current best results on [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF] benchmark instance set is obtained by [START_REF] Xu | Variable neighborhood search for consistent vehicle routing problem[END_REF], who proposed a Variable Neighborhood Search procedure using dedicated local search methods for quickly solving local optima. This approach is based on improving template solutions generated by 3 different shaking methods. A problem extension, denoted the genConVRP, is proposed by Kovacs et al. (2015a) in which: routes do not necessarily start at the same time, customers are associated with AM/PM time windows and a maximum number of drivers per customer is defined. Subramanyam and Gounaris (2016) proposes a branch-and-cut framework to solve the consistent traveling salesman problem which is a particular case of the conVRP using a single-vehicle. They solve randomly generated instances with up to 51 customers.

The Time-Consistent VRP (TCVRP) of [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] is solved with a dedicated Large Neighborhood Search (LNS) framework. At each iteration, the routes of all periods are destroyed. A VRP with multiple time windows and no waiting time (VRPmTW-nw) is defined to reduce the number of time-classes of one passenger. A heuristic a branch-and-price is used to recreate the routes. The minimum cost solutions for C max = 1 to 5 are saved in the process.

Another related work is the Time Window Assignment Vehicle Routing Problem (TWAVRP)

introduced by [START_REF] Spliet | The Time Window Assignment Vehicle Routing Problem[END_REF]. In the TWAVRP, a single time window of fixed width has to be assigned to some regular customers before the effective daily demand is known.

Chapter 4. Weekly transport problem

The assignment is based on a set of demand scenarios, each one being associated with a given probability. The objective is to minimize the expected traveling cost. The TWAVRP is a particular case of the genConVRP if scenarios are seen as periods and the number of drivers per user is set to infinity. However, the objective differs: genConVRP optimizes the total transportation cost and TWAVRP the average transportation cost. A branch-price-andcut algorithm is proposed to optimally solve instances with up to 25 customers. [START_REF] Spliet | The discrete time window assignment vehicle routing problem[END_REF] proposes a variant called the discrete-time window assignment vehicle routing problem where the chosen time windows are selected from a discrete set.

Consistency issues are also often related to having stochastic customers in the VRP [START_REF] Ritzinger | A survey on dynamic and stochastic vehicle routing problems[END_REF]. For example, Sungur et al. ( 2010) uses a combination of robust optimization in a first phase master problem and stochastic programming with recourse for daily schedules to address the uncertainty in service times and customer occurrence. [START_REF] Erera | Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints[END_REF] investigate the opportunity to give a main fixed route as well as a backup one to frequent customers in a stochastic context.

Finally, the question of service time consistency presents some similarities with some nonperiodic applications such as the synchronization of multiple vehicles at the same node. In this case, the arrival time of multiple vehicles at a given location should be synchronized to perform a collective operation. Then, vehicles continue their routes independently. A survey on synchronization in VRP is given by [START_REF] Drexl | Synchronization in Vehicle Routing-A Survey of VRPs with Multiple Synchronization Constraints[END_REF].

Contributions to the literature

The literature review shows that there is still some gap between what has been proposed in the literature and practical implementation of time consistency for a DARP application.

In this chapter, we use the notion of time-classes introduced by [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] and explore solutions where some users accept several time-classes. Compared to the TCVRP proposed in [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF], we propose a refinement of the C max minimization approach.

Regarding the VRP attributes, we investigate a more realistic setting than [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]. In particular, we consider time windows and maximum ride times in a problem with multiple MSIs (e.g. multiple pickup and delivery locations). As a result, solutions might contain routes that contain waiting times. We keep the assumption that improving consistency by artificially introducing waiting times within routes is not realistic for drivers. Similarly to Kovacs et al. (2015a), we consider that the departure time of routes can be changed to improve consistency.

As we consider a paratransit user application, we will refer to passengers or patients as users in the remaining of the chapter.

Modeling the consistent dial-a-ride-problem (TC-DARP)

Modeling the consistent dial-a-ride-problem (TC-DARP)

We consider a set of users U to be transported during a planning horizon T . Users may require a particular space v ∈ V in the vehicle such as seats or wheelchair spaces. There is a homogeneous fleet of vehicles based at a single depot o. The vehicle capacity is defined by a vector Q = {Q 1 , . . . , Q |V| } representing the availability of each space type v ∈ V.

Each user u ∈ U has a pickup node denoted by p u ∈ P, a delivery node d u ∈ D, a maximum ride time T u , and a demand indicator β t u ∈ {0, 1} for each period t ∈ T . β t u = 1 if user u requires transportation at period t and 0 otherwise. Each user can be serviced at most once on any period. Note that if two users have a common origin or destination, nodes are duplicated so that each pickup node and each delivery node has exactly one user.

The TC-DARP is defined on a directed graph G = (V, A) with the vertex set V = {P ∪D ∪o} and the arcs set A contains arcs of the following forms: (o, i) where i ∈ P; (i, j) where i, j ∈ P ∪ D, i = j; and (i, o) where i ∈ D. Each node i ∈ V is associated with a service duration Note that we do not consider explicitly users with more than one address. Actually, time consistency is meaningful for a given address. A person with two distinct addresses is modeled as two different people (one per address).

= µ u,2 = µ u,3 = 1. The shift of route ω ∈ Ω departure time at period t ∈ T is expressed by continuous variables δ t ω ∈ [0, ∆ + ω ].

Objectives

Two objective functions are defined for the TC-DARP. The first one is the minimization of transportation costs and the second one is the minimization of time inconsistency. Transportation costs are defined by the sum of fixed and routing costs. Fixed costs are related to the cost of owning the vehicles. Then, the cost C ω of a route ω ∈ Ω depends on its duration (which may include some waiting time) and on its length.

               m 1 = |U| - u∈U µ u,2 m c = u∈U µ uc - u∈U µ u,c+1 ∀c ∈ {1, . . . , |C| -1} m |C| = u∈U µ u|C| (4.4)

Constraints

The set of TC-DARP feasible solutions is defined by the following constraints: (4.16) ensures that time-classes are defined in increase order. For example, time-class #2 is allocated to a user only if time-class #1 already exists and is not compatible with a given service time.

ω∈Ωu y t ω = β t u ∀u ∈ U, t ∈ T , (4.5) ω∈Ω y t ω ≤ v ∀t ∈ T , (4.6) c∈C z t uc = 1 ∀u ∈ U, t ∈ T u , (4.7) h t u = ω∈Ru (H uω y t ω + δ t ω ) ∀u ∈ U, t ∈ T u , (4.8) δ t ω ≤ ∆ + ω y t ω ∀ω ∈ Ω, t ∈ T , (4.9) s - uc ≤ h t u + M (1 -z t uc ) ∀c ∈ C, u ∈ U, t ∈ T u , (4.10) h t u ≤ s + uc + M (1 -z t uc ) ∀c ∈ C, u ∈ U, t ∈ T u , ( 4
z t uc ≤ µ uc ∀c ∈ C, u ∈ U, t ∈ T u ,
µ uc+1 ≤ µ uc ∀c ∈ C, ∀u ∈ U, ∀t ∈ T , (4.17) y t ω , z t uc , µ uc ∈ {0, 1} ∀c ∈ C, u ∈ U, t ∈ T , ω ∈ Ω, (4.18) δ t ω , h t u s - uc , s + uc , v ∈ R + ∀c ∈ C, u ∈ U, t ∈ T , ω ∈ Ω. ( 4
z cut = 1 ⇒ s - uc ≤ h t u ≤ s + uc ∀u ∈ U, t ∈ T u , c ∈ C. ( 4
Finally, variables definition is given by constraints (4.18) and (4.19).

Solution method

In this section, we present the solution method to solve the bi-objective TC-DARP. This method consists of a Master Set Partitioning Problem (MSPP) that is fed with a set of routes generated through a Large Neighborhood Search algorithm (LNS). This section is structured as (line 4). This last procedure consists in solving a multi-period DARP with cost objective only.

Note that this procedure generates the pool L during the solving of the multi-period DARP.

This solution is required to find the cost upper bound f (line 5).

Lines 7 to 15 describe an iteration of the algorithm. In order to find a new temporal solution S two procedures detailed in Section 4.4.3 have to be executed (see Figure 4.4). The first procedure is the optimization of the inconsistency g subject to a maximal cost f (line 7).

The value of the best inconsistency found after this first optimization is g(S). Given that, the procedure starts with a feasible solution S * , the result of the first procedure ensures that g(S) ≤ lex g(S * ). The ≤ lex operator represents a lexicographic comparison between the two vectors. This comparison can also be an strictly lower, in that case written as < lex . The second procedure is the optimization of cost f subject to a maximal inconsistency g(S)

found in the previous optimization step (line 8). During these two procedures, L can be fed with new routes.

If the temporal solution S is strictly better than S * for at least one of the objectives (i.e.

if f (S) < f (S * ) or g(S) < lex g(S * ), line 9) then solution S * is updated with S (line 10) and solution S * is added to the Pareto front (if S * is a non-dominated solution, line 11). Otherwise, the step ε is increased geometrically by φ (line 13).

At the end of each iteration, the maximal cost f is updated, for the next iteration, based on the cost of S * (line 15). Pool L is filled with the new routes at each iteration. Because the size of L can be too large for regular computer memory, the size is limited to N max . Routes in L are first ordered by the consistency-first criteria described in Section 4.4.4 and only the first N max routes are kept in L (line 16).

In our case, the fleet size is not constrained, so it is trivial to show that it exists a extreme point in the Pareto front such that every user has only one time-class (i.e. g = (0, . . . , |U|)). Therefore the stopping criteria (line 6) is met when g = (0, . . . , |U|).

Solving the multi-period DARP (MP-DARP)

The set of non-dominated solutions of the TC-DARP defines a Pareto front in which one of the extreme points corresponds to a solution with minimum cost but with a high number of time-classes. This extreme point is found by solving a simplified version of the TC-DARP, called multi-period DARP (MP-DARP) that ignores the consistency requirements. The MP-DARP is modeled as follows: So by definition and with the same notation, route ω is said to be non-strongly dominated by ω if, ether both routes visit the same set of users in the same sequence and C ω > C ω , or neither route visits the same set of users in the same sequence.

min f =λv + ω∈Ω t∈T C ω y t ω (4.21) s.t. ω∈Ru y t ω ≥ 1 ∀u ∈ U, t ∈ T u (4.22) r∈R y t r ≤ v ∀t ∈ T (4.23) y t ω ∈ {0, 1} ∀ω ∈ Ω, t ∈ T (4.24) v ∈ N (4.25)
In this algorithm, the pool of routes L is initialized with non-strongly dominated routes found during the solution of independent Dial-A-Ride problems, one for each period t ∈ T (line 3). Each independent problem minimizes the total transportation cost composed of the distance-related cost and the time-related cost.

The DARP of each period t is solved using the LNS-SCP framework presented in Tellez et al. (2018b). This framework is a large neighborhood search based matheuristic that quickly yields cost-efficient routes. This LNS-SCP framework uses a record to record procedures with a temporary, current and best solutions. All the routes that were part of the current solution are added to L.

In the MP-DARP, the inconsistency objective is not considered. So, the visiting times of passengers are not relevant. Thus, this problem can be solved by using a subset of the pool L considering only non-weakly dominated routes following definition 4.2. This subset is called Each iteration of Algorithm 7 consists in four steps: 1) select a subset of non-weakly dominated routes; 2) solve the MP-DARP with the routes selected ; 3) pool management, and 4) update the best solution. This process iterates until M axIter * iterations with no improvement of objective value has been performed.

D(L).
In step 1) a set of routes is selected from L (line 10).This set is enriched with projection and complementary routes (see Definition 4.3) and added to the restricted pool of routes L (line 12). The set of selected routes L is obtained by first restricting L to D(L) and then by applying one of the selection rules that will be described in Section 4.4.4. In step 2), the MP-DARP instance formed by the pool L and S * is solved by a MILP solver with a time limit t max (line 13). If the best solution S * is not empty, S * is used to initialize the MILP solver from a feasible solution. This initialization is called warm-start.

Given the presented MP-DARP formulation of is a set covering problem and not a set partitioning problem, solution S may contain some users served by more than two routes. In this case, the solution can be easily repaired by solving the MP-DARP with a new pool of routes L temp and a warm-start on S (line 15). The new pool of routes L temp is initialized with the routes of the solution S and enriched as follows. For each user u visited more than once in S and for each route r that visit user u, a new route r identical to route r but that does not visit user u is added to L temp . Finally, routes in L temp are added to L (line 16).

Step 3) (lines 18-20) performs pool management. The current pool of routes is cleared if the MP-DARP could not be solved optimally. This mechanism aims to keep a manageable pool size and it is inspired by previous works (see e. to maintain a manageable pool size.

Finally, the current best solution S * and the counter of iterations without improvement are updated on Step 4) (lines 21-26). The possibility to use the previous solutions as a warm-start has one main consequence, the value of the objective function can not increase after each iteration. Given this property, when the value of the objective function does not change after several iterations, we suppose the procedure has reached a local optimum. This is why the value of itN onImp is used as a stopping criterion indicator.

Solution method

Mono-objective optimization procedure

This section presents the procedure to solve the TC-DARP for one objective constrained by a maximum value on the other objective. This procedure, detailed in Algorithm 8, is used in Algorithms 6 to solve either the optimization of inconsistency subject to a maximal cost or the optimization of cost subject to a maximal inconsistency.

Algorithm 8 uses the same structure as Algorithm 7. However, here the TC-DARP is solved instead of MP-DARP and a new source of routes denoted L new , is introduced.

Input parameters for Algorithm 8 are the objective function z, the additional constraints k which define the maximum accepted value for the second objective, the initial solution S ini , and the pool of routes L. The main variables are the restricted pool of routes L (initially empty), the current solution S, and the best found solution S * that is initialized to S ini (lines 2-6).

As for Algorithm 7, each iteration consists in four steps: 1) select routes; 2) solve an instance the mono-objective TC-DARP; 3) pool management; and 4) update the best solution. This process iterates until M axIter iterations with no improvement of S * has reached (see line 7).

The set of selected routes is chosen by using the corresponding policy defined by one source of routes s and one selection rule r. The source s provides a pool of routes from which the selection rule r chooses a subset l. There are two distinct sources of routes, pool L and a new pool called L new . If the source is pool L, we select a select a subset l of size N from L using the selection rule r (line 10). Otherwise, the source is L new which is generated on the fly based on solution S * (line 12). L new is particularly designed to be consistent with the current time-classes of S * . The procedure for generating L new is detailed in Section 4.5.

Similarly to source L, we select a select a subset l from L new using the selection rule r (line 10). Then, L new is added to the pool L (line 14).

We define multiple selection rules. Each selection rule proposes a different way of choosing routes from a source according to a given criterion. A detailed description of each rule is presented in Section 4.4.4.

For diversification purposes, we define several policies combining the two sources and two selection rules into an ordered list O. Policies are selected at each iteration sequentially, one after the other, based on the following rule: the procedure jumps to the next policy in O if the solution S * has not been improved in the last iteration. If the solution has been improved, the same policy is kept for the next iteration. When the last policy in O is reached, the procedure sets off again with the first policy.

As in Algorithm 7, the first step finishes when the selected routes and their projection and complementary routes are added to the current pool L (lines 16 and 17).

In step 2, line 18, the TC-DARP is solved by optimizing the objective z subject to constraints ((4.5)-(4.19) and constraints k that limits the value on the other objective. When the objective is the transportation cost, constraints (4.26) shall also be included to prevent µ uc variables to take arbitrary values and create empty time-classes. The input routes are L and the constituent routes of S * . The MILP solver is initialized with the routes of S * to ensure to find a solution with at least the same performance as S * and to increase convergence speed. The computation time for the solver is limited to t max . When the objective is lexmin g, the TC-DARP is solved multiple times following the hierarchical order of the objectives {m |C|-1 , . . . , m 1 }. First we solve the problem minimizing m |C| . The result obtained with this objective must then be considered in the model as a constraint. Then, we have to solve the model minimizing m |C|-1 , and the result obtained will not affect or reduce the result obtained with the first objective. This process is done for all the objectives defined in g.

Finally steps 3 and 4 are identical and have the same function that steps 3 and 4 of Algorithm 7 respectively.

Step 3 performs pool management and Step 4 the best solution and stopping criteria management.

Selection rules

When the restricted pool L becomes too large, the MILP solver cannot improve the given initial solution. Hence, a key element is to select a subset of routes of reasonable size in L (line 10) or L new (line 13). We present in this section three performance indicators used to guide route selection and two route selection strategies called Sequential Selection and Random Biased Selection.

Performance indicators used for route selection

To select routes efficiently, they have to be sorted by their expected performances in a weekly solution. So we introduce several performance indicators that are used to evaluate each route ω ∈ L:

• F ω : Solution cost. This is the best cost of the solution of which route ω has been part of.

Initially F ω is set to infinity. Each time a new solution S is found in Algorithm 6, F ω is updated as follows:

F ω = min{F ω , f (S)}.
• G ω : Solution inconsistency. This is the lowest inconsistency of the solution in which route ω has been part of. Initially G ω is set to infinity. Each time a new solution S with route ω is found, the performance is updated with the minimum value G ω = min{G ω , g(S)}.

Two sorting criterion are defined. The first sorting criteria is the cost-first criteria (F ω , Ct ω , C ω ) that lexicographically sort the routes in ascending order, first by the solution cost F ω , then by the normalized sub-problem cost Ct ω and finally by the route variable cost C ω . The second sorting criteria is the inconsistency-first criteria (G ω , F ω , Ct ω ) that lexicographically sort the Chapter 4. Weekly transport problem routes in ascending order, first by the solution inconsistency G ω , then by the solution cost F ω , and finally by the normalized sub-problem cost Ct ω . This last criteria is used to limit the size the L in Algorithm 6.

Sequential selection (SS)

The Sequential Selection (SS) rule is the first selection rule. The purpose of this rule is to gradually cover the routes inside a pool of routes. This method sequentially chooses routes differently according to a given objective. If the objective is to minimize costs, routes are sorted with cost-fist criteria and if the objective is to minimize inconsistency, routes are sorted with inconsistency first criteria. The SS rule starts by sorting routes of the pool.

From the sorted list, routes are processed one by one to finally select N routes. For each route, we check whether it was selected in a previous call or not. If it was selected before, it can be selected again with a probability of γ. Otherwise, it is always selected. The memorizing of these selected routes is initialized at the beginning of Algorithm 8. The mechanism used to select routes ensures that routers belonging to the same previous solution (i.e. with the same overall performance, F ω or G ω ), will be kept together. This mechanism aims to increase the chances to find complete feasible solutions within the routes selected. Nonetheless, this sorting step has to be performed each time the rule is called because performance indicators such as F ω and G ω may change from one iteration to another.

Roulette wheel selection (RW)

The roulette wheel is the second selection rule. It is inspired by the roulette wheel mechanism proposed in [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. Similar to the SS rule, routes are first sorted according to criteria (F ω , C t ω , C ω ) if the objective is the cost minimization, and criteria (G ω , C t ω , C ω ) if the objective is the inconsistency minimization. Then N routes are chosen from the sorted list l based on their position following the next rule: position=ξ ρ × |l|, where 0 ≤ ξ < 1 is a 4.5. Route generation: DARP with multiple time windows random number and ρ ∈ [1, +∞[. Because the list is sorted by decreasing performance, this probabilistic choice assigns a higher probability to the routes with higher performance.

Route generation: DARP with multiple time windows

The MSPP framework is initialized with routes that have been generated by solving independent DARPs. These routes are combined to form more consistent solutions. Nevertheless, timeconsistency can be improved by generating routes that are dominated in terms of cost (i.e. routes which cost can be improved by modifying the sequence of visits).

These dominated routes, used in Algorithm 8 (line 12), may never be generated by the LNS operators used to solve the DARP. This section describes the procedure used to generate new routes that are likely to improve time-consistency. The proposed approach was inspired by [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]. Section 4.5.1 presents the main process for the generation of a new set of routes denoted L new . Section 4.5.2 presents how time windows are defined.

Main process for the generation of new routes

The process for generating new routes consistent with the current solution works as follows:

1. One user ū is selected randomly among the set of users that have the maximum number of time-classes C max .

2. For each period t ∈ T , new routes are generated as follows:

(i) A set T W t u of multiple time windows are defined for each user u ∈ U according to their service times: if u = ū, multiple times windows are defined to decrease its current number of time-classes, while for the rest of users (u = ū) the number of time-classes can be maintained (Section 4.5.2).

(ii) Routes are generated by solving an auxiliary Dial-A-Ride Problem with Multiple Time Windows (DARPmTW) for the period t. The routes generated during this process are gathered into a sub-pool of routes denoted L t new (Section 4.5.3).

3. The sub-pools L t new are gathered into a single pool denoted L new = ∪ t∈T L t new and returned to MSPP (line 12, Algorithm 8).

In [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF], the TC-VRP does not have time windows. The auxiliary problem solved is a vehicle routing problem with multiple time windows and no waiting time (VRPmTWnw). The multiple time windows help to define new routes that can decrease the number of time-classes for user ū. Waiting times are forbidden since the insertion of unnecessary waiting times could artificially improve consistency.

Chapter 4. Weekly transport problem

h 1 u h 5 u h 3 u h 4 u a pu b pu -Λ +Λ -Λ +Λ T W1 T W2 Figure 4.7: Construction of W(H, u) = {T W 1 , T W 2 } for user u with pickup time windows [a pu , b pu ] and H = {h 1 u , h 5 u , h 3 u , h 4 u }.
In our case, the initial problem integrates time windows. The sub-problem is a Dial-A-Ride

Problem with Multiple Time Windows and minimal route duration (DARPmTW). Routes may integrate waiting times due to time windows but waiting times that artificially improve time-consistency are still forbidden.

Definition of time windows for the DARPmTW

Let T W t u be the set of multiple time windows to be defined for each user u ∈ U in the DARPmTW solved to generates new routes for the period t. If u = ū, T W t u is defined in order to decrease its current number of time-classes, while for the rest of users (u = ū) T W t u is defined such that the number of time-classes can be maintained.

Let us recall some notation: we consider a user u ∈ U with pickup time window [a pu , b pu ], the subset of time periods with transportation demands T u ⊆ T and variables h t u representing the pickup service time of user u at period t ∈ T u . We denote by µ(H) the number of time-classes for the set of service times H. So µ(H u ) is the number of time-classes of user u. The service times are allocated to time-classes as in [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]. For each user u ∈ U, the answers to the following two yes/no questions determine how the multiple time windows T W t u are defined:

Q1 Is u the selected user ū?

Q2 Is the number of time-classes of user u decreased by 1 if the service time h t u at period t is removed? This question can be answered by checking if the inequality |µ(H u \ {h t u })| < |µ(H u )| holds.

Route generation: DARP with multiple time windows

The answers to questions Q1 and Q2 yield four ways to define multiple time windows: Yes/Yes Changing the service time h t ū to any service time in the time windows T W t ū has to decrease the number of time-classes for this user. So T W t ū = T W(H ū \ {h t ū}, ū).

Yes/No

Let [e t ū, l t ū] ∈ T W(H ū, ū) be the time window satisfied by service time

h t ū (e t ū ≤ h t ū ≤ l t ū). Defining T W t ū = T W(H ū, ū) \ {[e t ū, l t ū]
} will enforce a decrease in the number of time-classes for this user.

No/Yes In this case, the service time h t u defines a time-class on its own, so T W t u = {[a pu , b pu ]}. As a result, any feasible service time at period t can be accepted.

No/No

We distinguish two possibilities. In the first one, T W t u is defined similarly as in case Yes/No. This possibility is selected with a probability ν = θ × (C max -µ(H u )), where C max is the maximum number of time-classes in the current solution, and θ is a fixed parameter. In the second one (selected with probability 1 -ν), time windows T W t u are set as in Case No/Yes. This may generate routes that increase the number of time-classes of this user. However, as in [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF], we observe that this temporary relaxation helps decrease the number of time-classes of user ū. These four cases are summarized in Table 4.4.

Q2: µ(H

u \ {h t u }) < µ(H u )? Yes No Q1: u = ū? Yes T W t ū = T W(H ū \ {h t ū}, ū) T W t ū = T W(H ū, ū) \ {[e t ū, l t ū]} No T W t u = {[a pu , b pu ]} With probability ν: T W t u = T W(H u , u) \ {[e t u , l t u ]} Otherwise: T W t u = {[a pu , b pu ]} Table 4
.4: Overview of cases for the definition of T W t u .

Solving the DARPmTW

The DARPmTW is solved by adapting the LNS-SCP algorithm proposed by Tellez et al.

(2018b). The LNS-SCP algorithm has been designed to solve a single period DARPs with a single time window at each pickup or delivery point. We extended it to handle multiple time windows. Additionally, routes should not include unnecessary waiting times that artificially improve time consistency at the cost of increasing waiting times. To the best of our knowledge, the DARPmTW has not been treated in the literature.

Solving the multiple time-windows scheduling problem

The scheduling procedure aims to determine if there is a schedule that satisfies timing constraints at each node of a given route. Besides the set of multiple time windows T W t u , each user in the route has the original constraints defined in Section 4. At the same time, a maximum forward time shift ∆ + ω is computed. This value indicates how much the route schedule can be shifted forward while preserving both its feasibility and the route duration. The detailed procedure can be found in Appendix B.0.4.

Given the scheduling obtained in Phase I, Phase II checks the satisfaction of multiple time windows without increasing the duration of the route. Phase II is described by Algorithm 9.

Note, the satisfaction is verified at pickup nodes because the time consistency is only defined at pickups times.

Each iteration of Algorithm 9 corresponds to the feasibility check of the service time at the current node. Nodes are considered sequentially following the route sequence. This algorithm visits all nodes and chooses a feasible service in a time window for each pickup node or detects infeasibility. The only lever to modify service times is the maximum time shift of the route: service times can be delayed by at most ∆ + ω units without violating any timing constraint nor increasing the route duration. Each time the schedule has to be shifted forward to ensure feasibility, the value of ∆ + ω is decremented by the value of the corresponding time shift. In lines 5-20, the algorithm checks time windows T W t u until finding a feasible one (line 5). Three cases are considered: (i) If service time takes place before the opening of the time window (w n i < a), the route is shifted forward by the quantity w n i -a, so that the new service time is

Computational experiments

The matheuristic described in Section 4.4.1 was coded in C++ and the mathematical models were solved with CPLEX Concert Technology 12.6 running on a single thread on an Intel Xeon E5-1620 v3 @3.5Ghz processor.

This section details computational experiments one these two families of instances. It is structured as follows: Section 4.6.1 presents the value of parameters used by our algorithms.

Section 4.6.2 introduces the instances used to evaluate our approach. They are built from real data provided by the GIHP Company. Section 4.6.3 evaluates the main components of the matheuristic approach. In Section 4.6.4, the MSPP is assessed on benchmark instances [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF], [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF]) for the time-consistent VRP. Finally, Section 4.6.5 presents managerial insights regarding cost performances and time consistency.

Parameters settings

After preliminary tests on a representative subset of instances, parameters shown in Table 4.5

were found to provide the best average performance. The value of parameter ε has a strong impact on the computing time. A higher value of ε enables to decrease the computation time, however, the quality of the Pareto front approximation is considerably deteriorated. Thus, ε = 0.01 seems to be a good trade-off between computing time and the quality of the solution. The MSPP is less sensitive to parameter φ but its value needs to be greater than 1.5 to have a significant impact on the value of ε.

We found that a It max greater than 4 does not improve the quality of each point of the Pareto front. Parameters N and t max were determined to maximize the number of times the MILP solver can solve the TC-DARPs to proven optimality. In the same way, the parameter N c was determined to solve the MP-DARP. Note that parameter N c is much bigger than N 4.6. Computational experiments because the MP-DARP contains less binary variables (so is an easier problem to solve) than the TC-DARP.

To keep the number of routes in memory under control, limits in the maximum size of the pool L and of the L new were set to 50000 routes and 5000 routes, respectively.

The choice of selection rules for the MP-DARP and route policies for the TC-DARP are the followings:

•

Description of instances

The time-consistent DARP studied in this chapter arose in the context of transportation of people with disabilities. We collected real data from the GIHP Company based in Lyon, France.

This data concerns the transportation of hundreds of persons (users) to MSIs. We decomposed this data according to geographical areas and built 8 small instances with 60 to 80 users, 4 medium-size instances with 120 to 160 users, and 2 large instances with 280 to 295 users. We assume an infinite homogeneous fleet; each vehicle has a capacity of 4 seats and 3 wheelchair spaces. Vehicles cost are composed of an hourly cost α =23.8 e and a cost per kilometer τ =0.17 e. Additionally, we artificially set an arbitrarily small vehicle fixed cost of λ = 1 to favor solutions with the same variable cost but fewer vehicles.

Travel times and distances are obtained from the Open Source Routing Machine2 (OSRM)

proposed by [START_REF] Luxen | Real-time routing with openstreetmap data[END_REF]. For each user u ∈ U, we defined maximum ride times according to direct travel time t pu,du between the pickup location p u and the delivery location

d u .
The following formula generates maximum ride times (RT ) that are between 15 and 30 minutes larger than direct travel times: RT = 15 × (t pu,du + 15)/15 .

Time windows at MSIs are 15 minutes wide. The size of time-classes is 10 minutes wide.

Finally, time windows at pickup locations and service times strongly influence the actual design of routes, but their impact is independent of the efficiency of our solution method. Thus, we ignored them for the sake of simplicity.

Evaluation of the metaheuristic components

In this section, we present the tests that we used to evaluate the main components of the proposed matheuristic MSPP. We compare several settings of the algorithm on a representative sample of five instances of different sizes. Five runs are performed for each instance and setting. Although TC-VRP is the closest problem to the TC-DARP, there are some differences between both problems. The TC-VRP has the following limitations: (i) it has a single depot and no time windows; (ii) it assumes a limited fleet of vehicles; (iii) the objective function is to minimize C max ; and (iv) routes must start at time 0 and no waiting time is allowed.

Nevertheless, every instance of the TC-VRP can be converted into an instance of the TC-DARP by defining one copy of the depot for each request. Ride times and time windows are relaxed by setting arbitrarily large values. Finally, since the VRP routes are no subject to time windows nor ride times, routes can be traveled in either direction. Thus, each time a route is appended to the pool, the reverse route is also appended.

RconVRP instances by Feillet et al. (2014)

This benchmark proposes 10 small instances of the TC-VRP. The first 5 instances with 10 users and the next 5 with 12 users. Due to the size of the instances, we solved the instances optimally by using CPLEX for an exact comparison. Table 4.8 presents the comparison with the MSPP over 10 runs.

In columns 2-4, optimal solutions (Opt Cost) for each time-class are presented. In the next 3 columns, we report the average performance of the MSPP for each time-class. Note that the MSPP could not find most of the solutions with 3 time-classes and one with 2 time-classes. For each instance, the Gap is computed as ( Avg Cost -Best) / Best × 100. The last row is the average gap (Avg Gap) overall instances which is the average value of the corresponding column.

For single time-class solutions, the MSPP found 4 out of 10 instances are optimal solutions in the 10 runs. The average gap is 1.5%. The performance is better with 2 time-classes as 7 out of 10 solutions are optimal and an average gap is 0.2%.

Instances TC-VRP

This benchmark was built from real data collected in 14 distinct MSIs, with several users ranging from 15 to 65, and 5 time periods (Monday to Friday). For each MSI, 5 profiles of transportation requests were randomly generated, where the average percentage of users requests varies between 50% to 90% every day. This leads to a total of 70 benchmark instances.

Transportation cost of solutions with 1 to 5 time-classes are provided for most instances. [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] solved the TC-VRP with an LNS-based matheuristic with a time limit of 1 hour. However, the MSPP does not stop until all users reach a single class. For each value of C max , our lexicographic optimization explores all non-dominated solutions. This approach is more time consuming but returns a more complete Pareto Front that can help decision-makers to select appropriate solutions.

Tables 4.9 and 4.10 shows the average gap of the MSPP with respect to the LNS method, aggregated in two different ways. For each instance, we compute the gap as (Cost MSPP -Cost LNS)/Cost LNS × 100. Thus, any negative gap represents an improvement.

Managerial insights about time-consistency and transportation costs

This section provides a set of managerial insights regarding the relationship between timeconsistency and transportation costs. Figures 4.9 Avg Gap (%) -0.98% -0.92% -0.78% -0.12% -0.33% Depending on the instance size, the cost increase percentage for reaching single class solutions can vary from 4% in C01_60 to 23% in the C12_280 instance. Note that values in the y-axis are ordered but non-scaled as the distance between points is always constant. To draw a scaled and readable Pareto Front, we reduce the scope of solutions and focus on a single time-class.

As an example, Figure 4.12 shows the instances scaled for solutions with a 2 time-classes. The y-axis presents the percentage of users in that instance with having 2 time-classes.

Economic impact route time shift

In this section, we compute the impact of flexible departure time of routes on time-consistency.

This effect has been studied by [START_REF] Kovacs | A template-based adaptive large neighborhood search for the consistent vehicle routing problem[END_REF] for the conVRP, showing that departure time flexibility provides considerable improvement in the solution quality under tight consistency requirements. As far as the TC-DARP is concerned, the departure flexibility is limited by time-windows and maximum ride-time constraints. Routes departure can be scheduled at any time between its earliest and its latest departure date. We define the maximum time shift as the difference between these two schedules. The maximum time shift of route ω is denoted ∆ + ω . Columns 6-8 present the minimum gap on 5 runs with respect to the minimum cost found by the MSPP when no time shift is allowed (∆ + ω = 0). The last row shows the average values. The last row shows the minimum gap (Gap Min) on 5 runs with respect to the minimum cost found for both variants. This row shows that flexible departure time reduces the transportation costs for highly consistent solutions. The average gain is found on single-class solutions with 1.44% (= 1.68-0.24) saving and decreases with increment of C max . The managerial implication is that shifting time departure can improve time-consistency without modifying transportation costs in a DARP context.

Conclusions

This chapter introduced a new variant of the multi-period DARP denoted the time-consistent DARP. This problem aims to find a balance between two objectives, the transportation cost Some disabilities are very sensitive to inconsistent schedules. In this study, we show that economic solutions are already fairly consistent with very few passengers having 3 time-classes.

Moreover, with a small increase in transportation costs (<1%), passengers' schedules will be at

Context

GIHP Company

The GIHP company is one of the biggest transport companies for people with disabilities in the Auvergne-Rhône-Alpes region in France. Founded in 1998, GIHP is specialized in the transport Private transport: people with reduced mobility often demand individual transports for their daily life activities. Unlike other types of transportation, this is not financed by the government.

Vehicle rentals: GIHP offers the possibility to rent a vehicle without a driver. There is a wide variety of vehicles that can carry from 1 to 5 people in wheelchairs or up to 9 seats.

The problem

Currently, GIHP organizes the transport for each MSI (Client) independently. Routes, vehicles, and drivers are usually dedicated to each client. There are various advantages of managing MSIs in this way. For example, the optimization of routes for a single MSI is easier than for multiple MSIs using conventional non-automated methods. From a management point of view, contracting and negotiation with each MSI independently are less complex to manage and with a high-bargaining power. However, this clustering policy is certainly sub-optimal from the economic point of view and the additional costs must be weighed against its benefits.

On the contrary transport pooling with MSIs has probably economic advantages but it supposes a simultaneous negotiation process and requires a specialized mechanism for pricing share routes. Figure 5.1 pictures the CURRENT clustering policy for 16 users attending 3 MSIs.

Each line represents one user connecting one pickup (node) and one delivery (MSI) point. Each polygon represents an independent cluster.

The scope of the study

There are multiple ways of dividing a big problem into smaller sub-problems. The objective of this study is to evaluate alternative policies of grouping users and compare them with the CURRENT policy from both an economic and a service quality point of view. Alternative policies consider transport pooling among MSIs in different ways.

-The economic indicator is the total transport cost defined as follows:

T C = vehicle ownership costs + β × total traveled time + α × total distance covered (5.1)

With α the unitary time cost, β the unitary distance cost.

-The service quality unit is the user ride time which is the time expended in the vehicle from the pickup moment to the delivery time of each at passenger at MSIs.

The clustering problem

Decomposing a problem into smaller sub-problems is a common approach for dealing with large size routing problems. In the scientific community, this problem is known as the clustering problem. It consists of creating groups (clusters) of users according to a clustering policy and to a proximity-based criterion. Clustering policies reflect management practices regarding what is possible or not to group while proximity criteria measures how far(near) are the users.

Proximity measures

The geographic distance is very often the proximity measure between two independent locations (points) in a classic clustering problem. In a Dial-a-Ride system, however, each user i ∈ U has one pickup p(i) ∈ P and one delivery d(i) ∈ D location. Thus, points need to be considered in 105

Chapter 5. Assessment of transport pooling policies couples rather than independently. Additionally, there is a temporal dimension between points that should be considered. Figure 5.2 shows graphically the difference between the proximity of points and users. users in routing problems [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF][START_REF] Prescott-Gagnon | A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows[END_REF]. In the following sections, we present classic measures from the literature.

Pickup relatedness

The pickup relatedness C p ij between user i and user j is the cheapest transport cost between pickup points.

C p ij = min{c p(i)p(j) ; c p(j)p(i) } (5.3)
With c p(i)p(j) the transport cost from pickup p(i) to pickup p(j) following equation 5.2.

Delivery relatedness

The delivery relatedness C d ij between user i and user j is the cheapest transport cost between delivery points.

C d ij = min{c d(i)d(j) ; c d(j)p(i) } (5.4)
With c d(i)d(j) the transport cost from delivery d(i) to delivery d(j) following equation 5.2.

Relatedness of Shaw (1998)

The relatedness of Shaw (1998) C p-d ij between user i and user j take into account both pickup and delivery locations. This measure is based on the Shaw (1998) distance-related operator

The clustering problem

which considers only the distance between points. Given that our objective function is cost-based rather than distance-based, the relatedness is computed as follows:

C p-d ij = c p(i)p(j) + c p(i)d(j) + c d(j)p(i) + c d(i)d(j) 4 (5.5)
With c uv the transport cost from u to v following equation 5.2.

Time relatedness

Prescott-Gagnon et al. ( 2009) proposes a spatial-temporal measure for the vehicle routing problem with time windows. This measure was adopted by [START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF] for a DARP context. The proposed adaptation considers only the temporal dimension conserving the structure of the measure. The time relatedness C t ij between user i ∈ U and user j ∈ U is computed as follows:

C t ij = min{t p(i)p(j) ; t p(j)p(i) } 2T max + 1 T ij + T ji (5.6)
With T ij the width of the interval of feasible visiting times defined as follows:

T ij = max{1; min{l d(j) , l d(i) + t d(i)d(j) } -max{e d(j) , e d(i) + t d(i)d(j) }} (5.7)
T max is a scaling factor set to the largest value of t uv with u, v ∈ P ∪ D.

Clustering policies

We define two new clustering policies. The MSI clustering policy (C-MSI) consisting of grouping MSIs and the user clustering policy (C-USER) consisting of grouping users.

MSI clustering policy (C-MSI)

The MSI clustering policy (C-MSI) consists of grouping close related MSIs. The particularity of this policy is that each MSI can belong to only one cluster and so there is a single contractualized solution. Figure 5.3 shows a 2-cluster solution following this policy. The cluster on the right side (blue) has 2 MSIs while the cluster on the left side (green) has only one MSI.

The MSI clustering policy can be modeled as a mixed-integer linear program. Let U be the set of users. C ij is the relatedness between user i ∈ U and user j ∈ U computed with one proximity measure of Section 5.2.1. K(m) is the set of users attending MSI m ∈ M and M(i)

the MSI of user i ∈ U. N is the number of clusters. It is assumed in this modeling approach that each cluster has one centroid which can be placed in the same position as any of the users belonging to this cluster. Note that users' positions do not have a physical representation because it is associated with a pair of points. Decision variables x ij ∈ {0, 1} are 1 if user i is assigned to cluster whose centroid is j and 0 otherwise. Variable y i ∈ {0, 1} are 1 when the cluster with centroid in j is chosen. The objective is to find the best assignment of users to clusters such that the sum of distances is minimized.

min f =   i,j∈U C ij x ij   (5.8) s.t. j∈U x ij = 1 ∀ i ∈ U
(5.9) j∈U y j = N (5.10)

x ij ≤ y j ∀ i, j ∈ U (5.11)

x rj ≤ x ij ∀i, j ∈ U, r ∈ K(M(i))
(5.12)

x ij , y i ∈ {0, 1} , ∀ i, j ∈ U (5.13) Constraints 5.9 make sure that each user i ∈ U is assigned to only one cluster. Constraints 5.10 define the number of clusters needed. Constraints 5.11 force y j variables to take 1 when at least one user is assigned to the cluster located in j. Constraints 5.12 make sure that users from the same MSI are assigned to the same cluster. Finally, variables definitions are given by constraints 5.13.

Intuitively, this policy is cheaper than the CURRENT policy because MSIs are now allowed to pool transport routes. Thus, vehicles can pickup users for multiple MSIs. However, the tendency of service quality is not predictable because longer routes not necessarily imply longer ride times.

Solving Approach

The user clustering policy (C-USER)

The second policy is the user clustering policy (C-USER). It consists of grouping users independently of the notion of MSIs. From a management perspective, this policy supposes that MSIs can share the transport management of a group of users with other MSIs. Additionally, as these users can share the same route there should be a pricing mechanism to bill users individually. policy imposes some relevant management challenges to MSI, there is an economic advantage that this study aims to quantify. This policy is a relaxation of the clustering problem in which users can be assigned to any cluster without constraint. We expect transport routes to take longer than other policies. However, the quality of service not necessarily worse.

Solving Approach

The general solving approach consists of 2 stages, clustering first and then, in solving each cluster independently.

Input data

We consider a sample data set of 562 users attending to 31 MSIs of the Auvergne-Rhône-Alpes region. Transportation requests correspond to the period of Monday morning including users some in boarding schools. As this is a single period problem, the terms of requests and users are equivalent and can be used interchangeably. MSIs can be of 3 different sizes: 14 small with between 1 and 9 users, 12 medium-size with between 10 and 40 users, and 5 big-size with between 41 and 76 users as shown in Table 5.1. Travel times and distances are obtained from the Open Source Routing Machine 1 (OSRM) by [START_REF] Luxen | Real-time routing with openstreetmap data[END_REF].

Ride times

One of the main measures of service quality is the users' riding time. To avoid long times values a maximum ride time constraint is usually imposed on each user. This constraint should be proportional to the travel time following a direct way. For GIHP there are several constraints to limit the travel time, but their method can not be generalized for any transport time. Thus, we propose the following step-wise function proposing acceptable limits for users:

Time windows and service times

The most common time window is at MSIs. Vehicles should arrive between 15 minutes of the MSI opening time.The service duration for users using seats is 2 minutes for pickup and 1 minute for delivery operations. For users in a wheelchair, it is 5 minutes at pickup locations and 2 minutes at delivery locations.

Vehicles

GIHP has 22 vehicle types with different configurations for people in wheelchairs (W) and seats (S). Each vehicle has fixed ownership cost (C.FIXED), and a variable distance cost (α).

There is a driving cost (β) which is dependent on the vehicle type. Big vehicles are more expensive because drivers require a special license. Table 5.2 presents the list of vehicles and their configurations. Vehicles are sorted for the lowest to the highest fixed cost.

Computational experiments

The experiments were run on a CPU Intel Xeon E5-1620 v3 @3.5Ghz. The clustering problem was solved using CPLEX 12.6. The routing problem was solved using the LNS-SCP algorithm with the parameters of Apendix C.0.1. As this algorithm is not an exact approach, each problem instance is solved 5 times. However, in the evaluation of policies, only the cheapest solution is considered in each case.

Comparison proximity measures

In Section 5.2.1 we present 4 proximity-based measures named: pickup-related, delivery-related, relatedness of [START_REF] Shaw | Using constraint programming and local search methods to solve vehicle routing problems[END_REF] and time-related by [START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF]. The objective of this

Comparison of MSI clustering policies (C-MSI)

The C-MSI policy consists of clustering MSIs as presented in Section 5.2.2. From an economic perspective, the results confirm the correlation between the number of clusters and the transport costs. The smaller the number of clusters, the lower the costs. Note, in this study the CURRENT policy increases by 34.6% the transport cost. With the C-MSI policy, it can be saved between 14.8% (=34.6%-19.8%) and 31.4% (=34.6%-3.3%) depending on the chosen scenario. Cost reductions are explained by a relevant decrease in the number of routes from 129 (CURRENT) to 65 (C-MSI( 2)). This reduction is reflected in longer routes with a growing percentage of MSI pooling (up to 85%) and a growing percentage of en-route reconfigurations (up to 18%).

From the service quality perspective, ride times are similar. There is a slight decrease in the average ride time with the reduction of clusters. However, this difference is not significant regarding the standard deviation. The variability of rides times is small and stable overall scenarios (CV=0.6). These results show that despite a stronger restriction in the clustering possibilities of this policy, there are significant economic advantages and the service time is not affected by the number of clusters.

Comparison of user clustering policies (C-USER)

The C-USER policy is a more flexible scenario for clustering users. From an economic perspective, these results show the same behavior about the relationship between the number of clusters and the total cost. With the C-USER policy, it can be saved between 14.4%(=34.6%-20.2%) and 32.4%(=34.6%-2.2%). However, savings decrease with the number of clusters. Cost savings are explained by the reduction of routes from 127 (CURRENT)

Computational experiments

to 67 (C-USER(2)). Again, this cost decrease is accompanied by a significant reduction in the number of routes, an increase in the number of routes visiting several MSIs (up to 85%) and an increasing proportion of routes reconfiguring en-route (up to 18%). These results confirm the economic potential of promoting transport pooling policy and the use of reconfigurable vehicles.

Overall, ride times do not vary considerably from one scenario to another. We can only observe see a slight increase in the median of C-USER(4). However, this change it is not significant.

Global comparison

From a global perspective, we can compare all clustering policies at a time. Table 5.5 presents the general characteristics of the best solutions found with each policy. BKS refers to the best overall cost-based solution.

From an economic point of view, the CURRENT policy is the most expensive overall. The C-USER strategy has a lower total cost that the C-MSI strategy, except in the 4-cluster scenario where it is 1% more expensive (= 13.9-12.9). However, cost differences are so small that cost can be considered equal. Regarding the number of routes, the C-USER policy is superior to MSI policy. The difference in the number of routes growths with the number of clusters from 2 (=69-67) to 16 (=97-81). The number of routes in the C-USER policy is smaller because routes are longer in distance and duration. The number of routes reconfiguring en-route is quite stable. The C-USER policy, however, is less sensitive to the variation in the number of clusters. Regarding the quality of service, there are no significant differences between C-MSI and C-USER policies. The low variability and stability of ride times confirm the robustness of the maximum ride time function. scenarios. This knowledge of vehicles can guide transporters like the GIHP in the process of designing or buying new vehicles.

Conclusions

GIHP manages the transport independently for each MSIs. This policy has many advantages in the processes of planning, negotiation, pricing, and contracting with each MSI. However, this policy is sub-optimal from the economic point of view and the additional cost must be compared with the benefits. In this study, the cost of the CURRENT policy is estimated to around 30% when it is compared with the best possible scenario.

Two alternative policies, allowing the pooling of transport between several MSIs, are proposed. The C-MSI policy grouping MSIs and the C-USER policy grouping users. The most flexible policy (C-USER) assumes that users from one MSI can be split into different clusters.

These policies can save between 15% (16 clusters) and 30% (2 clusters) of transport costs compared to the CURRENT policy depending on the number of clusters. Both policies have comparable savings, but C-MSI policy has fewer routes which from a management point of view makes C-USER policy better. This reduction is correlated to an increase in the number of routes pooling users from several MSIs. Selected vehicles are concentrated in very few dominant models (mostly reconfigurable). These vehicles have interesting configurations (like 3 seats + 3 wheelchairs) and low fixed ownership costs.

Regarding service quality, we found that user ride times are very stable regardless of the policy in the presence of maximum ride time constraints. Moreover, the proposed maximum ride time function currently used by GIHP company assures a good service level and low ride time variability.

As a perspective, we identified that balancing the number of users in each cluster could be desirable. This criterion could be integrated with the clustering model, as a constraint or an objective, to offer further insights.

C h a p t e r 6

Conclusions and perspectives

Conclusions

In this dissertation, we study the daily transport for people with disabilities (PWD). More precisely, the optimization of the long-term transport of PWD going to Medico Social Institutions (MSI).

In 2010, healthcare transport in France became one of the top ten priorities of the risk management plan due to the increasing cost of these transports. For Medico-Social Institutions (MSI), transport costs often represent the second largest expenditure after that of the staff ANAP (2016b). Despite this, few MSIs have the skills and means to effectively manage the transport, provide high-quality service and keep the costs down ANAP (2016b). In this context, this thesis as part of the NOMAd project proposed on one side a global optimization strategy and a transport pooling strategy for between MSIs on the other side. Both strategies with the objective are to improve economic performance while maintaining social and environmental goals.

The global optimization strategy consists of optimizing the long-term transport planning of PWD using operations research tools. A decision aiding tool for transport optimization was proposed for this purpose. The long-term planning considers one academic year. Following the current practice, we assumed that this transport plan is constructed from a pattern of identical weekly transportation plans. Defining a weekly schedule is a complex task that needs to be split into sub-problems. First, we worked on the planning of each sub-problem called the half-day transportation problem in Chapter 3. Then in Chapter 4 we solved the weekly transport problem considering both cost and service quality objectives into account.

The construction of long-term transportation planning is a complex problem that has not been completely solved in the scientific literature. A literature review about the transportation 121 Chapter 6. Conclusions and perspectives problems in the health sector was carried out in Chapter 2. This review helps us to characterize this transport type and to confirm that both the half-day and weekly transport problems are relevant contributions to the healthcare transport of people.

In Chapter 3, we solved the half-day transport problem consisting of designing the routes and determining the vehicles needed to serve the demand at a lower cost respecting service time constrains. This problem was modeled as a new variant of the Dial-A-Ride Problem (DARP) called the "Fleet size and mix DARP with configurable vehicle capacity" (FSM-DARP-RC).

This problem considers real-life features such as heterogeneous users (i.e. seat, wheelchair) and vehicles that can be configured en-route. Companies very often own configurable vehicles. Yet route designers do not plan routes considering this extra degree of flexibility. However, this study showed that companies can easily save up to 2.5% of the total cost just by allowing vehicles to use en-route reconfiguration. The utilization of reconfigurable vehicles is strongly dependent on vehicle ownership costs. For the evaluated instance, reconfigurable vehicles are advantageous for companies when vehicle ownership costs are less than 20% the cost of standard non-reconfigurable vehicles. More generally, this is the second contribution to a pickup and delivery problem with configurable vehicle capacity. The proposed approach presents original and efficient handling of reconfigurable capacities in an LNS heuristic. Experiments showed that it outperforms the previously proposed algorithm on this topic.

In Chapter 4, we solved the weekly transport problem to make half-day transport plans time-consistent for each user. This objective is proposed because some disabilities are very sensitive to inconsistent schedules. This problem is modeled as a new variant of the multi-period DARP denoted the "time consistent DARP". Unlike the half-day problem, this problem defines two objectives, the transport cost, and the user time-consistency. The time consistency objective is expressed as a lexicographic function of the number of users with different time-classes. This approach takes more time than traditional min-max objectives but returns a Pareto frontier that helps decision-makers selecting the appropriate solution. In this study, we showed that economic solutions are already fairly consistent with very few passengers having 3 time-classes.

Moreover, with a small increase in transportation cost (<1%) passengers' schedules will be at most 2 time-classes each. Additionally, we showed that allowing a flexible departure of routes improves the transportation costs of highly consistent solutions.

Finally, in Chapter 5 we evaluated both the economic and service quality impact of pooling the transport between different several MSIs. Currently, each MSI manages its planning (fleet, drivers and routes) independently because of the advantages planning, contracting and negotiating. However, this policy is sub-optimal from an economic point of view. The cost of the current policy is estimated at around 30% when it is compared with the best possible scenario.

Two alternative policies allowing the pooling of transport between several MSIs are proposed with different degrees of management rules to construct clusters. We found that both policies have comparable savings but the policy with higher flexibility has fewer routes. Regarding

Perspectives

service quality, we found that the characteristics of user rides were not sensitive to the different policies in the presence of maximum ride time constraints.

Perspectives

Generally, the methods and algorithms developed in this thesis can be applied to domains other than the transport of patients and passengers. The relaxation of ride time constrains for example results in another routing problem called pickup and delivery problem. This problem is commonly applied in the transport of goods in currier companies. In particular, future research for the different topics treated trough the chapters are:

In Chapter 1, the global methodology assumes that morning and afternoon routes are independent of each other. However, PWD willing to accept long ride times in the morning would expect short ride times in the afternoon and conversely. Thus, a model extension would be to consider other objectives or constrains to balance the ride times of users in vehicles.

In Chapter 3, the FSM-DARP-RC model can be extended with additional operational features such as the choice of different departure and arrival depots with limited capacity. For example, at GIHP some vehicles can choose between departing from the driver home, an MSI or the central depot. Incorporating real-time information (traffic, variable demand) may require the use of state-space-time networks with a fine time discretization (see, e.g. [START_REF] Mahmoudi | Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations[END_REF]) and specific optimization algorithms such as the Dynamic Discretization Discovery [START_REF] Boland | The continuous-time service network design problem[END_REF]. Another research area is the extension of the proposed algorithm to other types of pickup and delivery problems where reconfigurations are sometimes needed (e.g. trucks with adjustable compartments).

In Chapter 4, the TC-DARP was solved for a fleet of homogeneous vehicles. Extending the problem to consider a fleet of reconfigurable vehicles would require additional assignment constraints in the weekly problem. The question of driver-consistency is very sensitive for some disabilities. [START_REF] Braekers | A multi-period dial-a-ride problem with driver consistency[END_REF] studied the economic impact of driver-consistency on a DARP context. However, further research should include real-life features such as driver breaks, work balance, and contracting. Moreover, a multi-objective approach between transport cost, time-consistency, and driver-consistency in a DARP setting will be an interesting tool for decision-makers.

In Chapter 5, the proximity measures studied between requests (users) partially take into account different aspects of DARP. However, an indicator that considers together pickup and delivery locations, time windows, ride times and load are needed. Proximity measures are not only used in the clustering problems but the selection of requests in neighborhood-based heuristics [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF][START_REF] Prescott-Gagnon | A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows[END_REF]. The solved clustering problem minimizes the sum of transport costs between users and the cluster's centroid. However, other objective functions such as TSP tours or spanning trees between the users of the same 123 Chapter 6. Conclusions and perspectives cluster can provide a better estimation of the real transport costs.

A more general perspective would be to handle planning modifications in the context of regular transport services. Planning modifications are not too many but can be frequent in 984.9 984.9 984.9 989.9 1034.5 22.1 data5-41 1420.7 1420.7 1422.6 1461.6 1615.9 126.9 data5-44 1142.9 1142.9 1142.9 1149.4 1220.3 74.3 data5-46 1458.9 1458.9 1465.4 1492.9 1607.2 114.4 data5-48 1440.8 1449.4 1452.4 1459.8 1597.8 154.9 data5-55 1569.1 1569.1 1571.1 1581.0 1696.9 139.4 data5-59 2714.8 2721.5 2721.5 2883.6 3115.9 281.3 data5-64 2082.0 2082.0 2100.8 2112.4 2304.2 118.9 data5-65 1759.4 1759.4 1766.2 1777.1 1923.9 -48 1507.4 1507.4 1519.4 1531.6 1702.8 158.5 data6-55 1816.8 1816.8 1826.3 1854.4 1987.7 121.0 data6-59 2931.3 2931.3 2933.0 3037.4 3389.6 204.1 data6-64 2264.3 2264.3 2271.0 2305.6 2527.0 100.6 data6-65 1981.9 1981.9 1990.6 1998.3 2219.5 -44 1295.9 1295.9 1300.3 1307.0 1311.7 20.5 data7-46 1648.6 1648.6 1650.1 1664.6 1715.9 72.4 data7-48 1687.1 1698.9 1698.9 1712.0 1774.3 116.6 data7-55 1889.0 1889.0 1896.3 1918.0 2036.0 136.5 data7-59 3262.4 3262.4 3307.4 3596.6 3892.4 725.2 data7-64 2552.9 2552.9 2552.9 2583.6 2823.4 -27 1184.8 1193.9 1193.9 1193.9 1220.6 17.6 data8-32 1144.0 1144.0 1152.8 1152.8 1181.7 35.8 data8-41 1886.8 1886.8 1888.5 1898.0 1954.3 63.9 data8-44 1409.0 1409.0 1409.0 1414.9 1441.2 28.8 data8-46 1758.5 1758.5 1772.9 1774.8 1817.2 33.8 data8-48 1815.7 1815.7 1820.9 1824.4 1898.1 125.7 data8-55 2007.7 2007.7 2015.4 2037.2 2104.0 120.0 data8-59 3545.7 3545.7 3580.5 3874.4 4020.5 427.4 data8-64 2723.3 2723.3 2723.3 2743.0 2978.2 126.8 data8-65 2404.2 2404.2 2422.9 2433.5 2524.4 -27 1210.6 1210.6 1210.6 1219.5 1241.9 12.3 data9-32 1187.7 1187.7 1199.4 1199.4 1204.9 6.4 data9-41 2022.8 2022.8 2022.8 2022.8 2032.1 6.3 data9-44 1532.5 1532.5 1532.5 1532.5 1595.1 54.1 data9-46 1827.0 1827.0 1827.0 1841.6 1871.0 30.7 data9-48 1973.5 1973.5 1973.5 1992.8 2007.7 28.6 data9-55 2176.0 2176.0 2176.0 2188.1 2275.9 70.3 data9-59 3913.0 3913.0 3916.3 3946.6 4025.3 96.3 data9-64 2942.6 2942.6 2964.9 2964.9 2999.6 28.8 data9-65 2586.5 2586.5 2586.5 2604.7 2624.2 68.0 Table B.3: Benchmark Feillet et

1. 1

 1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 The NOMAd project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Field study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Stakeholders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Survey: needs analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 A multidimensional problem . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Transportation management processes . . . . . . . . . . . . . . . . . . . . . . . 1.5 Road map and contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Construction of the long-term transportation planning . . . . . . . . . . 1.5.2 Assessment of transport pooling policies . . . . . . . . . . . . . . . . . .

  Figure 3.1. . . . . . . . . . 54 3.2 Parameters (all defined in Section 3.4). . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 Vehicle types -costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Vehicle types -configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 Performance comparison of LNS-based heuristics for our instances (see A.2 for detailed results) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.6 Benchmark classic DARP Cordeau and Laporte (2003) (Detailed results in Section A.3) 61 3.7 Benchmark Qu and Bard (2013) (detailed results in A.4) . . . . . . . . . . . . . . . 62 3.8 Savings due to en-route configuration . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.9 Characteristics of vehicle types for fixed cost analysis . . . . . . . . . . . . . . . . . 64 3.10 Costs of vehicle types for fixed cost analysis . . . . . . . . . . . . . . . . . . . . . . 65 4.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.2 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.3 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.4 Overview of cases for the definition of T W t u . . . . . . . . . . . . . . . . . . . . . . 89 4.5 Parameters MSPP (all defined in Sections 4.3-4.5). . . . . . . . . . . . . . . . . . 92 4.6 Avg Gaps of MSPP variants for solutions with a C max of 3, 2 and 1 time-classes. . 94 4.7 Avg Gap(%) with respect to the best hypervolume (5 runs) . . . . . . . . . . . . . 95 4.8 Benchmark RconVRP instances from Feillet et al. (2014) . . . . . . . . . . . . . . . 97 4.9 Results aggregated by percentage of users requests on Feillet et al. (2014) benchmark 98 4.10 Results aggregated by instance size on Feillet et al. (2014) benchmark . . . . . . . 99 4.11 Economic implications of allowing a later departure of routes in solutions (Best solutions on 5 runs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.1 Global characteristics of the test data set . . . . . . . . . . . . . . . . . . . . . . . 110 xvii 5.2 Vehicle list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Comparison MSI clustering policy . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Comparison users clustering policy . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Global comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Vehicle's utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Parameters for the ALNS as in Masson et al. (2014) . . . . . . . . . . . . . . . . . A.2 Performance comparison of LNS-based heuristics . . . . . . . . . . . . . . . . . . . A.3 Results on the DARP instances Cordeau and Laporte (2003) . . . . . . . . . . . .

  instances "B" ignoring walker requirements. . . . B.1 Parameters LNS-SCP (Tellez et al., 2018b). . . . . . . . . . . . . . . . . . . . . . . B.2 Benchmark Feillet et al. (2014) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Benchmark Feillet et al. (2014) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.1 Parameters LNS-SCP algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .List of Figures1.1 The four stakeholders in the transportation for PWD . . . . . . . . . . . . . . . . . 1.2 Transportation from the MSI perspective . . . . . . . . . . . . . . . . . . . . . . . 1.3 Transportation from the user's perspective . . . . . . . . . . . . . . . . . . . . . . . 1.4 User's preferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Example of a reconfigurable vehicle (https://www.handynamic.fr/) . . . . . . . . 1.6 Transportation management processes . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Structuring a typical week . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Illustration of vehicle routes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9 Global approach to improve time-consistency . . . . . . . . . . . . . . . . . . . . . 2.1 Healthcare transport classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Vehicle with three configurations (http://handynamic.fr) . . . . . . . . . . . . . 3.2 Comparison of routes with and without vehicle capacity reconfiguration . . . . . . 3.3 Insertion of request r into route ω . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii List of Figures 3.4 Graphical representation of a route load . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Capacity of the vehicle presented in Figure 3.1. . . . . . . . . . . . . . . . . . . . . 3.6 Impact SCP component (Instance I01-80) . . . . . . . . . . . . . . . . . . . . . . . 3.7 Reactive SCP (Instance I13-280) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Fixed cost impact of reconfigurable vehicles (Instance I13-280) . . . . . . . . . . . 4.1 Solution with C max = 2 time-classes . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Solution with C max = 5 time-classes . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Pareto with the two optimization procedures of one iteration (Algorithm 6 lines 7 and 8). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Example of projection and complementary routes . . . . . . . . . . . . . . . . . . . 4.6 Example of 3 successive calls of the sequential selection rule with N = 6. . . . . . . 4.7 Construction of W(H, u) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Comparison Pareto front instance C01_60 . . . . . . . . . . . . . . . . . . . . . . 4.9 Pareto front C01_60 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Pareto front C10_160 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Pareto front C12_280 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Scaled Pareto fronts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 CURRENT clustering policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Proximity between points (left) and users (right) . . . . . . . . . . . . . . . . . . . 5.3 Clustering MSIs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Clustering of users (C-USER) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Solving approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Maximum ride time function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Comparison of proximity measures . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Comparison clustering policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Assignment of MSI to clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . healthcare transportation in France has become one of the top ten priorities of the risk management plan due to the increasing cost of these transports.

:

  decision support systems, transport pooling, passenger transport, optimization, healthcare Part of this chapter have been published in a conference paper and an extended version submitted to a journal: Tellez, O., Daguet, L., Lehuédé, F., Monteiro, T., Montoya, G. O., Péton, O., Vercraene, S., 2019. A stakeholder oriented approach to the optimization of transports of people with disabilities. Supply Chain Forum: An International Journal (Submitted) Tellez, O., Daguet, L., Lehuédé, F., Monteiro, T., Montoya, G. O., Péton, O., Vercraene, S., 27-29 August 2018a. Étude pour l'analyse et l'optimisation du transport des personnes en situation de handicap. In: Conférence Francophone en Gestion et Ingénierie des Systèmes Hospitaliers (GISEH). Geneva, Switzerland 1 Chapter 1. Introduction

  Figure 1.1: The four stakeholders in the transportation for PWD

Figure 1

 1 Figure 1.3: Transportation from the user's perspective

Figure

  Figure 1.4: User's preferences

Figure 1 . 5 :

 15 Figure 1.5: Example of a reconfigurable vehicle (https://www.handynamic.fr/)

  processes. (i) The transport mutualization to determine the opportunities of transport pooling between MSIs;(ii) the long-term planning processes defining the annual transportation plan of each user and logistics need like the fleet; (iii) the short-term planning processes to manage the day-to-day modifications of the transportation plan; and, (iv) the transport execution process covering the daily iterations between stakeholders and the follow up of routes. The scientific results of the following section respond to the need of decision support tool for the long-term planning. It is bounded with a dotted square in the Figure1.6.

  Figure 1.6: Transportation management processes

Figure 1 . 7 :

 17 Figure 1.7: Structuring a typical week

Figure 1 .

 1 Figure 1.8 illustrates two morning routes for transporting PWS to MSIs. Both routes have benefited of the transport pooling between the two MSIs. This problem is known as the fleet size and mix dial a ride problem with reconfigurable vehicle capacity (FSM-DARP-RC) which is a contribution of this thesis and that will be presented in Chapter 3.

Figure 1 . 8 :

 18 Figure 1.8: Illustration of vehicle routes

Figure 1 . 9 :

 19 Figure1.9: Global approach to improve time-consistency

  Figure 2.1 presents a global classification of healthcare transport based on the nature of the demand. The following sections present the characteristics of each category. The daily transport of PWD studied in this thesis is part of the non-emergency regular transport of patients as shown in gray.

Figure 2 . 1 :

 21 Figure 2.1: Healthcare transport classification

  [START_REF] Mo | Mass customizing paratransit services with a ridesharing option[END_REF] studied the option of providing a 20% discount for passengers who accept a 15-min earlier pick-up time or a later drop-off time. An application in Hong Kong paratransit service shows that this policy increases around 15% the number of people served.Unlike operational problems, Dyn-DARPs include, in almost any application, objectives combining cost and quality criteria. Indeed, dispatchers look for affordable solutions satisfying patient's preferences.[START_REF] Madsen | A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives[END_REF] proposed an insertion heuristic that permits a flexible way of weighting different goals for the paratransit service in the city of Copenhagen. Depending on the given weights, the solution reflects the user's preferences. In a German hospital,[START_REF] Hanne | Bringing robustness to patient flow management through optimized patient transports in hospitals[END_REF] considered a weighted objective function measuring criteria in a single time scale: 2.2. Optimization problems in the non-emergency transport of patients & passengers with disabilities patient inconvenience measured as the deviations to the latest desired time (total lateness); fleet operating cost (total earliness); fleet utilization (driving time); and patient satisfaction (total ride time of patients).

  a fleet size and mix dial-a-ride problem with multiple passenger types and a heterogeneous fleet of reconfigurable vehicles. In this new variant of the dial-a-ride problem, en-route modifications of the vehicle's inner configuration are allowed. The main consequence is that the vehicle capacity is defined by a set of configurations and the choice of vehicle configuration is associated with binary decision variables. The problem is modeled as a mixed-integer program derived from the model of the heterogeneous dial-a-ride problem. Vehicle reconfiguration is a lever to efficiently reduce transportation costs, but the number of passengers and vehicle fleet setting make this problem intractable for exact solution methods. A large neighborhood search metaheuristic combined with a set covering component with a reactive mechanism to automatically adjust its parameters is therefore proposed.The resulting framework is evaluated against benchmarks from the literature, used for similar routing problems. It is also applied to a real case, in the context of the transportation of disabled children from their home to medical centers in the city of Lyon, France.Keywords:Dial-A-Ride Problem, Fleet Size and Mix Problem, reconfigurable vehicles, heterogeneous fleet, large neighborhood search, set-covering, feasibility check. This chapter have been published in the journal chapter: Tellez, O., Vercraene, S., Lehuédé, F., Péton, O., Monteiro, T., 2018b. The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity. Transportation Research Part C: -A-Ride Problem (DARP) consists in designing vehicle routes in order to fulfill transportation requests scattered throughout a geographic area. The objective is to minimize costs while satisfying transportation requests. The DARP is a special case of the Pickup and Delivery Problem (PDP) in which constraints and objectives related to the quality of services offered to passengers are integrated (the reader may refer to[START_REF] Parragh | A survey on pickup and delivery problems[END_REF]

Figure 3

 3 Figure 3.1: Vehicle with three configurations (http://handynamic.fr)

  [START_REF] Ropke | Models and branch-and-cut algorithms for pickup and delivery problems with time windows[END_REF];[START_REF] Ropke | Branch and cut and price for the pickup and delivery problem with time windows[END_REF];[START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF]) are still limited in their ability to solve large size instances. Accordingly, several metaheuristics have been proposed to solve the DARP and its variants. In particular,[START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a-ride problem[END_REF] developed a Tabu Search algorithm and proposed a set of instances that are still used to benchmark new algorithms. The most successful heuristics that have been applied to these instances in the last ten years are the Variable Neighborhood Search (VNS) of[START_REF] Parragh | Variable neighborhood search for the dial-a-ride problem[END_REF], the Hybrid LNS (HLNS) of[START_REF] Parragh | Hybrid column generation and large neighborhood search for the dial-a-ride problem[END_REF], the Adaptive LNS (ALNS) of[START_REF] Masson | The Dial-A-Ride Problem with Transfers[END_REF], the deterministic annealing algorithm of[START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF], the evolutionary local search of[START_REF] Chassaing | An ELS-based approach with dynamic probabilities management in local search for the Dial-A-Ride Problem[END_REF] and the ALNS of[START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF].One of the most challenging parts of DARP heuristics is the scheduling algorithm. It determines the feasibility of routes with respect to temporal constraints and, in some case, parts of the objective function such as the routes' duration. Several efficient algorithms have thus been designed to satisfy the most common DARP constraints with the best possible complexity (see e.g.[START_REF] Hunsaker | Efficient feasibility testing for dial-a-ride problems[END_REF] Tang et al. (2010);[START_REF] Firat | Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh[END_REF]

Fleet

  Size and Mix VRP (FSM-VRP) introduced by[START_REF] Golden | The fleet size and mix vehicle routing problem[END_REF], which considers an unlimited fleet of various vehicle types and costs for using vehicles. Solving the problem amounts to determining the fleet of vehicles and designing routes simultaneously; (ii) the Heterogeneous VRP (HVRP) introduced by Taillard (1999), which considers a given fleet of various types of vehicles. In such problems, vehicle types can induce differences both in constraints (e.g. capacity) or objectives (e.g. distance related or fixed related costs).Regarding people transportation problems, the combined transportation of seated and wheelchair passengers by a heterogeneous fleet of vehicles has been studied inToth and Vigo (1997). This problem falls into the class of Heterogeneous Dial-A-Ride-Problems (HDARP) introduced later by Parragh (2011). In the latter chapter, the authors propose a branch-and-cut algorithm which optimally solves instances with up to 40 requests and a hybrid method which combines branch-and-price and VNS. The HDARP was also thoroughly investigated in[START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF]. The authors propose a branch-and-cut algorithm and a deterministic annealing metaheuristic to solve a multi-depot version of this problem. To our knowledge, variants of the FSM-DARP have not yet been covered by the literature.

Figure 3

 3 Figure 3.2: Comparison of routes with and without vehicle capacity reconfiguration

  vehicle k ∈ K has a starting depot o + k ∈ O + and an ending depot o - k ∈ O -. In practice, o + k and o - k often correspond to the same physical location. The set A contains three categories of arcs: Arcs

  [a i , b i ]. At depots o ∈ O + ∪ O -, we assume that load variations are null for all user types, vehicles are empty and the service time s o is null. Each vehicle k ∈ K is associated with a fixed cost f k , a cost per kilometer γ k and a set C k = {1, . . . , ck } of possible configuration indexes.

  satisfied and carried out by a single vehicle. Constraints (3.4) are flow conservation constraints at pickup and delivery nodes. Constraints (3.5) state that any vehicle k ∈ K leaving the node o + k must end-up at the node o - k . Constraints (3.6) set arrival time variables. If arc (i, j) ∈ A is used by a vehicle k, then the arrival time at node j is greater than the arrival time at node i plus the service duration in i and the transportation time from i to j. The big-M can be estimated as

3. 5 .

 5 Evaluation of the insertion of requests Algorithm 3: Schedule evaluation Input: Route ω = {1, ..., N }. Output: Minimal duration of route ω (-1 if infeasible) w 1 ← a 1 /* Beginning of the service */ H ← 0 /* Total waiting time on the route */ F 1 ← b 1 -w 1 /* Forward time slack at node 1 */ /* Phase 1: set up nodes at the earliest start */ for i = 2, . . . , N do

3. 5 .

 5 Evaluation of the insertion of requests diminution of load (i.e. delivery). Reconfigurations can therefore be done just before a pickup node. Second, let consider a feasible route for a given vehicle. The route has two consecutive pickups and the first one requires a new configuration among a set of feasible configurations S 1 .

Figure 3 .Figure 3

 33 Figure 3.4 presents the successive loads of a vehicle on a route with two types of users (seats and wheelchairs). In Figure 3.4, pickup operations are illustrated by arcs pointing to the right or to the top and deliveries are represented by arcs pointing to the left or to the bottom.Although the route has 7 nodes, a sufficient Capacity evaluation of the route requires only a capacity check in the nodes of the kernel, this is nodes 3 and 5.

4/*Proposition 1 .

 1 Compute the load profile for the kernel of the route */ 5 L = ∅ 6 l 1 = 0 7 for i ← 2, . . . , N do8 l i = l i-1 + (φ j,u ) u∈U 9 if i belongs to the kernel of ω then 10 L ← L ∪ {l i } 11 /*Find a feasible vehicle type */ 12 for k ← K(ω) in non-decreasing order of costs λ k do 13 if k can carry L then /The Capacity evaluation algorithm returns k(ω ), the cheapest vehicle type for the route ω , or the value -1 if no vehicle can perform route ω .

Figure 3 . 5 :

 35 Figure 3.5: Capacity of the vehicle presented in Figure 3.1.

Figure 3 .

 3 Figure 3.6 shows the cost evolution considering the best run of four metaheuristics in instance I01-80. The other 3 variants are not shown because their performance is almost that of LNS(2)-RSP. Two separate groups of algorithms can be identified, corresponding to metaheuristics with and without an SCP component. The SCP increases not only solution quality, but also convergence speed.

Figure 3 .

 3 Figure 3.7 shows the cost evolution on a large size instance I13-280. The variants without

  Figure 3.7: Reactive SCP (Instance I13-280)

  [START_REF] Gschwind | Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem[END_REF] with 0.5% Avg Gap and 9 BKS. An interesting remark is that the reactive layer of the SCP component was barely activate since the initial values of η = 1000 and t limit = 3 secs were sufficient for these instance sizes. The other two methods are the threshold acceptance (TA) based local search of[START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF] which has the highest average gap (1.16%) but also by far the lowest computation time, and the evolutionary local search (ELS)

  aimed to determine the size and composition of the fleet as a strategic decision. A matheuristic based on Large Neighbourhood Search and a Reactive Set Covering Problem (LNS-RSCP) was proposed to solve this problem for real instances of up to 295 user requests. Results on the real data set showed significant performance compared with six other LNS-based metaheuristics

Chapter 4 .

 4 Weekly transport problem

FigureFigure 4

 4 Figure 4.1-4.2.Monday Tuesday Wednesday Thursday Friday

  ζ i and a time window [a i , b i ]. Every arc (i, j) represents the fastest path from node i to node j and is associated with a travel time t ij and a distance d ij .We propose a route based MILP formulation of the TC-DARP. A route is any feasible sequence of nodes visited by a vehicle. Each route ω starts and finishes at node o and is characterized by a set of visited pickup and delivery nodes. Every pickup or delivery node i ∈ P ∪ D on a route ω is associated with a time H i,ω . H i,ω is the earliest possible service time of node i in a schedule of ω that minimizes its duration and respect time windows and maximum ride time constraints for each user in the route. In addition, for each route a maximum forward time shift ∆ + ω which represents the maximal amount of time by which its departure time can be postponed, without violating any time window or ride time constraints. The detailed scheduling procedure with the calculation ∆ + ω values is presented in Appendix B.0.4. Each route ω ∈ Ω is operated by one vehicle. Each vehicle is associated: weekly ownership cost λ, a cost per kilometer τ related the fuel consumption, and a cost per hour α related to driver cost. The TC-DARP can be seen as a bi-objective problem which consists of selecting a subset of routes from Ω such that all transportation requests on the planning horizon are satisfied within their time windows and maximum rime times. The first objective is to minimize the sum of fixed and variable traveling costs. The second objective is to minimize service time inconsistency.

  Tables 4.1, 4.2 and 4.3 synthesizes the mathematical notations for the sets, data and variables used in the TC-DARP mathematical model.

4. 3 .

 3 Modeling the consistent dial-a-ride-problem (TC-DARP) min f = λv + minimizes time inconsistency, which is modeled with a lexicographical refinement of the time-class model proposed by Feillet et al. (2014). The expression which is used in the MILP model is the following: minimizes the number of people having more than c timeclasses, where c decreases from |C| to 2. The expression u∈U µ uc counts the number of users with c or more time-classes. This is equivalent to the lexicographical minimization of the number of users with exactly |C| classes, |C| -1 classes, down to 1 classes. In the remaining of the chapter, we denote by lexmin g = m |C| , . . . , m 1 (4.3) the alternative formulation of this objective, where m c denotes the number of users having c time-classes. It is post-processed from the values of the µ uc variables using the following expressions:

  .20) They state that if a user u is assigned to the time-class c at period t, then its service time should be within the bounds of this time-class c. Constraints (4.13) set the width of a time-class. Constraints (4.14) avoid overlap between time-classes. Constraints (4.15) links the number of routes that serve one given user and the number of time-class variables. Constraints (4.16) define variables µ uc necessary for counting the number of time-classes of each user. Constraints (4.17)

  follows: Section 4.4.1 presents the general matheuristic framework named MSPP that traces the Pareto front between the two objectives of the TC-DARP. This framework relies on two main components. Section 4.4.2 presents the first component of the framework that is the construction of the initial solution. The second component is the mono-objective optimization procedure of the TC-DARP presented in Section 4.4.3. Then, Section 4.4.4 presents the rules to select the routes that are used during the solving.

  Figure 4.3: Pareto

Chapter 4 .

 4 Weekly transport problem Algorithm 6: Matheuristic framework (MSPP) Data: ε : initial value epsilon, φ : Increase factor of epsilon, Result: Pareto front /* Initialization */ 1 P aretoF ront ← ∅: Empty Pareto front 2 L ← ∅: Pool of routes 3 S ← ∅: temporal solution initially empty 4 S * , L ← initialSolution() /* See Section 4.4.2 */ 5 Set the cost upper bound: f ← f (S * ) /* Iterations */ 6 while stopping criterion is met do /* Optimize inconsistency and cost objectives, see Section 4.4.3 */ 7 S, L ← solveT CDARP (lexmin g, f ≤ f , S * , L) 8 S, L ← solveT CDARP (min f, g ≤ lex g(S), S, L) /* Update solution */ 9 if g(S) < lex g(S * ) ∨ f (S) < f (S * ) : f ← f (S * ) × (1 + ε) 16 Limit the size of L to N max 17 end 18 return P aretoF ront

Figure 4 . 4 :

 44 Figure 4.4: Pareto with the two optimization procedures of one iteration (Algorithm 6 lines 7 and 8).

Chapter 4 .

 4 Weekly transport problemThe objective function (4.21) which is the same as equation (4.1) represents the transportation cost. Constraints (4.22) are set covering constraints for demand satisfaction. Constraints (4.24) accounts for the number of vehicles v required. As a set covering model, this problem can be easily solved optimally provided the number of routes remains reasonable.Moreover, solutions of the MP-DARP provide feasible routes for the TC-DARP. Hence, the MP-DARP model can be used to build a good initial solution for the TC-DARP.Algorithm 7 presents the MP-DARP algorithm. A key element of this algorithm is the pool of routes L. This pool is a set of non-strongly dominated routes defined as follows: Definition 4.1. Strong route dominance. With ω and ω two routes, and C ω and C ω the costs of these routes respectively, route ω is said to strongly dominated ω if C ω ≤ C ω and both routes visit the same set of users in the same sequence.

Definition 4. 2 .

 2 Weak route dominance. Let us consider two routes ω ∈ Ω and ω ∈ Ω, with respective costs C ω and C ω . Route ω is said to weakly dominate ω if both routes visit the same set of users (in any order) and C ω ≤ C ω .

Figure 4 . 5 :

 45 Figure 4.5: Example of projection and complementary routes

  g. Grangier et al. (2017); Tellez et al. (2018b))

Chapter 4 .

 4 Weekly transport problem Algorithm 8: solveTCDARP( z, k, S ini , L ) Parameters: z: objective, k: additional constraints, S ini : initial solution, L: pool of routes. Data: t max : solver time limit, N : number of routes to append each time in the pool, M axIter: maximum number of iteration without improvement, O: list of policies Result: best solution found S * S ← ∅: current solution S * ← S ini : best solution found L ← ∅: restricted pool of routes Initialize policies in O itN onImp ← 0: number of iterations without improvement of S * while itN onImp < M axIter do /* 1. Select routes */ Select the corresponding source of routes s and selection rule r from list O if the source s is L then Select a subset l ⊆ L of N routes using r /* see Section 4.4.4 */ else Get new routes solving a DARP with multiple time windows: L new ← solveDARP mT W (S * ) /* See Section 4.5 */ Select a subset l ⊆ L new of N routes using r /* see Section 4.4.4 */ Add new routes in L new to L end Add projection and complementary routes in l Update pool L with routes from l /* 2. Solve an instance of the mono-objective TC-DARP */ Create S by solving a TC-DARP with time limit t max , objective z, additional constraints k, restricted pool L and warmstart S * /* 3. Pool management */ if TC-DARP is not solved to proven optimality then

Figure 4

 4 Figure 4.6: Example of 3 successive calls of the sequential selection rule with N = 6.

  In the formal definition of T W t u , we use a function W(H, u). This function returns a set of time windows within [a pu , b pu ]. Any service time inserted in these time windows will not create a new class. This is illustrated on Figure 4.7. The detailed construction process is given in Appendix B.0.1.

Chapter 4 .

 4 Weekly transport problemThe LNS-SCP algorithm is a Large Neighborhood Search (LNS) procedure in which a Set Covering Problem (SCP) is periodically solved to improve the current solution. As the SCP component cannot handle multiple time windows, we do not consider it here. Each iteration of the LNS procedure consists in partially destroying and repairing the current solution through dedicated heuristics. The repairing heuristic must build new feasible routes, and thus satisfy a set of timing and capacity constraints. The introduction of multiple time windows led us to modify the scheduling algorithm which embeds the time-feasibility check. We have developed an extension to the classic scheduling algorithm proposed in Tang et al. (2010) that tests whether the multiple time windows T W t u are satisfied once all other constraints are satisfied.

  3. That is a maximum ride time Tu , a pickup time window [a pu , b pu ] and a delivery time windows [a du , b du ]. The scheduling algorithm consists of two sequential phases. In the first phase, it solves a classing DARP scheduling problem considering only the original constrains. This problem has been studied by Tang et al. (2010); Gschwind, Timo (2015) and Tellez et al. (2018b). We use the scheduling algorithm presented in Tellez et al. (2018b). Given a route ω ∈ Ω, this algorithm checks time feasibility and, if the route is feasible, computes service times following the next lexicographic criterion: 1) minimize route duration, 2) schedule service times as early as possible.

  It max = 4 maximum number of iterations without improvement N = 100 × |U|/100 number of routes to be appended to the pool at each call of the TC-DARP N c = N × |T | number of routes to be appended to the pool at each call of the MP-DARP t max = 60s MILP solver time limit N max = 50000 size of the pool L N new = 5000 maximum number of routes in L new Parameters route policies θ = 1% probability of relaxing non-target users in the DARPmTW γ = 10% percentage of routes that can be re-selected in the sequential selection rule ρ = 6 roulette wheel parameterTable 4.5: Parameters MSPP (all defined in Sections 4.3-4.5).

  Selection rules MP-DARP: B = {SS} • Route policies TC-DARP: O = ({L, SS}, {L new , SS}) SS stands for the sequential selection rule and L new the pool generated through the DARP with the multiple time windows (see Section 4.4.2).

Figure 4

 4 Figure 4.8: Comparison Pareto front instance C01_60

  -4.11 show the Pareto Front obtained on GIHP instances with 60, 160 and 280 users respectively. Transportation cost is presented as the cost increase percentage with respect to the cheapest solution found on that instance (x-axis). The time consistency of non-strongly dominated solutions is shown in a vector form on the vertical axis. Each element of the vector represents the number of users having 3, 2 and 1 time-classes on that solution, respectively. Note that solutions with 4 or 5 time-classes are not represented in our tests because they have always been dominated by a solution with 3 time-classes.These Pareto fronts provide decision-makers with a fine intuition of the cost of timeconsistency associated with each user. A first observation is that all Pareto Fronts start with

Figure 4 .

 4 Figure 4.11: Pareto front C12_280

Figure 4 .

 4 Figure 4.12: Scaled Pareto fronts

  and the time consistency of users. Transportation costs include routing and vehicle ownership costs. The time consistency objective is expressed as a lexicographic function of the number of users having different time-classes. Regarding literature, this is a new way to express time consistency. It is more time consuming than traditional min-max objectives but returns a more detailed Pareto frontier that helps decision-makers selecting the appropriate solution.

  Regarding the TC-VRP problems, TC-DARP extends it by considering time windows and maximum ride times in a problem with multiple destinations. This problem was studied in the context of door-to-door transportation of children with disabilities in the Auvergne-Rhône-Alpes, a region of France.To compute the Pareto Front, we developed a matheuristic framework based on an epsilon constraint procedure and a master set partitioning problem (MSPP). Routes are generated by solving a DARP with multiple time windows and minimal wait time. At each iteration, a subset of routes is chosen to feed the MSPP procedure. Different selection rules are presented to this end. Experiments show the high performance of the MSPP on real-life instances for up to 295 users. MSPP was also tested on literature instances that achieved outstanding results for the TC-VRP benchmark.

  most 2 time-classes each. Finally, we show that allowing a flexible departure of routes improves the transportation costs of highly consistent solutions. For future research, the model can be extended with driver-related constraints such as working time shifts, breaks, and driverconsistency. Regarding vehicles, it can be extended to handle a heterogeneous fleet and en-route reconfigurations. is one of the biggest transport companies for people with disabilities in the Auvergne-Rhône-Alpes region, France.f Everyday GIHP transports more than one thousand people with disabilities to specialized centers called Medico Social Institutions (MSI). Currently, GIHP organizes the transport of each MSI independently. This policy of grouping users has many management and technical advantages, but a major drawback. It is sub-optimal from an economic point of view and the extra cost must be weighed against its benefits. This study reveals the additional cost of the current policy at around 30% compared with the best scenario. Two alternative policies allowing the pooling of transport between several MSIs in different ways are proposed. Policies differ in the flexibility of management rules to construct clusters. Both policies have comparable savings but the policy with higher flexibility has fewer routes. Regarding service quality, we found that the characteristics of user rides were not sensitive to the different policies in the presence of maximum ride time constraints.Keywords: transport pooling, clustering, proximity measures, dial-a-ride problem, reconfigurable vehicles, heterogeneous fleet

Chapter 5 .

 5 Assessment of transport pooling policiesfor persons with reduced mobility, and on behalf of institutions in the transport of people with physical or mental disabilities. GIHP has the particularity of having a fully associative shareholding. The board of directors is made up of representatives from associations of the medico-social sector, namely: ADAPEI of Rhône, ARIMC, APAJH, OVE Foundation, GIHP Auvergne-Rhône-Alpes, and GIHP National. This particularity is a competitive advantage over other transporters because there is a common interest in improving the quality of service and optimizing costs.GIHP has around 180 employees and 180 adapted vehicles. Part of the transportation activity is outsourced to about 100 drivers and 175 vehicles. Yearly GIHP provides about 500 000 trips covering 3.5 million kilometers. GIHP is present in a variety of transport services in the medico-social sector for different needs such as:Transport for Medico-social Institutions (MSI): the transport management for MSIs is the main economic activity of GIHP. This transport is mainly regular during the school year with daily frequencies or twice a week for People With Disabilities (PWD) in boarding houses.GIHP serves a wide range of social care facilities, such as rehabilitation centers for the elderly and MSIs for people with motor, mental or sensory disabilities. In this chapter, we study this transport type.Public transport: local authorities (i.e. municipalities) set up particular public services for people with reduced mobility to help them live independently. GIHP assures local transports for activities such as work, shopping, and leisure.

  Figure 5.1: CURRENT clustering policy

  Figure 5.2: Proximity between points (left) and users (right)

  Figure 5.3: Clustering MSIs

Figure 5 .

 5 Figure 5.4 shows the example of a 2-cluster solution following this policy. The cluster above (orange) covers users from 2 MSIs and the cluster below (blue) from the 3 MSIs. Although this

  Figure 5.5: Solving approach

Figure 5

 5 Figure 5.6: Maximum ride time function

Figure 5 .

 5 Figure 5.8 shows the behavior of routes for C-USER and C-MSI policies all along with the number of clusters. The first two lines, from top to bottom, show graphically the number of routes in the solution. The next two lines, the number of routes pooling transport between different MSIs. C-USER has fewer routes that C-MSI, and when the difference gets bigger, the difference in the number of routes pooling increases as well. For the C-MSI policy, the chances of transport pooling decrease with the number of clusters (33 clusters gets 0 routes pooling).

Figure 5 .

 5 Figure5.9 shows the number of requests in each cluster for a solution of each policy. The number in parentheses represents the number of clusters of the solution. The CURRENT policy shows the actual number of users at each MSI. The solution of the USER (16) policy increases the number of users in medium and big size clusters. This behavior is accented with the MSI (16) policy assigning a larger proportion of users to already big clusters. Thus, the C-USER policy seems to create more equitable clusters than the MSI policy. If this balance is an objective of the decision-maker, the C-USER policy would be preferred.

  large scale applications. In those cases, transport planners should adjust vehicle routes to adapt them to this new context. Transport planners have to minimize two antagonistic objectives: transport costs and the scheduling modifications for passengers already scheduled in the former routes. To our knowledge, this problem has not been studied in the literature. used for ALNS-based metaheuristics reinitialize incumbent solution with the best solution every 2000 iters. score for new best solutions σ 1 = 33 score for new improving solutions σ 2 = 20 score for new accepted solutions σ 3 = 15 reaction factor r = 0.1 recompute operator weights = 100 iters minimum weight operators = 0.1 maximum weight operators = 5

  Construction of T W(H, u) Parameters: u: user considered. H = {h 1 , . . . , h M }: set of the M service times of user u sorted in non-decreasing order. Data: Λ: width of time-classes. Output: The set of multiple time windows T W(H, u) 1 mtw = ∅ /* initialize an empty set of multiple time windows */ 2h = h 1 3 h = h 1 4 for i = 2, . . . , M do 5 if h i > h + Λ then 6 mtw ← mtw ∪ {[max{a pu ; h -Λ}, min{b pu ; h + Λ}]} 7 h = h i 8 h = h i 9 mtw ← mtw ∪ {[max{a pu ; h -Λ}, min{b pu ; h + Λ}]} Route ω = {1, ...,

  al. (2014) -record acceptance percentage. penalty = 10 000 penalty cost for incomplete solutions. Φ -= 10% minimal proportion of removed request used by removal operators. Φ + = 40% maximal proportion of removed request used by removal operators. p = 6roulette wheel parameter for the historical node-pair operator. σ + init = 4-regret repair operator for building the initial solution η = 1 000 launch frequency of the SCP. t limit = 60 sec imposed time limit for the SCP. ψ = 1.25 RSCP coefficient to recompute the launch frequency of the SCP.

  Healthcare transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Transport of staff, supplies, and patients & passengers . . . . . . . . . . 2.1.2 Emergency and non-emergency transport for patients & passengers . . . 2.1.3 Occasional and regular transport for patients & passengers . . . . . . . 2.2 Optimization problems in the non-emergency transport of patients & passengers with disabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Strategic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Tactical problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 Geographical dispersion of users . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	2 Literature review
	2.1

1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Operational problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Real-time problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii List of Tables 16 2.1 Emergency vs non-emergency transport . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Non-emergency transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Literature review non-emergency transport of patients & passengers . . . . . . . . 28 3.1 Matrix representation of S k for the vehicle presented in

Table 1

 1

	Chapter 1. Introduction
	Do you think you provide quality transport?		How many ressources do you deploy in the transportation activity?
	15%	8%	27%	Yes Rather yes No Rather no	25%	7%	29%	Low level Moderate level Significant level High level
		50%					39%
			Distance (km) Time (min)
	Median			30	60
	Mean			48	74
	Standard deviation	46	43

Table

1

.1 summarizes this distance in kilometers and minutes. Half of users live more than 30 km away from their MSIs and make more than 1 hour of ride time. Moreover, there is high dispersion of demands reflected Figure 1.2: Transportation from the MSI perspective in a standard deviation of 46 km and 43 minutes. Note that these values are approximately estimated and sometimes overestimated by some administrators. This condition reinforces the interest to consider the transport pooling among several MSIs. This strategy is barely implemented in current practices. According to

[START_REF] Rouquet | A typology of logistics pooling in supply chains[END_REF]

, this type of pooling is known as District pooling, and leads to a more collective and stronger supply chain. .1: Geographical dispersion of users

Table 2

 2

	.1 summarizes the differences between emergency and non-emergency transport
	services.
	Characteristics	Emergency	Non-demand
	Transport	Immediate	On-availability
	Demand	Unknown Unknown or known in advance
	Transportation cost	High	Medium-low
	Fleet utilization	Low	Medium-high
	Operating cost	High	Medium-low
	Service quality	High	Medium-low
	Response time	Short	Short-long
	Ride times	Short	Medium-long
	Table 2.1: Emergency vs non-emergency transport

Table 2

 2

	.2 summarizes the main characteristics of occasional and regular transport services.
	Note, however, in practice we can find hybrid transport systems that combine aspects from both
	regular and occasional transport. In the following section, we present optimization problems
	from the scientific literature in the context of non-emergency transport of P&P. Transport
	problems were classified according to the decision level.
		Occasional transport	Regular transport
	Frequent	Number of served patients	Transportation costs
	objectives	Transportation costs	Time-consistency
		Individual/collective preferences Staff-consistency
	Planning horizon	Short and medium term (i.e. hours, days)	Long-term (i.e. months, year)
	Operating cost	Medium-high	Low-medium
	Examples	Punctual medical appointments	Patients with long-term treat-ments
		Extra-curricular activities PWD Daily transport for PWD
		Table 2.2: Non-emergency transport

  for an extensive comparison of the acceptance criteria that support this choice. Similarly, the best solution s * is updated every time a new temporary solution s

	Chapter 3. Half-day transport problem
	Algorithm 1: The LNS-RSCP framework
	Input: Σ -: set of destroy operators, Σ + : set of repair operators,
	η: initial number of iterations between two solutions of a SCP,
	t limit : initial time limit for SCP.
	Output: Best solution found s * .
	Build initial solution s using repair operator σ + init ∈ Σ +
	Pool of routes: Ω ← ∅
	Request bank: B ← ∅
	iter ← 0
	while Termination criterion not met do
	/* LNS component */

s ← s Destroy quantity: Randomly select a proportion Φ ∼ U nif orm(Φ -, Φ + ) of requests to remove Operator selection: Randomly select a destroy operator σ -∈ Σ -and a repair operator σ + ∈ Σ + Destroy: Apply σ -to remove max{1, Φ • |R| } requests from s and place them into the request bank B Repair: Apply σ + to reinsert requests from B into s if Acceptance criterion is met then s ← s if Cost of s is better than the cost of s then s * ← s /* RSCP component */ Update Ω with the non-dominated routes of s if iter modulo η = 0 (every η iterations) then s ← Solve SCP(Ω, s * , t limit ) if the SCP is not solved to proven optimality then 19 Reinitialize Ω with the routes of s * 20 Every two consecutive failures to optimally solve the SCP: update parameter η Remove duplicate requests in s s * ← s iter ← iter + 1 return s * 3.4. Solution method

Table 3 .

 3 2 provide the best average performance for the optimization problems solved in this chapter. After experimentation, we found that: K-regret operators with K > 4 did not improve the solution quality and two removal operators (historical removal and random removal) are sufficient when the SCP component is active. Note that values for parameters η, t limit and ψ,

	can be automatically modified in the reactive version RSCP for different instance sizes (see
	Section 3.4.3).

Regarding the sequencing of feasibility evaluation, performing the Schedule evaluation (Algorithm 11) before the Capacity evaluation (Algorithm 2) can reduce computation time up to 50%. This reduction is mostly explained by the fact our data set (derived from real

Table 3 .

 3 2: Parameters (all defined in Section 3.4). data) is constrained more in time than in capacity. In other words, long pickup legs are seldom feasible because of time windows and maximum ride times. In addition, sorting vehicle types in non-increasing order of costs, before testing the vehicles capacity, can reduce computation time by up to 10% (Algorithm 4).

  to the former LNS implementation. The third metaheuristic ALNS(5)-SCP integrates the SCP component described in Section 3.4.3. The fourth variant, denoted LNS(2)-SCP, considers 2 destroy operators only (historical node-pair removal and random removal) and no adaptive layer. The fifth variant, denoted ALNS(5)-RSCP, is an extension of ALNS(5)-SCP integrating the reactive layer described in Section 3.4.3. The sixth variant, denoted LNS(5)-RSCP, does not include the adaptive layer. Finally, LNS(2)-RSCP extends the LNS(2)-SCP by including the reactive layer of Section 3.4.3. General parameters for all metaheuristics can be found in Table4.5. Additional parameters for ALNS

		Avg Cost	Avg Gap	Nb BKS
	Variant	Best	Avg	Best	Avg	(14)
	LNS(5)	2,348.51 2,357.59 3.60% 3.94%	3
	ALNS(5)	2,349.06 2,369.08 3.61% 4.46%	2
	ALNS(5)-SCP	2,289.81 2,300.03 1.34% 1.64%	7
	LNS(2)-SCP	2,289.74 2,297.23 1.27% 1.52%	9
	ALNS(5)-RSCP 2,235.25 2,242.52 0.13% 0.38%	9
	LNS(5)-RSCP	2,235.36 2,241.60 0.12% 0.31%	12
	LNS(2)-RSCP	2,236.46 2,243.91 0.13% 0.39%	10
	Table 3.5: Performance comparison of LNS-based heuristics for our instances (see A.2 for
	detailed results)

can be found in Table

A

.1

The first observation is that the SCP component brings significant improvement in the solution quality. In addition, it can be observed that the LNS can be considerably simplified when the SCP component is used. Indeed, the matheuristic with two destroy operators performs as well as the versions with five destroy operators. Comparing LNS(2)-SCP with LNS(2)-RSCP, it can be seen that a second subsequent improvement is obtained when the SCP includes the reactive layer to adapt its parameters during the search. According to this set of experiments, LNS(2)-RSCP configuration seems to outperform the other variants, either in performance or in simplicity.

  FSM-DARP-RC instances. we do not scale computational times here as CPU information is not available for all methods and our goal is not to compete with these three methods. Nevertheless,

				3.6. Computational experiments
	these experiments show that the performance of LNS(2)-RSCP remain competitive on simpler
	benchmark problems.
		NbBKS Avg	Avg Obj	Avg Gap
	Method	(20)	Time	Best	Avg	Best	Avg
	Braekers et al. (2014) (TA)	3	83.2 512.06 514.31 0.81% 1.16%
	Chassaing et al. (2016)(ELS)	6	592.4 511.14 513.67 0.64% 1.04%
	Gschwind and Drexl (2016) (ALNS)	9	209.5 509.04 510.19 0.32% 0.50%
	Ours (LNS2-RSCP)	8	727.1 509.53 511.62 0.38% 0.72%
	Table 3.6: Benchmark classic DARP Cordeau and Laporte (2003) (Detailed results in Sec-
	tion A.3)

Table 3

 3

	)-RSCP outperforms the MSALNS

.7: Benchmark

[START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF]

(detailed results in A.4)

Table 3

 3

.8: Savings due to en-route configuration

Table 3 .

 3 10: Costs of vehicle types for fixed cost analysis

  To model the problem, we introduce the binary decision variable y t

	U	set of users
	T	set of time periods
	T u set of time periods in which user u ∈ U needs to be transported.
	Ω	set of all routes
	Ω u set of routes serving user u ∈ U
	C	set of time-classes
			Table 4.1: Sets
	β t u	equal to 1 if user u ∈ U must be serviced on period t ∈ T , and 0 otherwise
	C ω	variable cost of route ω ∈ Ω
	λ	weekly vehicle cost ownership cost.
	H uω earliest time service to user u ∈ U by route ω ∈ Ω
	∆ + ω	maximum forward time shift of route ω ∈ Ω
	Λ	time-class width
			Table 4.2: Data
	Binary Variables
	y t
	Other variables
	δ t ω ∈ [0, ∆ + ω ] s -uc , s +	time shift (used margin) of route ω ∈ Ω at period t ∈ T

ω which is equal to 1 if route ω ∈ Ω is selected at period t ∈ T . The binary variable z t uc is equal to

1 if user u ∈ U is ω ∈ {0, 1} =1 if route ω ∈ Ω is selected at period t ∈ T , and 0 otherwise z t uc ∈ {0, 1} =1 if user u ∈ U is assigned to time-class c ∈ C at period t ∈ T ,

and 0 otherwise µ uc ∈ {0, 1} =1 if user u ∈ U uses time-class c ∈ C, and 0 otherwise uc ∈ R + lower and upper bounds for the time-class c ∈ C u for user u ∈ U h t u ∈ R + beginning of service for user u ∈ U at period t ∈ T v number of vehicles needed for the whole planning horizon m u number of users having c ∈ C time-classes (post-processed variable)

Table 4.3: Variables assigned to time-class c ∈ C at period t ∈ T . Binary variables µ uc indicate which time-classes from set C are actually used by user u. For example, if u has 3 time-classes, it is said to use classes 1, 2 and 3. Hence, µ u,1

  4.5. Route generation: DARP with multiple time windowsAlgorithm 9: Phase II: Scheduling extension for solving the DARPmTW Input: ω: Route with minimal duration and nodes from n 0 , . . . , n N being the first and last node the depot, T W t u : Set of multiple time windows sorted in ascending order, w i : service time at node n i , ∆ + If the service time takes place after the end of the time window (n i > b), the time window [a, b] cannot be used. it is removed from the set T W t u (lines 19-20) and the next time window is checked. If there is no more time window available in T W t u , infeasibility is detected.

	ω : maximum forward time shift of the Output: if route ω is feasible or unfeasible route. 1 i ← 1 2 while i < N do 3 if n i ∈ P then 4 u ← user with pickup n i /* Implies n i = p u */ 5 for each time window of the form [a, b] in T W t u do /* time windows */ 6 if w n i < a then 7 δ = a -w n i 8 if δ < ∆ + ω then /* feasible forward time shift */ 9 for each node j in ω do 10 w j = w j + δ 11 ∆ + ω ← ∆ + ω -δ 12 i ← 1 13 go to line 3 /* feasible pickup */ 14 else 15 return unfeasible 16 else if w n i ≤ b then 17 i ← i + 1 18 go to line 3 /* feasible pickup */ 19 else 20 T W t u ← T W t u \ {[a, b]} 21 return unfeasible 22 i ← i + 1 23 return feasible exactly a. After shifting the route, the algorithm starts over the scheduling procedure with the first node because this shift can provoke time windows violation at another node (line 9-12). If the value w n i -a is larger than ∆ + ω , then the route schedule is unfeasible (lines 14-15). (ii) If the service time at current node takes place in time window [a, b], then the next node is checked (lines 16-18). (ii) Chapter 4. Weekly transport problem

Table 4 .

 4 9 shows the numerical results aggregated by the percentage of presence during the week. For example, data-5-Y aggregates instances where, on average, 50% of users are

	Chapter 4. Weekly transport problem
	transported each day, while in the group data-9-Y the average percentage of users transported
	rises to 90%.
	Instance	Avg Gap Transportation cost
	C max	≤5	≤4	≤3	≤2	1
	data5-Y	-1.10% -1.00% -1.02% -0.21% -0.37%
	data6-Y	-1.03% -1.03% -0.81% -0.26%	0.83%
	data7-Y	-1.09% -0.96% -0.86%	0.13% -0.13%
	data8-Y	-1.06% -1.00% -0.72%	0.00% -0.25%
	data9-Y	-0.61% -0.61% -0.49% -0.27% -1.76%
	Avg Gap (%) -0.98% -0.92% -0.78% -0.12% -0.33%
	Nb Sols	70	70	70	70	70
	Nb new BKS	63	59	53	35	35

Table 4 .

 4 9: Results aggregated by percentage of users requests on[START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] benchmarkThe average relative gap (Avg Gap) overall instances between the results obtained with the MSPP and the LNS was improved for all time-classes. However, slightly better results are reported for solutions with 3, 4 and 5 time-classes. This result is confirmed with the number of new best know solutions (Nb new BKW) which is more than 50 for solutions above 3

	time-classes and 35 for solutions with 1 and 2 time-classes. A total number of 245 strictly new
	best solutions were found, as shown on the last row of the table. Detailed results can be found
	in Appendix B.1.

Table 4 .

 4 10 shows the numerical results aggregated by MSI. The last two digits of the instance name represent the number of users. This table shows that MSPP has better performance with larger size instances. However, particularly dataX-59 instances are the most difficult to solve for the MSPP with an over the cost of 3.41% for C max = 2 solutions and 2.39% for C max = 1 solutions.

Table 4 .

 4 10: Results aggregated by instance size on Feillet et al. (2014) benchmark

Table 5

 5

	.3 presents

  Table 5.4 presents the best solutions for the C-USER policy and the CURRENT policy. The number in parentheses represents the number of clusters of each scenario. The CURRENT policy has 33 clusters because of the 33 MSIs of the case study.

		CURRENT USER(16) USER(8) USER(4) USER(2) BKS(1)
	Relatedness	-	pickup pickup pickup pickup	-
	Total cost	11604.7 10364.0 9814.9 9253.6 8814.1 8620.1
	Cost savings (%)	34.6%	20.2%	13.9%	7.3%	2.2% 0.0%
	Nb. Routes	129	81	75	69	67	65
	Routes pooling (%)	0%	77%	80%	83%	82%	85%
	Routes reconfiguring (%)	0%	15%	19%	17%	16%	18%
	Max Nb. Reconfigurations	0	2	2	2	2	3
	Median. Ride time (min)	24.6	24.0	24.0	24.3	23.3	23.3
	Avg. Ride time (min)	27.5	26.0	26.3	26.6	26.1	25.9
	StdDev Ride time (min)	16.4	14.2	14.9	15.7	15.7	15.8
	Coef. Variation (CV=StdDev/Mean)	0.6	0.5	0.6	0.6	0.6	0.6
	Table 5.4: Comparison users clustering policy

Table A .

 A 1: Parameters for the ALNS as in[START_REF] Masson | The Dial-A-Ride Problem with Transfers[END_REF]

125

A.

2 Detailed results comparison of LNS-based algorithms

  TableA.2: Performance comparison of LNS-based heuristics. Time limits in column 2 are expressed in minutes. Average costs (Avg) are computed over 5 runs. Nb BKS refers to the number of best-known solutions (BKS). The Gap for every instance is computed as (value -BKS)/BKS × 100. General parameters for all metaheuristics can be found in TableA.1. Additional parameters for ALNS can be found in TableA.1.

		Appendix A. Appendix Chapter 3
		A.4
			LNS(5)		ALNS(5)	ALNS(5)-SCP	LNS(2)-SCP	ALNS(5)-RSCP	LNS(5)-RSCP	LNS(2)-RSCP
	Inst	Time	Best	Avg	Best	Avg	Best	Avg	Best	Avg	Best	Avg	Best	Avg	Best	Avg
	I01-80	16	1,791.69 1,798.30	1,803.42 1,811.81	1,757.22	1,757.70	1,757.22 1,757.22	1,757.22	1,757.22	1,757.22 1,757.22	1,757.22	1,757.22
	I02-60	16	911.79	913.64	911.88	926.49	925.09	926.38	911.79	913.21	915.02	922.48	911.79	914.45	915.34	922.63
	I03-80	16 Avg Gap	3.60%	3.94%	3.61%	4.46%	1.34%	1.64%	1.27%	1.52%	0.13%	0.38%	0.12%	0.31%	0.13%	0.39%
		NbBKS	3		2		7		9		9		12		10

Detailed results benchmark Qu and Bard (2013)

  According to[START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF], we denote by C t the cost related to travel time. It is computed as the total time (traveled distance divided by speed), times the cost per unit of time c time = $0.377/min. C p denotes the total passenger ride time cost with the unitary cost τ c = $0.0001 per minute. The vehicle ownership cost is C v = $0.01/van. Finally, the total cost is computed as C total = C t + C p + C v . 3 runs were performed of the LNS(2)-RSCP with an stopping criteria of 1 hour. For each instance C total corresponds to the best total cost found over 3 runs. The Gap is computed as in regarding to the best cost of[START_REF] Qu | The heterogeneous pickup and delivery problem with configurable vehicle capacity[END_REF]. .29 0.06 62.77 55.18 0.28 0.08 55.54 -11.52% -10.95% A201 53.57 0.23 0.06 53.86 52.81 0.27 0.06 53.14 -1.33% -2.28% A052 36.86 0.20 0.05 37.11 42.25 0.23 0.09 42.58 14.73% 13.99% A102 45.19 0.19 0.05 45.43 45.34 0.30 0.07 45.71 0.61% 2.92% A152 49.64 0.21 0.05 49.90 44.37 0.29 0.09 44.75 -10.32% -8.17% A202 49.79 0.24 0.06 50.09 48.56 0.30 0.09 48..22 0.05 44.25 37.01 0.37 0.06 37.44 -15.39% -15.09% B301 44.84 0.25 0.05 45.15 37.19 0.30 0.06 37.54 -16.85% -16.07% B401 47.65 0.21 0.05 47.91 38.82 0.26 0.05 39.13 -18.33% -18.28% B501 47.87 0.20 0.05 48.12 38.07 0.30 0.05 38.43 -20.15% -19.69% B601 45.83 0.22 0.05 46.10 40.10 0.20 0.05 40.36 -12.46% -12.12% B202 45.19 0.19 0.05 45.43 36.34 0.31 0.05 36.70 -19.21% -18.66% B302 44.42 0.19 0.05 44.66 37.73 0.21 0.05 37.98 -14.95% -14.83% B402 47.90 0.19 0.05 48.14 36.63 0.24 0.05 36.92 -23.30% -23.10% B502 46.50 0.18 0.05 46.73 36.93 0.24 0.05 37.21 -20.36% -17.73% B602 45.72 0.20 0.05 45.97 37.73 0.30 0.05 38.08 -17.16% -16.75% Avg 45.99 0.21 0.05 46.25 37.66 0.27 0.05 37.98 -17.82% -17.23% .44 0.22 0.05 43.72 36.34 0.35 0.05 36.74 -15.97% B301 43.90 0.27 0.05 44.21 36.47 0.35 0.05 36.86 -16.62% B401 43.99 0.29 0.05 44.32 37.20 0.25 0.04 37.50 -15.39% -15.59% B501 42.94 0.22 0.05 43.21 36.43 0.32 0.05 36.81 -14.82% B601 43.22 0.21 0.05 43.48 36.47 0.37 0.05 36.90 -15.14% B202 42.13 0.27 0.05 42.45 36.87 0.28 0.05 37.19 -12.38% B302 42.13 0.27 0.05 42.45 36.87 0.28 0.05 37.19 -12.38% B402 42.13 0.27 0.05 42.45 37.99 0.25 0.04 38.28 -9.82% -9.82% B502 40.38 0.23 0.04 40.65 37.69 0.26 0.04 37.99 -6.54% B602 39.70 0.23 0.05 39.98 36.49 0.25 0.05 36.79 -7.99% Avg 42.40 0.25 0.05 42.69 36.88 0.30 0.05 37.22 -12.71% -12.71% Table A.6: Benchmark Qu and Bard (2013) instances "B" ignoring walker requirements.

			MSALNS			LNS(2)-RSCP
	Inst	C t	C p	C v C total	C t	C p	C v C total Gap (*) Gap Avg
	A051 43.00 0.20 0.04 43.24 42.29 0.22 0.09 42.60 -1.47%	-1.71%
	A151 49.82 0.23 0.06 50.11 50.18 0.27 0.06 50.51	0.80%	0.18%
	A101 43.99 0.22 0.05 44.26 44.75 0.25 0.08 45.07 MSALNS LNS(2)-RSCP C t C p C v C total C t C p C v C total Gap A251 62.42 094 -2.29% 1.84% Avg Gap 1.17% -0.76% B201 43Inst
	A252 55.21 0.28 0.06 55.55 52.73 0.28 0.09 53.10 -4.42%	-4.62%
	Avg	48.95 0.23 0.05 49.23 47.85 0.27 0.08 48.19 -1.34%	-1.02%
	Table A.4: Benchmark Qu and Bard (2013) instance "A" scenario (iii) without groups
			MSALNS			LNS(2)-RSCP
	Inst	C t	C p	C v C total	C t	C p	C v C total	Gap	Avg Gap
	B201 43.99 0Table A.5: Benchmark Qu and Bard (2013) instance "B" scenario (iii) without groups

do 21 if i ∈ P then 22

  M }. Output: The set of service times h i ∀i ∈ ω and the maximal route time shift ∆ + ω , or -1 if infeasible 1 h 1 ← a 1 /* beginning of the service */ 2 H ← 0 /* total waiting time on the route */ 3 F ← b 1 -h 1 /* FTS latest start at node 1 */ 4 F ← b 1 -h 1 /* FTS earliest start at node 1 */ /* Phase 1: set up nodes at the earliest start */ 5 for i = 2, . . . , M do 6h i ← max{a i ; h i-1 + ζ i-1 + t i-1,i } + max{0; a i -(h i-1 + t i-1,i + ζ i-1 )} ← h 1 + F 16 for i = 2, . . . , M do 17 h i ← max{h i-1 + ζ i-1 + t i-1,i ; a i } /* Check route duration constraint */ 18 if (h M -h 1 ) > T then return -1

	Instance		Transportation cost		Time
	C max	≤5	≤4	≤3	≤2	≤1	(min)
	data5-15	663.2	663.2	663.2	674.1	782.3 11.6
	data5-21	773.7	779.1	779.1	779.1	817.3 21.9
	data5-25	617.4	617.4	617.4	622.2	669.0 29.1
	data5-26	767.6	767.6	771.9	778.8	815.9 45.8
	data5-27	934.6	934.6	934.6	942.0 1026.1 61.2
	data5-32
	13
	/* Phase 2: optimize route duration				*/
	14 ∆ + ω = F -F				/* route time shift */
	15 h 1 19
	/* Phase 3: check ride time constraints				*/

7 if h i > b i then return -1 8 H ← H 9 F = F 10 F ← min{F ; H + max{0; l i -h i }} 11 if i = M then 12 F ← min{F ; H} 20 for i = M -2, . . . , 1 u ← user of pickup i /* implies i = p u */ 23 δ ← (h du -h pu + ζ i ) -T u 24 if (δ > 0) then 25 h pu ← h pu + δ 26 if h pu > b i then return -1 27 for j = p u + 1, . . . , M do 28 w j ← max{a j ; h j-1 + ζ j-1 + t j-1,k } 29 if h j > b j then return -1 30 if T u -(h du -h pu + ζ i ) < 0 then

31 return -1 32 33 return {h i |i ∈ ω}, ∆ + ω 133 B.1 TC-VRP

  163.6 Table B.2: Benchmark Feillet et al. (2014)

	Instance		Transportation cost		Time
	C max	≤5	≤4	≤3	≤2	≤1	(min)
	data7-15	746.9	746.9	746.9	752.6	790.3 11.9
	data7-21	830.1	833.7	833.7	833.7	899.3 39.8
	data7-25	719.5	724.7	724.7	728.8	767.9 34.9
	data7-26	880.3	880.3	883.5	887.4	920.7 37.9
	data7-27 1053.4 1053.4 1053.4 1056.5 1108.5 39.7
	data7-32 1079.7 1079.7 1079.7 1097.3 1154.3 57.2
	data7-41 1644.8 1644.8 1648.5 1661.0 1730.4 63.2
	data7

Table C

 C : TELLEZ SANCHEZ DATE de SOUTENANCE : 4/10/2019 (avec précision du nom de jeune fille, le cas échéant) En France, le coût du transport médico-social a été estimé à 400 millions d'euros en 2012 et augmente à un taux annuel de 8% depuis. Pour un établissement médico-social (ESMS), ce coût représente souvent la deuxième dépense en importance après celle du personnel. Dans ce contexte, cette thèse appartenant au projet «Numérique et Optimisation pour une Mobilité Adaptée» (NOMAd) vise à améliorer le transport quotidien des personnes handicapées entre leur domicile et les ESMS. Pour cela, nous proposons la mutualisation du transport entre plusieurs ESMS ainsi qu'une stratégie d'optimisation globale de la planification annuelle de transport. La construction de la planification annuelle des transports est un problème complexe encore non complètement résolu dans la littérature scientifique. Conformément à la pratique actuelle, nous supposons que le plan de transport annuel est composé d'horaires hebdomadaires identiques divisés en demi-journées. Le problème d'optimisation sur une demi-journée, appelé "fleet size and mix dial-a-ride problem" considère plusieurs types de passagers et un parc hétérogène de véhicules reconfigurables qui peuvent être modifiés en route. La matheuristique LNS-RSCP est développée pour ce problème. L'optimisation du problème hebdomadaire, nommé time-consistent DARP, comprend simultanément des exigences de régularité de service et des objectifs de coût de transport. La matheuristique MSPP est développée pour ce problème. Actuellement, la gestion du transport est principalement réalisée intra-établissements, sans mutualisation. La mutualisation du transport, en plus de l'augmentation de la complexité du problème, suppose d'avoir un intérêt économique et un mécanisme commun de gestion et communication efficace entre les parties. Au niveau stratégique cette étude vise à évaluer l'impact de la mutualisation sur les coûts et temps de trajet. Opérationnellement, ce problème correspond au problème de clustering pour la résolution des problèmes de grande taille.MOTS-CLÉS : Optimisation, Recherche opérationnelle, transport, personnes en situation de handicap, mutualisation

	Prénoms : Oscar Augusto
	TITRE : Optimisation du transport quotidien des personnes en situation de handicap
	NATURE : Doctorat	Numéro d'ordre : AAAALYSEIXXXX
	Ecole doctorale : École Doctorale Informatique et Mathématiques (N° ED512)
	Spécialité : Génie Industriel
	RESUME :
	Laboratoire (s) de recherche : Laboratoire DISP
	Directeur de thèse: Thibaud MONTEIRO
	Président de jury : Maria DI MASCOLO
	Composition du jury :
	NORRE, Sylvie	Professeur Université Clermont-Auvergne	Rapporteur
	JUSSIEN GUERET, Christelle	Professeur Université d'Angers	Rapporteur
	DI MASCOLO, Maria	Directrice de recherche Laboratoire G-SCOP	Examinatrice
	GARAIX, Thierry	Maître Assistant École des Mines St. Étienne	Examinateur
	MONTEIRO, Thibaud	Professeur INSA Lyon	Directeur
	VERCRAENE, Samuel	Maître de conférences INSA Lyon	Co-directeur
	LEHUÉDÉ, Fabien	Professeur IMT Atlantique	Co-directeur
	PÉTON, Olivier	Professeur IMT Atlantique	Co-directeur

.1: Parameters LNS-SCP algorithm 137 FOLIO ADMINISTRATIF THESE DE L'UNIVERSITE DE LYON OPEREE AU SEIN DE L'INSA LYON NOM

Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2019LYSEI059/these.pdf © [O.A. Tellez Sanchez], [2019], INSA Lyon, tous droits réservés

In english "Digital and Optimization for Adapted Mobility"

https://disp-lab.fr/

https://www.ls2n.fr/

These instances will be made available on www.vrp-rep.org on acceptation of this chapter.

http://project-osrm.org/

GIHP: www.gihp-sa.com

http://project-osrm.org/

Acknowledgments

Strategic

Depot location [START_REF] Doerner | Multicriteria tour planning for mobile healthcare facilities in a developing country[END_REF] Facility location problems X X x x X X Fleet dimensioning [START_REF] Fu | Fleet size and mix optimization for paratransit services[END_REF] Fleet size and mix DARP X X X X X X X X X X Tactical [START_REF] Braekers | A multi-period dial-a-ride problem with driver consistency[END_REF] DARP driver consistent X X X X X X X X X Consistency [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF] VRP time consistent X X X X X Chapter 4 DARP time-consistent X X X X X X X X X Operational Vehicle routing [START_REF] Aldaihani | Hybrid scheduling methods for paratransit operations[END_REF] PDP with bus lines X X X X X X X [START_REF] Borndörfer | Telebus berlin: Vehicle scheduling in a dial-a-ride system[END_REF] H-DARP X X X -X X X X X [START_REF] Braekers | Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots[END_REF] H-DARP X X X X X X X X [START_REF] Coppi | A planning and routing model for patient transportation in health care[END_REF] H-DARP with scheduling X X X X X X X X [START_REF] Detti | A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare[END_REF] H-DARP with compatibility c. X X X X X X X X X [START_REF] Dikas | Scheduled paratransit transport systems[END_REF] Flexible bus lines X X X X X X X [START_REF] Fleischmann | Operations Research Proceedings[END_REF] DARP patient preferences X X X X X X X X [START_REF] Fu | Improving paratransit scheduling by accounting for dynamic and stochastic variations in travel time[END_REF] H-DARP time-dependent-S X X X X X X X X X X [START_REF] Fu | Scheduling dial-a-ride paratransit under time-varying, stochastic congestion[END_REF] DARP time-dependent-S X X X X X X X X [START_REF] Lehuédé | A multi-criteria large neighbourhood search for the transportation of disabled people[END_REF] DARP Multi-criteria X X X X X X X [START_REF] Molenbruch | Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation[END_REF] DARP Bi-objective X X X X X X X [START_REF] Paquette | Combining multicriteria analysis and tabu search for dial-a-ride problems[END_REF] H-DARP Multi-criteria X X X X X X X X X [START_REF] Parragh | Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem[END_REF] H-DARP X X X X X X X X [START_REF] Parragh | Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints[END_REF] H-DARP with driver c. X X X X X X X X Qu andBard (2015, 2013) H [START_REF] Beaudry | Dynamic transportation of patients in hospitals[END_REF] Dyn-DARP X X X -X X X X X X [START_REF] Fu | On-line and off-line routing and scheduling of dial-a-ride paratransit vehicles[END_REF] Dyn [START_REF] Mo | Mass customizing paratransit services with a ridesharing option[END_REF] DARP with discounts X X X X X X [START_REF] Schilde | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports[END_REF] Dyn-S-DARP X X X X X X X X X [START_REF] Xiang | The study of a dynamic dial-a-ride problem under timedependent and stochastic environments[END_REF] Dyn-DARP time-dependent-S X X X X X X X X X

Comparison based on time-classes

In this test we compare transportation costs for the cheapest solution found time-class. Although these instances have 5 time periods, users in non-dominated solutions present at most 3 timeclasses. Thus, for each run, we report the value of the cheapest solutions found with 3, 2 and 1 time-classes, respectively. Table 4.6 reports the corresponding computational results.

Comparison based on the quality of the Pareto front

The hypervolume indicator was introduced by [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF] in order to compare different Pareto fronts. In multi-objective problems, the hypervolume measures the volume between the set of non-dominated solutions and a reference point. In this study, we use nadir point as a reference point which is an artificial point compose by the best value found on each objective.

The larger the hypervolume indicator, the better is the front Pareto [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF]. The instance name is reported on Column 1. Column 2 presents the best hypervolume found regardless the run and the setting. The best results are shown in bold face.

In the next columns, we report the relative gap between the average value hypervolumes with the corresponding setting and the best hypervolume found (Best). It is computed as (Avg hyperpervolume -Best) / Best × 100. Row Avg is the average value of the corresponding column.

The first observation of Table 4.7 is that MSPP has the best results in 4 out 5 instances.

Surprisingly the MSPP-withRW provides slightly better results in the biggest instance. Comparing the average values (Avg) of MSPP-noDARPmTW against MSSP, we conclude that DARPmTW generate routes that significantly improve the solution quality (21.6%).

Overall we can confirm with this experiment that MSPP configuration outperforms other variants. As an example, Figure 4.8 shows graphically the difference of 3 Pareto Fronts of the same instance I01_60 using the 3 MSPP variants.

Performance evaluation on benchmarks from the literature

Since the TC-DARP is a new problem, there is no benchmark in the literature. However, to evaluate the performance of the MSPP, we solve reference instances for two other time-consistent routing problems. The first benchmark is an adaptation of the conVRP instances from [START_REF] Groër | The Consistent Vehicle Routing Problem[END_REF] called RconVRP. This adaptation, proposed by [START_REF] Feillet | A new consistent vehicle routing problem for the transportation of people with disabilities[END_REF], transforms

Fleet utilization

A relevant characteristic of solutions is the fleet of selected vehicles. Table 5.6 presents the percentage of vehicle types selected for 3 representative scenarios: CURRENT, C-MSI(2) and C-USER(2). The last two with 2 clusters each.

16 0 0 0 0 0 0% 0% 0% VAN18 8 0 0 0 0 0 0% 0% 0% VAN19 7 1 6 2 0 0 2% 0% 1% VAN20 2 1 0 0 0 0 3% 1% 0% VAN21 3 5 4 4 5 3 0% 0% 0% VAN22 22 0 0 0 0 0 0% 0% 0%

Table 5.6: Vehicle's utilization Overall, we can note that selected vehicles are concentrated in very few models. This suggests that the current fleet can be reduced to dominant models. Additionally, the percentage of reconfigurable vehicles is higher in the policies allowing transport pooling (C-MSI and C-USER).

Reconfigurable vehicles VAN12 and VAN13 are predominantly used in all scenarios. These vehicles have interesting configurations (i.e. 3 seats + 3 wheelchairs) and low ownership costs compared to other reconfigurable vehicles. Vehicle VAN10 which is cheaper was very little use probably because of its limited capacity for wheelchairs (up to 2). Vehicle VAN21 with a big capacity was not selected due to the high ownership cost. Even though the CURRENT scenario does not reconfigure en-route, there is significant utilization of these vehicles probably because of the (3-3) configuration.

Non-reconfigurable vehicles are also used but mostly in the CURRENT scenario. Vehicle

B.0.3 Parameters MSPP tests

• MSPP : algorithm as presented in this chapter.

• B = {(D(L), SS),

• O = {(L, SS); (L new , SS)}.

• MSPP-withRW : MSPP with the roulette wheel selection rule

• MSPP-noDARPmTW : MSPP without using DARPmTW.