Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes
de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante
beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps
avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN
pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points
on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant
une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction
for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et
reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution
courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le
problème est défini sur un réseau routier où différents chemins alternatifs peuvent être
utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des
arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine.
S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux
types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de
passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite
au transfert de leur demande d’un grand à un petit véhicule à un point de transfert.
Comme un point de transfert n’a pas de capacité, une problématique de synchronisation
apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour
leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées
de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés
à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que
le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR
originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests
a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été
divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur
sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où
l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les
résultats numériques montrent que la métaheuristique proposée exploite les opportunités
d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui
peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits
véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points
de transfert.
Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et
font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un
étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises
sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le
CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances
tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les
meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux
d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique
simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions.
Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans
la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail,
le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode
d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap-
prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles
qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment
rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la
réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les
instances utilisées pour tester notre approche hybride sont les mêmes que celles du second
article. Nous avons observé que notre algorithme ne peut produire que des solutions lé-
gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem
(CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing
Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ).
In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris-
tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic
is based on the ruin and recreate principle and removes strings of consecutive customers
in the routes of the current solution and then reinserts the removed customers to create a
new solution. The problem is formulated in a full road network where different alternative
paths can be used to go from one customer to the next. Also, the travel time on each arc
of the road network is not fixed, but depends on the departure time from the origin node.
Motivated from city logistics applications, we also consider two types of vehicles, large
and small, with large vehicles being forbidden from the downtown area. Thus, downtown
customers can only be served through a transfer of their goods from large to small vehicles
at designated transfer points. Since transfer points have no capacity, synchronization issues
arise when a large vehicle must meet one or more small vehicles to transfer goods. As
opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that
are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex
than the CVRP, important modifications to the original SISR metaheuristic were required.
To evaluate the performance of our algorithm, we generated a set of test instances by
extending existing instances of the TDVRPTW-RN . The road networks are divided into
three regions: downtown, boundary and outside. The downtown and outside areas are
the realm of small and large vehicles, respectively, while the boundary area that contains
the transfer points can be visited by both small and large vehicles. The results show
that the proposed metaheuristic exploits optimization opportunities by moving as much as
possible neutral customers (which can be served by either small or large vehicles) from the
routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points.
The second and third papers examine more fundamental issues, using the classical
CVRP as a testbed. In the second paper, an experimental study is designed to examine the
impact of inaccurate data (distances) on the performance of different types of heuristics,
as well as one exact method, for the CVRP. For this purpose, different levels of distance
inaccuracies were introduced into well-known benchmark instances for the CVRP with 100
to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the
best, even in the presence of high inaccuracy levels, and that they are not as much affected
by inaccuracies when compared to a simple heuristic. Some experiments performed on
real-world instances led to the same conclusions.
The third paper focuses on the integration of learning into the state-of-the-art SISR for
the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced
by a reinforcement learning technique inspired from ant colony systems. The learning
component is aimed at identifying promising edges, namely those that are often found in
previously encountered high-quality solutions. The inclusion of these promising edges is
then favored during the reinsertion of removed customers. The benchmark instances of
the second paper were also used here to test the new hybrid algorithm. We observed that
the latter can produce only slightly better solutions than the original SISR, due to the
quasi-optimality of the original solutions.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/32947 |
| Date | 02 1900 |
| Creators | Guillen Reyes, Fernando Obed |
| Contributors | Potvin, Jean-Yves, Gendreau, Michel, Vidal, Thibaut |
| Source Sets | Université de Montréal |
| Language | English |
| Detected Language | French |
| Type | thesis, thèse |
| Format | application/pdf |
Page generated in 0.0026 seconds