TY - JOUR
T1 - Solving large batches of traveling salesman problems with parallel and distributed computing
AU - Ozden, S. G.
AU - Smith, A. E.
AU - Gue, K. R.
N1 - Funding Information:
This research was supported in part by the National Science Foundation under Grant CMMI-1200567. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. The authors would like to thank Michael Robbins and Ataman Billor for data collection and testing the code.
Publisher Copyright:
© 2017 Elsevier Ltd
PY - 2017/9/1
Y1 - 2017/9/1
N2 - In this paper, we describe and compare serial, parallel, and distributed solver implementations for large batches of Traveling Salesman Problems using the Lin–Kernighan Heuristic (LKH) and the Concorde exact TSP Solver. Parallel and distributed solver implementations are useful when many medium to large size TSP instances must be solved simultaneously. These implementations are found to be straightforward and highly efficient compared to serial implementations. Our results indicate that parallel computing using hyper-threading for solving 150- and 200-city TSPs can increase the overall utilization of computer resources up to 25% compared to single thread computing. The resulting speed-up/physical core ratios are as much as ten times better than a parallel and concurrent version of the LKH heuristic using SPC3 in the literature. For variable TSP sizes, a longest processing time first heuristic performs better than an equal distribution rule. We illustrate our approach with an application in the design of order picking warehouses.
AB - In this paper, we describe and compare serial, parallel, and distributed solver implementations for large batches of Traveling Salesman Problems using the Lin–Kernighan Heuristic (LKH) and the Concorde exact TSP Solver. Parallel and distributed solver implementations are useful when many medium to large size TSP instances must be solved simultaneously. These implementations are found to be straightforward and highly efficient compared to serial implementations. Our results indicate that parallel computing using hyper-threading for solving 150- and 200-city TSPs can increase the overall utilization of computer resources up to 25% compared to single thread computing. The resulting speed-up/physical core ratios are as much as ten times better than a parallel and concurrent version of the LKH heuristic using SPC3 in the literature. For variable TSP sizes, a longest processing time first heuristic performs better than an equal distribution rule. We illustrate our approach with an application in the design of order picking warehouses.
UR - http://www.scopus.com/inward/record.url?scp=85017448781&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85017448781&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2017.04.001
DO - 10.1016/j.cor.2017.04.001
M3 - Article
AN - SCOPUS:85017448781
SN - 0305-0548
VL - 85
SP - 87
EP - 96
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -