Computer Science and Information Systems 2010 Volume 7, Issue 4, Pages: 789-811
Full text ( 1068 KB)
Cited by

An evolutionary solution for multimodal shortest path problem in metropolises

Abbaspour Rahim A., Samadzadegan Farhad

This paper addresses the problem of time-dependent shortest multimodal path in complex and large urban areas. This problem is one of the important and practical problems in several fields such as transportation, and recently attracts the research focus due to developments in new application areas. An adapted evolutionary algorithm, in which chromosomes with variable lengths and particularly defined evolutionary stages were used, was employed to solve the problem. The proposed solution was tested over the dataset of city of Tehran. The evaluation consists of computing shortest multimodal path between 250 randomly selected pairs of origins and destination points with different distances. It was assumed that three modes of walking, bus, and subway are used to travel between points. Moreover, some tests were conducted over the dataset to illustrate the robustness of method. The experimental results and related indices such as convergence plot show that the proposed algorithm can find optimum path according to applied constraints.

Keywords: multimodal shortest path, genetic algorithm, metropolis