Article Contents
Article Contents

# Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock

• * Corresponding author: Binghai Zhou
• Cross-docking is a kind of process that products are unloaded in front of the inbound doors, consolidated based on the downstream demand, and then directly transferred to the outbound doors without a long storage process during the transportation. In this paper, a multi-door cross-dock truck scheduling problem is investigated in which the scheduling and sequencing assignment of trucks need to be considered, with the objectives of minimizing the inner transportation cost in the cross-dock and the total truck waiting cost. The major contribution of this paper is that a novel product-related time window constraint and the temporary storage area are firstly introduced to adapt to different physical conditions of goods considering real-world requirements. Then, a Lagrangian relaxation algorithm is proposed which aims to decompose the relaxed problem into several easy-to-be-solved sub-problems. Besides, a subgradient algorithm is used at each iteration to further deal with these sub-problems. Finally, theory analysis and simulation experiments of different problem scales are carried out during the comparison with a Greedy algorithm to evaluate the performance of the proposed algorithm. Results indicate that the Lagrangian relaxation algorithm is able to achieve more satisfactory near-optimal solutions within an acceptable time.

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C11.

 Citation:

• Figure 1.  The scheduling process at cross-dock

Figure 2.  Several values of %gap (group2) based on the different value of slackness

Figure 3.  Values of %gap and %dev in group 2

Table 1.  Computer results for problems in group 1, b = 0.98, 0.95, and 0.90

 p=0.98 p=0.95 p=0.90 L G L G L G I #t×#d s IP LR %gap CPU UB %dev IP LR %gap CPU UB %dev IP LR %gap CPU UB %dev 1 15 1.683 1.683 5.32 0.55 1.815 10.43 1.98 1.98 4.97 0.56 2.187 10.43 1.643 1.643 5.27 0.46 1.99 11.99 2 20 1.701 1.701 4.82 0.5 1.89 8.37 2.1 2.1 4.38 0.33 2.278 8.45 1.785 1.785 5.39 0.42 1.754 8.03 3 4×2 30 1.729 1.729 3.44 0.53 2.004 15.27 2.059 2.059 3.55 0.42 2.358 14.54 1.997 1.997 3.59 0.51 1.769 14.69 4 15 2.56 2.56 9.55 0.66 2.45 14.81 2.56 2.56 9.27 0.68 2.816 14.52 2.765 2.765 9.83 0.84 3.013 14.96 5 20 2.26 2.26 8.15 0.8 3.064 13.02 2.659 2.659 7.03 0.8 3.225 12.76 2.872 2.872 6.89 0.8 2.838 13.4 6 5×3 30 2.498 2.498 10.55 0.65 2.648 12.76 2.602 2.602 9.02 0.8 3.152 12.76 2.862 2.862 11 0.96 3.089 12.89 7 15 2.709 2.709 6.58 1.59 3.954 26.35 3.078 3.078 6.33 1.61 4.163 26.62 2.924 2.924 6.46 1.07 3.83 27.95 8 20 3.108 3.108 4.32 1.64 3.533 25 3.205 3.205 4.32 1.06 4.257 24.27 2.66 2.66 4.62 1.33 4.087 23.06 9 6×3 30 2.495 2.495 7.55 1.6 3.735 26.32 3.08 3.08 6.29 1.02 4.016 26.06 2.957 2.957 6.54 1.27 4.257 27.1 10 15 3.31 3.31 4.76 1.92 4.153 13.37 3.755 3.988 4.21 2.35 4.72 13.37 4.068 4.068 4.04 1.88 4.153 12.84 11 20 3.425 3.624 6.35 1.93 4.337 14.81 3.89 3.897 4.96 1.91 4.518 15.11 4.155 4.17 6.05 2.38 3.433 15.87 12 7×3 30 3.257 3.471 3.69 3.13 3.747 21.32 3.572 3.732 3.55 2.66 4.625 21.98 3.375 3.471 3.41 3.19 4.163 22.2 13 15 3.18 3.381 7.79 5.86 4.848 29.61 3.58 3.636 6.04 7.1 5.051 30.53 3.09 3.09 7.61 7.1 3.788 30.84 14 20 3.155 3.301 6.23 4.89 4.847 29.92 3.42 3.628 6.23 7.41 5.049 30.53 3.171 3.301 6.17 4.94 3.786 29 15 7×4 30 3.178 3.204 6.83 5.38 4.262 32.8 3.595 3.641 5.38 8.41 5.014 31.24 3.285 3.386 6.62 8.41 4.061 32.49 16 15 3.65 3.826 5.76 4.4 5.089 24.08 4.058 4.159 5.7 4.27 5.472 24.08 3.588 3.701 5.81 5.34 5.472 25.28 17 20 3.425 3.425 5.58 5.79 5.329 21.76 4.117 4.228 5.03 4.45 5.438 22.91 4.489 4.608 5.53 5.57 4.894 23.14 18 8×3 30 3.785 3.85 6.41 8.54 4.745 22.79 4.095 4.184 5.57 10.05 5.214 23.49 4.258 4.435 7.19 8.37 4.432 24.19 19 15 3.455 3.485 4.57 8.09 5.375 35.21 3.986 4.1 4.76 7.03 5.973 36.3 3.698 3.772 4.57 7.03 5.973 35.94 20 20 3.576 3.678 5.81 6.36 4.802 34.09 4.168 4.18 4.76 7.64 5.856 33.42 3.259 3.344 5.09 9.17 6.09 33.09 21 8×4 30 3.385 3.428 6.14 9.16 5.446 32.42 4.15 4.18 4.76 11.33 5.856 33.42 3.857 3.929 4.52 11.33 5.739 33.09 Instance is short for $i$, $t$ for trucks, $d$ for doors, $s$ for the slackness of temporary storage capacity (%), $L$ for the Lagrangian relaxation algorithm, $G$ for the Greedy algorithm. The value of $IP, LP$ and $UB$ is in $10^5$.

Table 2.  Computer results for problems in group 2 (slackness = 10)

 Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm LR %gap CPU time UB %dev 1 9×3 4.759 5.21 18 5.965 18.8 2 9×4 4.856 5.28 19.76 6.382 24.5 3 9×5 4.661 4.38 30.13 6.8 39.5 4 10×3 5.527 5.25 42.36 6.876 14.43 5 10×4 5.595 4.76 15.57 7.014 21.56 6 10×5 5.055 5.75 44.57 7.609 43.35 7 11×5 6.017 7.86 77.65 8.618 31.41 8 11×6 5.997 9.09 80.49 9.149 38.69 9 15×6 8.223 9.09 177.84 12.43 37.39 10 15×7 8.21 7.42 124.02 13.09 47.64 11 20×10 10.89 9.91 265.06 20.73 71.41

Table 3.  Computer results for problems in group 2 (slackness = 15)

 Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm LR %gap CPU time UB %dev 1 9×3 4.742 5.17 24.5 5.892 19.3 2 9×4 4.813 4.97 22.69 6.382 24.5 3 9×5 4.559 5.65 36.25 6.66 40.72 4 10×3 5.456 5.09 40.71 6.674 16.1 5 10×4 5.195 4.76 31.97 7.142 30.92 6 10×5 5.355 5.3 42.97 7.609 35.32 7 11×5 6.017 6.54 55.32 8.618 33.86 8 11×6 5.6 7.45 91.46 9.149 41.4 9 15×6 8.403 8.26 125.77 12.43 35.68 10 15×7 8.237 6.65 81.64 13.18 49.35 11 20×10 10.64 8.26 164.22 20.69 68.47

Table 4.  Computer results for problems in group 2 (slackness = 20)

 Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm LR %gap CPU time UB %dev 1 9×3 5.035 4.53 18.16 6.003 13.12 2 9×4 4.764 5.32 27.23 6.173 29.83 3 9×5 4.758 6.02 26.69 6.899 34.3 4 10×3 5.466 4.92 29.03 6.674 16.1 5 10×4 5.087 5.56 27.07 7.142 32.45 6 10×5 5.075 4.9 40.41 7.609 42.79 7 11×5 6.037 7.41 62.67 8.618 32.18 8 11×6 5.777 7.41 62.09 9.139 46.64 9 15×6 8.012 7.41 133.29 12.4 36.94 10 15×7 8.045 5.82 159.65 13.22 45.71 11 20×10 10.85 7.41 226.27 20.73 66.9

Table 5.  Computer results for problems in group 2 (slackness = 30)

 Instances #trucks×#doors Lagrangian relaxation algorithm Greedy algorithm LR %gap CPU time UB %dev 1 9×3 4.76 4.8 17.01 5.965 19.3 2 9×4 4.647 5.08 22.76 6.108 30.38 3 9×5 4.684 3.9 22.59 6.8 39.5 4 10×3 5.943 4.9 35.42 6.344 6.74 5 10×4 5.375 4.76 42.1 7.082 26.54 6 10×5 5.315 4.76 47.71 7.609 36.34 7 11×5 6.057 4.76 50.29 8.618 35.51 8 11×6 5.817 6.54 77.44 9.149 46.99 9 15×6 8.221 6.54 114.18 12.37 40.67 10 15×7 8.527 4.29 148.43 13.3 47.33 11 20×10 10.79 5.66 302.54 23.68 70.76

Figures(3)

Tables(5)