Article ID: | iaor2009330 |
Country: | Netherlands |
Volume: | 15 |
Issue: | 2 |
Start Page Number: | 179 |
End Page Number: | 190 |
Publication Date: | Feb 2008 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Bampis Evripidis, Angel Eric, Pascual Fanny |
Keywords: | heuristics: local search |
We introduce an exponential neighborhood for the Vehicle Routing Problem 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 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