Distribution Routing Problem with Time Window Under
Constraint of Pallet Loading

doi:10.16097/j.cnki.1009-6744.2023.06.026

Abstract

Abstract: To address issues such as chaotic delivery, this paper introduces pallets with adjustable support structure heights as carriers for loading and unloading in delivery services. Firstly, we design a pallet loading scheme inspired by the "wall building" theory and propose a route optimization strategy for delivery vehicles considering the constraint of three-dimensional pallet loading. We then formulate a two-objective optimization model that seeks for the highest average vehicle loading rate and the lowest total cost, which substitute the loading efficiency into the time cost. A solution algorithm, called 3DRP (Three-Dimensional Routing with Pallet), is designed, which combines the route optimization strategy with the constraint of three-dimensional pallet loading. To verify the effectiveness of our method, we test it on the LOH & NEE three-dimensional loading example, achieving a loading rate of 68.2%. Moreover, we validate our method using data from an express company in Chongqing, which shows that our method can achieve an average vehicle loading rate of 83.02% with no time penalty costs on some routes. By comparing our proposed method with the traditional 3D loading scheme, we conclude that the optimization of three-dimensional packing of express can balance the high loading rate of vehicles, reduce time and penalty costs by 97.5%, and improve vehicle utilization.

Key words: logistics engineering, path optimization, 3DRP algorithm, vehicle loading rate

摘要： 针对快递码放混乱等问题，本文引入可调节支撑结构高度的托盘作为装卸载体进行配送服务。首先，设计基于“砌墙”理论的托盘装载模式，提出托盘三维装载约束下配送车辆路径优化方案；其次，将装卸效率代入配送时间成本，构建平均车辆装载率最高和总成本最低的双目标优化模型；然后，结合托盘三维装载约束下配送车辆路径优化方案，设计托盘装载路径算法(Three-Dimensional Routing with Pallet, 3DRP)，并利用 LN(LOH & NEE) 三维装载算例进行验证，得到68.2%的装载率，验证了其在快递配送问题中的有效性；最后，本文对重庆市某快递公司的配送数据进行实例验证，方案最终结果显示，本文方法可以做到平均车辆装载率83.02%，且部分路径可以做到0时间惩罚成本。通过本文方案与传统三维装载方案的对比分析可知，将托盘作为载体进行快递三维装箱的优化可以兼顾车辆高装载率，并节约97.5%的时间惩罚成本，提高车辆利用率。

关键词: 物流工程, 路径优化, 托盘装载路径算法, 车辆装载率

CLC Number:

TP18

LIU Yong, YUE Zhi-cheng, WANG Yong. Distribution Routing Problem with Time Window Under Constraint of Pallet Loading[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(6): 262-273.

刘永, 岳志城, 王勇. 托盘装载约束下带时间窗的配送车辆路径优化研究[J]. 交通运输系统工程与信息, 2023, 23(6): 262-273.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/10.16097/j.cnki.1009-6744.2023.06.026

http://www.tseit.org.cn/EN/Y2023/V23/I6/262

References

[1] GEORGE J A, ROBINSON D F. A heuristic for packing boxes into a container[J]. Computers & Operations Research, 1980, 7(3): 147-156.

[2] 崔会芬, 许佳瑜, 朱鸿国, 等. 基于改进遗传算法的三维单箱装箱问题研究[J]. 工业工程与管理, 2018, 23 (1): 86-89. [CUI H F, XU J Y, ZHU H G, et al. Study on three dimensional single box-packing based on improved genetic algorithm[J]. Industrial Engineering and Management, 2018, 23(1): 86-89.]

[3] EL-ASHMAWI W H, ABD ELMINAAM D S. A modified squirrel search algorithm based on improved best fit heuristic and operator strategy for bin packing problem [J]. Applied Soft Computing, 2019, 82: 105565.

[4] 李俊, 张煜, 计三有, 等. 集装箱船舶装箱排序问题的两阶段算法[J]. 交通运输系统工程与信息, 2017, 17 (1): 183-190. [LI J, ZHANG Y, JI S Y, et al. Two-phase algorithm for containership sequencing and bin packing problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(1): 183-190.]

[5] GZARA F, ELHEDHLI S, YILDIZ B C. The pallet loading problem: Three-dimensional bin packing with practical constraints[J]. European Journal of Operational Research, 2020, 287(3): 1062-1074.

[6] 杨玉冰, 杨松坡. 基于列生成和分支定界算法的两阶段二次装箱问题[J/OL]. 计算机集成制造系统, (2022- 05- 26) [2023- 07- 06]. http://kns.cnki.net/kcms/detail/ 11.5946.TP.20221011.1404.002.html. [YANG Y B, YANG S P. Two-stage quadratic packing problem based on column generation and branch and bound algorithm [J]. Computer Integrated Manufacturing Systems, (2022- 05- 26) [2023- 07- 06]. http://kns.cnki.net/kcms/detail/ 11.5946.TP.20221011.1404.002.html.]

[7] GENDREAU M, IORI M, LAPORTE G, et al. A tabu search algorithm for a routing and container loading problem[J]. Transportation Science, 2006, 40(3): 342- 350.

[8] CHEN Z, YANG M, GUO Y, et al. The split delivery vehicle routing problem with three-dimensional loading and time Windows constraints[J]. Sustainability, 2020, 12 (17): 6987.

[9] BORTFELDT A, YI J. The split delivery vehicle routing problem with three-dimensional loading constraints[J]. European Journal of Operational Research, 2019, 282(2): 545-558.

[10] 杜博文, 张英贵, 刘春君, 等. 带三维装载和一对一取送约束的车辆路径优化研究[J]. 工业工程与管理, 2022, 27(2): 35-44. [DU B W, ZHANG Y G, LIU C J, et al. Optimization one-to-one pickup and delivery vehicle routing problem with three-dimensional loading constraints[J]. Industrial Engineering and Management, 2022, 27(2): 35-44.]

[11] 王勇, 魏远晗, 蒋琼, 等. 三维装载约束下基于运输资源共享的车辆路径问题 [J]. 计算机集成制造系统, 2023, 29(9): 3153-3170. [WANG Y, WEI Y H, JIANG Q, et al. Vehicle routing problem based on transportation resource sharing under three-dimensional loading constraints[J]. Computer Integrated Manufacturing Systems, 2023, 29(9): 3153-3170.]

[12] WANG Y, YUAN Y Y, GUAN X Y, et al. Collaborative two-echelon multicenter vehicle routing optimization based on state-spaced-time network representation[J]. Journal of Cleaner Production, 2020, 258: 120590.

[13] LOH T H. NEE A Y C. A packing algorithm for hexahedral boxes[C]. Singapore: Proceedings of the Industrial Automation 92 Conference, 1992.

[14] NGOI B K A, TAY M L, CHUA E S. Applying spatial representation techniques to the container packing problem[J]. The International Journal of Production Research, 1994, 32(1): 111-123.

[15] BISCHOFF E E, RATCLIFF M S W. Issues in the development of approaches to container loading[J]. Omega, 1995, 23(4): 377-390.

Distribution Routing Problem with Time Window Under Constraint of Pallet Loading

托盘装载约束下带时间窗的配送车辆路径优化研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	SONG Li-ying, ZHAO Shi-chao, BIAN Qian, DU Peng, SHEN Peng-ju. Fresh Food Distribution Route Optimization of Mixed Fleets in Urban and Rural Areas Under Low Carbon Perspective [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(6): 250-261.
[2]	XIN Yu-chen, LI Run-chao, YANG Hua-long. Disturbance Management of VRPSDP Based on Waiting Strategy [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(5): 155-161.
[3]	WEN Bin-bin, HE Shi-wei, CHI Ju-shang, JIN Fu-cai. Containers Allocation and Recycle Transportation Problem with an Improved Branch-and-price Algorithm [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 223-234.
[4]	ZHANG Jin, ZHU Hong-xing, SHEN Hao, LI Guo-qi. Location-routing Problem of Emergency Logistics for Engineering Construction Projects Under Complex Environments [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 280-289.
[5]	ZHENG Yan, BEN Yu-shu, WANG Kang-de, JIANG Xiao-hong. Carbon Emission Efficiency Evaluation and Driving Factors Analysis of Logistics Enterprises [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 11-21.
[6]	. Multi-objective Optimization of Cold Chain Logistics Distribution Path Considering Time Tolerance [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 275-284.
[7]	SHI Chu-wei, MA Chang-xi, MA Cun-rui. Reliability Logistics Network Design Based on Two Stage Robust Optimization [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 285-299.
[8]	GAO Tian-hang, XU Xing, WU Hong-yu, BI Shan-shan, TIAN Jia. Division Model of Container Port Hinterland Considering Shippers' Behavior Decisions [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 10-16.
[9]	YAN Fang, DENG De-ping, CHAI Fu-liang, MA Yan-fang. Optimization of Dynamic Collection Route of Smart Garbage Bins Considering Negative Environmental Effects [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 265-274.
[10]	ZHANG Ying-gui , YAO Ying-hua, GAO Quan, LEI Ding-you. Optimization Model and Algorithm of Balanced Loading Layout of Railway Container Mixed Goods [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 214-222.
[11]	JIANG Xiao-hong, CHEN Sha, ZHANG Yi. Calculation Method of Total Carbon Emission and Efficiency of Logistics Enterprises [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 313-321.
[12]	ZHOU Xiao-xiang, HUANG Cheng-feng. Evolutionary Game and its Stability for Joint Distribution Alliance of Rural Logistics [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 265-272.
[13]	WANG Qing-bin , YU Jiang-ning, ZHENG Jian-feng. Interference Management Model for Drop and Pull Transport with New Tasks [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 160-166.
[14]	LIU Wu-sheng , LI Wang, ZHOU Qing, DIE Qian. "Drone-Vehicle" Distribution Routing Optimization Model [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 176-186.
[15]	ZHU Lan , MA Xiao, LIU Zhuo-fan. Time-dependent Green Vehicle Routing Problem [J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 187-194.