A Memetic Algorithm for Routing in Urban Public Transportation Networks

摘要

This paper presents a new memetic algorithm, which solves bi-criteria version of Routing Problem in Urban Public Transportation Networks. Our solution returns a set of routes, containing at most k quasi-optimal paths with the earliest arrival in the first instance and with minimal number of transfers in the second. The method was implemented and tested on the real-life public transportation network of Warsaw city in Poland. This network was completed with walk links and therefore resultant routes are more practical. Effectiveness of the described solution was compared in two aspects: time complexity and quality of results, with another three algorithms for considered problem. Computational experiments clearly show the memetic algorithm be highly competitive with comparable ones, yielding new improved solutions in the most cases of tested source/destination specifications.