Local search algorithms for the robust vehicle routing problem with time windows and budget uncertainty
Igor Malheiros  1, 2@  , Michael Poss  1@  , Vitor Nesello  2@  , Anand Subramanian  3@  
1 : Laboratoire dÍnformatique de Robotique et de Microélectronique de Montpellier
Université de Montpellier : UMR5506, Centre National de la Recherche Scientifique : UMR5506
2 : Atoptima
Atoptima
3 : UNIVERSIDADE FEDERAL DA PARAÍBA

Due to real-life logistics necessities, the vehicle routing problem with time windows (VRPTW) has received substantial attention. In its deterministic version, all the input data are static and previously known. Nevertheless, the travel time may be uncertain in practice. This work focuses on a robust optimization to handle the uncertainty in travel times. We approach the problem using the iterated local search metaheuristic combined with a new evaluation algorithm to enhance the local search phase. Specifically, we introduce a polynomial-time algorithm that allows penalization for infeasible solutions for the robust VRPTW leading the local search to explore the search space wider than other algorithms.


Personnes connectées : 2 Vie privée
Chargement...