State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths
Taking into account the multi-modality of urban transportation networks for computing the itinerary of an individual passenger introduces a number of additional constraints such as mode restrictions and various objective functions. In this paper, constraints on modes are gathered under the concept of viable path, modeled by a nondeterministic finite state automaton (NFA). The goal is to find the non-dominated viable shortest paths considering the minimization of the travel time and of the number of modal transfers. We show that the problem, initially considered by Lozano and Storchi (2001), is a polynomially-solvable bi-objective variant of the mono-objective regular language-constrained shortest path problem (Barett et al., 2000andDelling et al., 2009). We propose several label setting algorithms for solving the problem: a topological label-setting algorithm improving on algorithms proposed by Pallottino and Scutell, 1998andLozano and Storchi, 2001, a multi-label algorithm using buckets and its bidirectional variant, as well as dedicated goal oriented techniques. Furthermore, we propose a new NFA state-based dominance rule. The computational experiments, carried-out on a realistic urban network, show that the state-based dominance rule associated with bidirectional search yields significant average speed-ups. On an expanded graph comprising 1,859,350 nodes, we obtain on average 3.5 non-dominated shortest paths in less than 180ms.
bidirectional search finite state automaton label-setting algorithms state-based dominance rule bi-objective regular language-constrained shortest path problem multi-modal transportation state-based estimated travel times