带装卸顺序约束的装载配送联合优化算法研究

李珍萍, 刘洪伟, 周文峰, 鄂尔江, 田歆

系统工程理论与实践 ›› 2019, Vol. 39 ›› Issue (12) : 3097-3110.

PDF(807 KB)
中国科学院数学与系统科学研究院期刊网
PDF(807 KB)
系统工程理论与实践 ›› 2019, Vol. 39 ›› Issue (12) : 3097-3110. DOI: 10.12011/1000-6788-2019-0258-14
论文

带装卸顺序约束的装载配送联合优化算法研究

    李珍萍1, 刘洪伟1, 周文峰1, 鄂尔江2, 田歆3,4
作者信息 +

Study on joint optimization algorithm for loading and distribution with loading and unloading sequence constraints

    LI Zhenping1, LIU Hongwei1, ZHOU Wenfeng1, E Erjiang2, TIAN Xin3,4
Author information +
文章历史 +

摘要

互斥产品（如液体、危险化学品等）不能混装到同一个容器中，物流企业通常使用多隔舱运输车为顾客配送多种互斥产品，合理确定装载与配送路径是提高配送效率、降低配送成本的重要手段.本文考虑互斥产品的装卸顺序约束、在途运输时间约束等，构建了以配送成本最小化为目标的互斥产品装载配送联合优化模型，设计了求解模型的改进遗传算法，算法采用蜂王进化和基于概率的边重构交叉运算，有效提高了寻优能力.本文利用Augerat提供的车辆路径问题标准测试集构造算例测试算法的运行时间和求解效果.结果显示，改进遗传算法的求解效果明显优于经典遗传算法.对于小规模算例，改进的遗传算法可以得到精确最优解，对于中等规模和不超过101个顾客点的大规模算例，改进的遗传算法可以在130秒内得到近似最优解.本文的创新点在于构建了一类新的车辆路径扩展问题的数学模型并设计了求解模型的快速有效算法，为物流企业制定多类型互斥产品配送计划提供了理论依据和算法支持.

Abstract

Mutually exclusive products (such as liquids, hazardous chemicals, etc.) cannot be mixed into the same container. Logistics companies usually use multi-compartment trucks to deliver mutually exclusive products to customers. The loading and vehicle routing strategies are the key issues to determine the distribution efficiency and distribution costs. Considering the constraints of loading and unloading sequence and transportation time of mutually exclusive products, a joint optimization model of loading and distribution is constructed to minimize the distribution cost. This paper designs an improved genetic algorithm for solving the model, using the queen evolution and the edge reconstruction crossover operations based on probability to lift the ability of finding the optimal solution. Then we construct the testing examples based on the vehicle routing problem benchmark provided by Augerat to verify the running time and solving efficient of genetic algorithm. The simulation results show that, the solutions obtained by improved genetic algorithm are better than those of classical genetic algorithm, for small-scale examples, the improved genetic algorithm can obtains global optimal solution; for the medium-sized or large size examples with no more than 101 customers, the approximate optimal solution can be obtained in 130 seconds using genetic algorithm. The innovation of this paper lies in the establishment of a mathematical model for a new expended vehicle routing problem and the design of a fast and effective algorithm for solving the model. The mathematical model and algorithm of this paper provide a theoretical basis and algorithmic support for logistics companies to draw up distribution schedule of mutually exclusive products.

关键词

互斥产品 / 装卸顺序约束 / 装载配送联合优化 / 混合整数规划 / 遗传算法

Key words

mutually exclusive products / loading and unloading sequence constraint / joint optimization of loading and distribution / mixed integer programming / genetic algorithm

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
李珍萍 , 刘洪伟 , 周文峰 , 鄂尔江 , 田歆. 带装卸顺序约束的装载配送联合优化算法研究. 系统工程理论与实践, 2019, 39(12): 3097-3110 https://doi.org/10.12011/1000-6788-2019-0258-14
LI Zhenping , LIU Hongwei , ZHOU Wenfeng , E Erjiang , TIAN Xin. Study on joint optimization algorithm for loading and distribution with loading and unloading sequence constraints. Systems Engineering - Theory & Practice, 2019, 39(12): 3097-3110 https://doi.org/10.12011/1000-6788-2019-0258-14
中图分类号： TP301.6   

参考文献

[1] 齐玉东, 齐玉华, 谢晓方. 基于两次禁忌搜索的军事物资装运方案研究[J]. 计算机工程与设计, 2012, 33(7):2766-2770. Qi Y D, Qi Y H, Xie X F. Study on loading and transportation scheme of military materials based on twice tabu search algorithm[J]. Computer Engineering and Design, 2012, 33(7):2766-2770.
[2] 颜瑞, 马晓娟, 梁廷政, 等. 军事空运路径与装载联合优化问题研究[J]. 中国电子科学研究院学报, 2017, 12(1):7-13. Yan R, Ma X J, Liang T Z, et al. Research on optimal joint problem of routing and loading in military airlift[J]. Journal of CAEIT, 2017, 12(1):7-13.
[3] 钱丹, 刘建胜, 袁彬, 等. 多车型联运整车物流配送优化模型及算法研究[J]. 制造业自动化, 2015(6):65-68. Qian D, Liu J S, Yuan B, et al. Study on finished vehicle logistics optimization based on multi-types carrier's collaborative distribution[J]. Manufacturing Automation, 2015(6):65-68.
[4] Nowakowski P. A proposal to improve e-waste collection efficiency in urban mining:Container loading and vehicle routing problems-A case study of Poland[J]. Waste Management, 2017, 60:494-504.
[5] 符卓. 带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J]. 系统工程理论与实践, 2004, 24(3):123-128. Fu Z. The capacitated open vehicle routing problem and its tabu search algorithm[J]. Systems Engineering-Theory & Practice, 2004, 24(3):123-128.
[6] Coté J F, Guastaroba G, Speranza M G. The value of integrating loading and routing[J]. European Journal of Operational Research, 2017, 257(1):89-105.
[7] Iori M, Salazar-González J J, Vigo D. An exact approach for the vehicle routing problem with two-dimensional loading constraints[J]. Transportation science, 2007, 41(2):253-264.
[8] 王征, 胡祥培, 王旭坪. 带二维装箱约束的物流配送车辆路径问题[J]. 系统工程理论与实践, 2011, 31(12):2328-2341. Wang Z, Hu X P, Wang X P. Vehicle routing problem in distribution with two-dimensional loading constraint[J]. Systems Engineering-Theory & Practice, 2011, 31(12):2328-2341.
[9] 高学东, 谷淑娟, 白尘, 等. 考虑物流配送路网结构及配送量约束的客户聚类算法[J]. 系统工程理论与实践, 2012, 32(1):173-181.Gao X D, Gu S J, Bai C, et al. Road network and distribution scale constrained customer clustering algorithm in logistics distribution application[J]. Systems Engineering-Theory & Practice, 2012, 32(1):173-181.
[10] 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.
[11] Zhang D, Cai S, Ye F, et al. A hybrid algorithm for a vehicle routing problem with realistic constraints[J]. Information Sciences, 2017, 394:167-182.
[12] 王超, 金淳, 韩庆平. 三维装载与CVRP联合多目标优化问题的模型及算法[J]. 控制与决策, 2016, 31(5):929-934. Wang C, Jin C, Han Q P. Model and algorithm for multi-objective joint optimization of three dimensional loading and CVRP[J]. Control and Decision, 2016, 31(5):929-934.
[13] Zachariadis E E, Tarantilis C D, Kiranoudis C T. The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints[J]. European Journal of Operational Research, 2016, 251(2):369-386.
[14] Mannel D, Bortfeldt A. A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints[J]. European Journal of Operational Research, 2016, 254(3):840-858.
[15] Benavent E, Landete M, Mota E, et al. The multiple vehicle pickup and delivery problem with LIFO constraints[J]. European Journal of Operational Research, 2015, 243(3):752-762.
[16] Doerner K F, Fuellerer G, Hartl R F, et al. Metaheuristics for the vehicle routing problem with loading constraints[J]. Networks:An International Journal, 2007, 49(4):294-307.
[17] Pollaris H, Braekers K, Caris A, et al. Iterated local search for the capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints[J]. Networks, 2017, 69(3):304-316.
[18] Pollaris H, Braekers K, Caris A, et al. Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints[J]. EURO Journal on Transportation and Logistics, 2016, 5(2):231-255.
[19] 王旭坪, 詹红鑫, 孙自来, 等. 基于蚁群禁忌混合算法的成品油多舱配送路径优化研究[J]. 系统工程理论与实践, 2017, 37(12):3215-3226. Wang X P, Zhan H X, Sun Z L, et al. Route optimization for the refined oil multi-compartment distribution based on ant colony and tabu search hybrid algorithm[J]. Systems Engineering-Theory & Practice, 2017, 37(12):3215-3226.
[20] 孙丽君, 石海洋, 胡祥培. 考虑司机工作量均衡的成品油配送优化[J]. 系统工程理论与实践, 2018, 38(3):677-686. Sun L J, Shi H Y, Hu P X. An optimization method of product oil distribution considering drivers' workload balance[J]. Systems Engineering-Theory & Practice, 2018, 38(3):677-686.
[21] 王茜, 吉清凯, 胡祥培. 多车型多车槽VRP的混合导引反应式禁忌搜索算法[J]. 管理工程学报, 2016, 30(3):179-187. Wang Q, Ji Q K, Hu X P. A hybrid guided reactive tabu search for Heterogeneous fixed fleet multi-compartment vehicle routing problem[J]. Journal of Industrial Engineering/Engineering Management, 2016, 30(3):179-187.
[22] Augerat P, Belenguer J M, Benavent E, et al. Benchmark[Z]. http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/. 2018.01.22.

基金

国家自然科学基金（71771028）；北京市自然科学基金（Z180005）；北京市属高校高水平创新团队支持计划项目（IDHT20180510）；北京市智能物流系统协同创新中心开放课题（BILSCIC-2018KF-09）
PDF(807 KB)

632

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉