increasing function of x and L1|2.
When L2 ≤ L1, the optimal strategy is to serve the customers in∗(I) = L1C,11||22 +in the first time period, resulting in a total costL2 √= L1|2 + L2. z
If L1,1|2 ≤ (1 + 2)L1, then Algorithm IMMEDIATE is applied and it finds the optimal solution:√ rSMART(I) = 1.
IfL1,1|2 > (1+ 2)L1,thenAlgorithmDELAYisapplied.
We derive
rSMART(I) = z(DELAY,I) = L1 ++L1|2,2 = L1 ++L1|2 z∗(I) L1|2 L2 L1|2 L2
L1
≤ 
In
conclusion, we have≤ √ 
rSMART=(I) ≤+√√2 for all instances
I. Thus, rSMART 2 when p 1 2. The tightness of the bound and the optimality of the algorithm come from
Theorem 1. ■
Next, we consider what happens when we restrict ourselves to instances where customer locations are on the entire real line. Obviously, the lower bound provided in Theorem 1 is still valid.
Theorem 5.√ An optimal algorithm with competitive ratio
2 exists for instances with customer locations on the real line (R− ∪ R+).
Proof. Observe that the vehicle has to pass the depot when going from a customer located on R− to a customer locatedonR+ andviceversa.Therefore,thelengthofanytour is the sum of the distances traveled on R− and R+. It follows that it is optimal to partition each customers set− and a subset ofC1, C1|2 and
C2 into a subset of customers located on R customerslocatedonR+ (customerslocatedattheoriginmay be included in either one of the sets), to compute the length of an optimal tour starting and ending at the depot and visiting
all customers in each subset, and to apply SMART√ (1 + √2)
on R− and SMART(1 + 2) on R+. ■
3.2. The Euclidean Plane
A lower bound on the competitive ratio of any algorithmfor DMPRP with customer locations in the Euclidean plane (R2) is given in the next theorem.
Theorem 6. The
competitive ratio of any algorithm for DMPRP with customer locations in the
Euclidean plane is greater than or equal to 
.
Proof. Consider the following instance. The depot is
located at the origin O. Customers are located on three line segments
emanating from O. The endpoints A, B, and C of the
three line segments lie on the circle with radius 
. The distance
between A and B as well as the distance between
B
and C is (distance
between A and C is approximately 
small). The
customers in C1, with |C1| = n, are
distributeduniformlyonthelinesegmentOA.Halfofthecustomers in C1|2, with |C1|2|
= 2n, are distributed uniformly on the line segment OB and
the other half of the customers are distributed uniformly over the line segment
OC. For large enough n (depends on ), the customers on a line
segment are always visited consecutively in an optimal vehicle route, i.e., it
never pays to zig-zag between customers on different line segments.
Consequently, any algorithm for DMPRP has three choices. The
first choice is to serve only the customers in C1 in the
first time period. In that case, let the customers in C2,
with |C2| = n, be distributed
uniformly on the line segment OA. The algorithm produces a solution with
cost 
AO plus OA 
and
OC + CO).
The optimal off-line solution has cost 2 
BO
plus OA 
). The ratio tends to 
tends to
0. The second choice is to
serve the customers in C1 ∪
C1|2 in the first time period. In that case, let the
customers in C2, with |C2| = n, be distributed
uniformly on the line segment OC. The algorithm produces a solution with
cost
(OA + AO and OB 
plus
OC + CO).
The optimal off-line solution has cost 2BO plus OC+CO). The ratio tends to
when tends to 0. The final choice is
to serve the customer in C1 and the customers in C1|2 on the line segment OB in
the first time period. In that case, let
half of the customers in C2,
with |C2| = 2n, be distributed
uniformly on the line segment OA and the other half of the customers be
distributed uniformly on the line segment OB. The algorithm produces a
solution with cost (1
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.