Back to Search Start Over

A Path Relinking Approach with an Adaptive Mechanism to Control Parameters for the Vehicle Routing Problem with Time Windows

Authors :
Hideki Hashimoto
Mutsunori Yagiura
Source :
Evolutionary Computation in Combinatorial Optimization ISBN: 9783540786030, EvoCOP
Publication Year :
2008
Publisher :
Springer Berlin Heidelberg, 2008.

Abstract

We propose a path relinking approach for the vehicle routing problem with time windows. The path relinking is an evolutionary mechanism that generates new solutions by combining two or more reference solutions. In our algorithm, those solutions generated by path relinking operations are improved by a local search whose neighborhood consists of slight modifications of the representative neighborhoods called 2-opt*, cross exchange and Or-opt. To make the search more efficient, we propose a neighbor list that prunes the neighborhood search heuristically. Infeasible solutions are allowed to be visited during the search, while the amount of violation is penalized. As the performance of the algorithm crucially depends on penalty weights that specify how such penalty is emphasized, we propose an adaptive mechanism to control the penalty weights. The computational results on well-studied benchmark instances with up to 1000 customers revealed that our algorithm is highly efficient especially for large instances. Moreover, it updated 41 best known solutions among 356 instances.

Details

ISBN :
978-3-540-78603-0
ISBNs :
9783540786030
Database :
OpenAIRE
Journal :
Evolutionary Computation in Combinatorial Optimization ISBN: 9783540786030, EvoCOP
Accession number :
edsair.doi...........9fbdbd85718ca3de75b05bf4ad8378e1
Full Text :
https://doi.org/10.1007/978-3-540-78604-7_22