考虑三维装箱约束的车辆路径问题研究

doi:10.16381/j.cnki.issn1003-207x.2015.01.016

中国管理科学 ›› 2015, Vol. 23 ›› Issue (1): 128-134.doi: 10.16381/j.cnki.issn1003-207x.2015.01.016

考虑三维装箱约束的车辆路径问题研究

颜瑞¹, 张群², 胡睿²

1. 北京信息科技大学经济管理学院, 北京 100192;
2. 北京科技大学东凌经济管理学院, 北京 100083

收稿日期:2012-10-12 修回日期:2013-10-13 出版日期:2015-01-20 发布日期:2015-01-21
作者简介:颜瑞(1986-),男(汉族),江苏连云港人,北京信息科技大学经济管理学院讲师,研究方向:生产运营、物流优化.
基金资助:
国家自然科学基金资助项目(71172168);中央高校基本科研业务费(FRF-AS-13-003A,FRF-TP-14-058A2);北京哲学社会科学规划项目(12JGB024)

Research of Vehicle Routing Problem with Three-Dimensional Loading Constraints

YAN Rui¹, ZHANG Qun², HU Rui²

1. School of Economics and Management, Beijing Information Science & Technology University, Beijing 100192, China;
2. Dongling School of Economics and Management, University of Science & Technology Beijing, Beijing 100083, China

Received:2012-10-12 Revised:2013-10-13 Online:2015-01-20 Published:2015-01-21

摘要/Abstract

摘要： 针对实际物流配送问题的特点,建立考虑三维装箱约束的车辆路径问题模型,提出求解该问题的引导式局部搜索算法。采用改进的模糊遗传算法求解车辆路径问题,提出一种新的模糊逻辑控制器,并采用引导式局部搜索算法求解三维装箱问题。通过计算标准算例检验算法性能,试验结果表明引导式局部搜索算法能够在较短时间内得到质量较高的近似最优解。

关键词: 车辆路径, 三维装箱, 模糊遗传算法, 局部搜索

Abstract: In distribution process, the volume of goods could be a key influential factor. An important combination of three-dimensional loading and vehicle routing problem, known as the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3DL-CVRP) is adhessed, which aimed at arranging as much as possible items while control their total weight under the vehicle's loading limit. Based on the real distribution problem, a 3DL-CVRP model was build and a heuristics algorithm named Guided Local Search Fuzzy Genetic Algorithm(GLSFGA) was given. This new algorithm rooted from the improved Fuzzy Genetic Algorithm and designed for VRP specifically. The fuzzy logic controller in GLSFGA was brand new because of its creative guiding methods. The GLSFGA had shown an overall good performance compared to the benchmark approach.

Key words: vehicle routing, three-dimensional packing, fuzzy genetic algorithm, local search

中图分类号:

O224

颜瑞, 张群, 胡睿. 考虑三维装箱约束的车辆路径问题研究[J]. 中国管理科学, 2015, 23(1): 128-134.

YAN Rui, ZHANG Qun, HU Rui. Research of Vehicle Routing Problem with Three-Dimensional Loading Constraints[J]. Chinese Journal of Management Science, 2015, 23(1): 128-134.

参考文献

[1] Iori M. Meta-heuristic algorithm for combinatorial optimization problems[J]. OR: A Quarterly Journal of Operations Research, 2005, 3(2): 163-166.

[2] Iori M, Salazar-Gonzalez JJ, Vigo D. An exact approach for the vehicle routing problem with two-dimensional loading constraints[J]. Transportation Science, 2007, 41(2): 253-264.

[3] Gendreau M, Iori M, Laporte G, et al. A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints[J]. Networks, 2008, 51(1): 4-18.

[4] Khebbache S, Prins C, Yalaoui A,et al. Memetic algorithm for two-dimensional loading capacitated vehicle routing problem with time windows[C]. Proceedings of International Conference on Computers and Industrial Engineering, Troyes, French,July 6-8,2009.

[5] Leung S C H, Zheng Jiemin, Zhang Defu, et al. Simulated annealing for the vehicle routing problem with two-dimensional loading constraints[J]. Flexible Services and Manufacturing Journal, 2010,22(1-2): 61-82.

[6] Leung S C H, Zhou Xiyue, Zhang Defu,et al. Extended guided tabu search and a new packing algorithm for the two-algorithm loading vehicle routing problem [J]. Computers & Operations Research, 2011, 38(1): 205-215.

[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] Moura A, Oliveira J. An integrated approach to the vehicle routing and container loading problems[J]. OR Spectrum, 2009, 31(4): 775-800.

[9] Fuellerer G, Doerner K F, Hartl R F,et al. Metaheuristics for vehicle routing problems with three-dimensional loading constraints[J]. European Journal of Operational Research, 2010, 201(3): 751-759.

[10] Iori M, Martello S. Routing problems with loading constraints[J]. TOP, 2010, 18(1): 4-27.

[11] 马珊静,陈峰,宋德朝,等. 越库配送物流系统车辆调度算法的研究[J]. 现代制造工程,2009,(1):12-15,127.

[12] 宁爱兵,熊小华,马良. 城市物流配送中的三维装箱算法[J]. 计算机工程与应用,2009,45(9):207-208(211).

[13] 王征,胡祥培,王旭坪. 带二维装箱约束的物流配送车辆路径问题[J]. 系统工程理论与实践,2011,31(12):2328-2341.

[14] McClintock S, Lunney T, Hashim A. Using fuzzy logic to optimize genetic algorithm performance[C]. Proceedings of the IEEE Intelligent Engineering Systems, Budapest, Hungary, September, 1997.

[15] Ruan Qingfang, Zhang Zhengqian, Miao Lixin, et al. A hybrid approach for the vehicle routing problem with three-dimensional loading constraints[J]. Computers & Operations Research, 2011, 38(11): 1-11.

[16] Junqueira L, Morabito R, Yamashita D S. Three-dimensional container loading modes with cargo stability and load bearing constraints[J]. Computers & Operations Research, 2012, 39(1): 74-85.

[17] Holland J. Adaptation in natural and artificial system[M]. Cambridge: MIT Press, 1992.

[18] 张丽萍,柴跃廷. 车辆路径问题的改进遗传算法[J]. 系统工程理论与实践,2002,22(8):79-84.

[19] 玄光男,程润伟. 遗传算法与工程优化[M]. 北京:清华大学出版社,2004.

[20] Xu H Y, Vukovich G. Fuzzy evolutionary algorithms and automatic robot trajectory generation[C]. Proceedings of the First IEEE World Congress on Evolutionary Computation, Orland, America, June 27-29, 1994.

[21] Zeng X,Rabenasolo B. A fuzzy logic based design for adaptive genetic algorithms [J]. Proceedings of the fifth European Congress on Intelligent Techniques and Soft Computing, 1997: 660-664.

[22] Hu N, Wang D, Zhao D, et al. Study of fuzzy control based on genetic algorithms[J]. Nanjing University of Aeronautics & Astronautics, 1997,29(5):544-548.

考虑三维装箱约束的车辆路径问题研究

Research of Vehicle Routing Problem with Three-Dimensional Loading Constraints

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	徐东洋, 李昆鹏, 崔利刚, 田倩南. 供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题[J]. 中国管理科学, 2021, 29(1): 127-137.
[2]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[3]	方文婷, 艾时钟, 王晴, 范君博. 基于混合蚁群算法的冷链物流配送路径优化研究[J]. 中国管理科学, 2019, 27(11): 107-115.
[4]	潘雯雯, 郭海湘, 杜天松, 刘晓, 王德运. 油套管回收车辆路径问题及基于清除小生境差分演化求解算法研究[J]. 中国管理科学, 2018, 26(5): 118-128.
[5]	王晶, 刘昊天, 黄钧. 考虑伤情分类的灾后创伤伤员救治与转运路径优化研究[J]. 中国管理科学, 2017, 25(8): 114-122.
[6]	颜瑞, 朱晓宁, 张群, 戚耀元, 蔺俞铮. 考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学, 2017, 25(7): 67-77.
[7]	符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5): 78-86.
[8]	刘艳秋, 徐世达, 张颖, 李佳. 考虑路径可行性与仓储集货模式下的回收车辆路径问题研究[J]. 中国管理科学, 2016, 24(12): 98-107.
[9]	李进, 傅培华, 李修琳, 张江华, 朱道立. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学, 2015, 23(10): 98-106.
[10]	张江华, 李进, 高敏刚. 同时集散货物的开放式车辆路径问题研究[J]. 中国管理科学, 2013, 21(4): 187-192.
[11]	张群, 颜瑞. 基于改进模糊遗传算法的混合车辆路径问题 [J]. 中国管理科学, 2012, (2): 121-128.
[12]	王征, 张俊, 王旭坪. 多车场带时间窗车辆路径问题的变邻域搜索算法[J]. 中国管理科学, 2011, 19(2): 99-109.
[13]	余明珠, 李建斌, 雷东. 装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J]. 中国管理科学, 2010, 18(2): 89-95.
[14]	侯立文, 谭家美, 赵元. 求解带时间窗的客户需求可分条件下的车辆路径问题[J]. 中国管理科学, 2007, 15(6): 46-51.
[15]	陆琳, 谭清美. 基于自感应蚁群算法的VRPSDP问题研究[J]. 中国管理科学, 2007, 15(2): 97-103.