Hybrid search with neighborhood reduction for the multiple traveling salesman problem

Pengfei HE; Jin-Kao HAO

doi:10.1016/j.cor.2022.105726

Hybrid search with neighborhood reduction for the multiple traveling salesman problem

Pengfei HE
, Jin-Kao HAO^*

^*Corresponding author for this work

Research output: Journal Publications › Journal Article (refereed) › peer-review

32 Citations (Scopus)

Abstract

We present an effective hybrid algorithm with neighborhood reduction for solving the multiple traveling salesman problem (mTSP). This problem aims to optimize one of the two objectives: to minimize the total traveling distance (the minsum mTSP) or to minimize the longest tour (the minmax mTSP). The proposed algorithm hybridizes inter-tour optimization with an efficient neighborhood search based on tabu search and intra-tour optimization using the traveling salesman heuristic EAX. A dedicated neighborhood reduction strategy is introduced to avoid the examination of non-promising candidate solutions and thus speed up the neighborhood search. Results of extensive computational experiments are shown on 41 popular instances from several sources and 36 new large instances. Comparisons with five state-of-the-art methods in the literature demonstrate a high competitiveness of the proposed algorithm. Additional experiments on applying a classical TSP heuristic to the minsum mTSP instances show excellent results.

Original language	English
Article number	105726
Number of pages	19
Journal	Computers and Operations Research
Volume	142
Early online date	10 Feb 2022
DOIs	https://doi.org/10.1016/j.cor.2022.105726
Publication status	Published - Jun 2022
Externally published	Yes

Bibliographical note

Acknowledgments:
We are grateful to the reviewers for their useful comments and suggestions which helped us to significantly improve the paper. We would like to thank authors of Karabulut et al., 2021, Pandiri and Singh, 2015, Wang et al., 2017, Yuan et al., 2013: Prof. K. Karabulut and Prof. M. F. Tasgetiren for sharing their executable code; Prof. A. Singh, Dr. Y. Wang, and Dr. S. Yuan for providing their test problems and answering our questions.

Publisher Copyright:
© 2022 Elsevier Ltd

Funding

Support from the China Scholarship Council (CSC, grant No. 201906850087) for the first author is acknowledged.

Keywords

Hybrid heuristic
Multiple traveling salesman
Neighborhood reduction
Traveling salesman

Access to Document

10.1016/j.cor.2022.105726

Cite this

@article{ff436ecfe1c64d429c431e4946df8364,

title = "Hybrid search with neighborhood reduction for the multiple traveling salesman problem",

abstract = "We present an effective hybrid algorithm with neighborhood reduction for solving the multiple traveling salesman problem (mTSP). This problem aims to optimize one of the two objectives: to minimize the total traveling distance (the minsum mTSP) or to minimize the longest tour (the minmax mTSP). The proposed algorithm hybridizes inter-tour optimization with an efficient neighborhood search based on tabu search and intra-tour optimization using the traveling salesman heuristic EAX. A dedicated neighborhood reduction strategy is introduced to avoid the examination of non-promising candidate solutions and thus speed up the neighborhood search. Results of extensive computational experiments are shown on 41 popular instances from several sources and 36 new large instances. Comparisons with five state-of-the-art methods in the literature demonstrate a high competitiveness of the proposed algorithm. Additional experiments on applying a classical TSP heuristic to the minsum mTSP instances show excellent results.",

keywords = "Hybrid heuristic, Multiple traveling salesman, Neighborhood reduction, Traveling salesman",

author = "Pengfei HE and Jin-Kao HAO",

note = "Acknowledgments: We are grateful to the reviewers for their useful comments and suggestions which helped us to significantly improve the paper. We would like to thank authors of Karabulut et al., 2021, Pandiri and Singh, 2015, Wang et al., 2017, Yuan et al., 2013: Prof. K. Karabulut and Prof. M. F. Tasgetiren for sharing their executable code; Prof. A. Singh, Dr. Y. Wang, and Dr. S. Yuan for providing their test problems and answering our questions. Publisher Copyright: {\textcopyright} 2022 Elsevier Ltd",

year = "2022",

month = jun,

doi = "10.1016/j.cor.2022.105726",

language = "English",

volume = "142",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - Hybrid search with neighborhood reduction for the multiple traveling salesman problem

AU - HE, Pengfei

AU - HAO, Jin-Kao

N1 - Acknowledgments: We are grateful to the reviewers for their useful comments and suggestions which helped us to significantly improve the paper. We would like to thank authors of Karabulut et al., 2021, Pandiri and Singh, 2015, Wang et al., 2017, Yuan et al., 2013: Prof. K. Karabulut and Prof. M. F. Tasgetiren for sharing their executable code; Prof. A. Singh, Dr. Y. Wang, and Dr. S. Yuan for providing their test problems and answering our questions. Publisher Copyright: © 2022 Elsevier Ltd

PY - 2022/6

Y1 - 2022/6

N2 - We present an effective hybrid algorithm with neighborhood reduction for solving the multiple traveling salesman problem (mTSP). This problem aims to optimize one of the two objectives: to minimize the total traveling distance (the minsum mTSP) or to minimize the longest tour (the minmax mTSP). The proposed algorithm hybridizes inter-tour optimization with an efficient neighborhood search based on tabu search and intra-tour optimization using the traveling salesman heuristic EAX. A dedicated neighborhood reduction strategy is introduced to avoid the examination of non-promising candidate solutions and thus speed up the neighborhood search. Results of extensive computational experiments are shown on 41 popular instances from several sources and 36 new large instances. Comparisons with five state-of-the-art methods in the literature demonstrate a high competitiveness of the proposed algorithm. Additional experiments on applying a classical TSP heuristic to the minsum mTSP instances show excellent results.

AB - We present an effective hybrid algorithm with neighborhood reduction for solving the multiple traveling salesman problem (mTSP). This problem aims to optimize one of the two objectives: to minimize the total traveling distance (the minsum mTSP) or to minimize the longest tour (the minmax mTSP). The proposed algorithm hybridizes inter-tour optimization with an efficient neighborhood search based on tabu search and intra-tour optimization using the traveling salesman heuristic EAX. A dedicated neighborhood reduction strategy is introduced to avoid the examination of non-promising candidate solutions and thus speed up the neighborhood search. Results of extensive computational experiments are shown on 41 popular instances from several sources and 36 new large instances. Comparisons with five state-of-the-art methods in the literature demonstrate a high competitiveness of the proposed algorithm. Additional experiments on applying a classical TSP heuristic to the minsum mTSP instances show excellent results.

KW - Hybrid heuristic

KW - Multiple traveling salesman

KW - Neighborhood reduction

KW - Traveling salesman

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

U2 - 10.1016/j.cor.2022.105726

DO - 10.1016/j.cor.2022.105726

M3 - Journal Article (refereed)

AN - SCOPUS:85124482694

SN - 0305-0548

VL - 142

JO - Computers and Operations Research

JF - Computers and Operations Research

M1 - 105726

ER -

Hybrid search with neighborhood reduction for the multiple traveling salesman problem

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this