An exponential (matching based) neighborhood for the vehicle routing problem |
| |
Authors: | Eric Angel Evripidis Bampis Fanny Pascual |
| |
Affiliation: | (1) IBISC, Université d’évry Val d’Essonne, CNRS FRE 2873, 523 Place des Terrasses, 91000 Evry, France |
| |
Abstract: | We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case with non-unit customers’ demands the exploration of the neighborhood becomes an -hard problem. |
| |
Keywords: | Local search Exponential neighborhood Vehicle routing problem Matching |
本文献已被 SpringerLink 等数据库收录! |