Иностранные языки \ Иностранные языки

Competitive Analysis for Dynamic Multiperiod. Uncapacitated Routing Problems Enrico Angelelli and M. Grazia Speranza, страница 5

There are two natural algorithms to consider and analyze as a first step towards constructing an effective algorithm for DMPRP.Namely,thealgorithmwhichservesallcustomersin C₁|2 inthefirsttimeperiod,whichwewillcallIMMEDIATE, and the algorithm that postpones all customers in C₁|2 to the second time period, which we will call DELAY.

Ouranalysisofthesetwosimplealgorithmswillshowthat√ their competitive ratio is quite far from the lower bound 2 shown in Theorem 1.

Algorithm 1 (IMMEDIATE). Visit all customers in C₁and C₁|2 in the first time period and visit all customers in C₂in the second time period.

Theorem 2. The competitive ratio of Algorithm IMMEDIATE for instances with customer locations on the nonnegative real line is 2.

Proof. It is easy to see that z∗(I) ≥ L_all≥ max(L_1,1|2,L₂) and z(IMMEDIATE,I) = L_1,1|2 +L₂. Therefore,

2Lall

rIMMEDIATE = 2

Lall

for all instances I. Thus rIMMEDIATE ≤ 2.

Toseethattheboundistight,consideranyinstanceI where C₁= ∅ and the sets C₁|2 and C₂are identical and non-empty.

Then,

z(IMMEDIATE,I) = 2L1|2 = _2.■ z∗(I) L₁|2

Algorithm 2 (DELAY). Visit all customers in C₁in the first time period and visit all customers in C₁|2 and C₂in the second time period.

Theorem 3. The competitive ratio of Algorithm DELAY for instances with customer locations on the non-negative real

line is 2.

Proof. Since z∗(I) ≥ L_all≥ max(L₁,L₁|2_,2) and z(DELAY,I) = L₁+ L₁|2_,2, we obtain

r_DELAY(I) ≤ L1 + L1|2,2 ≤ 2Lall ≤ 2

Lall Lall

for all instances I. Thus rDELAY ≤ 2.

To see that the bound is tight, consider any instance I where the sets C₁and C₁|2 are identical and nonempty and C₂= ∅. Then,

z(DELAY,I) L₁+ L₁

z∗(I) = L1 = 2. ■

We now consider a parameterized algorithm that applies either IMMEDIATE or DELAY, based on the information available at the beginning of the first period.

Algorithm 3 (SMART(p)). If L₁> 0 and L_1,1|2 ≤ pL₁,

then apply IMMEDIATE, else apply DELAY.

Algorithm SMART(p) visits all customers in C₁|2 in the first time period if C₁is nonempty and L_1,1|2 ≤ pL₁, i.e. if the customers in C₁|2 are not “too far” from the customers in C₁, while it postpones all customers in C₁|2 to the second time period otherwise. Throughout the paper we will assume p > 1.

Next, we will show that the proposed algorithm, for an appropriate parameter choice, is optimal in the sense that no algorithm exists with a better competitive ratio.

Theorem4.√ ThecompetitiveratioofAlgorithmSMART(1+

2) for instances with customer locations on the non-√

negative real line is 2. The algorithm is optimal.

Proof. The cases L₁= 0 and L₁|2 ≤ L₁are trivial. In the first case Algorithm DELAY is applied and the offline optimal solution is found. In the second case Algorithm IMMEDIATE is applied and the off-line optimal solution is

found. In both cases the ratio r_SMART(I) equals 1. Now, let us assume 0 < L₁< L₁|2 and observe that L_1,1|2 = L₁|2.

When L₁< L₂, the optimal strategy is to serve the customers in C1^|2 in the second time period, resulting in a total cost z∗(I) = _L₁++√_L₁|_2,2_.