Route Generation Phase
CHAPTER 5. ROUTE GENERATION PHASE
5.1.3 Updating the route
An inserted customer can impact the deliveries to customers that appear both before it and after it on the route. For the customers earlier in the route, there might not be as much time to postpone their deliveries, whereas deliveries to the customers later in the route might have to start earlier.
Pseudocode for the Update()-procedure is shown in algorithm 2.
After the insertion of customer j in the route, the l-values of the customers prior in the route and thee-values of customers later in the route have to be updated, see lines 4–7 and 9–12 of the pseudocode. In practice, the latest delivery time for the customers preceedingj have to be updated only as long as the value for the recently updated customer has changed. For example, if li−1 does not change, there is no need to recalculateli−2. The same holds for the earliest delivery time for the customers following j.
Algorithm 2 Pseudo-code for the Update()-procedure.
1: {Update the total load on the route}
2: Dr =Dr+qj
3:
4: {Update the latest delivery time for the customers prior in the route}
5: for c=i . . .0 do
6: lc=min(lc, lc+1−tc,c+1−sc)
7: end for
8:
9: {Update the earliest delivery time for the customers later in the route}
10: for c=i+ 1. . . n+ 1 do
11: ec=max(ec, ec−1+sc−1+tc−1,c)
12: end for
13:
14: {Compute the implied earliest departure time and latest completion time}
15: e0 =max(e0, en+1−ST)
16: ln+1 =min(ln+1, l0+ST)
17:
18: {If the implied earliest departure time has changed, update the e-values for the customers just before the point of insertion}
19: if e0 > e0 then
20: e0 =e0
21: for c= 1. . . i do
22: ec =max(ec, ec−1+sc−1+tc−1,c)
23: end for
24: end if
25:
26: {If the implied latest completion time has changed, update the l-values for the customers just after the point of insertion}
27: if ln+1 < ln+1 then
28: ln+1 =ln+1
29: for c=n . . . i+ 1 do
30: lc =min(lc, lc+1−tc,c+1−sc)
31: end for
32: end if
33:
34: {Update the cumulative distance to the depot for the customers later in the route}
35: for c=i . . .0 do
36: ac=ac+ (ti,j+tj,i+1−ti,i+1) +sj
37: end for
CHAPTER 5. ROUTE GENERATION PHASE
Furthermore, if the latest completion time of route ln+1 or the earliest de-parture time e0 has changed due to the insertion of a new customer j, the additional updates have to be performed.
If e0 has increased, then after updating the e-values for the customers after the insertion point, the values frome0 forward toei have to be updated. Sim-ilarly, ifln+1 has changed, then after updating thel-values for the customers prior to the point of insertion, the values fromln+1 backward toli+1 must be updated.
There is no further explanation of the updating procedure in the article of Campbell and Savelsbergh, which makes it hard for the reader to see what happens if a certain situation occurs. Consider the partially constructed route in figure 5.6 with route duration less than the shift time ST.
PSfrag replacements
. . . . . .
tij
t01 tii+1
tji+1
tnn+1
e0 e1 ei
ej = max(Ej, ei+si+tij) en
ei+1 en+1
Figure 5.6: Partially constructed route with route duration less than shift time. Only the earliest possible delivery times are displayed.
Customer j is to be inserted into the route between customers i and i+ 1.
Assume that e0 has changed due to the insertion, and that e-value for the customer in position i is changed in the updating process. Remember that ej was computed as max(Ej, ei+si+tij). Due to the change in ei, it seems necessary to re-evaluate ej. If ej is determined by the second term of the maximum, then the e-values for the customers following customer j will also have to change, including the value of the earliest completion time of the route, en+1. The last change will cause e0 to change again due to the shift time limit, and the whole updating procedure will have to be repeated.
The question is now how many times the updating procedure have to be repeated and whether an O(n) complexity of the whole updating phase can be preserved. The same doubtful situation occurs if the latest completion time of the route,ln+1, is changed due to the shift time limit, and the l-value for the customer in position i+ 1 is changed during the updating procedure.
In the following, it will be shown that there will be no need to update the values of ej, or lj, and thus going through the updating procedure several times. It can be shown that if such updates are necessary, the insertion would not have been feasible in the first place.
To simplify further explanations it is assumed, that service time for each customer is included in travel time from this customer to the next.
Statement 5.2. Assume that insertion of customer j causes delay of the earliest completion time and thus change of e0. Assume that ei is changed in the updating process. The value of ej will remain unchanged, as otherwise the insertion would have been infeasible with respect to shift time limit.
Proof of the statement 5.2. Assume that insertion of customer j be-tween customers i and i + 1 is feasible. Then one of the conditions that have to hold is
a0 ≤ST (5.21)
After insertion the new value of en+1 can be computed based on the value of ej:
en+1 =ej +tji+1+ai+1 (5.22) and e0 is re-calculated to:
e0 =en+1−ST (5.23)
Due to the updating procedure, the e-value of customer i is changed to enewi =e0+ (a0−ai) (5.24) The only way for ej to change is if condition (5.25) holds.
enewi +tij > ej ⇔ (5.25)
e0+ (a0 −ai) +tij> ej ⇔ (5.26) e0+ (a0 −ai) +tij> en+1−tji+1−ai+1 (5.27) By substitution of e0 in (5.27) with the right hand side of equation (5.23) following is deduced:
en+1−ST +a0−ai+tij > en+1−tji+1−ai+1 ⇔ (5.28) a0+tij+tji+1+ai+1−ai > ST ⇔ (5.29) a0+tij+tji+1−tij−tji+1 > ST ⇔ (5.30)
a0 > ST (5.31)
The last equation contradicts the assumption that the insertion of customer j was feasible – see equation (5.21).
CHAPTER 5. ROUTE GENERATION PHASE
A similar statement can be proved for updating the l-values:
Statement 5.3. Assume that insertion of customerj causes the latest depar-ture time to be decreased, and that the latest completion time is also changed due to the shift time limit, ln+1 = l0 +ST. Assume that li+1 is changed in updating process. The value of lj will remain unchanged, as otherwise the insertion would have been infeasible with respect to the shift time limit.
Proof. Similar to the one for statement 5.2 and not presented here, but can be found in appendix A.
Apart from the updates mentioned in the above, the total delivery volume of the route and the cumulative travel distance to the depot of the customers preceeding j have to be updated – lines 1-2 and 34-37 of the pseudocode described in algorithm 2. Clearly, all these updates can be done in linear time thus preserving the overall time complexity of O(n3) – O(n2) if seeding is applied – for the proposed insertion algorithm.