基于改进模糊遗传算法的混合车辆路径问题

Abstract

Abstract: A hybrid mathematic model is proposed with multi-depot, multi-type and multi-product vehicle routing problem. An improved fuzzy genetic algorithm is presented to solve the hybrid vehicle routing problem. Crossover probability and mutation probability are dynamic adjusted by improved fuzzy logistic controller, in order to speed up algorithm convergence and avoid falling into local optimal solution. Compared with standard example fuzzy genetic algorithm has good results and efficiency. Fuzzy genetic algorithm is used for the experiment of hybrid vehicle routing model, and the experiment get a good result.

Key words: vehicle routing problem, fuzzy genetic algorithm, multi-depot

CLC Number:

O224
C931

ZHANG Qun, YAN Rui. Hybrid Vehicle Routing Problem Based on Improved Fuzzy Genetic Algorithm[J]. Chinese Journal of Management Science, 2012, (2): 121-128.

References

[1] Dantzig,G., Fulkerson, R., Johnson, S.. Solution of a large-scale travelling salesman problem[J]. Operations Research, 1954, 2: 393-410.
[2] Dantzig, G., Ramser, J.. The truck dispatching problem[J]. Management Science, 1959, 6: 80-90.
[3] Skrlec, D., Filipec, M., Krajcar, S.. A heuristic modification of genetic algorithm used for solving the single depot capacitated vehicle routing problem [J]. Intelligent Information Systems, 1997, 8(10): 184-188.
[4] Dantzig, G., Fulkerson, R., Johnson, S.. A tabu search heuristic for multi-depot vehicle routing problem [J]. Operations Research, 1954, 2: 393-410.
[5] 陈新庄,郭强,范昌胜. 多车场满载车辆路径优化算法[J]. 计算机工程与设计,2008,29(22):5866-5871.
[6] 段凤华,符卓. 有软时窗多车场开放式车辆路径及其禁忌搜索[J]. 计算机工程与应用,2008,44(36):42-44.
[7] 李臻,雷定猷. 多车场车辆优化调度模型及算法[J]. 交通运输工程学报,2004,4(1):83-86.
[8] Mirabi, M., Fatemi Ghomi, S.M.T., Jolai, F.. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing prbolem[J]. Robotics and Computer-Integrated Manufacturing, 2010, 26: 564-569.
[9] Crevier, B., Cordeau, J.F., Laporte, G.. The multi-depot vehicle routing problem with inter-depot routes[J]. European Journal of Operational Research, 2007, 179: 756-773.
[10] Zhang, J., Tang, J.F., Fung, R.Y.K.. A scatter search for multi-depot vehicle routing problem with weight-related cost[J]. Asia-Pacific Journal of Operational Research, 2011, 28(3): 323-348.
[11] 蓝伯雄,张跃. 求解带时间窗的装—卸载问题的概率式禁忌搜索算法[J]. 中国管理科学,2004,12(2):66-72.
[12] 王征,张俊,王旭坪. 多车场带时间窗车辆路径问题的变邻域搜索算法[J]. 中国管理科学,2011,19(2):99-109.
[13] 李敏,郭强,刘红丽. 多车场多配送中心的物流配送问题研究[J]. 计算机工程与应用,2007,43(8):202-208.
[14] 王晓博,李一军. 多车型单配送中心混合装卸车辆路径问题研究[J]. 系统工程学报,2010,25(5):629-636.
[15] 王晓博,李一军. 多车场多车型装卸混合车辆路径问题研究[J]. 控制与决策,2009,24(12):1769-1774.
[16] 杨元峰. 多车场多车型车辆路径问题的改进遗传算法[J]. 计算机与现代化,2008,(9):10-13.
[17] 钟石泉,贺国光. 多车场有时间窗的多车型车辆调度及其禁忌算法研究[J]. 运筹学学报,2005,9(4):67-73.
[18] 刘冉,江志斌,陈峰等. 多车场满载协同运输问题模型与算法[J]. 上海交通大学学报,2009,43(3):455-459.
[19] 戎丽霞. 模糊需求条件下的多车场车辆路径问题. 第三届中国智能计算大会论, 济南,2009.
[20] 李军,郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京:中国物资出版社,2001.
[21] 李敏强,寇纪淞,林丹等. 遗传算法的基本理论及应用[M]. 北京:科学出版社,2002.
[22] 蒋艳凰,赵强利. 机器学习方法[M]. 北京:电子工业出版社,2009.
[23] McClintock, S., Lunney, T., Hashim, A.. Using fuzzy logic to optimize genetic algorithm performance. Proceedings of the IEEE Intelligent Engineering Systems. Budapest, Hungary: IEEE, 1997.
[24] 李擎,郑德玲,唐勇等. 一种新的模糊遗传算法[J]. 北京科技大学学报,2002,23(1): 85-89.
[25] 程林辉,王江晴. 求解车辆路径问题的改进遗传算法[J]. 计算机工程与应用,2010,46(36): 219-221.
[26] Holland, J.. Adaptation in Natural and Artificial Systems[M]. Cambridge:MIT Press,1992.
[27] 郎茂祥,胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学,2002,10(5):51-56.
[28] 玄光男,程润伟. 遗传算法与工程优化[M]. 北京:清华大学出版社,2004.
[29] Xu, H.Y., Vukovich, G.. Fuzzy evolutionary algorithms and automatic robot trajectory generation. Proceedings of the First IEEE World Congress on Evolutionary Computation. Orland, America: IEEE, 1994.

Hybrid Vehicle Routing Problem Based on Improved Fuzzy Genetic Algorithm

PDF (PC)

Knowledge

Cited

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]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	HOU Li-wen, TAN Jia-mei, ZHAO Yuan. Solving Vehicle Routing Problem with Split Deliveries and Time Window Constraints [J]. Chinese Journal of Management Science, 2007, 15(6): 46-51.
[15]	WANG Xiao-bo, LI Yi-jun. Research on Optimization of VRPTW Based on Improved Two Phase Algorithm under Electronic Commerce [J]. Chinese Journal of Management Science, 2007, 15(6): 52-59.