Computing Multicriteria Shortest Paths in Stochastic Multimodal Networks Using a Memetic Algorithm

the human mobility is always organized nowadays in a multimodal context. However, the transport system has become more complex. For the sake of helping passengers, building Advanced Travelers Information Systems (ATIS) has therefore become a certain need. Since passengers tend to consider several other criteria than the travel time, an efficient routing system should incorporate a multi-objective analysis. Besides, the transport system may behave in an uncertain manner. Integrating uncertainty into routing algorithms may thus provide more robust itineraries. The main objective of this paper is to propose a Memetic Algorithm (MA) in which a Genetic Algorithm (GA) is combined with a Hill Climbing (HC) local search in order to solve the multicriteria shortest path problem in stochastic multimodal networks. As transport modes, railway, bus, tram and metro are considered. As optimization criteria, stochastic travel time, number of changes and walking time are taken into account. 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 unlike classical deterministic algorithms and pure GA and HC, the proposed MA is efficient enough to be integrated within real world journey-planning systems.