Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms

摘要

This paper treats with K-shortest viable path problem in a transportation network including multiple modes. The considered modes are metro, rapid-bus, private and walking. In this network, a viable path is one that the number of mode changes is limited and the traverse time and also the walking, metro and private usage are restricted subjected to some constraints. The traverse time is defined dependent on congestion level. Because constrained shortest path is NP-hard, we extend two metaheuristic algorithms namely GASA and BACS for the given problem. GASA is a Greedy Algorithm Simulated Annealing and BACS is a bi-direction searching Ant Colony System made by two colonies of ants. We evaluate the validation of these algorithms applying several multimodal random networks. In addition, their results are compared with CPLEX 12.1. We find that GASA is appropriate for small networks and BACS has better performance in median and large-scale networks. Our results on Tehran network also demonstrate that BACS provides better objective values than BACS ones because Tehran public transportation is sparse.