基于GIS的物流配送路线优化的研究
|
摘要
随着市场经济的发展,物流对经济活动的影响日益明显。配送流程是物流活动中直接与消费者相连的环节,而车辆路径规划问题(VRP)又是物流配送中关键的一环。因此,对车辆路径规划问题进行研究,建立满足客户需求的车辆优化系统,是提升企业服务水平及资源利用率的重要课题。
物流配送所涉及到的信息80%以上与空间地理信息有着直接的关系,对地理空间有很大的依赖性。而地理信息系统(GIS)技术作为获取、存储、分析和处理空间地理数据的工具,具有强大的空间数据管理和空间分析能力。于是本文将GIS技术应用到物流配送中来辅助解决路径规划问题。本文主要研究内容为:
(1)研究了物流配送系统和GIS的发展过程及现状特征,指出两者相结合的可行性和必要性。
(2)对现有国内外VRP解决方法进行研究和比较,得出了两阶段法虽在VRP求解上具有优越性、但其初始解却很少从空间角度考虑的结论。
(3)利用空间聚类对需求点进行分簇以得到初始解,使得VRP问题变为K个旅行商问题(TSP);并根据VRP的特点,对所采用的K-means算法进行改进,同时通过实验验证了正确性。
(4)在各分簇内引入蚁群算法来解决TSP问题,并通过仿真实验,研究分析了蚁群算法在求解TSP问题上各参数对结果的影响及其最佳设置。
(5)通过对标准VRP问题进行实验与结果分析,验证了“加权K-means+蚁群”算法求解VRP问题的有效性、准确性及优越性。
最后,在实验结果的基础上,提出切合实际系统集成方案,完成了一个原型系统,实现空间和属性数据库的统一存储管理、电子地图基本操作、最优路径查找功能。
With the development of market economy, logistics influences to the economic activity obviously day by day. Distribution is the tach in the logistics activity with consumer connected link directly, logistics distribution for vehicle routing problem, is a pivotal tach of the logistics distribution optimization. Therefore, carrying on the vehicle routing problem and establishment a system that can meet the customer’s needs immediately, is an important topic to promote the service and the resources use rate.
80 percent of logistics distribution information which depends on the geography space is related with the geography space information directly. While GIS , which support us to get, manage, operate, analyze and display the geographic space data, has the powerful capability of managing and analyzing geography data. So we apply GIS to the logistics system to optimize VRP. This paper’s main research works include:
(1)To research the development and current character of logistics distribution system and GIS, and to point out the necessity and feasibility of the integration of logistics distribution system and GIS.
(2)To study and compare the VRP current research work, and get the conclusion of 2-Phase Algorithm’s advantage , but the initial value is not considered by the spatial point.
(3) The problem of customers classifying is solved by clustering algorithm, then the Vehicle Routing Problem is abstracted as TSP. Aiming at the trait of VRP, to accomplish improvement and implement to the K-means, and prove the veracity by experiment.
(4)Then Ant Colony Algorithm was used to offer solution to TSP. By making stimulation experiment, this experiment also devoted to investigations of how to set parameters which affects the capability and results, when Ant Colony Algorithm is employed in dealing with TSP. And analyzing the experiment result proves the validity and correctness of the combination algorithm of improved K-means and Ant Colony Algorithm.
(5)According to experiment, to prove the validity、veracity and superiority of the algorithm proposed by this paper to solve VRP.
Finally, on the basis results of above experiment, this paper have proposed practical system integration solutions and then accomplished a prototype model. This research have realized the storage and management of spatial and attribute database, the basic operation function of electronic map and the shortest route searching function component module.
物流配送所涉及到的信息80%以上与空间地理信息有着直接的关系,对地理空间有很大的依赖性。而地理信息系统(GIS)技术作为获取、存储、分析和处理空间地理数据的工具,具有强大的空间数据管理和空间分析能力。于是本文将GIS技术应用到物流配送中来辅助解决路径规划问题。本文主要研究内容为:
(1)研究了物流配送系统和GIS的发展过程及现状特征,指出两者相结合的可行性和必要性。
(2)对现有国内外VRP解决方法进行研究和比较,得出了两阶段法虽在VRP求解上具有优越性、但其初始解却很少从空间角度考虑的结论。
(3)利用空间聚类对需求点进行分簇以得到初始解,使得VRP问题变为K个旅行商问题(TSP);并根据VRP的特点,对所采用的K-means算法进行改进,同时通过实验验证了正确性。
(4)在各分簇内引入蚁群算法来解决TSP问题,并通过仿真实验,研究分析了蚁群算法在求解TSP问题上各参数对结果的影响及其最佳设置。
(5)通过对标准VRP问题进行实验与结果分析,验证了“加权K-means+蚁群”算法求解VRP问题的有效性、准确性及优越性。
最后,在实验结果的基础上,提出切合实际系统集成方案,完成了一个原型系统,实现空间和属性数据库的统一存储管理、电子地图基本操作、最优路径查找功能。
With the development of market economy, logistics influences to the economic activity obviously day by day. Distribution is the tach in the logistics activity with consumer connected link directly, logistics distribution for vehicle routing problem, is a pivotal tach of the logistics distribution optimization. Therefore, carrying on the vehicle routing problem and establishment a system that can meet the customer’s needs immediately, is an important topic to promote the service and the resources use rate.
80 percent of logistics distribution information which depends on the geography space is related with the geography space information directly. While GIS , which support us to get, manage, operate, analyze and display the geographic space data, has the powerful capability of managing and analyzing geography data. So we apply GIS to the logistics system to optimize VRP. This paper’s main research works include:
(1)To research the development and current character of logistics distribution system and GIS, and to point out the necessity and feasibility of the integration of logistics distribution system and GIS.
(2)To study and compare the VRP current research work, and get the conclusion of 2-Phase Algorithm’s advantage , but the initial value is not considered by the spatial point.
(3) The problem of customers classifying is solved by clustering algorithm, then the Vehicle Routing Problem is abstracted as TSP. Aiming at the trait of VRP, to accomplish improvement and implement to the K-means, and prove the veracity by experiment.
(4)Then Ant Colony Algorithm was used to offer solution to TSP. By making stimulation experiment, this experiment also devoted to investigations of how to set parameters which affects the capability and results, when Ant Colony Algorithm is employed in dealing with TSP. And analyzing the experiment result proves the validity and correctness of the combination algorithm of improved K-means and Ant Colony Algorithm.
(5)According to experiment, to prove the validity、veracity and superiority of the algorithm proposed by this paper to solve VRP.
Finally, on the basis results of above experiment, this paper have proposed practical system integration solutions and then accomplished a prototype model. This research have realized the storage and management of spatial and attribute database, the basic operation function of electronic map and the shortest route searching function component module.
引文
[1] 罗来仪,王智强.现代物流知识问答[M].北京:对外经济贸易大学出版,2002.
[2] 霍亮.空间物流信息系统[M].北京:测绘出版社.2006.
[3] 叶水盛.GIS 基本原理与应用开发[M].吉林:吉林大学出版社,2004.
[4] 陈智,基于 GIS 的物流配送系统的研究与应用[D].浙江大学,2006.
[5] 邬伦,张晶,赵伟.地理信息系统[M].北京:电子工业出版社,2002.
[6] 刘志强,丁鹏,盛焕烨.物流配送系统设计[M].清华大学出版社,2004.
[7] 谢如鹤,张得志,罗荣武.物流系统规划[M].北京:中国物资出版社,2007.
[8] 李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物流出版社,2001.
[9] 马卫民.第三方物流配送优化问题及其竞争策略[D].西安交通大学,2003.
[10] 王之泰.物流工程研究[M].北京:首都经济贸易大学出版社,2004.
[11] 王景恒.物流关键技术优化方法研究[D].吉林大学.2006.
[12] 乐阳, 龚健雅. Dijkstra 最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3):p209-212.
[13] Brebner G., Woods R.. Dijkstra’s Shortest Path Routing Algorithm in Reconfigurable Hardware [J]. FPL2001, LNCS 2147, 2001:p653-657.
[14] Dieter Jungnickel. A Hard Problem: The TSP [J]. Algorithms and Computation in Mathematics, 2005:p1431-1550.
[15] Laporte G.. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms [J]. European Journal of Operational Research,1992,59: p345-358.
[16] David Simchi-Levi, Xin Chen, Julien Bramel. The Capacitated VRP with Unequal Demands [J]. Springer Series in Operations Research and Financial Engineering, The Logic of Logistics, 2005:p229-255.
[17] David Pisinger, Stefan Ropke. A general heuristic for vehiclerouting problem [J]. Computers&Operations Research,2007,34(88): p2403-2435.
[18] Destocherg M.,Lcustra J.K., Savelsbergh M.W..A Classification Scheme for Vehicle Routing and scheduling Problems [J]. European Journal of Operational Research, 1990, Res.46:p322-332.
[19] 韩世莲.物流配送线路多目标优化方法研究[D].东南大学,2006.
[20] 郎茂祥.物流配送车辆调度问题的模型和算法研究[D].北方交通大学2002.
[21] N.Christofides, A.Mingozzi, P.Toth. Exact Algorithms for The Vehicle Routing Problem, Based on Spanning Tree And Shortest Path Relaxations [J]. Math. Program, 1981,20: p255-282.
[22] Y.Caseau, F.Laburthe. Heuristics for Large Constrained Vehicle Routing Problems [J]. Journal of Heuristics, 1999,5(3):p281-303.
[23] 张潜,高立群.定位-运输路线安排问题的两阶段启发式算法[J].控制与决策, 2004,19(7):p773-777.
[24] 戴锡.车辆路线问题的二阶段启发式算法及其在现代物流中的应用[D].复旦大学,2004.
[25] Bayir M.A., Toroslu I.H., Cosar A.. Genetic algorithm for the multiple-query optimization problem [J]. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2007, 37(1):p147-153.
[26] Bucci M.. Optimization with simulated annealing [J]. C/C++ Users Journal, 2001,19(11):p671-680.
[27] Pacheco J., Marti R. Tabu search for a multi-objective routing problem [J]. Journal of the Operational Research Society, 2006, 57(1):p29-37.
[28] Fiesler E. Neural network classification and formalization [J]. Computer Standards & Interfaces, 1994, 16(3):p145-152.
[29] Macro Dorigo, Thomas Stutzle 著.张军,胡晓敏,罗旭耀等译.蚁群优化[M].北京:清华大学出版社,2007.
[30] 段海滨.蚁群算法原理及其应用[M].科学出版社, 2007.
[31] 左洪浩.蚁群优化算法及其应用研究[D].中国科学技术大学,2006.
[32] 高尚.蚁群算法理论、应用及其与其它算法的混合[D].南京理工大学 2005.
[33] Dorigo M., Maniczzo V., Colomi A.. Ant System: Optimization by A Colony of Cooperating Agents [J]. IEEE Transactions on Systems Man, and Cybernetics Part B, 1996,26(1): p29-41.
[34] Dorigo M., Gambardella L M.. Ant Colony System: A cooperative learning approach to the traveling salesman problem [J]. IEEE Trans. On Evolutionary Computation, 1997,1(1): p53-66.
[35] JüRGEN BRANKE and MICHAEL GUNTSCH. Solving the Probabilistic TSP with Ant Colony Optimization [J].Journal of Mathematical Modelling and Algorithms, 2004,3(4):p403-425.
[36] Sérgio Barreto, Cartlos Ferreira, José Paixāo, Beatriz Sousa Santos. Using clustering analysis in a capacitated location-routing problem [J]. European Journal of Operational Research, 2007, 170:p968-977.
[37] 孙焕良.基于空间分析的优化聚类算法及相关技术研究[D].东北大学,2005.
[38] 杨春成.空间数据挖掘中聚类分析算法的研究[D].解放军信息工程大学,2004 .
[39] (美)Shashi Ahekhar, Sanjay Chawla 著. 谢昆青,马修军,杨冬青.空间数据库[M].机械工业出版社,2003.
[40] Mu-Chun Su, Chien-Hsing Chou. A Modified Version of the K-Means Algorithm with a Distance Based on Cluster Symmetry [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2001, 23(6):p674-680.
[41] Ye Z W, Zheng Z B.. Research on the configuration of parameter α、β、ρ in ant algorithm exemplified by TSP[C]. Proceedings of theInternational Conference on Machine Learning and Cybernetics, 2003, 56(2):p2106-2111.
[42] Marc Reimann, Karl Doerner, Richard F. Hartl. Analyzing a Unified Ant System for the VRP and Some of Its Variants [J]. Springer Berlin/Heidelberg, 2003, LNCS2611:p300-310.
[43] B.Bullnheimer, R.F.Hartl, C.Strauss. An Improved ant System Algorithm for The Vehicle Routing Problem [J]. Annals of Operations Research, 1999, 89(13):p561-581.
[44] Gutjahr WJ. A graph-based ant system and its convergence [J]. Future Generation Computer System, 2000,16(8):p873-888.
[45] Bernd.Bullnheimer, Richard F.Hartl, Christine Strauss. Applying the Ant System to the Vehicle Routing Problem[C]. 2nd International Conference On Metaheuristics-MIC97, 1997:p1-11.
[46] 弓晋丽,程志敏.基于 matlab 物流配送路径优化问题遗传算法实现的实现[J]. 物流科技,2005,29(131):p103-105.
[47] Matis, Peter. Management of street routing problems using decision support system [J]. Komunikacie, 2006,8(3):p5-8.
[48] Tarantilis, C.D. Using a spatial decision support system for solving the vehicle routing problem [J]. Information and Management, 2002,39(5):p359-375.
[49] 李峻.GIS 决策支持可视化的研究[D].武汉大学,2001.
[50] http://www.supermap.com.cn[EB/OL], 超图的特点与应用.
[51] 徐业昌,李树祥,朱建民等.基于地理信息系统的最佳路径搜索算法[J].中国图像图形学报,1998,3(1):p39-43.
[52] 王平.GIS 中拓扑关系的建立与更新[D].解放军信息工程大学, 2002.
[53] http://www.crpc.rice.edu/softlib/catalog/tsplib.html [DB/OL]. TSP标准数据库.
[54] http://or.ingce.unibo.it/research/vrplib-a-vehicle-routing-problem-resources-library[DB/OL], VRP 问题标准数据库.
[2] 霍亮.空间物流信息系统[M].北京:测绘出版社.2006.
[3] 叶水盛.GIS 基本原理与应用开发[M].吉林:吉林大学出版社,2004.
[4] 陈智,基于 GIS 的物流配送系统的研究与应用[D].浙江大学,2006.
[5] 邬伦,张晶,赵伟.地理信息系统[M].北京:电子工业出版社,2002.
[6] 刘志强,丁鹏,盛焕烨.物流配送系统设计[M].清华大学出版社,2004.
[7] 谢如鹤,张得志,罗荣武.物流系统规划[M].北京:中国物资出版社,2007.
[8] 李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物流出版社,2001.
[9] 马卫民.第三方物流配送优化问题及其竞争策略[D].西安交通大学,2003.
[10] 王之泰.物流工程研究[M].北京:首都经济贸易大学出版社,2004.
[11] 王景恒.物流关键技术优化方法研究[D].吉林大学.2006.
[12] 乐阳, 龚健雅. Dijkstra 最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3):p209-212.
[13] Brebner G., Woods R.. Dijkstra’s Shortest Path Routing Algorithm in Reconfigurable Hardware [J]. FPL2001, LNCS 2147, 2001:p653-657.
[14] Dieter Jungnickel. A Hard Problem: The TSP [J]. Algorithms and Computation in Mathematics, 2005:p1431-1550.
[15] Laporte G.. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms [J]. European Journal of Operational Research,1992,59: p345-358.
[16] David Simchi-Levi, Xin Chen, Julien Bramel. The Capacitated VRP with Unequal Demands [J]. Springer Series in Operations Research and Financial Engineering, The Logic of Logistics, 2005:p229-255.
[17] David Pisinger, Stefan Ropke. A general heuristic for vehiclerouting problem [J]. Computers&Operations Research,2007,34(88): p2403-2435.
[18] Destocherg M.,Lcustra J.K., Savelsbergh M.W..A Classification Scheme for Vehicle Routing and scheduling Problems [J]. European Journal of Operational Research, 1990, Res.46:p322-332.
[19] 韩世莲.物流配送线路多目标优化方法研究[D].东南大学,2006.
[20] 郎茂祥.物流配送车辆调度问题的模型和算法研究[D].北方交通大学2002.
[21] N.Christofides, A.Mingozzi, P.Toth. Exact Algorithms for The Vehicle Routing Problem, Based on Spanning Tree And Shortest Path Relaxations [J]. Math. Program, 1981,20: p255-282.
[22] Y.Caseau, F.Laburthe. Heuristics for Large Constrained Vehicle Routing Problems [J]. Journal of Heuristics, 1999,5(3):p281-303.
[23] 张潜,高立群.定位-运输路线安排问题的两阶段启发式算法[J].控制与决策, 2004,19(7):p773-777.
[24] 戴锡.车辆路线问题的二阶段启发式算法及其在现代物流中的应用[D].复旦大学,2004.
[25] Bayir M.A., Toroslu I.H., Cosar A.. Genetic algorithm for the multiple-query optimization problem [J]. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2007, 37(1):p147-153.
[26] Bucci M.. Optimization with simulated annealing [J]. C/C++ Users Journal, 2001,19(11):p671-680.
[27] Pacheco J., Marti R. Tabu search for a multi-objective routing problem [J]. Journal of the Operational Research Society, 2006, 57(1):p29-37.
[28] Fiesler E. Neural network classification and formalization [J]. Computer Standards & Interfaces, 1994, 16(3):p145-152.
[29] Macro Dorigo, Thomas Stutzle 著.张军,胡晓敏,罗旭耀等译.蚁群优化[M].北京:清华大学出版社,2007.
[30] 段海滨.蚁群算法原理及其应用[M].科学出版社, 2007.
[31] 左洪浩.蚁群优化算法及其应用研究[D].中国科学技术大学,2006.
[32] 高尚.蚁群算法理论、应用及其与其它算法的混合[D].南京理工大学 2005.
[33] Dorigo M., Maniczzo V., Colomi A.. Ant System: Optimization by A Colony of Cooperating Agents [J]. IEEE Transactions on Systems Man, and Cybernetics Part B, 1996,26(1): p29-41.
[34] Dorigo M., Gambardella L M.. Ant Colony System: A cooperative learning approach to the traveling salesman problem [J]. IEEE Trans. On Evolutionary Computation, 1997,1(1): p53-66.
[35] JüRGEN BRANKE and MICHAEL GUNTSCH. Solving the Probabilistic TSP with Ant Colony Optimization [J].Journal of Mathematical Modelling and Algorithms, 2004,3(4):p403-425.
[36] Sérgio Barreto, Cartlos Ferreira, José Paixāo, Beatriz Sousa Santos. Using clustering analysis in a capacitated location-routing problem [J]. European Journal of Operational Research, 2007, 170:p968-977.
[37] 孙焕良.基于空间分析的优化聚类算法及相关技术研究[D].东北大学,2005.
[38] 杨春成.空间数据挖掘中聚类分析算法的研究[D].解放军信息工程大学,2004 .
[39] (美)Shashi Ahekhar, Sanjay Chawla 著. 谢昆青,马修军,杨冬青.空间数据库[M].机械工业出版社,2003.
[40] Mu-Chun Su, Chien-Hsing Chou. A Modified Version of the K-Means Algorithm with a Distance Based on Cluster Symmetry [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2001, 23(6):p674-680.
[41] Ye Z W, Zheng Z B.. Research on the configuration of parameter α、β、ρ in ant algorithm exemplified by TSP[C]. Proceedings of theInternational Conference on Machine Learning and Cybernetics, 2003, 56(2):p2106-2111.
[42] Marc Reimann, Karl Doerner, Richard F. Hartl. Analyzing a Unified Ant System for the VRP and Some of Its Variants [J]. Springer Berlin/Heidelberg, 2003, LNCS2611:p300-310.
[43] B.Bullnheimer, R.F.Hartl, C.Strauss. An Improved ant System Algorithm for The Vehicle Routing Problem [J]. Annals of Operations Research, 1999, 89(13):p561-581.
[44] Gutjahr WJ. A graph-based ant system and its convergence [J]. Future Generation Computer System, 2000,16(8):p873-888.
[45] Bernd.Bullnheimer, Richard F.Hartl, Christine Strauss. Applying the Ant System to the Vehicle Routing Problem[C]. 2nd International Conference On Metaheuristics-MIC97, 1997:p1-11.
[46] 弓晋丽,程志敏.基于 matlab 物流配送路径优化问题遗传算法实现的实现[J]. 物流科技,2005,29(131):p103-105.
[47] Matis, Peter. Management of street routing problems using decision support system [J]. Komunikacie, 2006,8(3):p5-8.
[48] Tarantilis, C.D. Using a spatial decision support system for solving the vehicle routing problem [J]. Information and Management, 2002,39(5):p359-375.
[49] 李峻.GIS 决策支持可视化的研究[D].武汉大学,2001.
[50] http://www.supermap.com.cn[EB/OL], 超图的特点与应用.
[51] 徐业昌,李树祥,朱建民等.基于地理信息系统的最佳路径搜索算法[J].中国图像图形学报,1998,3(1):p39-43.
[52] 王平.GIS 中拓扑关系的建立与更新[D].解放军信息工程大学, 2002.
[53] http://www.crpc.rice.edu/softlib/catalog/tsplib.html [DB/OL]. TSP标准数据库.
[54] http://or.ingce.unibo.it/research/vrplib-a-vehicle-routing-problem-resources-library[DB/OL], VRP 问题标准数据库.