A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem

Pandiri Venkatesh; Alok Singh; Rammohan Mallipeddi

doi:10.1109/CEC.2019.8790018

A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem

Pandiri Venkatesh
, Alok Singh
, Rammohan Mallipeddi

School of Electronics Engineering

University of Hyderabad

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

10 Scopus citations

Abstract

The maximum scatter traveling salesman problem (MSTSP) is a variant of the well-known traveling salesman problem (TSP) where the objective is to find a Hamiltonian cycle on a graph that maximizes the minimum length among its constituent edges. The MSTSP finds important application in manufacturing and medical imaging. In this study, we propose a multi-start iterated local search algorithm for the MSTSP. Two local search algorithms based on insertion and modified 2-opt moves have been developed as part of our approach. To investigate the performance of the proposed approach, benchmark instances from the standard TSPLIB are used. Computational results and their analysis show the effectiveness of the proposed approach.

Original language	English
Title of host publication	2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1390-1397
Number of pages	8
ISBN (Electronic)	9781728121536
DOIs	https://doi.org/10.1109/CEC.2019.8790018
State	Published - Jun 2019
Event	2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Wellington, New Zealand Duration: 10 Jun 2019 → 13 Jun 2019

Publication series

Name	2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings

Conference

Conference	2019 IEEE Congress on Evolutionary Computation, CEC 2019
Country/Territory	New Zealand
City	Wellington
Period	10/06/19 → 13/06/19

Access to Document

10.1109/CEC.2019.8790018

Cite this

Venkatesh, P., Singh, A., & Mallipeddi, R. (2019). A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem. In 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings (pp. 1390-1397). Article 8790018 (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CEC.2019.8790018

Venkatesh, Pandiri ; Singh, Alok ; Mallipeddi, Rammohan. / A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem. 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 1390-1397 (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings).

@inproceedings{c5bd11923f3649238dc3a247dc20ebf9,

title = "A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem",

abstract = "The maximum scatter traveling salesman problem (MSTSP) is a variant of the well-known traveling salesman problem (TSP) where the objective is to find a Hamiltonian cycle on a graph that maximizes the minimum length among its constituent edges. The MSTSP finds important application in manufacturing and medical imaging. In this study, we propose a multi-start iterated local search algorithm for the MSTSP. Two local search algorithms based on insertion and modified 2-opt moves have been developed as part of our approach. To investigate the performance of the proposed approach, benchmark instances from the standard TSPLIB are used. Computational results and their analysis show the effectiveness of the proposed approach.",

author = "Pandiri Venkatesh and Alok Singh and Rammohan Mallipeddi",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 IEEE Congress on Evolutionary Computation, CEC 2019 ; Conference date: 10-06-2019 Through 13-06-2019",

year = "2019",

month = jun,

doi = "10.1109/CEC.2019.8790018",

language = "English",

series = "2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1390--1397",

booktitle = "2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings",

address = "United States",

}

Venkatesh, P, Singh, A & Mallipeddi, R 2019, A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem. in 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings., 8790018, 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1390-1397, 2019 IEEE Congress on Evolutionary Computation, CEC 2019, Wellington, New Zealand, 10/06/19. https://doi.org/10.1109/CEC.2019.8790018

A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem. / Venkatesh, Pandiri; Singh, Alok; Mallipeddi, Rammohan.
2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 1390-1397 8790018 (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings).

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

TY - GEN

T1 - A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem

AU - Venkatesh, Pandiri

AU - Singh, Alok

AU - Mallipeddi, Rammohan

PY - 2019/6

Y1 - 2019/6

N2 - The maximum scatter traveling salesman problem (MSTSP) is a variant of the well-known traveling salesman problem (TSP) where the objective is to find a Hamiltonian cycle on a graph that maximizes the minimum length among its constituent edges. The MSTSP finds important application in manufacturing and medical imaging. In this study, we propose a multi-start iterated local search algorithm for the MSTSP. Two local search algorithms based on insertion and modified 2-opt moves have been developed as part of our approach. To investigate the performance of the proposed approach, benchmark instances from the standard TSPLIB are used. Computational results and their analysis show the effectiveness of the proposed approach.

AB - The maximum scatter traveling salesman problem (MSTSP) is a variant of the well-known traveling salesman problem (TSP) where the objective is to find a Hamiltonian cycle on a graph that maximizes the minimum length among its constituent edges. The MSTSP finds important application in manufacturing and medical imaging. In this study, we propose a multi-start iterated local search algorithm for the MSTSP. Two local search algorithms based on insertion and modified 2-opt moves have been developed as part of our approach. To investigate the performance of the proposed approach, benchmark instances from the standard TSPLIB are used. Computational results and their analysis show the effectiveness of the proposed approach.

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

U2 - 10.1109/CEC.2019.8790018

DO - 10.1109/CEC.2019.8790018

M3 - Conference contribution

AN - SCOPUS:85071290677

T3 - 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings

SP - 1390

EP - 1397

BT - 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 IEEE Congress on Evolutionary Computation, CEC 2019

Y2 - 10 June 2019 through 13 June 2019

ER -

Venkatesh P, Singh A, Mallipeddi R. A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem. In 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2019. p. 1390-1397. 8790018. (2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings). doi: 10.1109/CEC.2019.8790018

A Multi-Start Iterated Local Search Algorithm for the Maximum Scatter Traveling Salesman Problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this