State-based accelerations and bidirectional search for bi-objective multi-modal shortest paths

• Published in: Transportation research. Part C, Emerging technologies Emerging technologies, 2013-02, Vol.27, p.233-259
• Main Authors: Artigues, Christian, Huguet, Marie-José, Gueye, Fallou, Schettini, Frédéric, Dezou, Laurent
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Bi-objective regular language-constrained shortest path problem; Bidirectional; Bidirectional search; Buildings. Public works; Computation; Dominance; Exact sciences and technology; Finite state automaton; General. Plotting; Ground, air and sea transportation, marine construction; Label-setting algorithms; Mathematical analysis; Multi-modal transportation; Networks; Searching; Shortest-path problems; State-based dominance rule; State-based estimated travel times; Transportation infrastructure
• ISSN: 0968-090X; 1879-2359
• DOI: 10.1016/j.trc.2012.08.003

► We give new labeling algorithms for a biobjective multimodal shortest path proble. ► We show the problem is a polynomial variant of the label-constrained shortest path. ► We propose improvements and corrections to the Lozano and Storchi (2001) approach. ► We propose new state-based dominance rules and goal-oriented techniques. ► We propose a bidirectional algorithm yielding significant speedups on real networks. 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., 2000; Delling 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à (1998) and Lozano 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.