Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec\nfenêtres de temps où un gain est associé à chaque client et où l'objectif est\nde maximiser la somme des gains recueillis moins les coûts de transport.\nDe plus, un même véhicule peut effectuer plusieurs tournées durant\nl'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple,\ndans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées\ncomplètes de travail. Nous croyons que ce type de\nproblème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries\nélectroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile.\n\nDans le premier chapitre de cette thèse, nous présentons d'abord une revue de la\nlittérature consacrée aux\nproblèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une\nréutilisation des véhicules. Nous présentons les\nméthodologies générales adoptées pour les résoudre, soit les méthodes exactes,\nles méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées\ndynamiques où certaines données sur le problème ne sont pas connues à l'avance.\n\nDans le second chapitre, nous décrivons un algorithme\nexact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est\nde maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec\ngains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court\nchemin élémentaire avec contraintes de ressources.\n\nPour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise.\nLe troisième chapitre propose donc\nune méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux\nhiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes).\n\nDans le quatrième chapitre, qui traite du cas dynamique,\nune stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des\nrequêtes à venir. L'approche repose sur la génération de scénarios pour\ndifférentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir\nune nouvelle\nrequête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête.\n\nEnfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues\nde recherche future.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.