A parallel heuristic algorithm to solve the vehicle routing problem with time windows

Jakub Nalepa, Zbigniew J Czech

Abstract


The following article presents a parallel heuristic algorithm to solve the vehicle routing problem with time windows (VRPTW). The fleet size is minimized in the first phase and the traveled distance in the second one. The objective is to compare the accuracy of solutions obtained by the sequential and the parallel heuristics in the first phase. The influence of the population diversification and child generation on the accuracy is analyzed together with the speedups for the memetic algorithm in the second phase. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger’s benchmarking tests.

Keywords


vehicle routing problem with time windows; heuristics; memetic algorithm; approximation algorithm

Full Text:

PDF

References


Blocho M., Czech Z. J.: An improved route minimization algorithm for the vehicle routing problem with time windows. ZN Pol. SI. Studia Informatica Vol. 30, No. 1(39), Gliwice 2010, p. 5-19.

Czech Z. J., Mikanik W., Skinderowicz R.: Implementing a parallel simulated annealing algorithm. Proceedings of the 8th international conference on parallel processing and applied mathematics, 2010, Vol. 6067, p. 146-155.

Nagata Y., Braysy O.: A powerful route minimization heuristic for the vehicle routing problem with time windows. Operation Research Letters, 2009, Vol. 37, p. 333-338.

Nagata Y., Braysy O., Dullaert W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers and Operations Research, 2010, Vol. 37, p. 724-737.

Moscato P., Cotta C: A Gentle Introduction to Memetic Algorithms in F. Glover (Ed.), Handbook of Metaheuristics, Kluwer 2003, p. 105-144.

Problems and benchmarks: The world's best solutions for Gehring and Homberger's benchmark: http://www.sintef.no/Projectweb/TOP/ProblemsA'RPTW/

CI TASK - Galera: http://www.task.gda.pl/kdm/sprzet/Galera




DOI: http://dx.doi.org/10.21936/si2012_v33.n1.101