Speeding up sequential simulated annealing by parallelization

Zbigniew J. Czech

doi:10.1109/PARELEC.2006.74

Speeding up sequential simulated annealing by parallelization

Zbigniew J. Czech

Department of Algorithmics and Software (RAU/RAU5)

University of Silesia in Katowice

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

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 VRPTWcan 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.

Original language	English
Title of host publication	PARELEC 2006 - Proceedings
Subtitle of host publication	International Symposium on Parallel Computing in Electrical Engineering
Pages	349-354
Number of pages	6
DOIs	https://doi.org/10.1109/PARELEC.2006.74
Publication status	Published - 2006
Event	International Symposium on Parallel Computing in Electrical Engineering, PARELEC 2006 - Bialystok, Poland Duration: 13 Sept 2006 → 17 Sept 2006

Publication series

Name	PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering

Conference

Conference	International Symposium on Parallel Computing in Electrical Engineering, PARELEC 2006
Country/Territory	Poland
City	Bialystok
Period	13/09/06 → 17/09/06

Keywords

Bicriterion optimization
Parallel simulated annealing
Vehicle routing problem with time windows

ASJC Scopus subject areas

Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/PARELEC.2006.74

Cite this

@inproceedings{5e33c92dfa7e484c8a96478a38f62fcb,

title = "Speeding up sequential simulated annealing by parallelization",

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 VRPTWcan 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 = "Bicriterion optimization, Parallel simulated annealing, Vehicle routing problem with time windows",

author = "Czech, \{Zbigniew J.\}",

year = "2006",

doi = "10.1109/PARELEC.2006.74",

language = "English",

isbn = "0769525547",

series = "PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering",

pages = "349--354",

booktitle = "PARELEC 2006 - Proceedings",

note = "International Symposium on Parallel Computing in Electrical Engineering, PARELEC 2006 ; Conference date: 13-09-2006 Through 17-09-2006",

}

Czech, ZJ 2006, Speeding up sequential simulated annealing by parallelization. in PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering., 1698686, PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering, pp. 349-354, International Symposium on Parallel Computing in Electrical Engineering, PARELEC 2006, Bialystok, Poland, 13/09/06. https://doi.org/10.1109/PARELEC.2006.74

Speeding up sequential simulated annealing by parallelization. / Czech, Zbigniew J.
PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering. 2006. p. 349-354 1698686 (PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Speeding up sequential simulated annealing by parallelization

AU - Czech, Zbigniew J.

PY - 2006

Y1 - 2006

N2 - 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 VRPTWcan 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.

AB - 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 VRPTWcan 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.

KW - Bicriterion optimization

KW - Parallel simulated annealing

KW - Vehicle routing problem with time windows

UR - https://www.scopus.com/pages/publications/45749110882

U2 - 10.1109/PARELEC.2006.74

DO - 10.1109/PARELEC.2006.74

M3 - Conference contribution

AN - SCOPUS:45749110882

SN - 0769525547

SN - 9780769525549

T3 - PARELEC 2006 - Proceedings: International Symposium on Parallel Computing in Electrical Engineering

SP - 349

EP - 354

BT - PARELEC 2006 - Proceedings

T2 - International Symposium on Parallel Computing in Electrical Engineering, PARELEC 2006

Y2 - 13 September 2006 through 17 September 2006

ER -

Speeding up sequential simulated annealing by parallelization

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this