\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

The split delivery vehicle routing problem with time windows and three-dimensional loading constraints

Abstract / Introduction Full Text(HTML) Figure(9) / Table(5) Related Papers Cited by
  • This paper presents complex variants of the vehicle routing problem: the Vehicle Routing Problem with Time Windows and Three-Dimensional Loading Constraints (3L-VRPTW) and the Split Delivery Vehicle Routing Problem with Time Windows and Three-Dimensional Loading Constraints (3L-SDVRPTW). The difference between the two problems is whether a customer can be visited in two or more tours. Under the conditions of satisfying customer demands and loading constraints, the 3L-VRPTW model and the 3L-SDVRPTW model are constructed with the aim of minimizing transportation costs. To efficiently solve the above problems, a two-layer method is proposed in this study, including a routing stage and a packing stage. The Adaptive Large Neighborhood Search algorithm based on the Metropolis criterion is used to obtain the vehicle routing. The genetic algorithm is used to solve the packing stage, ensuring that the goods are packed in a way that minimizes pre-movements. The proposed algorithms are tested on different instances, verifying their effectiveness. Additionally, numerical experiments are conducted using instances with different customer distributions. The results show that when customers are located in multiple small areas, split delivery it distribution can significantly reduce penalty costs and be more economical.

    Mathematics Subject Classification: Primary: 90B06, 90B40; Secondary: 90C31.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The placement of goods in the vehicle

    Figure 2.  Diagram of blocked goods during loading and unloading

    Figure 3.  Two-layer algorithm flow chart

    Figure 4.  Split delivery Coding Diagram

    Figure 5.  Customer repeat delivery route adjustment

    Figure 6.  Placement points created when goods are placed

    Figure 7.  Fitness calculation

    Figure 8.  Mutation operation

    Figure 9.  Crossover operation

    Table 1.  Parameters for packing and routing

    Parameter Meaning Value
    $ \alpha $ the importance of the time window width of node $ j $ in route selection $ 2 $
    $ \beta $ the importance of the travel distance from node $ i $ to node $ j $ in route selection $ 5 $
    $ \rho $ the attenuation coefficient in ALNS weights update method $ 0.4 $
    $ w(h) $ initial operator weight in ALNS weights update method $ 10 $
    $ T $ start temperature in metropolis criterion $ 6000 $
    $ \varphi $ cooling rate in metropolis criterion $ 0.8 $
    $ ethnic\_num $ Genetic algorithm population size $ 400 $
    $ mutation\_n $ Genetic algorithm mutation times MAX$ (n/10, 3) $
    $ crossover\_n $ Genetic algorithm crossover times MAX$ (n/10, 3) $
     | Show Table
    DownLoad: CSV

    Table 2.  Parameters for packing and routing

    Zhang et al. (2017) results Our results
    Instance v DC CPU(avg.) v DC CPU(avg.)
    VRPTWP01 5 323.33 352.10 4 290.52 6.34
    VRPTWP02 5 295.29 232.28 5 293.29 6.29
    VRPTWP03 5 303.60 430.27 5 295.68 21.20
    VRPTWP04 6 380.19 371.88 6 380.13 27.45
    VRPTWP05 7 416.35 545.72 6 322.97 20.34
    VRPTWP06 7 408.99 306.38 6 382.53 19.92
    VRPTWP07 7 407.91 604.70 5 386.59 25.11
    VRPTWP08 7 425.90 637.32 5 392.69 31.36
    VRPTWP09 8 530.50 549.60 8 478.84 33.10
    VRPTWP10 10 668.74 956.40 8 635.60 69.79
    VRPTWP11 11 619.34 1032.98 8 566.63 77.20
    VRPTWP12 9 688.60 671.37 9 616.36 54.50
    VRPTWP13 11 626.72 1347.24 8 606.10 58.25
    VRPTWP14 8 765.37 1221.68 9 593.15 80.10
    VRPTWP15 12 713.23 1091.86 9 688.37 48.58
    VRPTWP16 11 746.67 429.32 11 722.70 72.30
    VRPTWP17 15 994.28 484.99 14 1021.67 86.51
    VRPTWP18 18 1206.51 636.18 12 1038.36 116.30
    VRPTWP19 16 1211.99 783.59 13 1062.29 379.91
    VRPTWP20 24 1644.56 1512.11 18 1637.50 513.38
    VRPTWP21 23 1603.88 2174.74 19 1592.08 579.54
    VRPTWP22 26 1811.19 2170.98 20 1695.83 560.10
    VRPTWP23 24 1654.13 1950.79 18 1487.11 593.00
    VRPTWP24 21 1644.55 1745.54 18 1636.60 676.32
    VRPTWP25 27 1836.02 2877.48 23 1909.72 742.78
    VRPTWP26 32 2144.47 3250.49 28 2136.91 762.43
    VRPTWP27 28 2002.63 3037.26 25 2061.50 669.30
     | Show Table
    DownLoad: CSV

    Table 3.  The results of 3L-VRPTW and 3L-SDVRPTW are compared under the C-type distribution of customers

    3LP- VRPTW 3LP- SDVRPTW
    TTC v DC PC TTC v DC PC GAP1 GAP2 GAP3
    RB1-C101 4, 324.74 9 1255.74 1269 3727.57 11 1151.07 376.5 16.02% 9.09% 237.05%
    RB1-C102 3, 988.68 10 1269.18 719.5 3556.44 9 1118.44 638 12.15% 13.48% 12.77%
    RB1-C103 3, 181.09 9 1024.59 356.5 3313.51 9 1304.51 209 -4.00% -21.46% 70.57%
    RB1-C104 2, 861.83 9 922.83 139 3154.42 9 1204.92 149.5 -9.28% -23.41% -7.02%
    RB1-C105 4, 171.72 9 1226.22 1145.5 3772.11 10 1305.11 467 10.59% -6.04% 145.29%
    RB1-C106 4, 427.65 9 1158.15 1469.5 3819.70 11 1340.70 279 15.92% -13.62% 426.70%
    RB1-C107 3, 995.31 9 1265.31 930 3747.56 11 1477.06 70.5 6.61% -14.34% 1219.15%
    RB1-C108 3, 557.61 9 1203.11 554.5 3408.97 10 1262.47 146.5 4.36% -4.70% 278.50%
    RB1-C109 3, 414.74 9 1159.74 455 3341.28 9 1448.78 92.5 2.20% -19.95% 391.89%
    RB1-C201 10, 714.41 10 1104.91 7609.5 8248.71 9 2286.71 4162 29.89% -51.68% 82.83%
    RB1-C202 8, 775.77 9 1384.27 5591.5 7748.01 9 2484.01 3464 13.26% -44.27% 61.42%
    RB1-C203 7, 147.95 9 1425.95 3922 7585.58 9 2641.58 2944 -5.77% -46.02% 33.22%
    RB1-C204 5, 227.92 9 1280.42 2147.5 5174.23 9 2194.23 1180 1.04% -41.65% 81.99%
    RB1-C205 9, 654.78 10 1263.78 6391 9494.36 9 2155.36 5539 1.69% -41.37% 15.38%
    RB1-C206 10, 134.18 9 1158.68 7175.5 7705.13 9 2559.13 3346 31.52% -54.72% 114.45%
    RB1-C207 9, 213.50 10 1279.50 5934 7744.87 9 2585.87 3359 18.96% -50.52% 76.66%
    RB1-C208 9, 082.69 10 1402.69 5680 7637.01 9 2579.51 3057.5 18.93% -45.62% 85.77%
     | Show Table
    DownLoad: CSV

    Table 4.  The results of 3L-VRPTW and 3L-SDVRPTW are compared under the R-type distribution of customers

    3LP- VRPTW 3LP- SDVRPTW
    TTC v DC PC TTC v DC PC GAP1 GAP2 GAP3
    RB1-R101 3, 947.32 11 1112.32 635 4213.90 13 1191.90 422 -6.33% -6.68% 50.47%
    RB1-R102 3, 564.88 11 1094.38 270.5 3930.91 11 1093.41 637.5 -9.31% 0.09% -57.57%
    RB1-R103 3, 430.19 11 1027.19 203 3942.55 12 1118.05 424.5 -13.00% -8.13% -52.18%
    RB1-R104 3, 276.00 10 1028.00 248 3636.57 12 1000.57 236 -9.92% 2.74% 5.08%
    RB1-R105 3, 408.90 10 1060.40 348.5 3850.58 12 1198.58 252 -11.47% -11.53% 38.29%
    RB1-R106 3, 124.93 10 954.43 170.5 3561.43 11 1040.93 320.5 -12.26% -8.31% -46.80%
    RB1-R107 2, 894.89 9 923.89 171 3200.49 10 943.99 256.5 -9.55% -2.13% -33.33%
    RB1-R108 2, 769.42 9 931.92 37.5 3279.55 11 1014.05 65.5 -15.56% -8.10% -42.75%
    RB1-R109 3, 060.11 10 906.61 153.5 3587.60 12 1157.60 30 -14.70% -21.68% 411.67%
    RB1-R110 2, 988.27 9 966.77 221.5 3797.84 13 1114.84 83 -21.32% -13.28% 166.87%
    RB1-R111 2, 845.27 9 901.77 143.5 3413.99 11 954.49 259.5 -16.66% -5.52% -44.70%
    RB1-R112 2, 725.15 9 862.15 63 3309.30 11 1043.30 66 -17.65% -17.36% -4.55%
    RB1-R201 4, 844.66 9 1572.16 1472.5 4935.85 9 2381.35 754.5 -1.85% -33.98% 95.16%
    RB1-R202 4, 254.56 9 1471.56 983 4513.62 9 2041.12 672.5 -5.74% -27.90% 46.17%
    RB1-R203 3, 914.02 9 1425.02 689 4047.08 9 1813.08 434 -3.29% -21.40% 58.76%
    RB1-R204 3, 359.97 9 1263.97 296 3619.00 9 1588.00 231 -7.16% -20.40% 28.14%
    RB1-R205 4, 599.70 9 1577.20 1222.5 4817.93 9 2176.43 841.5 -4.53% -27.53% 45.28%
    RB1-R206 3, 926.54 9 1513.54 613 4358.62 9 2009.12 549.5 -9.91% -24.67% 11.56%
    RB1-R207 3, 794.08 9 1409.58 584.5 4231.71 9 1904.71 527 -10.34% -26.00% 10.91%
    RB1-R208 3, 267.91 9 1260.41 207.5 3951.00 9 2001.00 150 -17.29% -37.01% 38.33%
    RB1-R209 4, 154.16 9 1500.66 853.5 4542.32 9 2164.32 578 -8.55% -30.66% 47.66%
    RB1-R210 4, 291.22 9 1619.72 871.5 4360.44 9 1906.94 653.5 -1.59% -15.06% 33.36%
    RB1-R211 3, 927.77 9 1409.27 718.5 4134.56 9 2000.06 334.5 -5.00% -29.54% 114.80%
     | Show Table
    DownLoad: CSV

    Table 5.  The results of 3L-VRPTW and 3L-SDVRPTW are compared under the RC-type distribution of customers

    3LP- VRPTW 3LP- SDVRPTW
    TTC v DC PC TTC v DC PC GAP1 GAP2 GAP3
    RB1-R101 3, 947.32 11 1112.32 635 4213.90 13 1191.90 422 -6.33% -6.68% 50.47%
    RB1-R102 3, 564.88 11 1094.38 270.5 3930.91 11 1093.41 637.5 -9.31% 0.09% -57.57%
    RB1-R103 3, 430.19 11 1027.19 203 3942.55 12 1118.05 424.5 -13.00% -8.13% -52.18%
    RB1-R104 3, 276.00 10 1028.00 248 3636.57 12 1000.57 236 -9.92% 2.74% 5.08%
    RB1-R105 3, 408.90 10 1060.40 348.5 3850.58 12 1198.58 252 -11.47% -11.53% 38.29%
    RB1-R106 3, 124.93 10 954.43 170.5 3561.43 11 1040.93 320.5 -12.26% -8.31% -46.80%
    RB1-R107 2, 894.89 9 923.89 171 3200.49 10 943.99 256.5 -9.55% -2.13% -33.33%
    RB1-R108 2, 769.42 9 931.92 37.5 3279.55 11 1014.05 65.5 -15.56% -8.10% -42.75%
    RB1-R109 3, 060.11 10 906.61 153.5 3587.60 12 1157.60 30 -14.70% -21.68% 411.67%
    RB1-R110 2, 988.27 9 966.77 221.5 3797.84 13 1114.84 83 -21.32% -13.28% 166.87%
    RB1-R111 2, 845.27 9 901.77 143.5 3413.99 11 954.49 259.5 -16.66% -5.52% -44.70%
    RB1-R112 2, 725.15 9 862.15 63 3309.30 11 1043.30 66 -17.65% -17.36% -4.55%
    RB1-R201 4, 844.66 9 1572.16 1472.5 4935.85 9 2381.35 754.5 -1.85% -33.98% 95.16%
    RB1-R202 4, 254.56 9 1471.56 983 4513.62 9 2041.12 672.5 -5.74% -27.90% 46.17%
    RB1-R203 3, 914.02 9 1425.02 689 4047.08 9 1813.08 434 -3.29% -21.40% 58.76%
    RB1-R204 3, 359.97 9 1263.97 296 3619.00 9 1588.00 231 -7.16% -20.40% 28.14%
    RB1-R205 4, 599.70 9 1577.20 1222.5 4817.93 9 2176.43 841.5 -4.53% -27.53% 45.28%
    RB1-R206 3, 926.54 9 1513.54 613 4358.62 9 2009.12 549.5 -9.91% -24.67% 11.56%
    RB1-R207 3, 794.08 9 1409.58 584.5 4231.71 9 1904.71 527 -10.34% -26.00% 10.91%
    RB1-R208 3, 267.91 9 1260.41 207.5 3951.00 9 2001.00 150 -17.29% -37.01% 38.33%
    RB1-R209 4, 154.16 9 1500.66 853.5 4542.32 9 2164.32 578 -8.55% -30.66% 47.66%
    RB1-R210 4, 291.22 9 1619.72 871.5 4360.44 9 1906.94 653.5 -1.59% -15.06% 33.36%
    RB1-R211 3, 927.77 9 1409.27 718.5 4134.56 9 2000.06 334.5 -5.00% -29.54% 114.80%
     | Show Table
    DownLoad: CSV
  • [1] E. E. Bischoff and M. S. W. Ratcliff, Issues in the development of approaches to container loading, Omega, 23 (1995), 377-390.  doi: 10.1016/0305-0483(95)00015-G.
    [2] A. Bortfeldt, A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints, Computers & Operations Research, 39 (2012), 2248-2257.  doi: 10.1016/j.cor.2011.11.008.
    [3] A. Bortfeldt and J. Homberger, Packing first routing second-a heuristic for the vehicle routing and loading problem, Computers & Operations Research, 40 (2013), 873-885.  doi: 10.1016/j.cor.2012.09.005.
    [4] A. Bortfeldt and J. Yi, The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints, European Journal of Operational Research, 282 (2020), 545-558.  doi: 10.1016/j.ejor.2019.09.024.
    [5] S. CeschiaA. Schaerf and T. Stützle, Local search techniques for a routing-packing problem, Computers & Industrial Engineering, 66 (2013), 1138-1149.  doi: 10.1016/j.cie.2013.07.025.
    [6] J.-F. CordeauG. LaporteP. Legato and L. Moccia, Models and tabu search heuristics for the berth-allocation problem, Transportation Science, 39 (2005), 443-556.  doi: 10.1287/trsc.1050.0120.
    [7] G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, Management Science, 6 (1959), 80-91.  doi: 10.1287/mnsc.6.1.80.
    [8] M. Dror and P. Trudeau, Savings by split delivery routing, Transportation Science, 23 (1989), 141-145. 
    [9] L. Fanjul-PeyroR. Ruiz and F. Perea, Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times, Computers & Operations Research, 101 (2019), 173-182.  doi: 10.1016/j.cor.2018.07.007.
    [10] G. FuellererK. F. DoernerR. F. Hartl and M. Iori, Metaheuristics for vehicle routing problems with three-dimensional loading constraints, European Journal of Operational Research, 201 (2010), 751-759.  doi: 10.1016/j.ejor.2009.03.046.
    [11] M. GendreauM. IoriG. Laporte and S. Martello, A tabu search algorithm for a routing and container loading problem, Transportation Science, 40 (2006), 342-350. 
    [12] J. A. George and D. F. Robinson, A heuristic for packing boxes into a container, Computers & Operations Research, 7 (1980), 147-156.  doi: 10.1016/0305-0548(80)90001-5.
    [13] Z.-H. HuY. ZhaoS. Tao and Z.-H. Sheng, Finished-vehicle transporter routing problem solved by loading pattern discovery, Ann Oper Res, 234 (2015), 37-56.  doi: 10.1007/s10479-014-1777-1.
    [14] T. IbarakiS. ImahoriM. KuboT. MasudaT. Uno and M. Yagiura, Effective local search algorithms for routing and scheduling problems with general time-window constraints, Transportation Science, 39 (2005), 206-232.  doi: 10.1287/trsc.1030.0085.
    [15] L. JunqueiraJ. F. Oliveira and R. Morabito, An optimization model for the vehicle routing problem with practical three-dimensional loading constraints, International Transactions in Operational Research, 20 (2013), 645-666.  doi: 10.1111/j.1475-3995.2012.00872.x.
    [16] K. KangI. Moon and H. Wang, A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem, Applied Mathematics and Computation, 219 (2012), 1287-1299.  doi: 10.1016/j.amc.2012.07.036.
    [17] S. P. Ladany and A. Mehrez, Optimal routing of a single vehicle with loading and unloading constraints, Transportation Planning and Technology, 8 (1984), 301-306.  doi: 10.1080/03081068408717261.
    [18] B. MahvashA. Awasthi and S. Chauhan, A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints, International Journal of Production Research, 55 (2017), 1730-1747. 
    [19] D. Männel and A. Bortfeldt, Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban, European Journal of Operational Research, 264 (2018), 119-137.  doi: 10.1016/j.ejor.2017.05.034.
    [20] A. Moura, A model-based heuristic to the vehicle routing and loading problem, International Transactions in Operational Research, 26 (2019), 888-907.  doi: 10.1111/itor.12586.
    [21] A. Moura and J. F. Oliveira, An integrated approach to the vehicle routing and container loading problems, OR Spectrum, 31 (2009), 775-800.  doi: 10.1007/s00291-008-0129-4.
    [22] S. PaceA. TurkyI. Moser and A. Aleti, Distributing fibre boards: A practical application of the heterogeneous fleet vehicle routing problem with time windows and three-dimensional loading constraints, Procedia Computer Science, 51 (2015), 2257-2266.  doi: 10.1016/j.procs.2015.05.382.
    [23] H. PollarisK. BraekersA. CarisG. K. Janssens and S. Limbourg, Iterated local search for the capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints, Networks, 69 (2017), 304-316.  doi: 10.1002/net.21738.
    [24] M. RajaeiG. Moslehi and M. Reisi-Nafchi, The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale, European Journal of Operational Research, 299 (2022), 706-721.  doi: 10.1016/j.ejor.2021.08.025.
    [25] S. ReilA. Bortfeldt and L. Mönch, Heuristics for vehicle routing problems with backhauls time windows and 3D loading constraints, European Journal of Operational Research, 266 (2018), 877-894.  doi: 10.1016/j.ejor.2017.10.029.
    [26] S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472.  doi: 10.1287/trsc.1050.0135.
    [27] P. Shaw, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing, Problems, Springer, Berlin, Heidelberg, 1999. doi: 10.1007/3-540-49481-2_30.
    [28] M. M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operations Research, 35 (1987), 254-265.  doi: 10.1287/opre.35.2.254.
    [29] M. TangB. JiX. Fang and S. S. Yu, Discretization-Strategy-Based Solution for Berth Allocation and Quay Crane Assignment Problem, Journal of Marine Science and Engineering, 10 (2022), 495.  doi: 10.3390/jmse10040495.
    [30] Y. Tao and F. Wang, An effective tabu search approach with improved loading algorithms for the 3L-CVRP, Computers & Operations Research, 55 (2015), 127-140.  doi: 10.1016/j.cor.2013.10.017.
    [31] C. A. Vega-MejíaJ. R. Montoya-Torres and S. M. N. Islam, A nonlinear optimization model for the balanced vehicle routing problem with loading constraints, International Transactions in Operational Research, 26 (2019), 794-835.  doi: 10.1111/itor.12570.
    [32] L. WeiZ. Zhang and A. Lim, An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with three-dimensional loading constraints, IEEE Computational Intelligence Magazine, 9 (2014), 18-30.  doi: 10.1109/MCI.2014.2350933.
    [33] J. Yi and A. Bortfeldt, The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery-a case study, Operations Research Proceedings, 282 (2020), 545-558.  doi: 10.1016/j.ejor.2019.09.024.
    [34] E. E. ZachariadisC. D. Tarantilis and C. T. Kiranoudis, The Pallet-Packing Vehicle Routing Problem, Transportation Science, 4 (2012), 341-358.  doi: 10.1287/trsc.1110.0373.
    [35] D. ZhangS. CaiF. YeY.-W. Si and T. T. Nguyen, A hybrid algorithm for a vehicle routing problem with realistic constraints, Information Sciences, 394/395 (2017), 167-182.  doi: 10.1016/j.ins.2017.02.028.
    [36] Z. ZhangL. Wei and A. Lim, An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints, Transportation Research Part B: Methodological, 82 (2015), 20-35.  doi: 10.1016/j.trb.2015.10.001.
  • 加载中

Figures(9)

Tables(5)

SHARE

Article Metrics

HTML views(8575) PDF downloads(265) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return