Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands |
| |
Authors: | Leonora Bianchi Mauro Birattari Marco Chiarandini Max Manfrin Monaldo Mastrolilli Luis Paquete Olivia Rossi-Doria Tommaso Schiavinotto |
| |
Institution: | (1) IDSIA, Lugano, Switzerland;(2) IRIDIA, Université Libre de Bruxelles, Brussels, Belgium;(3) Intellectics Group, TU Darmstadt, Germany;(4) School of Computing, Napier University, Scottland, UK |
| |
Abstract: | This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The
problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances
are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended
exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly
helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related
problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized
solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that,
for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions
than state-of-the-art algorithms. |
| |
Keywords: | 68T20 90C27 90C59 90B06 90C15 |
本文献已被 SpringerLink 等数据库收录! |
|