Speeding Up Sequential Simulated Annealing by Parallelization

Author

Czech, Zbigniew J.

Author_Institution

Silesian Univ. of Tech., Gliwice

fYear

2006

fDate

13-17 Sept. 2006

Firstpage

349

Lastpage

356

Abstract

A parallel algorithm of simulated annealing to solve the vehicle routing problem with time windows (VRPTW) is considered. The VRPTW is an NP-hard bicriterion optimization problem in which both the number of vehicles and the total distance traveled by vehicles are minimized. The objective is to establish to what extent the computation time required to solve the VRPTW can be decreased by a number of co-operating parallel processes with no loss of quality of solutions. The quality of a solution is meant as its proximity to the optimum (or best known) solution. Furthermore, some factors are proposed which allow to rank the VRPTW benchmarking tests according to their difficulties

Keywords

computational complexity; minimisation; operations research; parallel algorithms; simulated annealing; vehicles; NP-hard bicriterion optimization problem; parallel algorithm; parallel process; sequential simulated annealing; time windows; vehicle routing problem; Benchmark testing; Computational modeling; Concurrent computing; Logistics; Parallel algorithms; Procurement; Raw materials; Routing; Simulated annealing; Vehicles; Parallel simulated annealing; bicriterion; optimization; vehicle routing problem with time windows;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Computing in Electrical Engineering, 2006. PAR ELEC 2006. International Symposium on

Conference_Location

Bialystok

Print_ISBN

0-7695-2554-7

Type

conf

DOI

10.1109/PARELEC.2006.74

Filename

1698686