Modeling method and optimization by the variable neighborhood search for the pickup and delivery problem with transshipment
Méthodes de modélisation et d’optimisation par recherche à voisinages variables pour le problème de collecte et de livraison avec transbordement
Résumé
The thesis is conducted under the ANR project PRODIGE and
it is focused on seeking strategies allowing the optimization of transport
in general and road freight transport in particular. The transportation problem
support for this study is the pickup and delivery problem with transshipment.
This problem generalizes several classical transportation problems.
Transshipment is used as optimization and flexibility leverage. To
study and solve this problem, analyzes are performed along three axes :
the first objective concerns the development of an analytical model, more
accurately a mathematical model with mixed variables. This model allows
providing optimal solution to the decision maker, but has the disadvantage
of requiring a time resolution that grows exponentially with the size
of the problem. This limitation is overcome by the second line of the study
that solves the transportation problem studied by an approximate optimization
method while ensuring satisfactory solutions. The method used
is a mataheuristic broadly followed the variables neighborhoods research
principles. In the third objective, the overall results obtained in the thesis
are tested in real transport situation via the PRODIGE project.
La présente thèse se déroule dans le cadre du projet ANR PRODIGE
et est axée sur la recherche de stratégies permettant l’optimisation
du transport en général et du transport routier de marchandises en particulier.
Le problème de transport support de cette étude est le problème
de collecte et livraison avec transbordement. Ce problème généralise plusieurs
problèmes de transports classiques. Le transbordement y est utilisé
comme levier de flexibilité et d’optimisation. Pour analyser et résoudre ce
problème, les analyses sont effectuées suivant trois axes : le premier axe
concerne l’élaboration d’un modèle analytique plus précisément d’un modèle
mathématique en variables mixtes. Ce modèle permet de fournir des
solutions optimales au décisionnaire du transport mais présente l’inconvénient
de nécessiter un temps de résolution qui croit exponentiellement
avec la taille du problème. Cette limitation est levée par le deuxième axe
d’étude qui permet de résoudre le problème de transport étudié par une
méthode d’optimisation approchée tout en garantissant des solutions satisfaisantes.
La méthode utilisée est une métaheuristique inspirée de la
recherche à voisinages variables (VNS). Dans le troisième axe, l’ensemble
des résultats obtenus dans la thèse sont testés en situation de transports
réels via le projet PRODIGE.
Loading...