Article Contents
Article Contents

# Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery

• * Corresponding author: Haoxun Chen and Bo Dai
• Freight bus is a new public transportation means for city logistics, and each freight bus can deliver and pick up goods at each customer/supplier location it passes. In this paper, we study the route planning problem of freight buses in an urban distribution system. Since each freight bus makes a tour visiting a set of pickup/delivery locations once at every given time interval in each day following a fixed route, the route planning problem can be considered a new variant of periodic vehicle routing problem with pickup and delivery. In order to solve the problem, a Mixed-Integer Linear Programming (MILP) model is formulated and an Adaptive Large Neighborhood Search (ALNS) algorithm is developed. The development of our algorithm takes into consideration specific characteristics of this problem, such as fixed route for each freight bus, possibly serving a demand in a later period but with a late service penalty, etc. The relevance of the mathematical model and the effectiveness of the proposed ALNS algorithm are proved by numerical experiments.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

 Citation:

• Figure 1.  City freighters in an urban distribution system

Figure 2.  Freight buses in an urban distribution system

Figure 3.  An example of freight bus lines

Figure 4.  The procedure framework of ALNS

Figure 5.  The average performances of CPLEX and ALNS ($M = 3$)

Figure 6.  The average performances of CPLEX and ALNS ($M = 5$)

Table 3.  Experimental results of small size instances

 Instances $Cplex_{Obj}$ LB $ALNS_{Obj}$ $Gap_{Cplex}$ $Gap_{ALNS}$ $Imp_{ALNS-Cplex}$ $CPU_{Cplex}$ $CPU_{ALNS}$ 7-3a 1067.1 1067.1 1067.1 0.00 0.00 0.00 86.3 7.9 7-3b 986.6 986.6 986.6 0.00 0.00 0.00 89.6 7.6 7-3c 1076.9 1076.9 1076.9 0.00 0.00 0.00 87.9 8.2 7-3d 962.0 962.0 962.0 0.00 0.00 0.00 87.6 8.7 7-3e 1005.8 1005.8 1005.8 0.00 0.00 0.00 87.5 7.9 7-5a 1984.1 1984.1 1984.1 0.00 0.00 0.00 257.3 19.7 7-5b 1945.1 1945.1 1945.1 0.00 0.00 0.00 262.1 20.3 7-5c 1887.0 1887.0 1887.0 0.00 0.00 0.00 258.2 21.9 7-5d 1940.4 1940.4 1940.4 0.00 0.00 0.00 259.3 19.8 7-5e 1896.6 1896.6 1896.6 0.00 0.00 0.00 260.3 20.3 13-3a 1459.9 1074.8 1197.0 35.83 11.37 18.01 3600 25.8 13-3b 1519.1 1089.3 1207.8 39.46 10.88 20.49 3600 25.6 13-3c 1800.1 1342.1 1530.6 34.13 14.05 14.97 3600 26.9 13-3d 1397.4 1007.7 1123.6 38.67 11.50 19.59 3600 26.3 13-3e 2878.7 1848.4 2086.5 55.74 12.88 27.52 3600 27.1 13-5a 3761.2 2527.9 2847.0 48.79 12.62 24.30 3600 40.3 13-5b 3232.8 2264.2 2673.5 42.78 18.08 17.30 3600 39.7 13-5c 3329.6 2220.5 2607.1 49.95 17.41 21.70 3600 42.3 13-5d 3402.7 2238.7 2581.8 51.99 15.33 24.13 3600 41.2 13-5e 3405.6 2427.8 2856.6 40.28 17.66 16.12 3600 40.3

Table 1.  Parameter Setting of the ALNS for different sizes of instances

 Parameter Small instances Medium instances Large instances Maximum iterations number of ALNS $(N)$ 25000 30000 35000 The roulette parameter $(r)$ 0.1 0.1 0.1 The score increment of generating a new best solution (Q1) 5 5 5 The score increment of generating a better solution (Q2) 3 3 3 The score increment of generating a worse solution (Q3) 1 1 1 Initial temperature parameter $\left(P_{\text {init}}\right)$ 100 120 120 Cooling rate $(\mathrm{h})$ 0.992 0.994 0.996 Removal fraction $(\rho)$ 0.2 0.2 0.3 Noise parameter $(\mathrm{u})$ 0.1 0.1 0.1

Table 2.  Performance indicators

 Abbreviation Definition $Cplex_{Obj}$ The best feasible objective value found by CPLEX in a preset running time LB The lower bound produced by CPLEX in a preset running time $ALNS_{Obj}$ The best feasible objective value obtained by ALNS after a preset number of iterations $Gap_{Cplex}$ The gap between $Cplex_{Obj}$ and LB, which is defined as ($Cplex_{Obj}$- LB)/LB*100 $Gap_{ALNS}$ The gap between $ALNS_{Obj}$ and LB, which is defined as ($ALNS_{Obj}$- LB)/ LB*100 $Imp_{ALNS-Cplex}$ The improvement (reduction) of $ALNS_{Obj}$ over $Cplex_{Obj}$, which is defined as ($Cplex_{Obj}$- $ALNS_{Obj}$)/ $Cplex_{Obj}$*100 $CPU_{Cplex}$ The CPU time (second) of CPLEX $CPU_{ALNS}$ The CPU time (second) of ALNS

Table 4.  Experimental results of medium size instances

 Instances $Cplex_{Obj}$ LB $ALNS_{Obj}$ $Gap_{Cplex}$ $Gap_{ALNS}$ $Imp_{ALNS-Cplex}$ $CPU_{Cplex}$ $CPU_{ALNS}$ 20-3a 2884.5 1966.6 2161.4 46.67 9.91 25.07 5400 135.7 20-3b 3014.2 2101.2 2251.3 43.45 7.14 25.31 5400 140.7 20-3c 3058.2 2069.5 2268.2 47.77 9.60 25.83 5400 133.2 20-3d 2649.0 1807.7 2013.2 46.54 11.37 24.00 5400 135.7 20-3e 2904.7 1949.3 2141.2 49.01 9.84 26.29 5400 134.2 20-5a 5161.4 2951.8 3365.4 74.86 14.01 34.80 5400 216.4 20-5b 4527.3 2627.2 2992.6 72.32 13.91 33.90 5400 203.5 20-5c 4758.4 2698.5 3065.1 76.34 13.59 35.59 5400 218.8 20-5d 4474.2 2556.1 2852.5 75.04 11.60 36.25 5400 199.5 20-5e 4522.8 2573.0 2927.5 75.78 13.78 35.27 5400 220.3 30-3a 4964.2 2664.8 3003.9 86.29 12.73 39.49 7200 289.3 30-3b 5401.6 2922.8 3321.7 84.81 13.65 38.50 7200 276.8 30-3c 4688.7 2520.6 2860.1 86.02 13.47 39.00 7200 296.3 30-3d 4540.4 2381.9 2728.1 90.62 14.53 39.92 7200 295.3 30-3e 4654.2 2502.6 2844.2 85.97 13.65 38.89 7200 287.6 30-5a - 4325.6 5167.3 - 19.46 - 7200 356.7 30-5b 8140.4 4084.0 4859.6 99.32 18.99 40.30 7200 320.7 30-5c - 4390.0 5249.4 - 19.58 - 7200 364.3 30-5d - 3973.0 4733.7 - 19.15 - 7200 378.9 30-5e - 4154.9 4938.6 - 18.86 - 7200 352.1 40-3a 6214.3 2835.6 3371.3 119.15 18.89 45.75 10800 478.7 40-3b 6389.9 2832.7 3372.6 125.58 19.06 47.22 10800 480.3 40-3c - 2917.5 3469.4 - 18.92 - 10800 437.9 40-3d 6072.1 2832.0 3381.9 114.41 19.42 44.30 10800 509.3 40-3e 6112.3 3008.5 3590.5 103.17 19.35 41.26 10800 469.5 40-5a - 4824.4 6020.8 - 24.80 - 10800 597.3 40-5b - 5065.7 6325.8 - 24.88 - 10800 600.1 40-5c - 4944.1 6088.1 - 23.14 - 10800 623.5 40-5d - 4823.4 5940.9 - 23.17 - 10800 591.2 40-5e - 4664.0 5764.5 - 23.60 - 10800 589.7

Table 5.  Experimental results of large size instances

 Instances $Cplex_{Obj}$ LB $ALNS_{Obj}$ $Gap_{Cplex}$ $Gap_{ALNS}$ $Imp_{ALNS-Cplex}$ $CPU_{Cplex}$ $CPU_{ALNS}$ 60-3a 11510.5 4550.1 5313.7 152.97 16.78 53.84 14400 979.3 60-3b - 5140.4 5971.6 - 16.17 - 14400 1000.1 60-3c 11918.4 4742.3 5507.3 151.32 16.13 53.79 14400 1005.3 60-3d - 4340.2 5106.7 - 17.66 - 14400 989.3 60-3e 11509.7 4694.8 5494.9 145.16 17.04 52.26 14400 996.1 60-5a - 8123.9 9972.9 - 22.76 - 14400 1421.6 60-5b - 7669.4 9493.1 - 23.78 - 14400 1432.3 60-5c - 8041.2 9809.9 - 22.00 - 14400 1410.5 60-5d - 8318.1 10172.5 - 22.29 - 14400 1396.3 60-5e - 8372.7 10135.2 - 21.05 - 14400 1389.3 80-3a - 6288.6 7419.3 - 17.98 - 18000 1523.4 80-3b - 5992.0 7135.8 - 19.09 - 18000 1612.3 80-3c - 6431.5 7683.1 - 19.46 - 18000 1496.8 80-3d - 5785.2 6836.7 - 18.18 - 18000 1527.4 80-3e - 6104.0 7264.1 - 19.01 - 18000 1559.3 80-5a - 8670.0 10889.2 - 25.60 - 18000 1963.2 80-5b - 8260.9 10207.5 - 23.56 - 18000 2001.3 80-5c - 8855.8 11163.3 - 26.06 - 18000 1989.7 80-5d - 8611.5 10627.6 - 23.41 - 18000 1967.3 80-5e - 8596.7 10703.1 - 24.50 - 18000 1995.3

Table 6.  The average performances of the two solution methods

 Instances $Gap_{Cplex}$ $Gap_{ALNS}$ $Imp_{ALNS-Cplex}$ $CPU_{Cplex}$ $CPU_{ALNS}$ 7-3 0 0 0 87.78 8.06 7-5 0 0 0 259.44 20.4 13-3 40.76 12.14 20.12 3600 26.3 13-5 46.76 16.22 20.71 3600 40.76 20-3 46.69 9.57 25.30 5400 135.9 20-5 74.87 13.38 35.16 5400 211.7 30-3 86.74 13.61 39.16 7200 289.1 30-5 99.32 19.21 40.30 7200 354.5 40-3 115.58 19.13 44.63 10800 475.1 40-5 - 23.92 - 10800 600.4 60-3 149.82 16.76 53.30 14400 994.0 60-5 - 22.38 - 14400 1410.0 80-3 - 18.74 - 18000 1543.8 80-5 - 24.63 - 18000 1983.4

Table 7.  The comparison of the average costs of the two systems

 Instances System without Freight bus System with Freight bus Cost Saving in percentage Small size instances 7-3 1237.50 1019.7 17.6 7-5 2363.04 1930.6 18.3 13-3 1779.70 1429.1 19.7 13-5 3400.00 2713.2 20.2 Medium size instances 20-3 2818.08 2167.1 23.1 20-5 3938.60 3040.6 22.8 30-3 3909.40 2951.6 24.5 30-5 6635.24 4989.7 24.8 40-3 4625.98 3437.1 25.7 40-5 8168.02 6028 26.2 Large size instances 60-3 7749.36 5478.8 29.3 60-5 14186.98 9916.7 30.1 80-3 10945.48 7267.8 33.6 80-5 16565.84 10718.1 35.3

Figures(6)

Tables(7)