Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 32759
Geospatial Network Analysis Using Particle Swarm Optimization

Authors: Varun Singh, Mainak Bandyopadhyay, Maharana Pratap Singh

Abstract:

The shortest path (SP) problem concerns with finding the shortest path from a specific origin to a specified destination in a given network while minimizing the total cost associated with the path. This problem has widespread applications. Important applications of the SP problem include vehicle routing in transportation systems particularly in the field of in-vehicle Route Guidance System (RGS) and traffic assignment problem (in transportation planning). Well known applications of evolutionary methods like Genetic Algorithms (GA), Ant Colony Optimization, Particle Swarm Optimization (PSO) have come up to solve complex optimization problems to overcome the shortcomings of existing shortest path analysis methods. It has been reported by various researchers that PSO performs better than other evolutionary optimization algorithms in terms of success rate and solution quality. Further Geographic Information Systems (GIS) have emerged as key information systems for geospatial data analysis and visualization. This research paper is focused towards the application of PSO for solving the shortest path problem between multiple points of interest (POI) based on spatial data of Allahabad City and traffic speed data collected using GPS. Geovisualization of results of analysis is carried out in GIS.

Keywords: GIS, Outliers, PSO, Traffic Data.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1094567

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2819

References:


[1] N. Deo and C.Y. Pang, "Shortest-path algorithms: Taxonomy and Annotation," Networks, vol. 14(2), 1984 pp. 275–323.
[2] C.W. Ahn and R.S. Ramakrishna, "A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations," IEEE Trans on Evolutionary Computation, vol. 6, no. 6, 2002, pp. 566-579.
[3] C. Davies and P. Lingras, "Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks", Eur J Oper Res, vol. 144(1), 2003, pp. 27–38.
[4] C. Mohamed, J. Bassem and L. Taicir, "A genetic algorithms to solve the bicriteria shortest path problem," Elec. Notes Discrete Math., vol. 36, 2010, pp.851–858.
[5] R. Hassanzadeha , I. Mahdavia, N. M. Amirib and A. Tajdina, "A Genetic Algorithm for Solving Fuzzy Shortest Path Problems with Mixed Fuzzy Arc Lengths," Mathematical and Computer Modelling, vol. 57(1–2), 2013, pp. 84–99.
[6] Hertz, , G. Laporte, and M. Mittaz, "A tabu search heuristics for the capacitated arc routing problem", J. Operations Research, vol. 48, 2000, pp. 129-135.
[7] Brandao, J and R.W. Eglese, "A deterministic tabu search algorithm for the capacitated arc routing problem," Computers and Operations Research, vol. 35, no. 4, 2008, pp. 1112-1126.
[8] S.O. Ok, W.J. Seo, J.H. Ahn, S. Kang and B. Moon, "An Ant Colony Optimization Approach for the Preference-Based Shortest Path Search, Communication and Networking," J. Comm. Comp .and Inf. Science, vol. 56, 2009, pp. 539-546.
[9] L.C.T. Bezerra, E.F.G. Goldbarg, L.S. Buriol and M.C. Goldbarg, "GRACE: A Generational Randomized ACO for the Multi-objective Shortest Path Problem," Evolutionary Multi-Criterion Optimization, LNCS, vol. 6576, 2011, pp. 535-549.
[10] W. Mohemmed , N. C. Sahoo, T.K. Geok, "Solving shortest path problem using particle swarm optimization", J. Applied Soft Computing, vol. 8 (4), 2008, pp. 1643-1653.
[11] Y. Tsujimura ,"Entropy-based genetic algorithm for solving TSP," Proc. IEEE Second Int. Conf. Knowledge-Based Intelligent Electronic Systems, vol. 2, 1998, pp. 285 - 290.
[12] H. Ismkhan, and K. Zamanifar, "Developing Improved Greedy Crossover to Solve Symmetric Traveling Salesman Problem," Int. J. Comp. Sc., vol. 9(4), 2012, pp.121-126.
[13] Y. Nagata and D. Soler, "A New Genetic Algorithm for the Asymmetric Traveling Salesman Problem," J. Expert Systems with Applications, vol. 39(10), 2012, pp. 8947-8953.
[14] C. X. Wang, D.W. Cui, Z.R. Wang, and D. Chen, "A Novel Ant Colony System Based on Minimum 1-Tree and Hybrid Mutation for TSP," Advances in Natural Computation, LNCS, vol. 3611, 2005, pp. 1269-1278.
[15] M. Mavrovouniotis and S. Yang, "A Memetic Ant Colony Optimization Algorithm for the Dynamic Travelling Salesman Problem", Soft Computing, vol. 15(7), 2011, pp. 1405-1425.
[16] R. Skinderowicz, "Ant Colony System with Selective Pheromone Memory for TSP", Computational Collective Intelligence: Technologies and Applications., LNCS, vol. 7654, 2012, pp. 483-492.
[17] X.H. Shi, Y.C. Liang, H.P. Lee, C. Lu and Q.X. Wang, "Particle swarm optimization-based algorithms for TSP and generalized TSP", Inf. Proc. Letters, vol. 103(5), 2007, pp.169–176.
[18] Y.F. Liao, D. Han Yau and C.L. Chen, "Evolutionary Algorithm to Traveling Salesman Problems," Computers and Mathematics with Applications, vol. 64(5), 2012, pp. 788–797.
[19] R.C. Eberhart and Y. Shi, "Comparison Between Genetic Algorithms and Particle Swarm Optimization", Proc .the 7th Annual Conf. on Evolutionary Programming, 1998, pp. 611–616.
[20] K. Sooda and T.R.G. Nair, "Comparative Analysis for Determining the Optimal Path using PSO and GA," Int. J. of Comp. App., vol. 32, no.4, 2011, pp. 8-12.
[21] D.W. Boeringer, D.H. Werner, "Particle swarm optimization versus genetic algorithms for phased array synthesis," IEEE Trans. Antennas Propagat. vol. 52 (3), 2004, pp. 771–779.
[22] E. Elbeltagi, T. Hegazy, D. Grierson, "Comparison Among Five Evolutionary Based Optimization Algorithms," Adv. Eng. Inform. vol. 19 (1), 2005, pp. 43–53.
[23] C. R. Mouser and S. A. Dunn, "Comparing genetic algorithms and particle swarm optimisation for an inverse problem exercise," ANZIAM J., vol. 46(E), 2005, pp. C89-C101.
[24] J. Kennedy and R.C. Eberhart, "Particle swarm optimization", Proc. IEEE International Conference on Neural Networks, 1995, pp.1942–1948.
[25] C.A. Quiroga, and D. Bullock. "Travel time studies with Global Positioning and Geographic Information Systems: An Integrated methodology," Trans. Research Part C, vol. 6(1) ,1998, pp. 101-127.
[26] A.F. Jensen, T.V Larsen , "Travel-Time Estimation in Road Networks Using GPS Data”, Unpublished.