带平衡约束三维装箱问题的双层混合遗传算法

交通运输系统工程与信息 ›› 2015, Vol. 15 ›› Issue (2): 203-209.

带平衡约束三维装箱问题的双层混合遗传算法

朱向^{*1, 2}，雷定猷²

1. 湖南涉外经济学院管理学院，长沙410205；2. 中南大学交通运输工程学院，长沙410075

收稿日期:2014-11-27 修回日期:2015-01-26 出版日期:2015-04-25 发布日期:2015-04-27
作者简介:朱向（1976-），男，湖南长沙人，博士，讲师.
基金资助:
国家自然科学基金研究项目（71371193）.

Bi-level Hybrid Genetic Algorithm for Three-dimensional Container Loading Problem with Balancing Constrains

ZHU Xiang ^{1, 2}，LEI Ding-you ²

1. School of Management, Hunan International Economics University, Changsha 410205, China; 2. School of Traffic & Transport Engineering, Central South University, Changsha 410075, China

Received:2014-11-27 Revised:2015-01-26 Online:2015-04-25 Published:2015-04-27

摘要/Abstract

摘要：

针对带重心平衡约束的三维装箱问题，基于框架式布局思想，设计双层混合遗传算法进行求解.根据装载物的特性定义核心货物元素及进行核心堆的构造，再结合极点、锚距等概念提出适合货物平衡装载的布局过程；在典型布局形成初始框架基础上，通过双层混合遗传算法的内、外层搜索分工与协作，获得货物最优装载方案.基于标准算例的实验及对比分析，证明所提出方法在提高装载率及实现重心平衡方面取得了较好效果.

关键词: 物流工程, 三维装箱, 平衡约束, 双层混合遗传算法, 框架式布局

Abstract:

Based on a framed-layout concept, a bi-level hybrid genetic algorithm (BHGA) is presented for the three-dimensional container loading problem (3DCLP) with balancing constraints. Firstly, the concept of core block and its generation tactics are proposed according to the freight characters. Then a construction process adapt to the balance loading is introduced combined with the concepts of extreme-point and anchordistance. Based on the initial frame and the co- evolution of internal and external searches of BHGA, the optimal placement for the freights can be determined. Lastly, the approach is tested on standard benchmark test data and is compared with the existed researches involving balance constrains. The results demonstrate that it is effective in improving the space use rate and balance level of the center gravity.

Key words: logistics engineering, 3DCLP, balancing constraints, BHGA, framed layout

中图分类号:

U294.5

朱向，雷定猷. 带平衡约束三维装箱问题的双层混合遗传算法[J]. 交通运输系统工程与信息, 2015, 15(2): 203-209.

ZHU Xiang,LEI Ding-you . Bi-level Hybrid Genetic Algorithm for Three-dimensional Container Loading Problem with Balancing Constrains[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(2): 203-209.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18980.shtml

http://www.tseit.org.cn/CN/Y2015/V15/I2/203

参考文献

[1] Pisinger D. Heuristics for the container loading problem[J]. European Journal of Operational Research, 2002, 141(2): 143-153.

[2] Bischoff E E, Ratcliff M S W. Issues in the development of approaches to container loading[J]. International Journal of Management Science, 1995, 23(3): 377-390.

[3] Gehring H, Bortfeldt A. A genetic algorithm for solving the container loading problem[J]. International Transactions in Operational Research, 1997, 4(5-6): 401-418.

[4] Davies A P, Bischoff E E. Weight distribution considerations in container loading[J]. European Journal of Operational Research, 1999, 114(3): 509- 527.

[5] Eley M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research, 2002, 141(2): 393-409.

[6] Egeblad J. Placement of two- and three- dimensional irregular shapes for inertia moment and balance[J]. International Transactions in Operational Research, 2009, 16 (6): 789-807.

[7] Baldi M M, Peroli G. The three-dimensional knapsack problem with balancing constraints[J]. Applied Mathematics and Computation, 2012, 218 (19): 9802- 9818.

[8] Liu J M, Yue Y. A novel hybrid tabu search approach to container loading[J]. Computers & Operations Research, 2011, 38(4) : 797-807.

[9] Lim A, Ma H. The single container loading problem with axle weight constraints[J]． Int. J. Production Economics, 2013, 144(6): 358-369.

[10] 雷定猷, 汤波. 一车多件货物装载布局优化模型与算法[J]. 铁道学报，2011，33(9)：1-9. [LEI D Y, TANG B. Optimizing model and algorithms of loading and packing multi-piece freights into one car[J]. Journal of The China Railway Society, 2011, 33(9): 1-9.]

[11] Crainic T, Perboli G. Extreme point- based heuristics for three-dimensional bin packing[J]. Informs Journal on Computing, 2008, 20(3): 368-338.

[12] Gongalves J F, Resende M G C. Biased random- key genetic algorithms for combinatorial optimization[J]. Journal of Heuristics, 2010, 17: 487-525.

[1]	张英贵, 姚璎华, 高全, 雷定猷. 铁路集装箱混合货物平衡装载布局优化模型与算法[J]. 交通运输系统工程与信息, 2022, 22(2): 214-222.
[2]	姜晓红, 陈莎, 张毅. 物流企业碳排放总量与效率测算方法[J]. 交通运输系统工程与信息, 2022, 22(2): 313-321.
[3]	周小祥, 黄承锋. 农村物流末端共配联盟演化博弈及稳定性研究[J]. 交通运输系统工程与信息, 2022, 22(1): 265-272.
[4]	王清斌, 于江宁, 郑建风. 甩挂运输模式下新增运输任务的干扰管理模型[J]. 交通运输系统工程与信息, 2021, 21(6): 160-166.
[5]	柳伍生, 李旺, 周清, 迭纤. “无人机-车辆”配送路径优化模型与算法[J]. 交通运输系统工程与信息, 2021, 21(6): 176-186.
[6]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[7]	奇格奇, 张子贤, 卫振林, 李宝文. 基于语义挖掘的快递运输货品风险评价研究[J]. 交通运输系统工程与信息, 2021, 21(4): 248-255.
[8]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.
[9]	杨华龙，辛禹辰，高浩然. 随机扰动项呈离散分布的库存路径和定价问题的模型与算法[J]. 交通运输系统工程与信息, 2021, 21(2): 211-216.
[10]	辛禹辰，施胜男，杨华龙. 基于订单拆分的线上到线下连锁门店配送优化模型[J]. 交通运输系统工程与信息, 2020, 20(5): 212-217.
[11]	于江霞，杜红亚，罗太波. 基于客户分类的即时配送路径优化研究[J]. 交通运输系统工程与信息, 2020, 20(4): 202-208.
[12]	刘杰，黎浩东，张萌. 基于点线能力约束的多层级节点协同布局优化模型及算法研究[J]. 交通运输系统工程与信息, 2020, 20(2): 107-113.
[13]	尹小庆，莫宇迪，董陈晨，林云. 考虑行程时间可靠性的城市冷链末端配送站选址研究[J]. 交通运输系统工程与信息, 2019, 19(6): 176-183.
[14]	曾庆成，马佳慧，张晓琳. 混合下单模式下在线餐饮订单配送优化模型[J]. 交通运输系统工程与信息, 2019, 19(6): 184-190.
[15]	燕晨屹，王喜富，员丽芬. 跨境供应链网络海外仓的鲁棒性选址模型及算法[J]. 交通运输系统工程与信息, 2019, 19(6): 191-198.