Identifiant pérenne de la notice : 248167189
Notice de type
Notice de regroupement
Note publique d'information : Dans cette thèse, nous présentons trois extensions de problèmes combinatoires classiques.
Le problème de tournées de véhicules avec conflits généralise le problème de tournées
de véhicule, en considérant l'incompatibilité qui peut exister entre certaines demandes
qui doivent par conséquent être affectées à des véhicules différents. Le problème
de placement bidimensionnel est généralisé en introduisant la notion de conflits partiels.
Les objets partiellement conflictuels et affectés à un même support de rangement (grande
plaque rectangulaire) doivent être séparés par une distance de sécurité. Le troisième
problème étudié est celui des tournées de véhicules avec chargement bidimensionnel.
Deux nouvelles variantes de ce problème, prenant en compte des conflits partiels toutes
les deux, ont été considérées : une variante mono-objectif et une autre bi-objectif,
qui en plus de l'objectif classique de minimisation du coût total des tournées, s'intéresse
à l'équilibrage des chargements en termes de surface occupée. Des modèles mathématiques
ont été proposés pour ces problèmes et plusieurs méthodes heuristiques et métaheuristiques
ont été développées pour les résoudre. Un algorithme de branchement et de coupes a
également été utilisé pour obtenir des bornes pour le problème de tournées de véhicules
avec conflits
Note publique d'information : In this thesis, we present three extensions of classical combinatorial problems. The
first problem is the Vehicle Routing Problem with conflicts which extends the well-known
vehicle routing problem by adding incompatibility constraints between customers’ demands.
The conflicting demands have to be therefore as-signed to different vehicles. The
two-dimensional Bin Packing Problem is also generalized by introducing partial conflicts.
A safe distance has to be kept between partially conflicting items assigned to the
same bin. The third problem studied is an extension of the two Dimensional Loading
Vehicle Routing Problem that considers partial conflicts. Two variants of this new
problem are introduced: the first is mono-objective and the second one is bi-objective.
In the bi-objective variant, the criterion of load balancing in terms of occupied
area in the vehicle is considered in addition to total cost minimization of the routes.
Several mathematical models have been pro-posed for these problems. Heuristic and
Meta-heuristic methods have also been developed to solve them. A branch and cut algorithm
has been used to obtain lower bounds for the vehicle routing problem with conflicts
paprika.idref.fr
data.idref.fr
Documentation
