Cette thèse porte sur les problèmes de tournées de véhicules avec
fenêtres de temps où un gain est associé à chaque client et où l'objectif est
de maximiser la somme des gains recueillis moins les coûts de transport.
De plus, un même véhicule peut effectuer plusieurs tournées durant
l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple,
dans 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
complètes de travail. Nous croyons que ce type de
problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries
électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile.
Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la
littérature consacrée aux
problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une
réutilisation des véhicules. Nous présentons les
méthodologies générales adoptées pour les résoudre, soit les méthodes exactes,
les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées
dynamiques où certaines données sur le problème ne sont pas connues à l'avance.
Dans le second chapitre, nous décrivons un algorithme
exact 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
de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec
gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court
chemin élémentaire avec contraintes de ressources.
Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise.
Le troisième chapitre propose donc
une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux
hié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).
Dans le quatrième chapitre, qui traite du cas dynamique,
une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des
requêtes à venir. L'approche repose sur la génération de scénarios pour
différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir
une nouvelle
requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête.
Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues
de recherche future.
This thesis studies vehicle routing problems with time windows, where a gain is associated
with each customer and where the objective is to maximize the total gain collected minus
the routing costs. Furthermore.
the same vehicle might be assigned to different routes during the planning horizon.
This problem has received little attention in the literature in
spite of its importance in practice. For example, in the
home delivery of perishable goods (like food), routes
of short duration must be combined to form complete workdays.
We believe that this type of problem will become increasingly important
in the future with the advent of electronic services, like e-groceries, where
customers can order goods through the Internet and get these goods
delivered at home.
In the first chapter of this thesis, we present a review of vehicle routing problems
with gains, as well as vehicle routing problems with
multiple use of vehicles. We discuss the general classes of
problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics.
We also introduce dynamic vehicle routing problems, where new information is revealed
as the routes are executed.
In the second chapter, we describe an exact algorithm for a vehicle routing problem with
time windows and multiple use of vehicles, where the first objective is to maximize the number of
served customers. To this end, the problem is modeled as a vehicle routing problem with gains.
The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm
with resource constraints.
To solve realistic instances in reasonable computation times, a heuristic approach is required.
The third chapter proposes an adaptative large neighborhood search where the various hierarchical
levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and
customers within routes).
The fourth chapter deals with the dynamic case. In this chapter, a strategy for
accepting or rejecting new customer requests is proposed. This strategy is based on the
generation of multiple scenarios for different realizations of the requests in the future.
An opportunity cost for serving a new request is then computed, based on an evaluation of the
scenarios with and without the new request.
Finally, the last chapter summarizes the contributions of this thesis and proposes future research
avenues.
