Memetic search for the minmax multiple traveling salesman problem with single and multiple depots

Pengfei HE; Jin-Kao HAO

doi:10.1016/j.ejor.2022.11.010

Memetic search for the minmax multiple traveling salesman problem with single and multiple depots

Pengfei HE
, Jin-Kao HAO^*

^*Corresponding author for this work

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

41 Citations (Scopus)

Abstract

The minmax multiple traveling salesman problem with single depot (the minmax mTSP) or multiple depots (the minmax multidepot mTSP) aims to minimize the longest tour among a set of tours. These two minmax problems are useful for a variety of real-life applications and typically studied separately in the literature. We propose a unified memetic approach to solving both cases of the minmax mTSP and the minmax multidepot mTSP. The proposed algorithm features a generalized edge assembly crossover to generate offspring solutions, an efficient variable neighborhood descent to ensure local optimization as well as an aggressive post-optimization for additional solution improvement. Extensive experimental results on 77 minmax mTSP benchmark instances and 43 minmax multidepot mTSP instances commonly used in the literature indicate a high performance of the algorithm compared to the leading algorithms. Additional experimental investigations are conducted to shed light on the rationality of the key algorithmic ingredients.

Original language	English
Pages (from-to)	1055-1070
Number of pages	16
Journal	European Journal of Operational Research
Volume	307
Issue number	3
Early online date	15 Nov 2022
DOIs	https://doi.org/10.1016/j.ejor.2022.11.010
Publication status	Published - 16 Jun 2023
Externally published	Yes

Bibliographical note

Acknowledgments:
We are grateful to the reviewers for their insightful and constructive comments, which helped us to improvement the paper. We also would like to thank authors of [20,25,26,23]: Dr. Jiongzhi Zheng for sharing their source code; Dr. Korhan Karabulut and Prof. M. Fatih Tasgetiren for sharing their executable code; Prof. Xingyin Wang and Dr. Yongzhen Wang for providing their test problems and answering our questions.

Publisher Copyright:
© 2022 Elsevier B.V.

Funding

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

Keywords

Combinatorial optimization
Heuristics
Minmax
Multidepot
Travelling salesman

Access to Document

10.1016/j.ejor.2022.11.010

Cite this

@article{993731bf190f4e869e4a3eb7a9b42de0,

title = "Memetic search for the minmax multiple traveling salesman problem with single and multiple depots",

abstract = "The minmax multiple traveling salesman problem with single depot (the minmax mTSP) or multiple depots (the minmax multidepot mTSP) aims to minimize the longest tour among a set of tours. These two minmax problems are useful for a variety of real-life applications and typically studied separately in the literature. We propose a unified memetic approach to solving both cases of the minmax mTSP and the minmax multidepot mTSP. The proposed algorithm features a generalized edge assembly crossover to generate offspring solutions, an efficient variable neighborhood descent to ensure local optimization as well as an aggressive post-optimization for additional solution improvement. Extensive experimental results on 77 minmax mTSP benchmark instances and 43 minmax multidepot mTSP instances commonly used in the literature indicate a high performance of the algorithm compared to the leading algorithms. Additional experimental investigations are conducted to shed light on the rationality of the key algorithmic ingredients.",

keywords = "Combinatorial optimization, Heuristics, Minmax, Multidepot, Travelling salesman",

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

note = "Acknowledgments: We are grateful to the reviewers for their insightful and constructive comments, which helped us to improvement the paper. We also would like to thank authors of [20,25,26,23]: Dr. Jiongzhi Zheng for sharing their source code; Dr. Korhan Karabulut and Prof. M. Fatih Tasgetiren for sharing their executable code; Prof. Xingyin Wang and Dr. Yongzhen Wang for providing their test problems and answering our questions. Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2023",

month = jun,

day = "16",

doi = "10.1016/j.ejor.2022.11.010",

language = "English",

volume = "307",

pages = "1055--1070",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Memetic search for the minmax multiple traveling salesman problem with single and multiple depots

AU - HE, Pengfei

AU - HAO, Jin-Kao

N1 - Acknowledgments: We are grateful to the reviewers for their insightful and constructive comments, which helped us to improvement the paper. We also would like to thank authors of [20,25,26,23]: Dr. Jiongzhi Zheng for sharing their source code; Dr. Korhan Karabulut and Prof. M. Fatih Tasgetiren for sharing their executable code; Prof. Xingyin Wang and Dr. Yongzhen Wang for providing their test problems and answering our questions. Publisher Copyright: © 2022 Elsevier B.V.

PY - 2023/6/16

Y1 - 2023/6/16

N2 - The minmax multiple traveling salesman problem with single depot (the minmax mTSP) or multiple depots (the minmax multidepot mTSP) aims to minimize the longest tour among a set of tours. These two minmax problems are useful for a variety of real-life applications and typically studied separately in the literature. We propose a unified memetic approach to solving both cases of the minmax mTSP and the minmax multidepot mTSP. The proposed algorithm features a generalized edge assembly crossover to generate offspring solutions, an efficient variable neighborhood descent to ensure local optimization as well as an aggressive post-optimization for additional solution improvement. Extensive experimental results on 77 minmax mTSP benchmark instances and 43 minmax multidepot mTSP instances commonly used in the literature indicate a high performance of the algorithm compared to the leading algorithms. Additional experimental investigations are conducted to shed light on the rationality of the key algorithmic ingredients.

AB - The minmax multiple traveling salesman problem with single depot (the minmax mTSP) or multiple depots (the minmax multidepot mTSP) aims to minimize the longest tour among a set of tours. These two minmax problems are useful for a variety of real-life applications and typically studied separately in the literature. We propose a unified memetic approach to solving both cases of the minmax mTSP and the minmax multidepot mTSP. The proposed algorithm features a generalized edge assembly crossover to generate offspring solutions, an efficient variable neighborhood descent to ensure local optimization as well as an aggressive post-optimization for additional solution improvement. Extensive experimental results on 77 minmax mTSP benchmark instances and 43 minmax multidepot mTSP instances commonly used in the literature indicate a high performance of the algorithm compared to the leading algorithms. Additional experimental investigations are conducted to shed light on the rationality of the key algorithmic ingredients.

KW - Combinatorial optimization

KW - Heuristics

KW - Minmax

KW - Multidepot

KW - Travelling salesman

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

U2 - 10.1016/j.ejor.2022.11.010

DO - 10.1016/j.ejor.2022.11.010

M3 - Journal Article (refereed)

AN - SCOPUS:85142738274

SN - 0377-2217

VL - 307

SP - 1055

EP - 1070

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

Memetic search for the minmax multiple traveling salesman problem with single and multiple depots

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this