Title: Low cost parallel solutions for the VRPTW optimisation problem

Authors: Olatz Arbelaitz, Clemente Rodriguez

Addresses: Department of Computer Architecture and Technology, University of the Basque Country, M. Lardizabal, 1, 20018 Donostia, Spain. ' Department of Computer Architecture and Technology, University of the Basque Country, M. Lardizabal, 1, 20018 Donostia, Spain

Abstract: In this paper, a two phase system (global optimisation and local optimisation) to solve VRPTW problems is described; both phases are based on Simulated Annealing and parallelised. For the first phase, different parallelisation strategies are presented and evaluated. Two algorithms, a synchronous one and an asynchronous one, stand out due to their good average behaviour. The second phase permits very fast improvement of the solutions, adding efficiency to the system. This system has been able to reach the optimal solution published for the Solomon|s benchmark in 85% of the problems, and more importantly, the averages of any set of random executions are less than 5% inferior to the best published.

Keywords: vehicle routing; time window; optimisation; simulated annealing; low cost parallelism; synchronous communication; asynchronous communication; parallel computing.

DOI: 10.1504/IJCSE.2005.009701

International Journal of Computational Science and Engineering, 2005 Vol.1 No.2/3/4, pp.175 - 182

Published online: 05 May 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article