A parallel hybrid genetic algorithm for the vehicle routing problem with time windows

A parallel hybrid genetic algorithm for the vehicle routing problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor2005540
Country: United Kingdom
Volume: 31
Issue: 12
Start Page Number: 2037
End Page Number: 2053
Publication Date: Oct 2004
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

A parallel version of a new hybrid genetic algorithm for the vehicle routing problem with time windows is presented. The route-directed hybrid genetic approach is based upon the simultaneous evolution of two populations of solutions focusing on separate objectives subject to temporal constraint relaxation. While the first population evolves individuals to minimize total traveled distance the second aims at minimizing temporal constraint violation to generate a feasible solution. Genetic operators have been designed to capture key concepts from successful routing techniques to further enhance search diversification and intensification. A master-slave message-passing paradigm characterizes the parallel procedure. The master component controls the execution of the algorithm, coordinates genetic operations and handles parent selection while the slave elements concurrently execute reproduction and mutation operators. Providing additional speed-up, the parallel algorithm further expands on its sequential counterpart, matching or even improving solution quality. Computational results show the proposed technique to be very competitive with the best-known heuristic routing procedures providing some new best-known solutions.

Reviews

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