An exponential (matching based) neighborhood for the vehicle routing problem

An exponential (matching based) neighborhood for the vehicle routing problem

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics: local search
Abstract:

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 NP-hard problem.

Reviews

Required fields are marked *. Your email address will not be published.