Research Article: The A Priori Traveling Repairman Problem

Date Published: July 28, 2017

Publisher: Springer US

Author(s): Martijn van Ee, René Sitters.

http://doi.org/10.1007/s00453-017-0351-z

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, 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 study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP.

Partial Text

In the last few decades, a lot of research has been done in stochastic combinatorial optimization. This field is concerned with classical combinatorial optimization problems, like the shortest path problem and the minimum Steiner Tree problem, but with additional uncertainty in the instance. For example, there are situations where the problem instance changes on a daily basis. Instead of reoptimizing every instance, because it might be impossible or undesirable, one can alternatively choose to pick one solution that will be good on average. This is the setting of a priori optimization. In this paper, we consider the a priori traveling repairman problem (TRP). This is a routing problem, where there is a probability distribution over subsets of the vertices that have to be visited. A preliminary version of this paper was published in [19].

In the decision version of the a priori traveling repairman problem in the independent decision model, we are given a weighted graph G with n vertices and root vertex r, probabilities documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$p_i$$end{document}pi for documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$i=1,ldots ,n$$end{document}i=1,…,n and a number k. Vertex i is active with probability documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$p_i$$end{document}pi. Further, assume that the edge weights are rationals and that the smallest weight is equal to 1. The question is whether there exists a tour, starting at the root, that has an expected sum of latencies of at most k. The next theorem shows that this decision version is contained in NP. Since it generalizes TRP, the decision problem is NP-complete.

Before presenting our algorithm, we are going to rewrite the objective function and state a basic lemma that we will need in the analysis. Any tour should start in the given root r. For a given tour and active set A, we denote documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$ell _i^A$$end{document}ℓiA as the latency of vertex documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$iin A$$end{document}i∈A in the tour shortcutted over A. If vertex i is not in A, then we define documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$ell _i^A=0$$end{document}ℓiA=0. Each vertex i has probability documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$p_i$$end{document}pi of being active. If documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$C_i$$end{document}Ci is the expected latency of vertex i given that i is active, the law of total probability gives that our objective becomes minimizing2documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$begin{aligned} {mathbb {E}}_Aleft[ sum _{i}{ell _i^A}right] =sum _{i}p_i{mathbb {E}}_Aleft[ ell _i^A|i text { is active}right] =sum _i p_i C_i. end{aligned}$$end{document}EA∑iℓiA=∑ipiEAℓiA|iis active=∑ipiCi.Let d(r, i) be the minimum cost of traveling from the root to vertex i. Note that documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$C_i$$end{document}Ci is the expected latency of vertex i, given that it is active. Hence, we obtain the following lemma.

To obtain an approximation guarantee for the a priori TRP on trees, we use Corollary 1. Note that finding a k-tour in a tree is similar to finding a k-tree in a tree. So, in this case we can solve the a priori k-MST problem, in which we have to find a tree spanning k vertices such that the expected cost of the tree is minimized. Here, shortcutting the tree is done by removing inactive vertices provided that the tree on the active vertices remains connected.

For general metrics, we show how to obtain an documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$(alpha ,beta )$$end{document}(α,β)-TSP-approximator with some constant documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$alpha $$end{document}α and documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$beta $$end{document}β. It turns out that finding such an approximator boils down to finding an approximation algorithm for certain variations of the tour single-sink rent-or-buy problem (tour SRoB).

There are still many open problems in the field of a priori optimization. For the a priori traveling repairman problem we were only able to give a constant-factor approximation in the uniform model and the constant is still large. For the correctness of Theorems 2 and 3 the uniformity of the probabilities is essential. It is not clear how to reduce the case of independent probabilities to the uniform model. Therefore, the problem is wide open in the independent decision model with non-uniform probabilities. Also, it is not known if the uniform problem can be solved efficiently in case all points are on the line. If any optimal solution has the property that no point is passed without visiting it, like in the deterministic problem, then the problem may be solved by dynamic programming. However, a proof of this property is missing and we have shown that this property does not hold in the scenario setting.

 

Source:

http://doi.org/10.1007/s00453-017-0351-z

 

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments