一种基于遗传算法的多模式多标准路径规划方法

测绘学报 ›› 2014, Vol. 43 ›› Issue (1): 89-96.

一种基于遗传算法的多模式多标准路径规划方法

于海璁,陆锋

中国科学院地理科学与资源研究所

收稿日期:2012-10-31 修回日期:2013-12-04 出版日期:2014-01-20 发布日期:2014-01-20
通讯作者: 于海璁 E-mail:yuhc@lreis.ac.cn
基金资助:
国家863计划项目;国家自然科学基金面上项目;资源与环境信息系统国家重点实验室自主创新基金

A multi-modal multi-criteria route planning method based on genetic algorithm

Received:2012-10-31 Revised:2013-12-04 Online:2014-01-20 Published:2014-01-20

摘要/Abstract

摘要：

单一路径评价标准难以满足日益多样化的出行路径规划需求。多标准路径规划成为公众出行服务的研究热点。然而，多标准路径规划本质上是具有NP特性的多标准决策问题，且涉及多种交通出行模式。多个不同标准的权重设置将直接影响路径规划结果。因此，如何科学合理地设置不同标准的权重成为多标准路径规划中的技术瓶颈。本文提出了一种适应多模式交通网络环境的多标准路径规划方法，借鉴遗传算法在求解多标准优化问题中的优势，将其扩展到多模式多标准路径规划中。该方法避免了不同出行标准权重设置中的主观性和不确定性，能够实现更为灵活的交通出行模式自动化组合，为出行者提供满足个性化需求的、多标准的出行路径规划服务。

关键词: 路径规划, 多模式, 多标准, 遗传算法

Abstract:

Single criterion routing can not meet the diverse needs of individuals for travel path selection. How to provide multi-criteria routing service has been a hot topic for advanced travel information systems. However, the multi-criteria routing is basically a complex NP problem, and involves different transportation modes. Arbitrary weight assignment for various criterion will remarkably affect the routing results. This paper proposes a multi-criteria route planning method for multi-modal transportation system. It takes the advantage of genetic algorithm for solving optimization problems and extends it to multi-modal routing environment. Various length of chromosome with mode tags is used to encode individuals. Both intra- and inter-mode evaluation operators are defined to guarantee the diversity evaluation. Pareto ranking method with a p-dimensional vector representing multiple criteria is used for fitness calculation. The presented method avoids subjective weight setting procedure, and can obtain various modes combination results for route planning to meet personalized requirements.

Key words: route planning, multi-modal, multi-criteria, genetic algorithms

中图分类号:

P208

于海璁陆锋. 一种基于遗传算法的多模式多标准路径规划方法[J]. 测绘学报, 2014, 43(1): 89-96.

参考文献

[1]MOONEY P,WINSTANLEY A.An evolutionary algorithm for multicriteria path optimization problems[J].International Journal of Geographical Information Science,2006,20(4):401-423 [2]PEREIRA C M N A.Evolutionary multicriteria optimization in core designs: basic investigations and case study[J].Annals of Nuclear Energy,2004,31(11):1251-1264 [3]LI R,LEUNG Y.Multi-objective route planning for dangerous goods using compromise programming[J].Journal of Geographical Systems,2011,13(3):249-271 [4]CHAKRABORTY B.GA-Based Multiple Route Selection for Car Navigation[J].,2004,:76-83 [5]HUANG B, FERY P, XUE L, et al.Seeking the Pareto front for multiobjective spatial optimization problems[J].International Journal of Geographical Information Science,2008,22(5):507-526 [6]MARTINS E Q V.On a multicriteria shortest path problem[J].European Journal of Operational Research,1984,16(2):236-245 [7]HANSEN P.Bicriterion path problems[J].,1980,:- [8]BRUMBAUGH-SMITH J,SHIER D.An empirical investigation of some bicriterion shortest path algorithms[J].European Journal of Operational Research,1989,43(2):216-224 [9]SKRIVER A J V,ANDERSEN K A.A label correcting approach for solving bicriterion shortest-path problems[J].,2000,27(6):507-524 [10]LOZANO A, STORCHI G.Shortest viable path algorithm in multimodal networks[J].,2001,35(3):225-241 [11]GEN M, CHENG R,WANG D.Genetic algorithms for solving shortest path problems[J].IEEE International Conference on Evolutionary Computation,1997,:13-16 [12]INAGAKI J, HASEYAMA M,KITAJIMA H.A genetic algorithm for determining multiple routes and its applications [J].,1999,:- [13]SUN Huiwen.A Genetic Algorithm for Travelling Salesman Problems[J].Journal of Southwest Jiaotong University,1996,31(5):550-554 [14]MA Xuan.A Genetic Algorithm for k Optimal Paths Problem Computer Engineering and Applications, 2006,(12): 100-101. (马炫, 求解k条最优路径问题的遗传算法[J].计算机工程与应用,2006,(12):100-101 [15]JIANG Bo.Study of Vehicle Routing Problem with Time Windows Based on Genetic Algorithm [D]. Beijing Jiaotong University, 2010. (蒋波. 基于遗传算法的带时间窗车辆路径优化问题研究[D]. 北京交通大学,2010. [16]LI Qing, ZHANG Wei, YIN Yi-xin, WANG Zhi-liang.An Improved Genetic Algorithm for Optimal Path Planning[J].Information and Control,2006,35(4):444-447 [17]HUANG Z D, LIU X J, HUANG C C, et al.A GIS-based framework for bus network optimization using genetic algorithm[J].Annals of GIS,2010,16(3):185-194 [18]ABBASPOUR R A,SAMADZADEGAN F.A Solution for Time-Dependent Multimodal Shortest Path Problem[J].Journal of Applied Sciences,2009,9(21):3804-3812 [19]ABBASPOUR R A,SAMADZADEGAN F.An Evolutionary Solution for Multimodal Shortest Path Problem in Metropolises[J].Computer Science and Information Systems,2010,7(4):789-811 [20] MICHALEWICZ Z. Genetic algorithms + data structures = evolution programs [M]. , Berlin; New York: Springer-Verlag.[J].,1996,:- [21]FONSECA C M,FLEMING P J.Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization[J].Proceedings of the Fifth International Conference on Genetic Algorithms, University of Illinois at Urbana-Champaign, July 17-2,1993,:- [22]YU Haicong, LU Feng.A Multi-criteria Route Planning Approach Considering Walking Guidance[J].Journal of Image and Graphics,2010,15(4):677-683 [23]ZITZLER E, DEB K,THIELE L.Comparison of multiobjective evolutionary algorithms: Empirical results[J].Evolutionary computation,2000,8(2):173-195