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

中国管理科学 ›› 2012, Vol. ›› Issue (2): 121-128.

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

张群, 颜瑞

北京科技大学东凌经济管理学院, 北京 100083

收稿日期:2011-05-16 修回日期:2012-01-11 出版日期:2012-04-29 发布日期:2012-04-25
基金资助:
国家重点基础研究发展规划(973,子课题)(2010CB955903-1)

Hybrid Vehicle Routing Problem Based on Improved Fuzzy Genetic Algorithm

ZHANG Qun, YAN Rui

School of Economics and Management, University of Science & Technology Beijing, Beijing 100083, China

Received:2011-05-16 Revised:2012-01-11 Online:2012-04-29 Published:2012-04-25

摘要/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

中图分类号:

O224
C931

张群, 颜瑞. 基于改进模糊遗传算法的混合车辆路径问题 [J]. 中国管理科学, 2012, (2): 121-128.

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

参考文献

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