Routing under Uncertainty: the a priori Traveling Repairman Problem

M. van Ee; R.A. Sitters

doi:10.1007/978-3-319-18263-6_21

Routing under Uncertainty: the a priori Traveling Repairman Problem

M. van Ee, R.A. Sitters

Amsterdam Business Research Institute

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

Abstract

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem (TSP), the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we give the first constant-factor approximation for a priori TRP.

Original language	English
Pages (from-to)	248-259
Journal	Lecture Notes in Computer Science
Volume	8952
DOIs	https://doi.org/10.1007/978-3-319-18263-6_21
Publication status	Published - 2015
Event	12th Workshop on Approximation and Online Algorithms - Berlin Duration: 11 Sep 2014 → 12 Sep 2014

Bibliographical note

Proceedings title: Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers
Publisher: Springer
Place of publication: Berlin
Editors: E. Bampis, O. Svensson

Access to Document

10.1007/978-3-319-18263-6_21

Cite this

@article{8f6a544a53f14f71bc48ff1608bee6d5,

title = "Routing under Uncertainty: the a priori Traveling Repairman Problem",

abstract = "The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem (TSP), the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we give the first constant-factor approximation for a priori TRP.",

author = "{van Ee}, M. and R.A. Sitters",

note = "Proceedings title: Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers Publisher: Springer Place of publication: Berlin Editors: E. Bampis, O. Svensson; 12th Workshop on Approximation and Online Algorithms ; Conference date: 11-09-2014 Through 12-09-2014",

year = "2015",

doi = "10.1007/978-3-319-18263-6_21",

language = "English",

volume = "8952",

pages = "248--259",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

}

TY - JOUR

T1 - Routing under Uncertainty: the a priori Traveling Repairman Problem

AU - van Ee, M.

AU - Sitters, R.A.

N1 - Proceedings title: Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroclaw, Poland, September 11-12, 2014, Revised Selected Papers Publisher: Springer Place of publication: Berlin Editors: E. Bampis, O. Svensson

PY - 2015

Y1 - 2015

N2 - The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem (TSP), the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we give the first constant-factor approximation for a priori TRP.

AB - The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem (TSP), the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we give the first constant-factor approximation for a priori TRP.

U2 - 10.1007/978-3-319-18263-6_21

DO - 10.1007/978-3-319-18263-6_21

M3 - Article

VL - 8952

SP - 248

EP - 259

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

T2 - 12th Workshop on Approximation and Online Algorithms

Y2 - 11 September 2014 through 12 September 2014

ER -

Routing under Uncertainty: the a priori Traveling Repairman Problem

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this