基于GIS的城市物流配送路径规划研究
|
摘要
随着计算机和网络技术的进一步发展和应用，现代物流配送正步入一个信息化、自动化、网络化、智能化的发展阶段。特别是近年来GIS在理论和应用中的发展为解决现代化物流配送提供了有利的条件。本文结合电子商务环境下的第三方物流企业的需要，对物流配送中的配送车辆的路径优化问题进行了研究。在借鉴前人研究成果的基础上，将GIS应用于物流配送路径分析中，利用GIS强大的空间分析功能来完善物流分析技术，通过一系列物流配送优化算法模型，开发了基于GIS的城市物流配送路径分析系统，从而为物流配送管理者提供科学的决策依据。
在解决城市物流配送路径规划问题时，本文采用分解的思路把整个路径规划问题分解成为配送区域划分子问题和单车辆路线优化子问题。在配送区域划分的求解过程中，本文首次提出了利用Voronoi图对配送区域进行区划的方法，避免了其他区划方法出现的区域半径确定的随意性以及配送区重叠或配送盲区的问题。在单车辆路线优化的求解过程中，本文采用启发式的方法--遗传算法来实现，并在遗传算法框架中加入局部搜索能力很强的贪婪算法，利用贪婪算法邻域搜索原则建立了一种新的遗传交叉算子--贪婪交叉算子，从而改善了遗传算法的局部搜索能力，达到了快速收敛的效果。
最后本文提出了基于GIS的城市物流配送路径分析系统的总体设计思路和详细的功能设计，并利用ARC／INFOR的MapObjects控件和VB为开发平台，开发了基于GIS的城市物流配送路径分析系统。
With the farther development of computer science and network technology, modern logistics distribution is stepping into quickly progress period .Especially ,in the resent years, the more widely application of GIS provides a advantageous condition to take the logistics distribution problem .This paper study on how to optimize the planning of vehicle routing to meet the demand of the third part logistics company. In order to resolve this NP problem ,this research introduces GIS into city logistics distribution planning system, modeling a sets of optimization algorithms based on the spatial analysis functions of GIS and actualize it on GIS platform.In the research on the vehicle routing planning , the whole problem is divided into two phases in the process of building model, which are area partition problem and single vehicle routing problem. This paper provides a new method called Voronoi-partition approach to deal with the area partition problem. As to single vehicle routing problem, a new kind of hybrid genetic algorithm is put forward. The idea for this hybrid genetic algorithm is to add a bran-new greedy operator into the framework of genetic algorithm to improve the efficiency of the algorithm .At last, this paper discusses about the framework design and detailed function design for the city logistics vehicle routing planning system based on GIS and actualize this system using mapobjects ActiveX control and Visual Basic platform .
在解决城市物流配送路径规划问题时，本文采用分解的思路把整个路径规划问题分解成为配送区域划分子问题和单车辆路线优化子问题。在配送区域划分的求解过程中，本文首次提出了利用Voronoi图对配送区域进行区划的方法，避免了其他区划方法出现的区域半径确定的随意性以及配送区重叠或配送盲区的问题。在单车辆路线优化的求解过程中，本文采用启发式的方法--遗传算法来实现，并在遗传算法框架中加入局部搜索能力很强的贪婪算法，利用贪婪算法邻域搜索原则建立了一种新的遗传交叉算子--贪婪交叉算子，从而改善了遗传算法的局部搜索能力，达到了快速收敛的效果。
最后本文提出了基于GIS的城市物流配送路径分析系统的总体设计思路和详细的功能设计，并利用ARC／INFOR的MapObjects控件和VB为开发平台，开发了基于GIS的城市物流配送路径分析系统。
With the farther development of computer science and network technology, modern logistics distribution is stepping into quickly progress period .Especially ,in the resent years, the more widely application of GIS provides a advantageous condition to take the logistics distribution problem .This paper study on how to optimize the planning of vehicle routing to meet the demand of the third part logistics company. In order to resolve this NP problem ,this research introduces GIS into city logistics distribution planning system, modeling a sets of optimization algorithms based on the spatial analysis functions of GIS and actualize it on GIS platform.In the research on the vehicle routing planning , the whole problem is divided into two phases in the process of building model, which are area partition problem and single vehicle routing problem. This paper provides a new method called Voronoi-partition approach to deal with the area partition problem. As to single vehicle routing problem, a new kind of hybrid genetic algorithm is put forward. The idea for this hybrid genetic algorithm is to add a bran-new greedy operator into the framework of genetic algorithm to improve the efficiency of the algorithm .At last, this paper discusses about the framework design and detailed function design for the city logistics vehicle routing planning system based on GIS and actualize this system using mapobjects ActiveX control and Visual Basic platform .
引文
1．牟旭东，陈健．物流—第三利润源．上海：上海远东出版社，2002
2．陈景，杨开忠．电子商务环境下我国物流业发展对策探讨．经济地理，2001，21(5)：55-56
3. Dantizig G., Ramser J.. The truck dispatching problem. Management Science, 1959(6): 80-91
4. Slin and B. Kernighan, An Effective Heuristic Algorithm for me Traveling Salesman Problem. Operation Research, 1973(21): 112-103
5. Clark G. and Wright J.. Scheduling of vehicles from a central depot to a number of delivery points. Opens. Res, 1964(4.): 25-27
6. Gillett B. E., L. R. Miller. A heuristic algorithm for the vehicle Dispatch Problem. Operations Research, 1974(22): 340-349
7. Christofides N, Mingozzi A, Toth p. The Vehicle Routing Problem, Combinatorial Optimization: Johnly Wiley, New York, 1979
8. Gendreau M.. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operation Research, 1996, 44(3): 469-477
9. Heuing-Suk Hwang. Design of supply-chain logistics system considering service level. Computers & Industrial Engineering 2002(43): 283-297
10．汤国安，赵牡丹．地理信息系统．北京：科学出版社，2001
11．刘志强，丁鹏，盛焕烨．物流配送系统设计．北京：清华大学出版社，2004
12．乐阳．网络分析模型在GIS中的实现与应用：[硕士学位论文]．武汉：武汉测绘科技大学，1999
13．王杰臣，毛海城，杨得志．图的结点—弧段联合结构表示法及其在GIS最优路径选取中的应用．测绘学报，2000(2)：24-28
14．王苏男，宋伟，姜文生．最短路径算法的比较．第三届中国人工智能联合学术会，1993
15．陆锋．最短路径算法：分类体系与研究进展．测绘学报，2001(8)：45—48
16．李林奎．达明公司物流配送系统规划与设计：[硕士学位论文]．兰州：西北工业大学，2003
17．周怡丹．基于GIS平台的物流配送路径规划的研究：[硕士学位论文]．武汉：武汉 大学，2003
18．舒永钢．基干真实街道的规模配送车辆线路优化问题研究：[硕士学位论文]．杭州：杭州商学院，2004
19．万志坚等．物流基础管理．广州：广东经济出版社，2005
20．Gary P．，Schneider，James T Perry．Electronic Commerce．北京：机械工业出版社，2000
21．万志坚等．物流企业管理．广州：广东经济出版社，2005
22．王江晴．符号智能与计算智能．武汉：湖北科学技术出版社，2002
23．王小平，曹立明．遗传算法—理论、应用与软件实现．西安：西安交通大学出版社，2002
24．谢秉磊，李军，郭耀煌．遗传算法在非满载车辆线路安排问题中的应用．中国学术期刊，1999(8)：1068-1069
25．胡小兵，吴树范，江驹．TSP的一种改进遗传算法．计算技术与自动化，2000(4)：24—26
26. Michalewicz Z.Genetic Algorithm+Data Structure=Evolution Programs, 2nd Springer-Verlag, New York, 1994
27. Bean. J. Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on ComPuting. 1994(6): 154—160
28．陈龙．基于遗传算法的约束性多TSP问题及其应用．重庆邮电学院学报，2000(12)：35—38
29. Goldberg D. E., Lingle R.. Alleles, Location and the Traveling Salesman Problem. Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985, 154-159
30. Davis L. Job Scheduling with Genetic Algorithms. Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985, 136-140.
31．郑晨辉．基于GIS的物流配送辅助系统研究：[硕士学位论文]．哈尔滨：哈尔滨理工大学，2004
32．乌伦，刘瑜，张晶等．地理信息系统—原理、方法和应用．北京：科学出版社，2001
33．薛伟．MapObjects—地理信息系统程序设计．北京：国防工业出版社，2004
34．刘光，刘小东．地理信息系统二次开发实例教程—VC．NET和MapObjects实现． 北京：清华大学出版社，2004
35．马良．TSP及其扩展问题的混合型启发式算法．上海理工大学学报，1999(21)：25-27
36．李强，黄莎白．GIS环境下的最佳路径规划．信息与控制，2000(29)：24-29
37．刘云翔．最短路径分析及GIS／GPS集成技术研究：[硕士学位论文]．长沙：国防科学技术大学，2002
38．刘三强，徐敏．基于矢量地图的路径寻优算法．微电子学与计算机，1999(5)：18—23
39．张可明，宋伯慧．物流系统分析．北京：清华大学出版社，北京交通大学出版社，2004
40．李军，郭耀煌．物流配送车辆优化调度理论与方法．北京：中国物资出版社，2001
41．陈军．Voronoi动态空间数据模型．北京：测绘出版社，2002
42. Aurenhammer, Franz. Voronoi diagram-A survey of a fundamental geometric data structure.ACM Computing Surveying, 1991,23(3):345-405
43．陈国良，王煦法，庄镇泉，王东生．遗传算法及其应用．北京：人民邮电出版社，1996
44. David Hand,Heikki Mannila Padhraic,Smyth. Principles of Data of Mining.张银奎等译．北京：机械工业出版社，中兴出版社，2003
45．何琳，王科俊．最优保留遗传算法及其收敛性分析．控制与决策，2000，15(1)：63—66
46．胡志杰．基于GIS的配送路径规划方法研究：[硕士学位论文]．武汉：武汉理工大学，2005
47．龚沛曾等编．Visual Basic程序设计教程．高等教育出版社．2000
48．韩鹏编著．地理信息系统开发—Mapobjects方法．武汉大学出版社．2004
2．陈景，杨开忠．电子商务环境下我国物流业发展对策探讨．经济地理，2001，21(5)：55-56
3. Dantizig G., Ramser J.. The truck dispatching problem. Management Science, 1959(6): 80-91
4. Slin and B. Kernighan, An Effective Heuristic Algorithm for me Traveling Salesman Problem. Operation Research, 1973(21): 112-103
5. Clark G. and Wright J.. Scheduling of vehicles from a central depot to a number of delivery points. Opens. Res, 1964(4.): 25-27
6. Gillett B. E., L. R. Miller. A heuristic algorithm for the vehicle Dispatch Problem. Operations Research, 1974(22): 340-349
7. Christofides N, Mingozzi A, Toth p. The Vehicle Routing Problem, Combinatorial Optimization: Johnly Wiley, New York, 1979
8. Gendreau M.. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operation Research, 1996, 44(3): 469-477
9. Heuing-Suk Hwang. Design of supply-chain logistics system considering service level. Computers & Industrial Engineering 2002(43): 283-297
10．汤国安，赵牡丹．地理信息系统．北京：科学出版社，2001
11．刘志强，丁鹏，盛焕烨．物流配送系统设计．北京：清华大学出版社，2004
12．乐阳．网络分析模型在GIS中的实现与应用：[硕士学位论文]．武汉：武汉测绘科技大学，1999
13．王杰臣，毛海城，杨得志．图的结点—弧段联合结构表示法及其在GIS最优路径选取中的应用．测绘学报，2000(2)：24-28
14．王苏男，宋伟，姜文生．最短路径算法的比较．第三届中国人工智能联合学术会，1993
15．陆锋．最短路径算法：分类体系与研究进展．测绘学报，2001(8)：45—48
16．李林奎．达明公司物流配送系统规划与设计：[硕士学位论文]．兰州：西北工业大学，2003
17．周怡丹．基于GIS平台的物流配送路径规划的研究：[硕士学位论文]．武汉：武汉 大学，2003
18．舒永钢．基干真实街道的规模配送车辆线路优化问题研究：[硕士学位论文]．杭州：杭州商学院，2004
19．万志坚等．物流基础管理．广州：广东经济出版社，2005
20．Gary P．，Schneider，James T Perry．Electronic Commerce．北京：机械工业出版社，2000
21．万志坚等．物流企业管理．广州：广东经济出版社，2005
22．王江晴．符号智能与计算智能．武汉：湖北科学技术出版社，2002
23．王小平，曹立明．遗传算法—理论、应用与软件实现．西安：西安交通大学出版社，2002
24．谢秉磊，李军，郭耀煌．遗传算法在非满载车辆线路安排问题中的应用．中国学术期刊，1999(8)：1068-1069
25．胡小兵，吴树范，江驹．TSP的一种改进遗传算法．计算技术与自动化，2000(4)：24—26
26. Michalewicz Z.Genetic Algorithm+Data Structure=Evolution Programs, 2nd Springer-Verlag, New York, 1994
27. Bean. J. Genetic algorithm and random keys for sequencing and optimization. ORSA Journal on ComPuting. 1994(6): 154—160
28．陈龙．基于遗传算法的约束性多TSP问题及其应用．重庆邮电学院学报，2000(12)：35—38
29. Goldberg D. E., Lingle R.. Alleles, Location and the Traveling Salesman Problem. Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985, 154-159
30. Davis L. Job Scheduling with Genetic Algorithms. Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985, 136-140.
31．郑晨辉．基于GIS的物流配送辅助系统研究：[硕士学位论文]．哈尔滨：哈尔滨理工大学，2004
32．乌伦，刘瑜，张晶等．地理信息系统—原理、方法和应用．北京：科学出版社，2001
33．薛伟．MapObjects—地理信息系统程序设计．北京：国防工业出版社，2004
34．刘光，刘小东．地理信息系统二次开发实例教程—VC．NET和MapObjects实现． 北京：清华大学出版社，2004
35．马良．TSP及其扩展问题的混合型启发式算法．上海理工大学学报，1999(21)：25-27
36．李强，黄莎白．GIS环境下的最佳路径规划．信息与控制，2000(29)：24-29
37．刘云翔．最短路径分析及GIS／GPS集成技术研究：[硕士学位论文]．长沙：国防科学技术大学，2002
38．刘三强，徐敏．基于矢量地图的路径寻优算法．微电子学与计算机，1999(5)：18—23
39．张可明，宋伯慧．物流系统分析．北京：清华大学出版社，北京交通大学出版社，2004
40．李军，郭耀煌．物流配送车辆优化调度理论与方法．北京：中国物资出版社，2001
41．陈军．Voronoi动态空间数据模型．北京：测绘出版社，2002
42. Aurenhammer, Franz. Voronoi diagram-A survey of a fundamental geometric data structure.ACM Computing Surveying, 1991,23(3):345-405
43．陈国良，王煦法，庄镇泉，王东生．遗传算法及其应用．北京：人民邮电出版社，1996
44. David Hand,Heikki Mannila Padhraic,Smyth. Principles of Data of Mining.张银奎等译．北京：机械工业出版社，中兴出版社，2003
45．何琳，王科俊．最优保留遗传算法及其收敛性分析．控制与决策，2000，15(1)：63—66
46．胡志杰．基于GIS的配送路径规划方法研究：[硕士学位论文]．武汉：武汉理工大学，2005
47．龚沛曾等编．Visual Basic程序设计教程．高等教育出版社．2000
48．韩鹏编著．地理信息系统开发—Mapobjects方法．武汉大学出版社．2004
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |