Spelling suggestions: "subject:"fenêtre""
31 |
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éhiculesAzi, Nabila 08 1900 (has links)
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.
|
32 |
Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de tempsAmghar, Khalid 04 1900 (has links)
Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. / We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.
|
33 |
Approches de modélisation et d’optimisation pour la conception d’un système interactif d’aide au déplacement dans un hypermarché / Modelling and optimization approaches for the conception of an intelligent navigation system to assist persons inside hypermarketsHadj Khalifa, Ismahène 16 June 2011 (has links)
Les travaux présentés dans cette thèse ont porté sur l’étude de faisabilité technique et logicielle du système i-GUIDE, système interactif de guidage des personnes dans les hypermarchés. Nous avons détaillé l’analyse fonctionnelle du besoin du système. Ensuite, nous avons étudié l’impact de l’intégration du système dans le magasin à travers le diagramme BPMN. Nous avons opté pour l’approche UML pour décrire les principales fonctionnalités de notre système ainsi que les objets nécessaires pour son bon fonctionnement. Une architecture du système i-GUIDE, basée sur la technologie RFID avec une application sous Android, a été présentée. Par ailleurs, nous avons proposé des approches d’optimisation de parcours dans un hypermarché basées sur la méthode de recherche tabou pour deux problèmes. Pour le premier problème, nous avons choisi le critère de la plus courte distance pour la détermination du chemin et pour le deuxième nous avons ajouté une contrainte de temps pour des articles en promotion. Avant de chercher le chemin le plus court à parcourir pour trouver les articles existants dans la liste de courses, nous avons proposé une méthode pour ladétermination des distances entre les articles de l’hypermarché pris deux à deux / The present work focuses on the technical feasibility study of i-GUIDE system which is a real time indoor navigation system dedicated to assist persons inside hypermarkets. We detailed its functional analysis. Then, we studied the impact of integrating the system inside hypermarkets. We opted for an UML design to describe its main functionalities and objects required. We presented architecture of i-GUIDE system based on RFID technology with an Android application. Furthermore, we introduced optimization approaches based on tabu search to compute the route visiting items existing in a shopping list for two problems. The first one treats the shortest path to pick up items and the second one adds a time constraint for promotional items. Before computing the shortest path, we introduced a method to determine distance between each two items existing in the hypermarket
|
34 |
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éhiculesAzi, Nabila 08 1900 (has links)
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.
|
35 |
Metaheuristics for vehicle routing problems : new methods and performance analysisGuillen Reyes, Fernando Obed 02 1900 (has links)
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.
|
Page generated in 0.0456 seconds