Abstract: Nowadays, passengers in urban public transport systems do not only seek a shorttime travel, but they also ask for optimizing other criteria such as cost and effort. Therefore, an efficient routing system should incsorporate a multiobjective analysis into its search process. Several algorithms have been proposed to optimally compute the set of nondominated journeys while going from one place to another such as the generalisation of the algorithm of Dijkstra. However, such approaches become less performant or even inapplicable when the size of the network becomes very large or when the number of criteria considered is very important. Therefore, we propose in this paper an advanced heuristic approach whereby a Genetic Algorithm (GA) is combined with a Variable Neighbourhood Search (VNS) to solve the Multicriteria Shortest Path Problem (MSPP) in multimodal networks. As transportation modes, we focus on railway, bus, tram and pedestrian. As optimization criteria, we consider travel time, monetary cost, number of transfers and the total walking time. The proposed approach is compared with the exact algorithm of Dijkstra, as well as, with a standard GA and a pure VNS. Experimental results have been assessed by solving real life itinerary problems defined on the transport network of the city of Paris and its suburbs. Results indicate that the proposed combination GA-VNS represents the best approach in terms of computational time and solutions quality for a real world routing system.
Dib et al. proposed a heuristic approach whereby a Genetic Algorithm (GA) was combined with a Variable Neighborhood Search (VNS) to solve the multicriteria shortest-path problem in multimodal networks REF .
An advanced GAVNS combination for multicriteria route planning in public transit networks
Expert Syst. Appl.
Expert Syst. Appl.
Computer Science