遗传算法在多车场车辆路径问题中的应用研究
|
摘要
当前,物流配送已成为企业重要的“第三方利润源”。车辆路径问题(Vehicle Routing Problem, VRP)是物流配送领域的核心内容。对车辆路径问题的研究具有非常重要的理论与现实意义。如今物流企业通常不只拥有一个配送中心(车场),而是拥有多个配送中心,多车场车辆路径问题(Multiple-Depot Vehicle Routing Problem, MDVRP)逐渐成为车辆路径问题领域的重要的新研究方向。
MDVRP属于NP难问题,即无法在多项式时间内求得最优解。现代启发式算法退而求其次,在可接受时间范围内求得问题的次优解,逐渐成为求解车辆路径问题的一个重要方向。因此本文采用改进的遗传算法对其进行求解。遗传算法是模拟生物进化论的自然选择和遗传学机理的生物进化过程仿生设计的,利用染色体在进化过程中的交叉、变异等过程,在解空间内进行全局搜索,寻求更优解。本文在对多车场车辆路径问题的研究中,改进了遗传算法,采用自然数编码染色体、改进的交叉算子及增加内外扰动等技术来求解。
本文的主要工作：1)通过对多车场车辆路径问题的学习,建立数学模型,并对不同研究方法进行总结归纳；2)增加了虚拟配送中心的方法,将多车场问题转化为单车场问题;3)采用改进的遗传算法对其求解。通过不同的数据集的测验,并对实验结果进行分析、比较和总结,证明改进算法有效性和适用范围。
In recent years, Logistics Distribution has become an important "third-party source of profit ", an important part in national economy. Vehicle Routing Problem the is core content area of Logistics Distribution. Therefore, the research on the vehicle routing problem is very important theoretical and practical significance. Today, many logistics companies usually have more than one distribution center (depot). Multiple-Depot Vehicle Routing Problem has become an important new area of research.
MDVRP is NP hard problem. Its optimal solution can not be obtained in polynomial time. Modern heuristic settling for less obtaining suboptimal solution of the problem within an acceptable time, has become an important research direction. This article uses an improved genetic algorithm to solve the problem. Genetic algorithms is bioniced by simulate biological evolution of natural selection and genetic mechanism of biological evolution.Using Chromosome crossover and mutation process in the evolutionary process to global search better solution within the solution space. In this paper, I have improverd genetic algorithm,with natural number coding chromosome, improved crossover operator and increasing the external perturbation techniques within the study multi-depot vehicle routing problem.
The main work of this paper. First through the multiple depot vehicle routing problem-based learning,established mathematical model and summarized different research methods. Second let MDVRP transformed into general VRP problom by increasing virtual distribution center. Third using improved genetic algorithm to solve the problom.Finally testing different data sets, analyzing, comparing and summarizing experiment results to prove the validity and scope of the improved algorithm.
MDVRP属于NP难问题,即无法在多项式时间内求得最优解。现代启发式算法退而求其次,在可接受时间范围内求得问题的次优解,逐渐成为求解车辆路径问题的一个重要方向。因此本文采用改进的遗传算法对其进行求解。遗传算法是模拟生物进化论的自然选择和遗传学机理的生物进化过程仿生设计的,利用染色体在进化过程中的交叉、变异等过程,在解空间内进行全局搜索,寻求更优解。本文在对多车场车辆路径问题的研究中,改进了遗传算法,采用自然数编码染色体、改进的交叉算子及增加内外扰动等技术来求解。
本文的主要工作：1)通过对多车场车辆路径问题的学习,建立数学模型,并对不同研究方法进行总结归纳；2)增加了虚拟配送中心的方法,将多车场问题转化为单车场问题;3)采用改进的遗传算法对其求解。通过不同的数据集的测验,并对实验结果进行分析、比较和总结,证明改进算法有效性和适用范围。
In recent years, Logistics Distribution has become an important "third-party source of profit ", an important part in national economy. Vehicle Routing Problem the is core content area of Logistics Distribution. Therefore, the research on the vehicle routing problem is very important theoretical and practical significance. Today, many logistics companies usually have more than one distribution center (depot). Multiple-Depot Vehicle Routing Problem has become an important new area of research.
MDVRP is NP hard problem. Its optimal solution can not be obtained in polynomial time. Modern heuristic settling for less obtaining suboptimal solution of the problem within an acceptable time, has become an important research direction. This article uses an improved genetic algorithm to solve the problem. Genetic algorithms is bioniced by simulate biological evolution of natural selection and genetic mechanism of biological evolution.Using Chromosome crossover and mutation process in the evolutionary process to global search better solution within the solution space. In this paper, I have improverd genetic algorithm,with natural number coding chromosome, improved crossover operator and increasing the external perturbation techniques within the study multi-depot vehicle routing problem.
The main work of this paper. First through the multiple depot vehicle routing problem-based learning,established mathematical model and summarized different research methods. Second let MDVRP transformed into general VRP problom by increasing virtual distribution center. Third using improved genetic algorithm to solve the problom.Finally testing different data sets, analyzing, comparing and summarizing experiment results to prove the validity and scope of the improved algorithm.
引文
[1]http://wiki.mbalib.com/wiki/%E8%BD%A6%E8%BE%86%E8%B7%AF%E7%B A%BF%E9%97%AE%E9%A2%98,2008.
[2]G.Laporte, Y.Nobert, D.Arpin. Optimal solutions to capacitated multidepot vehicle routing, Congressus Numerantium,1984(44):283-292.
[3]F.A.Tillman, The multiple terminal delivery problem with probabilistic demands.Transp.Sci,1969(3):192-204.
[4]马士华,孟庆鑫.供应链物流能力的研究现状及发展趋势[J].计算机集成制造系统,2005,11(3)：301-307.
[5]Holland著.自然和人工系统中的适应性.1975
[6]刘云霞.动态车辆调度问题分析及算法设计[D].成都：西南交通大学,2004.
[7]郭耀煌,李军.车辆优化调度[M].成都科技大学出版社,1994,22-48.
[8]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006,(01).
[9]张炯,郎茂祥.有时间窗配送车辆调度问题的禁忌搜索算法[J].北方交通大学学报,2004,(02)
[10]张涛,王梦光.遗传算法和3-opt结合求解带有能力约束的VRP[J].东北大学学报(自然科学版),1999,(03)
[11]王涛,蔡延光,张新政.现代物流中车辆路径问题的研究[J].物流科技,2005,(01).
[12]沈绍基.中国物流市场供求状况分析报告.物流科技,2000(2)：3-14.
[13]刘云霞.动态车辆调度问题分析及算法设计[D].成都：西南交通大学,2004.
[14]杨夷梅,杨玉军.分支定界算法优化研究[J].中国科技信息,2008,21：42-43.
[15]杜祜康,赵英凯.整数规划问题智能求解算法综述[J].计算机应用研究,2010,27(2)： 408-412.
[16]M.L.Fisher, Optimal Solution of Vehicle Routing Problems Using Minimum K-trees [J], Operations Research,1994,42:626-642.
[17]江贺,胡燕,李强,于红,TSP问题的脂肪计算复杂性与启发式算法设计[J].软件学报,2009,20(9)：2345-2351.
[18]陈晓伟,张悟移,耿继武.节约法在配送路线中的应用[J].昆明理工大学学报(理工版),2003,28(4)：140-143.
[19]Gendreau M. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers[J]. Operation Research,1996,44(3):469-477.
[20]王晓哗,王正欧.K_最近邻分类技术的改进算法[J].电子与信息学报,2005,27(3)：487-491.
[21]朱晓兰,赵一飞.C-W节约算法在装配企业采购物流中的应用[J].上海交通大学学报2007,41(9),1420-1423.
[22]祁文祥,陆志强,孙小明.带软时间窗的集货与送货多车辆路径问题节约算法[J].交通运输工程学报,2010,10(2)：99-103.
[23]方永慧,刘光远,贺一等.一种基于插入法的禁忌搜索算法[J].西南师范大学学报(自然科学版),2003,28(6)：887-891.
[24]http://baike.baidu.com/view/45853.htm.2010.5
[25]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社,2002：25-50.
[26]陈云霞,高洁萍,夏华风.基于遗传算法的多学科设计优化分解方法[J].北京航空航天大学学报,2009,35(6)：673-677.
[27]王学武,谭得健.神经网络的应用与发展趋势[J],计算机工程与应用,2003,3(2)：98-113.
[28]王永亮,袁振洲,李艳红.基于BP神经网络确定最优配送车辆数目问题的研究[J].交通标准化,2008,6(178).
[29]http://baike.baidu.com/view/367089.htm.2010.7
[30]章兢,周泉·基于克隆选择算法的物流配送车辆路径优化研究[J]·湖南大学学报：自然科学版,2004,31(5):54-58·(Zhang Jing, Zhou Quan. Study on the optimization of logistics distribution VRP based on immune clone algorithm [J].Journal ofHunan University:Natural Science,2004,31(5):54-58.)
[31]郭平,娜文晋.基于TSP问题的蚁群算法综述[J].计算机科学,2007,34(10)：181-185.
[32]詹士昌等.蚁群算法中有关算法参数的最优选择[J].科技通报,2003,19(5)：381-386.
[33]李敏强.遗传算法的基本理论与应用.北京：科学出版社,2003
[34]陈萍,黄厚宽,董兴业,求解卸装一体化的车辆路径问题的混合启发式算法[J].计算机学报,2008.31(4).
[35]Ching-Jung Tinga. Hybrid ant colony system for vehicle routing Problem with time windows[J].Journal of the Eastern Asia Society for Transportation Studies,2005,6:2822-2836.
[36]谢秉磊,郭耀煌,郭强.动态车辆路径问题：现状与展望[J].系统工程理论方法应用,2002,11(2)：116-120.
[37]刘冉,江志斌,耿娜,刘天堂,半开放式多车场车辆路径问题[J].上海交通大学学报,2010,44(11)：1540-1545.
[38]Andre LaMothe Ai Techniques For Game Programming[M].2004.
[39]李军,张红历.车辆优化调度可视化系统研究[J].交通运输工程学报,2004.4(1)：80-81.
[40]李军,郭耀煌著.物流配送系统车辆优化调度理论与方法[M]. 中国物资出版社,2001.
[41]刘云忠,宣慧玉.四辆路径问题的模型及算法研究综述[J].2005.19(1)：124-127.
[42]Sundararajan Arunapuram, Kamlesh Mathur, Daniel Solow, Vehicle Routing and Scheduling with Full Truckloads[J], Transportation science,2003,37:170-182.
[43]唐坤.车辆路径问题中的遗传算法设计[J].东华大学学报(自然科学版)2002,28(1)：66-70
[44]宋玉林.混合遗传算法在配送车辆调度问题中的研究和应用[D].硕士,华中科技大学,2004.
[45]http://itp.nat.uni-magdeburg.de/～mertens/TSP/node2.html.1999,05.
[46]Selim Tezel. Master's Project, Traveling Salesman's Sketchpad (TSSP),2002.
[47]刘海,郝志峰,林智勇.改进遗传交叉算子求TSP问题[J],华南理工大学学报(自然科学版).200230(12)：71-73.
[48]李军.非对称距离的旅行商问题的构造算法[J].运筹与管理,2000,9(1)：12-17.
[49]马良.旅行推销员问题的算法综述[J].数学的实践与认识,2002,32(2)：26-30
[50]屈援,汪波,钟石泉.单车场多送货点车辆路径问题的改进遗传算法[J].200743(25)：237-243.
[51]钟石泉,王雪莲.车场集送一体化车辆调度问题及其遗传算法研究[J].西安电子科技大学学报(社会科学版)2009 19(1)：63-68.
[52]刘兴,贺国光,高文伟.一种有时间约束的多车辆协作路径模型及算法[J].系统工程,2005(4)：105-107.
[53]邹彤,李宁,孙德宝,李菁.多车场车辆路径问题的遗传算法.计算机工程与应用[J],2004,21：82-83.
[54]钟石泉,贺国光,多车场车辆调度智能优化研究[J].华东交通大学学报.2004(21)：25-29.
[55]I. M. Chao, B. L. Golden, E. Wasil. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. Am. J. Math. Mgmt Sci. 1993(13):371-406.
[2]G.Laporte, Y.Nobert, D.Arpin. Optimal solutions to capacitated multidepot vehicle routing, Congressus Numerantium,1984(44):283-292.
[3]F.A.Tillman, The multiple terminal delivery problem with probabilistic demands.Transp.Sci,1969(3):192-204.
[4]马士华,孟庆鑫.供应链物流能力的研究现状及发展趋势[J].计算机集成制造系统,2005,11(3)：301-307.
[5]Holland著.自然和人工系统中的适应性.1975
[6]刘云霞.动态车辆调度问题分析及算法设计[D].成都：西南交通大学,2004.
[7]郭耀煌,李军.车辆优化调度[M].成都科技大学出版社,1994,22-48.
[8]郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006,(01).
[9]张炯,郎茂祥.有时间窗配送车辆调度问题的禁忌搜索算法[J].北方交通大学学报,2004,(02)
[10]张涛,王梦光.遗传算法和3-opt结合求解带有能力约束的VRP[J].东北大学学报(自然科学版),1999,(03)
[11]王涛,蔡延光,张新政.现代物流中车辆路径问题的研究[J].物流科技,2005,(01).
[12]沈绍基.中国物流市场供求状况分析报告.物流科技,2000(2)：3-14.
[13]刘云霞.动态车辆调度问题分析及算法设计[D].成都：西南交通大学,2004.
[14]杨夷梅,杨玉军.分支定界算法优化研究[J].中国科技信息,2008,21：42-43.
[15]杜祜康,赵英凯.整数规划问题智能求解算法综述[J].计算机应用研究,2010,27(2)： 408-412.
[16]M.L.Fisher, Optimal Solution of Vehicle Routing Problems Using Minimum K-trees [J], Operations Research,1994,42:626-642.
[17]江贺,胡燕,李强,于红,TSP问题的脂肪计算复杂性与启发式算法设计[J].软件学报,2009,20(9)：2345-2351.
[18]陈晓伟,张悟移,耿继武.节约法在配送路线中的应用[J].昆明理工大学学报(理工版),2003,28(4)：140-143.
[19]Gendreau M. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers[J]. Operation Research,1996,44(3):469-477.
[20]王晓哗,王正欧.K_最近邻分类技术的改进算法[J].电子与信息学报,2005,27(3)：487-491.
[21]朱晓兰,赵一飞.C-W节约算法在装配企业采购物流中的应用[J].上海交通大学学报2007,41(9),1420-1423.
[22]祁文祥,陆志强,孙小明.带软时间窗的集货与送货多车辆路径问题节约算法[J].交通运输工程学报,2010,10(2)：99-103.
[23]方永慧,刘光远,贺一等.一种基于插入法的禁忌搜索算法[J].西南师范大学学报(自然科学版),2003,28(6)：887-891.
[24]http://baike.baidu.com/view/45853.htm.2010.5
[25]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社,2002：25-50.
[26]陈云霞,高洁萍,夏华风.基于遗传算法的多学科设计优化分解方法[J].北京航空航天大学学报,2009,35(6)：673-677.
[27]王学武,谭得健.神经网络的应用与发展趋势[J],计算机工程与应用,2003,3(2)：98-113.
[28]王永亮,袁振洲,李艳红.基于BP神经网络确定最优配送车辆数目问题的研究[J].交通标准化,2008,6(178).
[29]http://baike.baidu.com/view/367089.htm.2010.7
[30]章兢,周泉·基于克隆选择算法的物流配送车辆路径优化研究[J]·湖南大学学报：自然科学版,2004,31(5):54-58·(Zhang Jing, Zhou Quan. Study on the optimization of logistics distribution VRP based on immune clone algorithm [J].Journal ofHunan University:Natural Science,2004,31(5):54-58.)
[31]郭平,娜文晋.基于TSP问题的蚁群算法综述[J].计算机科学,2007,34(10)：181-185.
[32]詹士昌等.蚁群算法中有关算法参数的最优选择[J].科技通报,2003,19(5)：381-386.
[33]李敏强.遗传算法的基本理论与应用.北京：科学出版社,2003
[34]陈萍,黄厚宽,董兴业,求解卸装一体化的车辆路径问题的混合启发式算法[J].计算机学报,2008.31(4).
[35]Ching-Jung Tinga. Hybrid ant colony system for vehicle routing Problem with time windows[J].Journal of the Eastern Asia Society for Transportation Studies,2005,6:2822-2836.
[36]谢秉磊,郭耀煌,郭强.动态车辆路径问题：现状与展望[J].系统工程理论方法应用,2002,11(2)：116-120.
[37]刘冉,江志斌,耿娜,刘天堂,半开放式多车场车辆路径问题[J].上海交通大学学报,2010,44(11)：1540-1545.
[38]Andre LaMothe Ai Techniques For Game Programming[M].2004.
[39]李军,张红历.车辆优化调度可视化系统研究[J].交通运输工程学报,2004.4(1)：80-81.
[40]李军,郭耀煌著.物流配送系统车辆优化调度理论与方法[M]. 中国物资出版社,2001.
[41]刘云忠,宣慧玉.四辆路径问题的模型及算法研究综述[J].2005.19(1)：124-127.
[42]Sundararajan Arunapuram, Kamlesh Mathur, Daniel Solow, Vehicle Routing and Scheduling with Full Truckloads[J], Transportation science,2003,37:170-182.
[43]唐坤.车辆路径问题中的遗传算法设计[J].东华大学学报(自然科学版)2002,28(1)：66-70
[44]宋玉林.混合遗传算法在配送车辆调度问题中的研究和应用[D].硕士,华中科技大学,2004.
[45]http://itp.nat.uni-magdeburg.de/～mertens/TSP/node2.html.1999,05.
[46]Selim Tezel. Master's Project, Traveling Salesman's Sketchpad (TSSP),2002.
[47]刘海,郝志峰,林智勇.改进遗传交叉算子求TSP问题[J],华南理工大学学报(自然科学版).200230(12)：71-73.
[48]李军.非对称距离的旅行商问题的构造算法[J].运筹与管理,2000,9(1)：12-17.
[49]马良.旅行推销员问题的算法综述[J].数学的实践与认识,2002,32(2)：26-30
[50]屈援,汪波,钟石泉.单车场多送货点车辆路径问题的改进遗传算法[J].200743(25)：237-243.
[51]钟石泉,王雪莲.车场集送一体化车辆调度问题及其遗传算法研究[J].西安电子科技大学学报(社会科学版)2009 19(1)：63-68.
[52]刘兴,贺国光,高文伟.一种有时间约束的多车辆协作路径模型及算法[J].系统工程,2005(4)：105-107.
[53]邹彤,李宁,孙德宝,李菁.多车场车辆路径问题的遗传算法.计算机工程与应用[J],2004,21：82-83.
[54]钟石泉,贺国光,多车场车辆调度智能优化研究[J].华东交通大学学报.2004(21)：25-29.
[55]I. M. Chao, B. L. Golden, E. Wasil. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. Am. J. Math. Mgmt Sci. 1993(13):371-406.