Title :
Speeding Up Sequential Simulated Annealing by Parallelization
Author :
Czech, Zbigniew J.
Author_Institution :
Silesian Univ. of Tech., Gliwice
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;
Conference_Titel :
Parallel Computing in Electrical Engineering, 2006. PAR ELEC 2006. International Symposium on
Conference_Location :
Bialystok
Print_ISBN :
0-7695-2554-7
DOI :
10.1109/PARELEC.2006.74
