Models and algorithms for integrated vehicle routing and driver scheduling problems

Dans cette thèse, nous étudions des problèmes d’optimisation liés au transport longue distance. Dans de tels systèmes, deux ressources distinctes — les véhicules et les conducteurs— doivent être conjointement affectées à un ensemble de tâches de transport afin de satisfaire la demande de transport tout en minimisant les coûts de planification. Dans un premier temps, nous abordons le Problème Intégré d’Itinéraires des Véhicules et d’Horaires des Conducteurs (IVRDSP — Integrated Vehicle Routing and Driver Scheduling Problem). Les caractéristiques communes observées dans le transport longue distance sont prises en compte: un même véhicule peut être conduit par plusieurs conducteurs ; un conducteur peut changer de véhicule au cours de son service ; et un conducteur supplémentaire peut voyager en tant que passager. Nous considérons également des situations où plusieurs véhicules peuvent être physiquement combinés pour exécuter certaines tâches. Ensuite, nous étudions une extension de l’IVRDSP dans laquelle l’heure de départ de chaque tâche peut être choisie à l’intérieur d’un intervalle prédéfini. Nous modélisons ces problèmes comme des programmes mixtes en nombres entiers (MIP) et décomposons le problème global en deux sous-problèmes : le Sous problème d’Ordonnancement des Conducteurs (DSSP) et le Sous-problème de Routage des Véhicules (VRSP). La procédure de résolution suit un processus en deux phases. Dans la première phase, le DSSP est résolu à l’aide d’une méthode heuristique basée sur la génération de colonnes. À partir des plannings de conducteurs obtenus, la seconde phase traite le VRSP,qui est formulé comme un modèle en MIP.