New variants and solution methods for the dial-a-ride problem : An application to the transportation of disabled children
Nouvelles variantes et méthodes de résolution pour le problème de transport à la demande : Application au transport d’enfants en situation de handicap
Résumé
This thesis introduces new models and solution methods for the Dial-A-Ride Problem (DARP). This work is applied to the regular transportation of disabled children between their homes and medico-social institutions. To ensure a high quality of service and low costs, the transportation must be carried out as efficiently as possible. None of the methods in the literature can solve real problems due to their large size (several thousand users). In addition, research has focused on the routing of vehicles. However, the integration of other elements revolving around transport would be beneficial for healthcare systems as a whole. In the three main chapters of this thesis, we provide some answers to these questions. Firstly, two machine learning methods are applied: an offline method extracts the characteristics of good solutions and uses them to create new heuristics; an online method called NRPA constructs the best sequence of users to insert. Secondly, we present the Commuting Dial-A-Ride Problem (Com-DARP). In this variant, each user has an outbound trip in the morning, a return trip in the evening, and a maximum daily ride time. The dependency between the morning request and evening request is used to improve transportation on a daily basis. We solve the problem with a metaheuristic : the Small and Large Neighborhood Search coupled with a Precedence Filter (SLNS-PF). Third, we introduce the Assignment Dial-A-Ride-Problem (ADARP). This variant extends the scope of the vehicle routing problem to include user assignment and resource allocation. The problem is solved by a new matheuristic called Iterative Route Search (IRS). In each chapter, experimental results are analyzed to provide new theoretical and practical perspectives.
Cette thèse introduit de nouveaux modèles et méthodes de résolution pour les problèmes de transport à la demande (DARP). Ce travail s’applique au transport régulier d'enfants en situation de handicap entre leurs domiciles et leurs lieux de prise en charge. Pour des raisons de coûts et de qualité de service, il doit être effectué aussi efficacement que possible. Aucune méthode de la littérature ne peut résoudre les problèmes réels car leur taille est trop importante (plusieurs milliers d'usagers). De plus, les recherches se concentrent sur l'organisation des tournées de véhicules. Cependant, l'intégration d'autres éléments gravitant autour du transport serait bénéfique pour les systèmes de santé dans leur ensemble. Nous apportons des éléments de réponse à ces enjeux dans les trois chapitres principaux de cette thèse. Premièrement, deux méthodes d'apprentissage automatique sont appliquées : une méthode offline extrait les caractéristiques des bonnes solutions et les utilise pour créer de nouvelles heuristiques ; une méthode online dénommée NRPA construit la meilleure séquence d'usagers à insérer. Deuxièmement, nous présentons le problème journalier de transport à la demande (Com-DARP). Dans cette variante, chaque usager a un trajet aller le matin, un trajet retour le soir, et un temps de trajet maximal journalier. La dépendance entre les deux demandes de trajet est utilisée pour améliorer le transport à l'échelle de la journée. Nous résolvons le problème avec une métaheuristique de recherche à petit et grand voisinage couplée à un filtre de précédences (SLNS-PF). Troisièmement, nous introduisons le problème d'affectation et transport à la demande (ADARP). Cette variante élargit le champ d'application du problème de tournées de véhicules en incluant l'affectation des usagers et l'allocation des ressources. Le problème est résolu par une nouvelle matheuristique nommée recherche itérative d'itinéraires (IRS). Dans chaque chapitre, les résultats expérimentaux sont analysés pour fournir de nouvelles perspectives théoriques et pratiques.
Domaines
Recherche opérationnelle [math.OC]
Origine : Version validée par le jury (STAR)