Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem

Güneş Erdoğan; Emre Alper Yildirim

doi:10.1287/trsc.2020.0999

Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem

Güneş Erdoğan, Emre Alper Yildirim

Koç University

Research output: Contribution to journal › Article › peer-review

11 Citations (SciVal)

82 Downloads (Pure)

Abstract

This paper presents new structural properties for the Carrier-Vehicle Traveling Salesman Problem. The authors provide a new mixed integer second order conic optimization formulation, with associated optimality cuts based on the structural properties, and an Iterated Local Search (ILS) algorithm. Computational experiments on instances from the literature demonstrate the superiority of the new formulation to the existing models and algorithms in the literature, and the high quality solutions found by the ILS algorithm.

Original language	English
Pages (from-to)	101-121
Number of pages	21
Journal	Transportation Science
Volume	55
Issue number	1
Early online date	18 Aug 2020
DOIs	https://doi.org/10.1287/trsc.2020.0999
Publication status	Published - 1 Jan 2021

Bibliographical note

Funding Information:
Funding: This work was supported by a University of Bath International Research Funding Scheme.

Keywords

Mixed-integer second-order conic optimization
Multivehicle systems
Traveling salesman problem

ASJC Scopus subject areas

Civil and Structural Engineering
Transportation

Access to Document

10.1287/trsc.2020.0999

cvtsp_TS_Savelsbergh_suggestions_25_apr_2020.PDFAccepted author manuscript, 460 KBLicence: CC BY-NC

Cite this

@article{36d762e70e534c03adb0c90002206fca,

title = "Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem",

abstract = "This paper presents new structural properties for the Carrier-Vehicle Traveling Salesman Problem. The authors provide a new mixed integer second order conic optimization formulation, with associated optimality cuts based on the structural properties, and an Iterated Local Search (ILS) algorithm. Computational experiments on instances from the literature demonstrate the superiority of the new formulation to the existing models and algorithms in the literature, and the high quality solutions found by the ILS algorithm.",

keywords = "Mixed-integer second-order conic optimization, Multivehicle systems, Traveling salesman problem",

author = "G{\"u}ne{\c s} Erdoğan and Yildirim, {Emre Alper}",

note = "Funding Information: Funding: This work was supported by a University of Bath International Research Funding Scheme. ",

year = "2021",

month = jan,

day = "1",

doi = "10.1287/trsc.2020.0999",

language = "English",

volume = "55",

pages = "101--121",

journal = "Transportation Science",

issn = "0041-1655",

publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

number = "1",

}

TY - JOUR

T1 - Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem

AU - Erdoğan, Güneş

AU - Yildirim, Emre Alper

N1 - Funding Information: Funding: This work was supported by a University of Bath International Research Funding Scheme.

PY - 2021/1/1

Y1 - 2021/1/1

N2 - This paper presents new structural properties for the Carrier-Vehicle Traveling Salesman Problem. The authors provide a new mixed integer second order conic optimization formulation, with associated optimality cuts based on the structural properties, and an Iterated Local Search (ILS) algorithm. Computational experiments on instances from the literature demonstrate the superiority of the new formulation to the existing models and algorithms in the literature, and the high quality solutions found by the ILS algorithm.

AB - This paper presents new structural properties for the Carrier-Vehicle Traveling Salesman Problem. The authors provide a new mixed integer second order conic optimization formulation, with associated optimality cuts based on the structural properties, and an Iterated Local Search (ILS) algorithm. Computational experiments on instances from the literature demonstrate the superiority of the new formulation to the existing models and algorithms in the literature, and the high quality solutions found by the ILS algorithm.

KW - Mixed-integer second-order conic optimization

KW - Multivehicle systems

KW - Traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85100501213&partnerID=8YFLogxK

U2 - 10.1287/trsc.2020.0999

DO - 10.1287/trsc.2020.0999

M3 - Article

SN - 0041-1655

VL - 55

SP - 101

EP - 121

JO - Transportation Science

JF - Transportation Science

IS - 1

ER -

Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this