Program > By author > Expositó Christopher

Thursday 27
Logistics, localisation, transport and air control
Marc Sevaux
› 14:00 - 14:20 (20min)
› Bât. A - TD 37
Tournées de véhicules avec contraintes de clustering
Marc Sevaux  1@  , Christopher Expositó  1, 2  , André Rossi  1  
1 : Université de Bretagne Sud - Lab-STICC  (UBS/Lab-STICC)  -  Website
Université de Bretagne Sud [UBS], CNRS : UMR6285
BP 92116 - 56321 Lorient cedex -  France
2 : Universidad de La Laguna, Departamento de Estadística, Investigación Operativa y Computación
Tenerife -  Espagne

 

De nombreuses applications de la logistique imposent que les clients à livrer soient regroupés en sous-ensembles (clusters) ce qui facilite la livraison ou tout travail amont ou aval de traitement des clients. On est alors face à un problème de « Clustered CVRP ». Le problème est celui du CVRP avec la contrainte supplémentaire que chaque cluster doit être visité intégralement par un même véhicule (ce véhicule peut visiter plusieurs clusters). Notre approche divise le problème en deux parties (stratégique et opérationnelle). Dans l'étape stratégique, on décide de l'ordre de visite des clusters et des affectations de ces clusters aux véhicules. Cette étape est réalisée à partir d'un algorithme de la littérature (Record-To-Record Travel Algorithm). Dans la partie opérationnelle, on indique dans quel ordre les clients seront visités à l'intérieur de chaque cluster. Ce sous-problème est le Shortest Hamiltonian Path Problem (NP-Difficile) qui est abordé à l'aide de plusieurs approches (MILP, Algorithmes de Christophides et de Lin-Kernighan). Les deux étapes sont itérées au sein d'une approche de type multi-start avec des phases d'intensification et de shaking. Les tests numériques montrent la validité de cette approche.


Online user: 1