Since the planning horizon consists of only two time periods (t = 1 and t = 2), there are three types of customers, customers C1 that are known at the beginning of the first time period and have to be served in that time period, customers C1|2 that are known at the beginning of the first time period and can be served either in the first or the second time period, and customers C2 that are unknown at the beginning of the first time period but become known at the beginning of the second time period and have to be served in the second time period. In this setting, there is only one decision that needs to be made at the beginning of the first time period: which customers in C1|2 to serve and which customers to postpone. Oncethisdecisionhasbeenmade,allthatremainsistosolvea traveling salesman problem for the customers that are served in the first time period and for the customers that are served in the second time period. The objective is to choose the set of customers to be served in the first time period in such a way that the total cost, i.e., the cost of the traveling salesman tour in the first time period plus the cost of the traveling salesman tour in the second time period, is minimum.
Let us denote by L1, L1|2, L2 the length of an optimal tour starting and ending at the depot and visiting all customers in C1, C1|2, C2, respectively, by L1,1|2 and L1|2,2 the length of an optimal tour visiting all customers in C1 ∪ C1|2, and in C1|2 ∪ C2, respectively. Moreover, we denote by Lall the length of an optimal tour starting and ending at the depot and visiting all customers, i.e., the customers in C1 ∪ C1|2 ∪ C2.
In our analysis, we restrict the set of possible customer locations to the real line and the Euclidean plane. Since the triangle inequality holds in both cases, we have that max(L1,L1|2) ≤ L1,1|2 ≤ L1 + L1|2. Similarly, max(L1|2,L2) ≤ L1|2,2 ≤ L1|2 + L2.
3.1. The Real Line
To gain an understanding of the complexity of DMPRP, we initially restrict ourselves to instances where customers are located on the non-negative real line (R+) and the depot
is located at the origin. It is useful to observe that, in this setting, the length of an optimal tour visiting a set of customers is twice the distance to the farthest (rightmost) customer. Accordingly, the length of an optimal tour visiting two sets of customers together equals the maximum length of the tours that visit each set of customers independently. Namely,
LA,B = max(LA,LB).
The next theorem provides a lower bound on the competitive ratio for any on-line algorithm.
Theorem 1. The competitive ratio of any algorithm for DMPRP with customer locations on the non-negative real√
line is greater than or equal to 2.
Proof. Consider the following instance. The customer set C1 contains a single customer at distance 1 from the depot (located at the origin) and the customer set C1|2 contains a single customer on the non-negative real line at distance a > 1 from the depot.
First, we consider algorithm A of the class
of algorithms that at the beginning of the first time period decide to visit
both customers. Now assume that the customer set C2, i.e.,
the set of customers that place an order at the beginning of the second time
period, contains a single customer at distance a from the depot. Then, z
= 2a + 2a, while the off-line
optimum is z∗(I) = 2 + 2a. Thus,rA ≥ 12+aa for all a
> 1.
Next, we consider algorithm A of the class of
algorithms thatatthebeginningofthefirsttimeperioddecidetovisitonly the customer
in C1. Now, assume that the customer set C2 is
empty, i.e., no orders arrive at the beginning of the second timeperiod.Then,z
= 2+2a,whilez∗(I) = 2a.Thus, rA ≥ 1+aa for all a > 1.
Consequently, for any algorithm A, we have
rA
for all a > 1.
2 for a = 1 + √2, we
obtain
rA ≥ √2. ■
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.