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

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

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

CLC Number:

O224

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.

References

[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)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10

[1]	XU Dong-yang, LI Kun-peng, CUI Li-gang, TIAN Qian-nan. Multi-commodity Unpaired Supply-demandand Split Pickup and Delivery Vehicle Routing Problem with Multi-depot and Multi-type Trucks [J]. Chinese Journal of Management Science, 2021, 29(1): 127-137.
[2]	GUO Fang, YANG Jun, YANG Chao. Study on Heterogeneous Electric Vehicle Routing and Batterycharging Problem with the Consideration of Differentiated Service Cost [J]. Chinese Journal of Management Science, 2019, 27(8): 118-128.
[3]	FANG Wen-ting, AI Shi-zhong, WANG Qing, FAN Jun-bo. Research on Cold Chain Logistics Distribution Path Optimization Based on Hybrid Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2019, 27(11): 107-115.
[4]	PAN Wen-wen, GUO Hai-xiang, DU Tian-song, LIU Xiao, WANG De-yun. The Vehicle Routing Problem with the Recycling of Oil Pipelines and Oil Casings and the Differential Evolution Algorithm based on Niching Clearing [J]. Chinese Journal of Management Science, 2018, 26(5): 118-128.
[5]	YAN Rui, ZHU Xiao-ning, ZHANG Qun, QI Yao-yuan, LIN Yu-zheng. Research ofthe Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain [J]. Chinese Journal of Management Science, 2017, 25(7): 67-77.
[6]	FU Zhuo, LIU Wen, QIU Meng. A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order [J]. Chinese Journal of Management Science, 2017, 25(5): 78-86.
[7]	LOU Zhen-kai. Bi-level Programming Model and Algorithmof Location-routing Problem in Emergency Logistics [J]. Chinese Journal of Management Science, 2017, 25(11): 151-157.
[8]	YANG Jun, FENG Peng-xiang, SUN Hao, YANG Chao. Carbon Emission Reduction Cost-Sharing Model in Supply Chain Based on Improvingthe Demand for Low-Carbon Products [J]. Chinese Journal of Management Science, 2015, 23(9): 87-96.
[9]	LI Jin, FU Pei-hua, LI Xiu-lin, ZHANG Jiang-hua, ZHU Dao-li. Study on Vehicle Routing Problem and Tabu Search Algorithmunder Low-carbon Environment [J]. Chinese Journal of Management Science, 2015, 23(10): 98-106.
[10]	ZHANG Jiang-hua, LI Jin, GAO Min-Gang. Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups [J]. Chinese Journal of Management Science, 2013, 21(4): 187-192.
[11]	GE Xian-long, XU Mao-zeng, WANG Wei-xin. Study on Multi-types Vehicle Routing Problem and Its Quantum Genetic Algorithm [J]. Chinese Journal of Management Science, 2013, (1): 125-133.
[12]	ZHANG Qun, YAN Rui. Hybrid Vehicle Routing Problem Based on Improved Fuzzy Genetic Algorithm [J]. Chinese Journal of Management Science, 2012, (2): 121-128.
[13]	WANG Zheng, ZHANG Jun, WANG Xu-ping. A Modified Variable Neighborhood Search Algorithm for the Multi Depot Vehicle Routing Problem with Time Windows [J]. Chinese Journal of Management Science, 2011, 19(2): 99-109.
[14]	WANG Xu-ping, WU Xu, MA Chao, YANG De-li. Study on Disruption Management for Vehicle Routing Problem with Break-down Vehicle [J]. Chinese Journal of Management Science, 2010, 18(6): 82-88.
[15]	YU Ming-zhu, LI Jian-bin, LEI Dong. The Research of VRP with Pick-up and Delivery and a New Tabu Search Based on Insertion Method [J]. Chinese Journal of Management Science, 2010, 18(2): 89-95.