﻿ ﻿ 一种基于遗传算法的多模式多标准路径规划方法
 文章快速检索 高级检索

A Multi-modal Multi-criteria Route Planning Method Based on Genetic Algorithm
YU Haicong1,2LU Feng1
Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101，China
First author: YU Haicong (1984—), male, PhD, interested in multi-modal transportation network, route planning, multi-creteria optimization, and GIS for transportation. E-mail： yuhc@lreis.ac.cn
Corresponding author：LU Feng E-mail：luf@lreis.ac.cn
Abstract: How to provide multi-criteria routing service has been a hot topic for advanced travel information systems. Basically, the multi-criteria routing is a complex NP problem, and involves different transportation modes. Arbitrary weight assignment for various criteria will remarkably affect the routing results. Thus, the challenge is to determine the appropriate relationship among multiple criteria.A multi-criteria route planning method for multi-modal transportation system was proposed. It took the advantage of genetic algorithm for solving optimization problems and extended it to multi-modal routing environment. Various length of chromosome with mode tags was used to encode individuals. Both intra- and inter-mode evolution operators were defined to guarantee the diversity. Pareto ranking method with a p-dimensional vector representing multiple criteria was 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

1 多标准路径问题

GA在路径规划中已有应用。在路径编码研究方面，编码方式的改进可以提高搜索效率，如基于优先权的路径编码方法[11]和基因值顺序表示该基因连接的后续基因位置[12]的编码方法。但是，这两种定长染色体编码方法的空间复杂度较高，对大规模网络缺乏可行性。一些学者提出了利用遗传算法解决单标准路径问题的方法，如TSP[13]、k则最短路径[14]、VRP[15]、最短路径优化[16]、公交线路优化[17]等。也有部分学者研究了单一交通模式下的多标准路径问题，包括针对开放空间的三维环境路径规划[18]和针对网络受限空间的路径规划[3, 19]等。关于多模式环境下的多标准路径规划问题，文献[20—21]提出了一种适应换乘网络的遗传算法。但该方法限于公共交通或步行换乘网络，无法支持具有复杂结构的公交模型，并且存在染色体编码冗余。

2 多模式多标准路径方法

2.1 染色体编码与解码

 图 1 多模式路径染色体编码示意图 Fig. 1 Chromosome encoding for multi-modal routes

2.2 适应性评价

xkij-xkji=-1j为起点1j为终点0j为非起止点 xkij=1 边(i,j)在路径中0其他 k=1,2,…,m

2.3 进化算子

 图 2 模式内交叉算子 Fig. 2 Intra-modal crossover operator

 图 3 模式间交叉算子 Fig. 3 Inter-modal crossover operator

 图 4 模式内变异算子 Fig. 4 Intra-modal mutation operator

 图 5 模式间变异算子 Fig. 5 Inter-modal mutation operator

2.4 计算流程

 图 6 多模式多标准遗传算法流程 Fig. 6 GA based multi-modal multi-criteria routing

3 试验分析与讨论

 pc phc pm phm 案例1 0.25 0.25 0.15 0.15 案例2 0.35 0.35 0.05 0.05 案例3 0.05 0.05 0.35 0.35 案例4 0.20 0.20 0.20 0.20 案例5 0.25 0.15 0.25 0.15

 图 7 更新数变化对比 Fig. 7 Scenarios with new generated number

 时间/min 费用/元 换乘次数 换乘模式 253 0 0 W 43 40 0 T 36 26 1 (W)ST 42 2.4 1 (W)S(W)B(W) 32 32 2 TST 40 12 2 (W)STB(W) 66 0.8 2 (W)BB(W)B(W)

 图 8 结果显示 Fig. 8 Results visualizations

 [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[M].Berlin: Springer-Verlag, 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[C]//Multiple Criteria Decision Making: Theory and Application.[S.l.]:Springer-Verlag,1980: 109. [8] BRUMBAUGH S 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]. Computers and Operations Research, 2000, 27(6):507-524. [10] LOZANO A, STORCHI G. Shortest Viable Path Algorithm in Multimodal Networks[J]. Transportation Research Part A: Policy and Practice, 2001, 35(3):225-241. [11] GEN M, CHENG R, WANG D. Genetic Algorithms for Solving Shortest Path Problems[C]//Proceedings of IEEE International Conference on Evolutionary Computation. Indianapolis:IEEE Press,1997:401-406. [12] INAGAKI J, HASEYAMA M, KITAJIMA H. A Genetic Algorithm for Determining Multiple Routes and Its Applications[C]// Proceedings of the 1999 IEEE International Symposium on Circuits and Systems.[S.l.]:IEEE, 1999:137-140. [13] SUN Huiwen. A Genetic Algorithm for Travelling Salesman Problems[J]. Journal of Southwest Jiaotong University, 1996, 31(5): 550-554. (孙惠文. 遗传算法求解旅行商问题[J]. 西南交通大学学报, 1996,31(5):550-554.) [14] MA Xuan. A Genetic Algorithm for k Optimal Paths Problem[J]. 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: Beijing Jiaotong University, 2010. (蒋波. 基于遗传算法的带时间窗车辆路径优化问题研究[D]. 北京: 北京交通大学, 2010.) [16] LI Qing, ZHANG Wei, YIN Yixin, et al. An Improved Genetic Algorithm for Optimal Path Planning[J]. Information and Control, 2006, 35(4):444-447. (李擎, 张伟, 尹怡欣, 等. 一种用于最优路径规划的改进遗传算法[J]. 信息与控制, 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] LIU Xuhong, ZHANG Guoying, LIU Yushu, et al. Path Planning Based on Multi-objective Genetic Algorithm[J]. Transactions of Beijing Institute of Technology, 2005, 25(7):613-616. (刘旭红, 张国英, 刘玉树, 等. 基于多目标遗传算法的路径规划[J]. 北京理工大学学报, 2005, 25(7):613-616.) [19] ABDELGAWAD H, ABDULHAI B, WAHBA M. Multiobjective Optimization for Multimodal Evacuation[J]. Transportation Research Record: Journal of the Transportation Research Board, 2010, 2196:21-33. [20] ABBASPOUR R A, SAMADZADEGAN F. A Solution for Time-dependent Multimodal Shortest Path Problem[J]. Journal of Applied Sciences, 2009, 9(21):3804-3812. [21] 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. [22] MICHALEWICZ Z. Genetic Algorithms+Data Structures=Evolution Programs[M]. Berlin: Springer-Verlag, 1996. [23] FONSECA C M, FLEMING P J. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization[C]//Proceedings of the Fifth International Conference on Genetic Algorithms, University of Illinois at Urbana-Champaign.San Mateo:[s.n.],1993:416-423. [24] YU Haicong, LU Feng. A Multi-criteria Route Planning Approach Considering Walking Guidance[J]. Journal of Image and Graphics, 2010, 15(4):677-683. (于海璁, 陆锋. 一种顾及步行引导的多标准路径规划方法[J]. 中国图象图形学报, 2010,15(4):677-683.) [25] ZITZLER E, DEB K, THIELE L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results[J].Evolutionary Computation, 2000, 8(2):173-195.
http://dx.doi.org/10.13485/j.cnki.11-2089.2014.
0013

0

#### 文章信息

YU Haicong, LU Feng

A Multi-modal Multi-criteria Route Planning Method Based on Genetic Algorithm

Acta Geodaeticaet Cartographica Sinica,2014,43(1):89-96.
"http://dx.doi.org/10.13485/j.cnki.11-2089.2014.0013