Online TSP with Known Locations

2025-05-02 0 0 619.97KB 23 页 10玖币

侵权投诉

Evripidis Bampis !

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Bruno Escoﬃer !

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Institut Universitaire de France, Paris, France

Niklas Hahn !

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Michalis Xefteris !

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Abstract

In this paper, we consider the Online Traveling Salesperson Problem (OLTSP) where the locations

of the requests are known in advance, but not their arrival times. We study both the open variant, in

which the algorithm is not required to return to the origin when all the requests are served, as well

as the closed variant, in which the algorithm has to return to the origin after serving all the requests.

Our aim is to measure the impact of the extra knowledge of the locations on the competitiveness of

the problem. We present an online 3/2-competitive algorithm for the general case and a matching

lower bound for both the open and the closed variant. Then, we focus on some interesting metric

spaces (ring, star, semi-line), providing both lower bounds and polynomial time online algorithms

for the problem.

2012 ACM Subject Classiﬁcation Theory of computation →Design and analysis of algorithms

Keywords and phrases TSP, online algorithms, competitive analysis

Digital Object Identiﬁer 10.4230/LIPIcs...

Funding

This work was partially funded by the grant ANR-19-CE48-0016 from the French National

Research Agency (ANR).

1 Introduction

In the classical Traveling Salesperson Problem (TSP), we are given a set of locations in a

metric space. The objective is to ﬁnd a tour visiting all the locations minimizing the total

traveled time assuming that the traveler moves in constant speed [

]. Ausiello et al. [

]

introduced the Online Traveling Salesperson Problem (OLTSP) where the input arrives over

time, i.e., during the travel new requests (locations) appear that have to be visited by the

algorithm. The time in which a request is communicated to the traveler (from now on we

will refer to him/her as the server) is called release time (or release date). Since then, a

series of papers considered many versions of OLTSP in various metric spaces (general metric

space [

], the line [

], or the semi-line [

]). Several applications can be modeled

as variants of OLTSP, e.g. applications in logistics and robotics [2, 16].

The performance of the proposed algorithms for OLTSP has been evaluated in the

framework of competitive analysis, by establishing upper and lower bounds of the competitive

ratio which is deﬁned as the maximum ratio between the cost of the online algorithm and

the cost of an optimal oﬄine algorithm over all input instances. However, it is admitted that

the competitive analysis approach is sometimes very pessimistic as it gives a lot of power to

the adversary. Hence, many papers try to limit the power of the adversary by suggesting

for instance the notion of a fair adversary [

], or by giving extra knowledge and hence more

power to the online algorithm by introducing the notion of ∆-time-lookahead [

], where the

©;

licensed under Creative Commons License CC-BY 4.0

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

arXiv:2210.14722v3 [cs.DS] 1 Nov 2022

XX:2 Online TSP with Known Locations

online algorithm knows all the requests that will arrive in the next ∆units of time, or the

-request-lookahead, where the online algorithm has access to the next

requests [

]. In the

same vein, Jaillet and Wagner [

] introduced the notion of disclosure dates, i.e., the dates at

which the requests become known to the online algorithm ahead of their release dates. More

recently, OLTSP has also been studied in the framework of Learning-Augmented Algorithms

[

]. Here, we study another natural way of giving more power to the online algorithm

by considering that the location of each request is known in advance, but its release date

arrives over time. The release date, in this context, is just the time after which a request

can be served. This is the case for many applications where the delivery/collection locations

are known (parcel collection from ﬁxed storage facilities, cargo collection on a harbour etc.).

Think for example of a courier that has to deliver packets to a ﬁxed number of customers.

These packets may have to be delivered in person, so the customers should be at home to

receive them. Each customer can inform the courier through an app when he/she returns

home and is ready to receive the packet. We refer to this problem as the online Traveling

Salesperson Problem with known locations (OLTSP-L) and consider two variants: in the

closed variant the server is required to return to the origin after serving all requests, while in

the open one the server does not have to return to the origin after serving the last request.

Previous results

The oﬄine version of the open variant of the problem in which the requests are known in

advance can be solved in quadratic time when the metric space is a line [

]. In [

], Bjelde

et al. studied the oﬄine closed variant providing a dynamic program based on the one of [

]

that solves the problem in quadratic time. For the online problem, Ausiello et al. [

] showed

a lower bound of 2for the open version and a lower bound of 1

64 for the closed version of

OLTSP, even when the metric space is the line. They also proposed an optimal 2-competitive

algorithm for the closed version and a 2

5-competitive algorithm for the open version of

OLTSP in general metric spaces. For the line, they presented a (7

3)-competitive algorithm

for the open case and a 1

75-competitive algorithm for the closed one. More recently, Bjelde

et al., in [

], proposed a 1

64-competitive algorithm for the close case (on the line) matching

the lower bound of [

]. They also provided a lower bound of 2

04 for the open case on the

line, as well as an online algorithm matching this bound. In [

], Blom et al. proposed a best

possible 1

5-competitive algorithm when the metric space is a semi-line. Chen et al., in [

presented lower and upper bounds of randomized algorithms for OLTSP on the line.

In [12], Hu et al. introduced learning-augmented algorithms for OLTSP. They proposed

three diﬀerent prediction models. In the ﬁrst model, the number of requests is not known

in advance and each request is associated to a prediction for both its release time and its

location. In the second model, they assume that the number of requests is given and that, as

in the ﬁrst model, a prediction corresponds to both the release time and the location of the

request. While being closer to our model, no direct comparison can be done between their

results and ours. In the third model, the prediction is just the release time of the last request.

In [

], Bernardini et al. focused also on learning-augmented algorithms and they introduced

a new error measure appropriate for many online graph problems. For OLTSP, they assume

that a prediction corresponds to both the release time and the location of a request. They

study OLTSP for metric spaces, but also the more special case of the semi-line. Their results

are not comparable to ours. In [

], Gouleakis et al. studied a learning-augmented framework

for OLTSP on the line. The authors deﬁne a prediction model in which the predictions

correspond to the locations of the requests. They establish lower bounds by assuming that

the predictions are perfect, i.e. the locations are given, and the adversary can only control

E. Bampis, B. Escoﬃer, N. Hahn and M. Xefteris XX:3

the release times of the requests. They also proposed upper bounds as a function of the value

of the error. Let us note that in the case where the error is equal to 0, their model coincides

with ours (see Table 1 for a comparison with our results).

2 Our contribution

In this work we study both the closed (closed OLTSP-L) and the open case of OLTSP-L

(open OLTSP-L) and present several lower and upper bounds for the problem. In Table 1,

we give an overview of our results and the state of the art.

Open OLTSP-L Closed OLTSP-L

Lower Bound Upper Bound Lower Bound Upper Bound

Semi-line 4/3

Thm. 11

13/9*

Thm. 12 11*

Prop. 13

Line 13/9

[11, Thm. 4]

3/2

Thm. 3

5/3*

[11, Thm. 3]

3/2

[11, Thm. 2]

3/2*

[11, Thm. 1]

Star 13/9

[11, Thm. 4]

3/2

Thm. 3

3/2

[11, Thm. 2]

3/2

Thm. 3

(7/4 + )∗

Cor. 8

Ring 3/2

Prop. 1

3/2

Thm. 3

3/2

[11, Thm. 2]

3/2

Thm. 3

5/3*

Thm. 5

General 3/2

Prop. 1

3/2

Thm. 3

3/2

[11, Thm. 2]

3/2

Thm. 3

Table 1

Results for the open and closed variants of OLTSP-L. Polynomial time algorithms are

denoted by * and tight results in bold.

We ﬁrst consider general metric spaces (dealt with in Section 4). For the closed version, a

lower bound of 3/2 has been shown in [

] (valid in the case of a line). We show that a lower

bound of 3

2holds also for the open case (on rings). We then provide a 3

2-competitive

online algorithm for both variants, thus matching the lower bounds. Although our algorithm

does not run in polynomial time, the online nature of the problem is a source of diﬃculty

independent of its computational complexity. Thus, such algorithms are of interest even if

their running time is not polynomially bounded.

However, it is natural to also focus on polynomial time algorithms. We provide several

bounds in speciﬁc metric spaces. In Section 5, we focus on rings and present a polytime

3-competitive algorithm for the closed OLTSP-L. Next, we give a polytime (7

4 +



competitive algorithm, for any constant

 >

0, in the closed case on stars (Section 6). In

Section 7, we study the problem on the semi-line. We present a simple polytime 1-competitive

algorithm for the closed variant and, for the open case, we give a lower bound of 4

3and an

upper bound (with a polytime algorithm) of 13/9.

To measure the gain of knowing the locations of the requests, we also provide some lower

bounds on the case where the locations are unknown, and more precisely on the case where

the number of locations is known but not the locations themselves. In the open case of the

problem, there is a lower bound of 2in [

] on the line that holds even when the number

of requests is known. Hence the same lower bound holds for the star and for the ring. We

provide a lower bound of 3

2(Proposition 10) for the semi-line. For the closed case, we show

a lower bound of 2 for the ring (Proposition 4) and the star (Proposition 6). We also present

a lower bound of 4

3(Proposition 9) for the semi-line. For the line, it is easy to see (with a

trivial modiﬁcation in the proof) that the lower bound of 1

64 on the line [

] still holds in

this model where we know the number of locations. These lower bounds show that knowing

XX:4 Online TSP with Known Locations

only the number of requests is not suﬃcient to get better competitive ratios in most cases,

and thus it is meaningful to consider the more powerful model with known locations.

3 Preliminaries

The input of OLTSP-L consists of a metric space

with a distinguished point

(the origin),

and a set

{q1, ..., qn}

requests. Every request

is a pair (

ti, pi

), where

is a point

(which is known at

= 0) and

ti≥

0is a real number. The number

represents the

moment after which the request

can be served (release time). A server located at the

origin at time 0, which can move with at most unit speed, must serve all the requests after

their release times with the goal of minimizing the total completion time (makespan).

When we refer to general metric spaces or general metrics, we mean the wide class of

metric spaces

deﬁned in [

]. This class contains all continuous metric spaces which have

the property that the shortest path from

x∈M

y∈M

is continuous in

and has length

(

x, y

). We note that our 3/2-competitive algorithm for general metric spaces also works for

discrete metric spaces (where you do not continuously travel from one point to another, but

travel in a discrete manner from point xat time tto point yat time t+d(x, y)).

For the rest of the paper, we denote the total completion time of an online algorithm

ALG

|ALG|

and that of an optimal (oﬄine) solution

OP T

|OP T |

. We recall that an

algorithm

ALG

-competitive if on all instances we have

|ALG| ≤ r· |OP T |

. We will often

use ρto denote |ALG|

|OP T |and tto quantify time.

4 General metrics

As mentioned earlier, [

] showed a lower bound of 3/2 for closed OLTSP-L, even in the case

of a line. In this section, we ﬁrst show that the same lower bound of 3/2 holds for open

OLTSP-L (in the case of a ring). We then devise a 3/2-competitive algorithm, for general

metrics, both in the open and in the closed cases, thus matching the lower bounds in both

cases.

Let us ﬁrst show the lower bound for open OLTSP-L.

IProposition 1.

For any

 >

0, there is no (3

−

)-competitive algorithm for open

OLTSP-L on the ring.

Proof.

Consider a ring with circumference 1 with 2 requests

and

, with a distance of

3from

and from each other as visualized in Figure 1. At time

= 1

3, without loss of

generality due to symmetry, we can assume that the algorithm is somewhere in the segment

(arc of the ring) [

](including both

and

). Then,

is released. The second request

is released at time 2

3. Hence,

OP T

can visit

and

in time 2

3, whereas the online

algorithm cannot ﬁnish before

= 1. Whether it serves

ﬁrst, it cannot serve the ﬁrst

request before time

= 2

3and will have to go a distance of 1

3to serve the second request,

as well. J

Now, let us present the 3/2-competitive algorithm. Roughly speaking, the principle of

the algorithm is:

ﬁrst, to wait (at the origin) a well chosen amount of time

. This time

depends both

on the locations of the requests and on the time they are released. It is chosen so that (1)

the optimal solution cannot have already visited (served the requests on) a large part of

its tour (closed case) / path (open case) and (2) there is a tour/path for which a large

part is fully revealed (which is a good tour to follow if not too long).

E. Bampis, B. Escoﬃer, N. Hahn and M. Xefteris XX:5

A B

Figure 1 Lower bound instance for open OLTPS-L on the ring

then, to choose an order of serving requests that optimizes some criterion mixing the

length of the corresponding tour/path and the fraction of it which is released at time

, and to follow this tour/path (starting at time

), waiting at requests if they are not

released.

More formally, we consider Algorithm 1, which uses the following notation (see Example 2

for an example illustrating the notation and the execution of the algorithm). For a given

order

σi

on the requests (where

σi

(1) denotes the ﬁrst request in the order,

σi

(2) the second

request, . . . ), we denote:

the length of the tour/path associated to

σi

(starting at

), i.e.,

(

O, σi

(1)) +

Pn−1

j=1 d

(

σi

(

)

, σi

(

+ 1)) in the open case,

(

O, σi

(1)) +

Pn−1

j=1 d

(

σi

(

)

, σi

(

+ 1)) +

d(σi(n), O)in the closed case;

αi

(

)the fraction of the tour/path associated to

σi

, starting at

, which is fully

released at time

. More formally, if requests

σi

(1)

, . . . , σi

(

k−

1) are released at

but

σi

(

)is not, then the tour/path is fully released up to

σi

(

), and

αi

(

) =

d(O,σi(1))+Pk−1

j=1 d(σi(j),σi(j+1))

`i.

Algorithm 1 Algorithm for closed and open OLTSP-L

Input: Oﬄine: Request locations p1, . . . , pn

Online: Release times t1, . . . , tn

1Let σ1, . . . , σn!be the orders of requests.

2For all i≤n!, compute `ithe length of the tour/path associated to σi.

Wait at

until time

deﬁned as the ﬁrst time

such that there exists an order

σi0

with (1) t≥`i0/2and (2) αi0(t)≥1/2.

4At time T:

Compute an order σi1which minimizes, over all orders σi(1≤i≤n!), (1 −βi)`i,

where βi= min{αi(T),1/2}.

Follow (starting at time T) the tour/path associated to σi1, by serving the

requests in this order, waiting at a request location if this request is not released.

IExample 2.

Let us consider the example of Figure 2 with three requests

q1, q2, q3

, released

respectively at time 2, 6 and 8. We focus on the closed case.

Let us consider the order

σ0

= (

q1, q2, q3

), with

= 12 (closed case). Then for 0

≤t <

we have

α0

(

) = 1

4, for 2

≤t <

6we have

α0

(

) = 1

2, for 6

≤t <

8we have

α0

(

) = 3

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OnlineTSPwithKnownLocationsEvripidisBampis!SorbonneUniversité,CNRS,LIP6,F-75005Paris,FranceBrunoEscoer!SorbonneUniversité,CNRS,LIP6,F-75005Paris,FranceInstitutUniversitairedeFrance,Paris,FranceNiklasHahn!SorbonneUniversité,CNRS,LIP6,F-75005Paris,FranceMichalisXefteris!SorbonneUniversité,CNRS,LIP6,F...

展开>> 收起<<

Online TSP with Known Locations.pdf

共23页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Online TSP with Known Locations

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: