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

Abstract

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

CLC Number:

P208

References

[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