A priori TSP in the scenario model

Martijn van Ee; Leo van Iersel; Teun Janssen; René Sitters

doi:10.1016/j.dam.2018.04.002

A priori TSP in the scenario model

Martijn van Ee^*
, Leo van Iersel
, Teun Janssen
, René Sitters

^*Corresponding author for this work

Amsterdam Business Research Institute

Research output: Contribution to Journal › Article › Academic › peer-review

195 Downloads (Pure)

Abstract

In this paper, we consider the a priori traveling salesman problem in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour. We show that this problem is already NP-hard and APX-hard when all scenarios have size four. On the positive side, we show that there exists a constant-factor approximation algorithm in three restricted cases: if the number of scenarios is fixed, if the number of missing vertices per scenario is bounded by a constant, and if the scenarios are nested. Finally, we discuss an elegant relation with an a priori minimum spanning tree problem.

Original language	English
Pages (from-to)	331-341
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	250
Early online date	16 Aug 2018
DOIs	https://doi.org/10.1016/j.dam.2018.04.002
Publication status	Published - 11 Dec 2018

Funding

We would like to thank Karen Aardal, Jan Driessen and Neil Olver for useful discussions. A part of the work by Teun Janssen has been performed in the project INTEGRATE “Integrated Solutions for Agile Manufacturing in High-mix Semiconductor Fabs”, co-funded by grants from France, Italy, Ireland, The Netherlands and the ECSEL Joint Undertaking. Martijn van Ee and René Sitters are supported by the NWO Grant 612.001.215 . Leo van Iersel was partially supported by the NWO , including Vidi grant 639.072.602 , and partially by the 4TU Applied Mathematics Institute .

Funders	Funder number
4TU Applied Mathematics Institute
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	612.001.215, 639.072.602
Electronic Components and Systems for European Leadership

Keywords

a priori optimization
Master tour
Optimization under scenarios
Traveling salesman problem

Access to Document

10.1016/j.dam.2018.04.002

A priori TSP in the scenario modelFinal published version, 337 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{614d619a75aa4c3aa5423a7986febaef,

title = "A priori TSP in the scenario model",

abstract = "In this paper, we consider the a priori traveling salesman problem in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour. We show that this problem is already NP-hard and APX-hard when all scenarios have size four. On the positive side, we show that there exists a constant-factor approximation algorithm in three restricted cases: if the number of scenarios is fixed, if the number of missing vertices per scenario is bounded by a constant, and if the scenarios are nested. Finally, we discuss an elegant relation with an a priori minimum spanning tree problem.",

keywords = "a priori optimization, Master tour, Optimization under scenarios, Traveling salesman problem",

author = "\{van Ee\}, Martijn and \{van Iersel\}, Leo and Teun Janssen and Ren{\'e} Sitters",

year = "2018",

month = dec,

day = "11",

doi = "10.1016/j.dam.2018.04.002",

language = "English",

volume = "250",

pages = "331--341",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A priori TSP in the scenario model

AU - van Ee, Martijn

AU - van Iersel, Leo

AU - Janssen, Teun

AU - Sitters, René

PY - 2018/12/11

Y1 - 2018/12/11

N2 - In this paper, we consider the a priori traveling salesman problem in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour. We show that this problem is already NP-hard and APX-hard when all scenarios have size four. On the positive side, we show that there exists a constant-factor approximation algorithm in three restricted cases: if the number of scenarios is fixed, if the number of missing vertices per scenario is bounded by a constant, and if the scenarios are nested. Finally, we discuss an elegant relation with an a priori minimum spanning tree problem.

AB - In this paper, we consider the a priori traveling salesman problem in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices of the scenario. The goal is to find a tour on all vertices that minimizes the expected length of the resulting restricted tour. We show that this problem is already NP-hard and APX-hard when all scenarios have size four. On the positive side, we show that there exists a constant-factor approximation algorithm in three restricted cases: if the number of scenarios is fixed, if the number of missing vertices per scenario is bounded by a constant, and if the scenarios are nested. Finally, we discuss an elegant relation with an a priori minimum spanning tree problem.

KW - a priori optimization

KW - Master tour

KW - Optimization under scenarios

KW - Traveling salesman problem

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

UR - https://www.scopus.com/pages/publications/85046159723#tab=citedBy

U2 - 10.1016/j.dam.2018.04.002

DO - 10.1016/j.dam.2018.04.002

M3 - Article

AN - SCOPUS:85046159723

SN - 0166-218X

VL - 250

SP - 331

EP - 341

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A priori TSP in the scenario model

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this