Christian Artigues
email: artigues@laas.fr

Marie-José Huguet
email: huguet@laas.fr

Fallou Gueye

Frédéric Schettini

Laurent Dezou

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

come   L'archive ouverte pluridisciplinaire

Introduction

Computing shortest paths in the context of mono-modal passenger transportation, where a single transportation mode (e.g. private vehicle, bus, subway) is used during the passenger's itinerary, has been the subject to extensive research since the publication of Dijkstra's algorithm in the 1950s. Among the considered extensions of the basic shortest path problem, the case where travel times (or costs) are time-dependent, allowing to take into account public transportation timetables or traffic congestion hours, has also been widely studied. Nowadays, thanks to powerful acceleration and/or preprocessing techniques (such as bidirectional search, A * search, landmarks, contraction hierarchies, etc.), computing shortest-paths very fast in large-scale network, either in a time-independent or in a time-dependent context, is not a challenge anymore for labeling algorithms [START_REF] Delling | Engineering Route Planning Algorithms[END_REF][START_REF] Delling | Time-dependent route planning. Robust and Online Large-Scale Optimization[END_REF][START_REF] Nannicini | Bidirectional A* search for timedependent fast paths[END_REF].

The case of multi-modal passenger transportation, which lies in the transportation of one or several passengers with different modes during the same itinerary, has been much less addressed. However, multi-modal transportation is subject to a growing interest in the research community, as multi-modality is now widely accepted for urban transportation as a necessary alternative to the exclusive use of private vehicles.

In this paper, we consider a bi-objective shortest path problem in a multi-modal urban transportation network: the minimum travel time/minimum number of transfers regular language-constrained shortest-path problem, initially considered by Lozano and Storchi [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF], and denoted by BI-RegL-CSPP by analogy to its mono-objective variant: the regular language (or label)-constrained shortest path problem RegL-CSPP defined by Barett [START_REF] Barett | Formal-language-constrained path problems[END_REF] and recently considered in [1,[START_REF] Delling | Accelerating multi-modal route planning by access nodes[END_REF][START_REF] Pajor | Multi-modal route planning[END_REF] 1 .

The problem can be briefly stated as follows. Consider a network G(V, E). Each node i ∈ V is "colored" by a mode m i (e.g. bus, walk, car, subway). Each arc (i, j) ∈ E has a weight corresponding to a travel time in mode m if m i = m j = m or to a transfer time if m i = m j . Furthermore, there are so-called path viability constraints. More precisely, the sequence of modes induced by a path is constrained in such a way that the string obtained by concatenating the path modes (considered as elements of an alphabet) must belong to a formal language described by a non-deterministic finite state automaton (NFA). Considering an origin node O and a destination node D, the goal is to find an O -D path for each of the non-dominated points in the space of two min sum objectives: the minimum total travel time and the minimum number of transfers (mode changes along the path). As in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF], we restrict ourselves to a time-independent version of the problem (travel times are constant) but we will briefly describe an extension scheme of the proposed algorithms to FIFO networks in Section 7.

Lozano and Storchi [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] implicitely assume (without mentioning it) that the problem can be solved in polynomial or pseudo-polynomial time. They proposed a label correcting algorithm to solve the problem, based on a topological labeling algorithm proposed by Pallottino and Scutellà in [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF].

In this paper, we first prove the problem can actually be solved in polynomial time. We propose a label setting extension of the Pallottino and Scutellà algorithm and several improvements to the Lozano and Storchi approach, among which a new state-based dominance rule. We also propose a multi-label approach based on buckets, from which we derive a bidirectional label setting algorithm. Goal-oriented techniques with statedependent estimated travel times are finally presented. We consider an application to the urban area of Toulouse (France), the purpose of which being to evaluate the tractability of the considered problem on a real-life network, as no computational experiments were reported in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF]. On this practical network, we compare the different algorithms. In particular, we study the impact of the dominance rules and of the size and nature of the NFA on the CPU time and on the number of touched nodes.

Section 2 briefly recalls the existing literature on the multi-modal shortest path problem, so as to introduce our motivations for the present study. Section 3 formally defines the problem and Section 4 establishes its complexity. The proposed algorithms are pre-sented in Section 5. Their performance on the considered real network are compared in Section 6. Further extensions and concluding remarks are presented in Section 7.

Literature review

Multi-modal transportation raises network modeling issues [START_REF] Chorus | Validation of a multi-modal travel simulator with travel information provision[END_REF][START_REF] Lo | Modeling competitive multi-modal transit services: a nested logit approach[END_REF]. A simple way of modeling the network, used by many authors [START_REF] Modesti | Sciomachen A utility measure for finding multiobjective shortest paths in urban multi-modal transportation networks[END_REF][START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF][START_REF] Bielli | Object modeling and path computation for multi-modal travel systems[END_REF], lies in assuming that the set of nodes is partitioned according to the modes. An arc linking two nodes of different subsets is called a transfer arc. Equivalently, nodes and/or arcs are labeled according to the associated mode [START_REF] Barett | Formal-language-constrained path problems[END_REF]. Once such a network is defined, one typically seeks to model the fact that some sequences of modes constituting a path can be infeasible in practice. A first (relaxed) way of taking account of such mode restrictions for shortest path computations was proposed by Modesti and Sciomachen [START_REF] Modesti | Sciomachen A utility measure for finding multiobjective shortest paths in urban multi-modal transportation networks[END_REF], as an extension of Dijkstra's algorithm to minimize a (single) global utility function defined by a weighted sum of modal characteristics of a path (time spent on the private car, time spent on the bus or subway, walking time, waiting time,...). For shortest path computation including hard modal constraints, (possibly infinite) mode-dependent travel times were used by Ziliaskopoulos and Wardell [START_REF] Ziliaskopoulos | An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays[END_REF], together with an arc representation, allowing to design mode constraints involving three nodes. A more general way of modeling the multi-modal constraints (among other applications) was proposed by Barett et al. [START_REF] Barett | Formal-language-constrained path problems[END_REF]. Each mode being viewed as an element of an alphabet and each arc of the network being labeled by a mode, the mode restrictions can be described by a regular language over the alphabet. The multi-modal shortest path problem then amounts to a regular language-constrained shortest path problem (RegL-CSPP). As a regular language can be represented by a non-deterministic finite state automaton (NFA), Barett et al. [START_REF] Barett | Formal-language-constrained path problems[END_REF] proved that the problem is polynomial in the number of states of the automaton. In [1,[START_REF] Delling | Accelerating multi-modal route planning by access nodes[END_REF][START_REF] Pajor | Multi-modal route planning[END_REF][START_REF] Sherali | The approach dependent, time-dependent, labelconstrained shortest path problem[END_REF][START_REF] Sherali | Time-dependent, label-constrained, shortest path problems with applications[END_REF], practical implementation issues of this method have been discussed. Barett et al. [1] proposed A * and bidirectional accelerations while Delling et al. [START_REF] Delling | Accelerating multi-modal route planning by access nodes[END_REF] and Pajor [START_REF] Pajor | Multi-modal route planning[END_REF] proposed, in addition, core-based and access node-based speed-up techniques and also considered time-dependent networks. With these techniques, they obtain a CPU time of 2.3 milliseconds on average for computing the O -D shortest path on a large intercontinental network with 50 700 647 nodes, 125 939 503 edges and a 3 state-automaton. Considering deterministic finite-state automaton (DFA) as input, Sherali et al. [START_REF] Sherali | Time-dependent, label-constrained, shortest path problems with applications[END_REF] extended the problem to time-dependence and propose a strongly polynomial algorithm for FIFO graphs. Sherali and Jeenanunta [START_REF] Sherali | The approach dependent, time-dependent, labelconstrained shortest path problem[END_REF] further extended the problem to approach-dependent travel times and propose a label-setting algorithm which consistently outperforms a label correcting algorithm designed for the same problem.

The main drawback of the approaches based on the RegL-CSPP is that they all consider only a single objective. However, when several modes are available, a user may want to select her/his itinerary among a set of alternatives, taking account of several objectives. To that purpose, two general classes of multi-objective multi-modal shortest path problems have already been considered in the literature: namely, (pseudo-)polynomial problems and NP-hard problems.

In [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF], Pallottino and Scutellà considered the Bi-RegL-CSPP problem without the viability constraints (any O -D path is feasible) but with the constraint that the number of transfers does not exceed a maximum number k max . Although the general bi-objective shortest path problem with min-sum objective is NP-hard, they showed that, in this case, the problem can be solved in pseudo-polynomial time (in n, the number of nodes in the network, and k max ), as it belongs to the category of bi-objective shortest path problems for which one of the two objectives takes its values in a discrete and finite set. They proposed a topological labeling approach where a label (i, k) represents an Oi path with k transfers.

In [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF], Lozano and Storchi directly extended this problem and the topological algorithm, so as to integrate mode restrictions using a NFA in a time-independent network, defining the Bi-RegL-CSPP considered in the present paper. Note they performed this extension without formally proving that the problem is (pseudo-)polynomial. We will prove in the sequel that the problem can actually be solved in polynomial time in n and |S|, the number of states of the NFA.

Bielli et al [START_REF] Bielli | Object modeling and path computation for multi-modal travel systems[END_REF] considered a simplified version of the NFA model but include timedependent arcs and time penalties for turning movements. Their objective is to compute the K-shortest paths under an upper bound of the maximum allowed number of transfers. The method can also be defined as an extension of the topological Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF] algorithm, with labels on arcs. Experimentations are limited to small networks. The largest one, presented in [START_REF] Bielli | Object modeling and path computation for multi-modal travel systems[END_REF], involves 1000 nodes and 2830 arcs and the K-shortest path algorithm runs in 6.5s on a Pentium II with 64 MB RAM. To our knowledge, no realistic computational experiments were carried out for the Bi-RegL-CSPP. Besides providing new algorithms and acceleration techniques, our main purpose in this paper is consequently to study the tractability of solving this bi-objective problems on a real network in reasonable computational time.

A more general class of approaches considers several different objective functions and, mostly, proposes extensions to multi-modality of the (NP-hard) bi-objective shortest path problem. Although we focus in this paper on the polynomial Bi-RegL-CSPP, we mention the recent experimental study carried out by Gräbener et al. [START_REF] Gräbener | Duthen Time dependent multi-objective best path for multi-modal urban routing[END_REF] for a more general problem since the number of transfers and minimum time objectives were also considered among other objectives in their study. They present an extension of Martin's algorithm [START_REF] Martins | On a multicriteria shortest path problem[END_REF] to deal with the multi-modal, multiobjective shortest path problem, considering only basic mode restrictions (the finite state automaton formalism is not used). When only the minimum number of transfers and minimum time objectives are considered, the method shows very fast computational times. For three modes (cycling, walking and public transportation), in a time-dependent context, the pareto-optimal paths are computed in 71.9 milliseconds in average for a network of 36694 nodes and 171443 edges. However the number of non-dominated paths is on average equal to 1.2. Actually, since the cycling mode can be taken from the origin to the destination (or left anywhere in the network), it generally dominates the other modes. This recent study partially answered our question in the sense that they showed that the bi-objective multi-modal problem is actually tractable when no complex mode restrictions are defined and when one of the modes tends to dominate the others.

In this paper we propose specific algorithms for the Bi-RegL-CSPP and we evaluate the practical tractability of real instances admitting significantly more non-dominated solutions and where complex mode restrictions are represented by a finite state automaton. Furthermore, we evaluate the efficiency of a new NFA state-based dominance rule and of a new bidirectional label-setting algorithm based on buckets.

3 Problem statement

Definition

Let M denotes the set of modes. The multi-modal transportation network is modeled by a multi-layered network G(V, E) with |V | = n such that each layer corresponds to a mode m ∈ M . Hence, a mode m i ∈ M is defined for each node i ∈ V while a travel time d ij is associated to each arc (i, j) ∈ E. An arc (i, j) such that m i = m j is called a transfer arc.

In terms of multi-modal characteristics, each path in G yields a sequence (or string) of modes. Among all strings of modes, only some subsets of strings are acceptable according to the feasibility constraints (or preferences). The acceptable mode sequences are represented via a non-deterministic finite state automaton (NFA), possibly issued from a user-defined regular expression [START_REF] Barett | Formal-language-constrained path problems[END_REF]. This NFA is given by a 5-uple A = (S, M, δ, s 0 , F ) where S = {1, . . . , |S|} is the set of states, s 0 is the initial state, F is the set of final states and δ : M × M × S → 2 S is the transition function such that δ(m, m ′ , s) gives the set of states obtained when traversing, from state s, an arc (i, j) with m i = m and m j = m ′ . We assume that δ(m, m ′ , s) = ∅ denotes the case where the transition is infeasible. Note that the case were δ(m, m ′ , s) is either the empty set or a singleton yields a deterministic finite state automaton (DFA).

A viable path is a path in G from the origin node O to the destination node D satisfying the constraints represented by the NFA. A path is viable if it starts with O (in state s 0 ) and reaches D in a final state s ∈ F .

We consider both the "minimum time" and "minimum number of transfers" objectives. We first recall definitions on multi-objective optimization [START_REF] Ehrgott | Multicriteria optimization[END_REF] applied to our problem. Let time(p) denote the travel time along a path p. Let ntr(p) denote the number of transfers along p. An efficient (or Pareto-optimal) solution is a feasible O-D path p such that there is no other path p ′ verifying either time(p ′ ) ≤ time(p) and ntr(p ′ ) < nbtr(p), or time(p ′ ) < time(p) and ntr(p ′ ) ≤ nbtr(p). In the objective space, a non-dominated point is a pair (t, k) such that there exists an efficient path p verifying time(p) = t and ntr(p) = k.

Considering the bi-objective "minimum time" and "minimum number of transfers" O-D viable path problem, the goal is to find all non-dominated points, and, for each of them, a single efficient path.

NFA scenarios

For our experimental evaluation on a real network, we consider 4 modes {w, b, c, s} (walking, bus, private car, subway) and 3 different mode configuration scenarios: M 1 = {w, b} (walk and bus only), M 2 = {w, b, s} (walk, bus and subway only) and M 3 = {w, b, c, s} (all modes).

For mode scenario M 3 (inspired by the one provided in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF]), we consider the following viability constraints. The private car can be taken only from O and, once left, cannot be taken again. For the subway, we assume that it can be taken at any time except at the origin but, once left, cannot be taken again, which corresponds to a user preference. In this case study we consider also that the destination is not in the subway and cannot be reached by car.

These viability constraints can be modeled by a NFA with |S| = 5 represented in Figure 1. Transition arcs between states are labeled by a mode m ∈ M where M = {w, b, c, s} ∪ {m O }, m O being a fictitious mode labeling only the origin O. A transition from state s to state s ′ labeled by m ∈ M describes the transition function of a traversed arc (i, j) in such a way that s ′ ∈ δ(m i , m j , s) with m j = m. If a mode m does not appear as a possible transition of a given state s, any transition towards this mode is forbidden. The state at origin is denoted s 0 and other states have the following meaning:

s 0 start s 1 s 2 s 3
• s 1 : the private car was not taken at the origin O and, so, mode c is forbidden for the remaining of the travel, while subway has not been taken yet;

• s 2 : the private car was taken at the origin O and has not been left yet;

• s 3 the private car cannot be taken anymore since it has already been taken and left while subway mode has not been taken yet;

• s 4 : the subway has been taken but not left;

• s 5 : the subway has been left.

We consider that the acceptable final states are reduced to F = {s 1 , s 3 , s 5 } (displayed in double circle in Figure 1). Indeed, state s 4 models the presence of the user in the subway, so she/he must leave the subway to reach her/his destination. State s 2 means the private car is currently being used and must be left in a parking area to reach the destination. For mode scenario M 2 , as the car is not considered anymore, states s 2 and s 3 are removed and only 3 states remain in the NFA (see Figure 2(b)). And, for subway mode, we consider the same viability constraints as in mode scenario M 3 . For mode scenario M 1 , as there are no constrained mode anymore, the NFA is empty. Note that all considered input NFAs are also DFAs. With this NFA, there are three non-dominated solutions to the Bi-RegL-CSPP from x 1 to x 5 : path (x 1 , x 4 , x 5 ) with 0 transfer and a travel time equals to 8, path (x 1 , x 6 , x 7 , x 5 ) with 2 transfers and a travel time of 5 and path (x 1 , x 2 , x 4 , x 3 , x 5 ) with 4 transfers and a travel time equals to 4. Note that path (x 1 , x 6 , x 4 , x 7 , x 5 ) of cost 4 is infeasible as the automaton, initially in state s 0 , is set to s 1 taking transfer arc (x 1 , x 6 ) and then to s 2 through transfer arc (x 6 , x 4 ) from which it is not possible to take the subway anymore.

Bi-RegL-CSPP example

Complexity

In this section we establish the complexity status of the Bi-RegL-CSPP which was not stated in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] although it was implicitly considered that the problem is pseudo-polynomial in n and k max (the maximum number of transfers). This seems intuitively correct. Indeed, Barett [START_REF] Barett | Formal-language-constrained path problems[END_REF] proved that the mono-objective RegL-CSPP is polynomially solvable, while Pallottino and Scutellà showed that the bi-objective minimum time/minimum number of transfers multi-modal shortest path problem (without viability constraints) is pseudopolynomially solvable under a threshold k max on the number of transfers.

Theorem 4.1. The Bi-RegL-CSPP can be solved in a time polynomial in n|S|.

Proof. Suppose in a first step that the number of transfers must not exceed a threshold k max . We build an expanded graph by creating a node per tuple (i, s, k) for i ∈ V , s ∈ S, k ∈ {0, 1, . . . , k max } and an arc from node (i, s, k) to (j, s ′ , k ′ ) valuated by d ij where (i, j) ∈ E, s ′ ∈ δ(m i , m j , s) and k ′ = k if m i = m j and k ′ = k + 1 if m i = m j . By solving the single-source, multi-destination mono-objective shortest path problem in this graph from node (0, s 0 , 0) (e.g. with Dijkstra's algorithm) we obtain all non-dominated solutions, simply by scanning the shortest paths ends (D, s, k) for s ∈ F and k ∈ {0, 1, . . . , k max }. This statement is a straightforward extension of the proof proposed by Barett [2] for the RegL-CSPP.

As the number of nodes in the expanded graph is equal to n|S|k max , we just showed that the problem is pseudo-polynomially solvable. Consider now a non-dominated O -D path in G(V, E). We claim that the number of times this path visits a given node i is not larger than |S|, the number of states of the NFA. Indeed, suppose the path visits twice a node i in state s, i.e from node (i, s, k) to node (i, s, k ′ ) of the expanded graph. Then, the subpath (i, s, k), . . . , (i, s, k ′ ) can obviously be removed without increasing the number of transfers and the travel time nor violating the viability constraints, which contradicts the assumption that the path is non-dominated. It follows that k max cannot be larger than n|S| and so the above-described algorithm is polynomial in n and |S|.

Note that setting k max to a number lower than n|S| accelerates the search and corresponds to a reasonable restriction in most applications.

Algorithms

In this section, we propose several algorithms and a new state-based dominance rule to solve the Bi-RegL-CSPP. All algorithms are based on a label setting principle which is described in Section 5.1. The dominance rules are presented in Section 5.2. The first algorithm (TLS), a label-setting version of the topological label algorithm proposed by [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] with additional corrections and improvements, is given in Section 5.3. The second algorithm (MQLS), described in Section 5.4, is a new label setting algorithm based on buckets. Section 5.5 presents the third algorithm (FB-MQLS), a bidirectional (Forward-Backward) adaptation of MQLS. Finally, Section 5.6 presents state-based goal oriented (A*) techniques for the unidirectional algorithms.

Label setting principle

The proposed algorithms use labels to represent paths. Let (i, s, k) denote a label representing a path from the origin to node i in state s and using k transfers. Each label has two attributes: t k is which denotes the arrival time on i and p k is which denotes the predecessor label of (i, s, k) on the path. Note that no algorithm needs to store more than one label (i, s, k) for given i, s and k.

All the proposed algorithms implement differently the following basic principles. Initially, a label (O, s 0 , 0) is generated with t 0 Os 0 = 0 and p 0 Os 0 = (O, s 0 , 0). The label is stored in a convenient data structure Q. The label setting process is then applied until Q becomes empty. At each iteration, the label (i, s, k) with minimum t k is is removed from Q and marked-up, as t k is is the shortest time from O to i in state s with k transfers. Let M ark k is ∈ {true, f alse} denote the mark indicator and let M denote the set of marked nodes. Then, the direct successors of node i are scanned. For each successor j, viability of the arc (i, j) is checked according to multi-modal restrictions and obtained labels (j,

s ′ , k ′ ) are considered for all s ′ ∈ δ(m i , m j , s), k ′ = k if m i = m j or k ′ = k + 1 if m i = m j .
If one of the three following conditions holds, (i) label (j, s ′ , k ′ ) was never visited;

(ii) the Bellman condition does not hold (t

k ′ js ′ > t k is + d ij );
(iii) dominance rules do not apply (see Section 5.2), the time and predecessor of (j, s ′ , k ′ ) are updated with

t k ′ js ′ ← t k is + d ij and p k ′ js ′ ← (i, s, k) and the label is inserted in Q or, if it is already present, Q is updated according to t k ′ js ′
decrease. Otherwise the label is discarded.

Dominance rules and state reduction

In this section, we give dominance rules allowing to discard labels. During the extension process, a label can be discarded if it can be proven that it cannot be extended to a better solution than another already generated label .

A first dominance rule, the basic dominance rule, is linked to the bi-objective optimization. It was used by Pallottino and Scutellà in [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF] to solve the bi-objective multi-modal shortest path without viability constraints.

Proposition 5.1 (Basic dominance rule). Consider two distinct labels

(i, s, k) and (i, s, k ′ ). If k ≤ k ′ and t k is ≤ t k ′ is , label (i, s, k ′ ) can be discarded (because it is dominated by the label (i, s, k)).
Enforcing this dominance rule yields only different solutions: if there are two solutions with same travel times and same numbers of transfers, only one of them is kept. This first dominance rule compares, for a given node, only labels having the same state.

The second dominance rule allows to go further by comparing, for the same node i, labels having different states.

For that, we consider a binary relation on the states such that s s ′ means that s yields more extension possibilities than s ′ . More precisely, Definition 5.1. State s dominates state s ′ (s s ′ ) if any input mode string accepted by s ′ is also accepted by s. [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] proposed a state-based dominance rule (Preference theorem) applying to the NFA they consider. In Appendix A, we underline a few limitations of this theorem and we opt for new a state-based different dominance rule. We define binary relation as follows.

Lozano and Storchi

Definition 5.2. s s ′ if for any mode pair (m, m ′ ) ∈ M , such that m is a feasible mode for state s, one of the following conditions holds:

   δ(m, m ′ , s ′ ) = ∅ δ(m, m ′ , s ′ ) = δ(m, m ′ , s) δ(m, m ′ , s) = s and δ(m, m ′ , s ′ ) = s ′
Note is reflexive (s s) and transitive, so is a preorder on the set of states.

Example. In the NFA presented in Figure 1, we have s 1 s 5 . Indeed, when m ∈ {c, s}, as it is infeasible to be in s 1 (or in s 5 ) with m = c or m = s, we have: Proof. This condition is just a particular case of standard NFA reduction rules [START_REF] Ilie | On NFA reductions in Theory is forever[END_REF].

δ(m, m ′ , s 1 ) = ∅ and δ(m, m ′ , s 5 ) = ∅, ∀m ′ ∈ M . When m ∈ {w,
This state merging condition can be used to reduce the initial automaton presented in Figure 1. After the reduction is also antisymmetric and defines a partial order on the set of states. In this figure, states s 1 and s 3 verify the above-described condition and we can build the reduced automaton of Figure 3.

s 0 start s 1 s 2 s 3 s 4 w, b c w, b s c w w s w, b Figure 3: Reduced NFA for mode scenario M 3 = {w, b, c, s}
Such a reduction is beneficial for the computational requirements as the previous section and computational experiments show that the complexities of the presented algorithms depend on the number of states of the NFA. We now propose the following state-based dominance rule.

Theorem 5.1 (State-based dominance rule). Consider two labels (i, s, k) and (i,

s ′ , k ′ ) with k ≤ k ′ , s s ′ and t k is ≤ t k ′ is ′ . Label (i, s, k) dominates (i, s ′ , k ′ ), which can be discarded.
Proof. From the definition of relation , we know that any transition from s ′ yields the same state as any transition from s. So label (i, s, k) has at least the same extension possibilities as label (i,

s ′ , k ′ ). The remaining conditions (k ≤ k ′ and t k is ≤ t k ′ is ′ )
show that any extension of (i, s ′ , k ′ ) is dominated by an extension of (i, s, k).

In the reduced automaton for mode scenario M 3 = {w, b, c, s} (Figure 3), we see that s 1 s4 is the only dominance relation. The automaton for mode scenario M 2 = {w, b, s} of Figure 2(b) cannot be reduced and dominance relation s 0 s 2 holds.

Note that if transitions are represented by a matrix, all dominance relations can be established during preprocessing in O(|M | 2 |S| 2 ) time.

In the algorithms described in the subsequent sections, different definitions of set D s can be used to parametrize the use of dominance rules:

• D s = ∅ corresponds to no dominance checking (except the Bellman condition).

• D s = {s} corresponds to basic dominance checking.

• D s = {s ′ ∈ S|s ′ s} corresponds to state-based dominance checking.

Topological label-setting (TLS) algorithm

Description

The topological Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF] algorithm was extended by Lozano and Storchi algorithm [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] to path viability modeled by a NFA. We describe below a label-setting variant named TLS (the original algorithm of [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] being described as a label-correcting algorithm) with additional improvements and corrections.

This algorithm (pseudo-code is given in Algorithm 1 and label setting procedure is given in Algorithm 2 of Appendix B) iterates on the number of transfers from 0 to k max . At each iteration k, it searches for the shortest path with exactly k transfers. To that purpose, data structure Q, used for storing labels, is made of two priority queues Q now and Q next , where Q now contains labels with k transfers and Q next contains labels with k + 1 transfers. Initially, Q now contains only label (O, s 0 , 0) while Q next is empty.

At a typical iteration, the minimum time label (i, s, k) is taken from Q now and the label extension principle is applied with some modifications regarding the general label setting algorithm. To check the dominance rules, a variable, denoted by BestV alue j,s ′ , stores all algong the search the shortest travel time found so far to reach node j in state s ′ (i.e. with at most k transfers). The variable is used to have an O(1) basic dominance checking (instead of enumerating all

t k ′′ js ′ such that k ′′ < k ′ ) and a O(|D s ′ |) state-based dominance checking (see Section 5.3.2). If the dominance condition holds, the label is discarded. Otherwise, if k = k ′ , BestV alue j,s ′ is updated and the new label (j, s ′ , k ′ ) is inserted in Q now . If k ′ = k + 1, the label is inserted in Q next .
Back to the TLS main procedure (Algorithm 1), as soon as the destination D (in a final state) is dequeued from Q now or if Q now becomes empty, Q now is set to Q next and Q next is emptied. The algorithm stops when Q next is empty, meaning that no non-dominated labels with k + 1 transfers could be found, or when the maximum number of transfers k max is reached.

In addition, the proposed version of TLS algorithm presents some improvements to the Lozano and Storchi algorithm:

• A label-setting algorithm is proposed in place a label-correcting algorithm, following the recommendations of [START_REF] Sherali | The approach dependent, time-dependent, labelconstrained shortest path problem[END_REF].

• At each iteration, when travel time of a new label is computed, the best travel time of previous solutions, denoted by BestLastSol is also used to prune labels (in addition to BestV alue).

• In [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF], a single label t is is used per node-state pair (i, s) for both extensions in Q now with k transfers and in Q next with k + 1 transfers. However, a path with k transfers may not be extended because it has a longer time than a path with k + 1 transfers. More details are given on this issue in Appendix A. We correct this problem by defining two labels t k is and t k+1 iq (see Appendix A for a more detailed explanation).

• We use the state-based dominance rule proposed in Section 5.2 instead of the one proposed in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] (see Appendix A for justifications).

With TLS, solutions are obtained in increasing numbers of transfers and decreasing travel times. In Appendix C, the algorithm is applied to the instance described in Figure 2 with the state-based dominance rule. 12 labels are marked and 18 labels are reached.

Complexity

Complexity of dominance rule checks.

The basic dominance rule on label (j, s ′ , k ′ ) can be performed in O(1). Indeed, for a given label (j, s ′ , k ′ ), we have only to keep track of the shortest time found so far to reach (j, Complexity of TLS We now establish the complexity of our implementation of TLS using binary heaps for Q now and Q next . Let k max denotes the maximum allowed number of transfers. Note k max is bounded from above by n|S|. For a given number of transfers k, at most n|S| labels (i, s, k) are selected as minimum time labels in Q now . For each of them, there are two operations: (a) deletion from Q now and (b) successor scan and insertion in Q now or Q next . Deletion from the binary heap can be done in O(log(n|S|)). Successor scan with the basic dominance rule (in O( 1)) and possible insertion (in O(log(n|S|)) has a worst-case complexity in O(|F S i | log(n|S|)) where F S i is the set of direct successors of i. The complexity of operation (a) is ignored (neglected) since it is lower than the complexity of operation (b). It follows that the worst-case time complexity of TLS with the basic dominance rule and binary heap implementation is O(k max |S||E| log(n|S|)). Running the state-based dominance rule takes in addition |S| operations for each successor so we obtain in this case a worst-case complexity of O(k max |S||E|(|S| + log(n|S|))).

s ′ , k ′′ ) with k ′′ ≤ k ′ , denoted BestV alue js ′ . A label (j, s ′ , k ′ ) is dominated if t k ′ js ′ ≥BestV alue js ′ ,

Multi-queue label-setting (MQLS) algorithm

Description

We propose an alternative algorithm that computes the shortest paths in increasing order of the time criterion values and in decreasing order of the number of transfers. Instead of considering two queues Q now and Q next , we build incrementally a list Q = {Q 0 , Q 1 , . . .} of buckets (priority queues) such that each bucket Q k ∈ Q contains labels representing paths with k transfers. More precisely, Q 0 is initialized with label (O, s 0 , 0), all other Q k being empty. The number of buckets K is set to k max . At each iteration, the label (i, s, k) with minimum travel time is taken among all non-empty priority queues. If a destination label (D, s, k * ) is dequeued, priority queues Q k ′ with k ′ > k * are discarded and K is set to k * -1, as the shortest path with k * transfers to D is found. Otherwise, non-dominated labels (j, s ′ , k ′ ) such that k ′ ≤ K issued from (i, s, k) are inserted in the corresponding priority queue Q k ′ by the label extension procedure. The algorithm stops when the shortest path with 0 transfer is found or when all queues are empty. The algorithm pseudo code is given in Algorithm 3 and the label extension procedure is given in Algorithm 4 of Appendix B. In Appendix C, the algorithm is also applied to the instance described in Figure 2. 12 labels are marked and 16 labels are reached by the search.

We show the equivalence of TLS and MQLS in the sense they both have the nice feature described by the following property. As in the standard Dijkstra algorithm, a label is "marked" as soon as it is dequeued from Q.

Proposition 5.3. The set of labels (i, s, k) marked by TLS or MQLS for a given (i, s) maps the set of all non-dominated points for the bi-objective Oi viable path problem with s as final state.

In particular, setting i = D and s ∈ F , we see that TLS and MQLS generates one and only one path for each non-dominated point.

Complexity

We determine the algorithm complexity, using binary heaps for each Q k ∈ Q. In Q at most k max n|S| labels are stored and dequeued (marked). For each iteration, there are three operations: (a) search of the minimum time value in the k max queues; (b) deletion of the corresponding label in O(log(n|S|)); and (c) for each scanned successor, a dominance check is possibly followed by an insertion operation in the appropriate queue in O(log(n|S|)). The basic dominance check can be made here in at most k max operations as all labels (j, s ′ , k ′′ ) with k ′′ ≤ k ′ must be checked. So, with this dominance rule, the operation (c) has an O(|F S i |(k max + log(n|S|)) worst-case time complexity. The state-based dominance rule can be applied in O(k max |S|), then the operation (c) as a worst-case time complexity of O(|F S i |(k max |S| + log(n|S|)).

Taking account of (a) and (b) operations, with the basic dominance rule, we obtain a worst-case complexity of

O(k max |S| (nk max + n log(n|S|) + |E|k max + |E| log(n|S|)) = O(k max |S||E| (k max + log(n|S|)) .
and, with the state-based dominance rule, this worst-case complexity is

O(k max |S| (nk max + n log(n|S|) + |E|k max |S| + |E| log(n|S|)) = O(k max |S||E| (k max |S| + log(n|S|)) .
The worst-case time complexity is increased compared to the TLS algorithm by a k max factor.

Bidirectional Multi-Queue Label Setting Algorithm (FB-MQLS)

We propose a bidirectional adaptation of MQLS, taking advantage of the multi-queue characteristics. There are two main issues in designing a bidirectional algorithm for the considered multi-modal problem. The first issue consists in modeling backward path viability. The second issue lies in exploiting the connection between a forward and backward label in the bi-objective context. The multi-queue structure will be here fully exploited as several label queues will be discarded when a given connection condition is reached. These issues are addressed in Section 5.5.1 and the algorithm FB-MQLS is described in Section 5.5.2.

General Principles

The proposed bidirectional algorithm (FB-MQLS) maintains, in a similar way as in MQLS algorithm, two priority queue lists (FQ for the forward search and BQ for the backward search) such that F Q k contains forward labels f t k i,s representing paths reaching i in state s with k transfers and BQ k contains backward labels bt k i,s representing paths originating from i with k transfers in state s.

Modeling backward path viability

We exhibit below three different possibilities to model backward path viability. Let A f = (S f , M, δ f , s f 0 , F f ) denotes the automaton for the forward search and A b = (S b , M, δ b , s b D , F b ) the automaton for the backward search. To obtain A b from A f , the first possibility is simply to reverse the arcs of A f as done in [START_REF] Pajor | Multi-modal route planning[END_REF].

In our case, for mode scenario M 3 , although the forward automaton is a DFA, the obtained state automaton becomes non-deterministic (see Figure 4 In practice, each time a label extension uses an arc that yields several possible successor states (in the backward path), all the corresponding labels are generated. Note that such an indeterminism may yield pairs (i, s) that may never reach the origin, inducing useless computations.

The second possibility is to use a deterministic finite state automaton for the backward search. This is always possible as there exist algorithms that transform a non-deterministic finite state automaton equivalent to any deterministic one, however it can be that for a given non-deterministic automaton with |S| states, the equivalent deterministic automaton has about 2 |S| states. An issue then, is to generate the deterministic automaton with a minimal number of states. Note that this issue also applies to the forward automaton which can be non-deterministic if it is obtained from a regular expression.

A third possibility is to obtain a (ǫ-free) NFA through the reverse regular expression, which can be done in polynomial time [START_REF] Schnitger | Regular Expressions and NFAs Without ǫ-Transitions[END_REF]. For example, the forward Comparing the different ways of obtaining the backward NFA for general forward NFA would be an interesting follow-up to the present study. In particular the speed-up obtained by optimizing the NFAs would have to be balanced with the CPU time needed to perform the NFA reductions and/or conversion to a minimum-state DFA. Nevertheless, to illustrate the potential gain of optimizing the (backward) NFA, we display, in right part of Figure 4, a possible deterministic finite state automaton for A b that can we have obtained manually from the reverse regular expression.

The state-based dominance rule applies also for the backward automaton. For the nondeterministic automaton of Figure 4

Connection and queue discarding rule

The second issue for designing a bidirectional algorithm for the considered problem is linked to connection consequences between a forward label and a backward label in terms of number of transfers. In case the backward automaton is simply obtained by a reversal of the forward arcs, a forward label (i f , k f , s f ) connects to a backward label (i b , k b , s b ) if i f = i b and s f = s b since the backward NFA has the same states as the forward NFA.

In case the backward automaton has been reduced, a correspondence must be established between the forward and the backward states. Let CS A b →A f (s) (respectively

CS A f →A b (s)) denote the set of A f (resp. A b ) states compatible with a given state s of A b s f 0 start s f 1 s f 2 s f 3 s f
(resp. A b ). A forward label (i f , k f , s f ) connects to a backward label (i b , k b , s b ) if i f = i b and s f ∈ CS A b →A f (s b ) or, equivalently, s b ∈ CS A f →A b (s f ).
For example, with the deterministic backward automaton case of Figure 4(c) and the forward automaton of Figure 4(a), compatible states are:

CS A f →A b (s f 1 ) = {s b 1 , s b 4 } CS A f →A b (s f 2 ) = {s b 2 }, CS A f →A b (s f 3 ) = {s b 3 } and CS A f →A b (s f 4 ) = {s b 1 }.
We show now that, even if we use the reversed forward automaton for backward search, additional state compatibilities can be automatically established between forward and backward states, so as to have earlier connections without using a manually optimized backward automaton. We first define formally state compatibility: Definition 5.3. Forward state s f

x and backward state s b y are compatible if, for any mode m the concatenation of any m-terminated mode string accepted by s f

x with any reversed m-terminated input string accepted by s b y is a valid string.

We now establish the forward/backward compatibility theorem (sufficient condition). In our example, there are no state-based dominance in the non-deterministic backward automaton but dominance s f 1 s f 4 holds in the forward one. Hence, since any input string accepted by s f 4 is accepted by s f 1 , it follows that s b 1 and s f 4 are compatible states, on which a connection can be established.

Note that if dominance relations are represented by a |S| × |S| boolean matrix, all compatibility relations can be precomputed in O(|S| 2 ) time.

In case of a connection, the interest of the multi-queue implementation appears. Indeed, when a connection is made between a label (i f , h, s f ) and a label (i b , q, s b ) such that the state s f of F A is compatible with state s b of BA and

f t h i,s f + bt q i,s b ≤ min (i ′ ,s ′ ,k ′ )∈F Q f t k ′ i ′ ,s ′ + min (i ′ ,s ′ ,k ′ )∈BQ bt k ′ i ′ ,s ′
holds, all priority queues F Q k ′ and BQ k ′ with k ′ ≥ h + q can be discarded since the right hand side is a lower bound of the shortest path with at least h + q transfers

Algorithm description

Algorithm FB-MQLS pseudo-code is given in Appendix B (Algorithm 5). FQ is initalized to a single priority queue F Q 0 with a single label (O, s 0 , 0) and BQ is initialized to a single priority queue BQ 0 with a labels (D, s D , 0). The upper bound of the number of transfers K is set to k max . BestCurrentSol k stores the best known solution with k transfers and k * corresponds to the number of transfers of the current best known solution.

The main loop computes the minimum time forward label (i f , s f , k f ) and the minimum time backward label (i b , s b , k b ). The search proceeds from the minimum time label among them, denoted by (i, s, k). The minimum time label (i, s, k) is then removed from its priority queue (F Q k or BQ k ) and the forward or backward label extension principle is performed in a similar way as the MQLS Label extension.

The main difference is that (for instance in the forward extension), for each new nondominated label (j, s ′ , k ′ ), a connection with the opposite direction search is searched by scanning all labels (j, s b , k ′′ ) with k ′ + k ′′ ≤ K and s b ∈ CS F A→BA (s ′ ) which possibly yields an O -D path of less than K transfers. If such a connection is established, its path time (f t k ′ j,s ′ + bt k ′′ j,s b ) is compared against the best O -D path already found with k ′ + k ′′ transfers whose time is stored as BestCurrentSol k ′ +k ′′ , to possibly update it. Moreover, if the given forward label (j, s ′ , k ′ ) is connected with a marked-up backward label with 0 transfer then label (j, s ′ , k ′ ) can be discarded as all non-dominated shortest paths from D to i have been found. The forward label extension algorithm is given in Algorithm 6. The backward label extension algorithm is symmetrical and not given in the paper.

After the forward or backward label extension, the queue discarding rule compares the minimum time BestCurrentSol k * obtained among already established connections, with the lower bound given by the sum of the minimum forward and backward label times

(f t k f i f ,s f + bt k b i b ,s b ).
If the test is positive, BestCurrentSol k * is the best path time for k * transfers and priority queues F Q k and BQ k with k ≥ k * can be discarded.

We show in Appendix B the execution of this algorithm for the example of Figure 2. The algorithms marks 8 labels and reaches 22 labels.

Complexity

Compared to MQLS, there is a computational overhead (only at label extension) induced by connection search (step 14 of Algorithm 6). Let us examine first this overhead in terms of complexity for the forward extension. With the basic dominance rule, recall the complexity of label extension is O(|F S i |(k max + log(n|S|)) for MQLS. For a backward deterministic automaton, connection search introduces an additive term equal to k max to search for all labels (j, s b , k ′′ ) as there is a single compatible state. For the nondeterministic backward automaton, the additive term can be bounded from above by s.k max where s = max s∈S

Goal-oriented techniques with state-dependent estimated travel times

Extension of algorithms TLS and MQLS using the A * principle (goal oriented search) is straightforward. An interesting possibility is to use a state-dependent heuristic. More precisely, for each label (i, s, k), a modified travel cost denoted by tk is is given by t k is + h k is where t k is is the travel time from the origin O to i and h k is is an estimation of the total travel time from i to the destination D, starting in state s with a number of performed transfers equal to k. tk is represents an estimation of the shortest path from a given origin to a given destination throught node i and in the algorithms the search of a label with the minimum travel time is replaced by the search of a label the minimum estimate total travel time. We consider here that h k is correspond to the euclidian distance from i to D over the maximal speed of the modes that can still be taken according to current state s and number of transfers k. Then, h k is is a lower bound of the minimum travel time from (i, s, k) to any label (D, s ′ , k ′ ) in the expanded graph, which insure the optimality of the A * search. Algorithms TLS and MQLS can be directly extended to A * principle by using tk is instead of t k is . An example of state-dependent heuristic can be to take the maximum average car speed in state s 2 to compte estimated travel times while in state s 1 , the times are computed according to the maximum average bus speed which is slower due to frequent stops.

Computational Experiments

The experimental comparisons were carried out on a network covering a part of the urban area of Toulouse (France). Considered modes are {w, b, c, s} (walking, bus, private car, subway) and we evaluate three different mode scenarios as previously stated: M 1 = {w, b} (walk and bus), M 2 = {w, b, s} (walk, bus and subway) and M 3 = {w, b, c, s} (all modes).

Viability constraints are modeled by the automaton of Figure 3. Table 1 details the different layers of the transportation network in terms of modes, nodes and arcs. Timetables for buses and subway are approximate by an average travel time for each corresponding arc in the network. All algorithms have been implemented in C++ and run on an 2.67 GHz Intel Xeon quad core processor W3520 with 4GB RAM under Linux Fedora 11. Experiments concern 100 randomly generated origin-destination pairs. Origin and destination are both chosen only in the street subnetwork and around the "center" of the city to avoid border effects. The minimum euclidean distance between them is set to 5 km. The maximum number of transfers is set to k max = 10.

Results

In Appendix D, Tables 3-8 present the impact of the dominance rules and of the different algorithms on the average CPU time and number of touched nodes needed to solve each of the 100 instances, with the three different NFA configurations. Figure 10 synthesizes the results in terms of average CPU time while Figure 11 concentrates on the number of touched nodes. We first give the characteristics of the obtained solutions and, next, we analyze the performance of the algorithms.

Found solutions

Table 2 presents the average results obtained by all algorithms on the three configurations in terms of average number of solutions, average and maximum number of transfers, minimum and maximum travel times. We obtain from 2 to 6 non dominated solutions per instance with the smallest average value for the most complex automaton. The average number of transfers follows the same trend, so the possibility of using car in the itineraries reduces the number of non-dominated solutions and transfers.

We obtain much more efficient solutions in average than Gräbener et al. in [START_REF] Gräbener | Duthen Time dependent multi-objective best path for multi-modal urban routing[END_REF] for the same objectives, even when the car is used. Although networks are different, we explain this difference by the fact that we do not have a dominant mode, since the private car can only be left at a limited number of nodes (parkings) and we have viability constraints. The minimum travel times are in average rather large to ensure a sufficiently large search space end exhibit differences between the algorithms. The larger itineraries correspond to full-walking paths which are always non-dominated as they are the only solutions that induce no transfers (origin and destination being set on the walking street network). The minimum number of transfers is consequently always 0. The average maximal number of transfers may seem large, but a transfer denotes a mode change including walking between stations, so for example a typical bus-subway path yields string wbwsw which involves 4 transfers while the user takes only two modes besides unavoidable walking parts.

Performance of algorithms and dominance rules without viability constraints

We first analyse the results of the different algorithms (TLS, MQLS, their goal oriented variants TLS-A*/MQLS-A* and FB-MQLS) with and without the basic dominance rule on the configuration involving mode scenario M 1 = {w, b} and no viability constraints. As there is no automaton, the maximal number of labels (nodes in the expanded graph) is (n b + n w )k max = 629 810. Detailed results are given in Tables 3-4 and on top of Figures 1011). Table 3 displays the running time of each combination algorithm/dominance rule in ms while Table 4 gives the number of touched nodes for each combination. In addition, Tables 3 and4 give in row "∆ b. d." the average speed-up and touched node-decrease obtained when using the basic dominance rule compared to the simple Bellman condition. Row "∆ FB" provides the average speed-up (touched nodedecrease) of the bidirectional algorithm compared with other algorithms, using the basic dominance rule.

In this configuration, the problem is precisely the bi-objective problem studied by Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF]. The TLS algorithm with the basic dominance rule combination can be considered as the reference algorithm, as it resorts to the method proposed by Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF]. It solves the instances in 132 ms on average with 150 162 touched labels. The basic dominance rule is very efficient as it generates speed-ups from 36% (on TLS) to 45% (on FB-MQLS). The bidirectionnal search is at least 24% faster than the unidirectional algorithms, including the A* variants. The speed-up brought by A* search on unidirectional search is significant but remains modest (12% speed-up for TLS). Note that the speed-ups brought by A* and the state-based dominance rule closely follow the percentage of decrease nodes (15% on average for A* and 37% on average for the basic dominance rule). In the bidirectional search, the need to manage the set of priority queues and to establish connections between several labels having different numbers of transfers induces a computational overhead which explains that the drastic reduction of touched nodes (52% on average) is not fully reflected by the obtained speed-up (41% on average). For the same reasons, the MQLS algorithm has a lower number of touched nodes than the TLS algorithm while it is 11% slower.

In conclusion, the proposed bidirectional FB-MQLS algorithm, used in conjunction with the basic-dominance rule, improves significantly the reference TLS algorithm (45% speed-up yielding an average running time of 89 ms with 64 362 reached labels).

Performance of algorithms and dominance rules with the 3-state NFA

We consider now the mode scenario M 2 (walk, bus and subway) with the 3-state NFA (Tables 5-6 and middle of Figures 1011). The potential number of labels (i, s, k) now reaches (n s + 2(n b + n w ))k max = 1, 260 000. In addition to TLS, MQLS, and their A* variant, we consider two versions of the FB-MQLS algorithm: FB-MQLS-ND denotes the FB-MQLS algorithm with the non deterministic backward automaton presented in Figure 4(b) while FB-MQLS-D denotes the variant with the deterministic backward automaton presented in Figure 4(c). In Tables 5 (6), we give in row "∆ s. d." the average speed-up (touched node-decrease) obtained when using the state-based dominance rule compared to the basic dominance condition. Row "∆ FB-ND (b. d.)" corresponds to the average speed-up or slowdown (touched node-decrease or increase) of the bidirectional algorithm with the basic dominance rule compared with other algorithms (also using the basic dominance rule) while row "∆ FB-ND (s. d.)" give the same value using the state-based dominance rule.

We observe, independently of the considered dominance rule, that rank FB-MQLS < TLS-A* <MQLS-A*< TLS <MQLS (in terms of increasing running times) is conserved. As expected, a general slowdown is observed for all combinations algorithm/dominance rule. The TLS algorithm with the basic dominance rule now solves the instances in 200 ms in average (34% slower than for the preceding configuration) with a number of touched nodes equal to 218 233. Globally, switching from the basic to the state based dominance rule yields speed-ups for all algorithms from 5% (on FB-MQLS-ND) to 23% (on MQLS). The larger improvement is for the mono-directional algorithms (always more than 20% speed-up) while the bidirectional search is less positively impacted (max 11% speed-up). The speed-up brought by the bidirectional search is also important : it runs from 24% to 41% faster than the unidirectional algorithms. The fastest algorithm if the FB-MQLS-D which in-turn yields an additional speed-up of 25% to FB-MQLS-ND, when used with the state-based dominance rule. Hence, despite the additional forward/backward state compatibilities and dominance rules, optimizing the automaton still yields significant improvements. We also have to underline the leveling effect of the state based dominance rule on the speed-up brought by the bidirectional algorithm. Last, the A* search improves the unidirectional algorithms more than for the previous mode configuration, with an average speed-up of 19%.

In terms of the number of touched nodes, we observe the same phenomenon as for the previous mode configuration: MQLS(-A*) obtains a lower number of touched nodes than TLS(A-*) but the computational overhead is not compensated by the node reduction. For the state-based dominance rule, the reduction of the number of nodes (19% on average for the unidirectionality algorithms) yields the equivalent speed-up (21% on average). As also observed in the previous configuration, FB-MQLS-ND with the basic dominance rule yields an important average touched node decrease compared to the unidirectional algorithms of 52% while it yields "only" a 38% average speed-up.

In conclusion, the proposed bidirectional algorithm (without optimization of the backward automaton) in conjunction with the new state-based-dominance rule improves significantly the reference TLS algorithm with the basic dominance rule (41% speed-up, running time 117 ms, 87 175 reached labels). The speed-up reaches 53% with the optimized backward automaton which reaches an average running time of 94 ms with only 62 936 touched labels.

Performance of algorithms and dominance rules with the 4-state NFA Tables 7-8 and the bottom part of Figures 1011show the results on the 4-state NFA and full mode scenario M 3 . The potential number of labels (i, s, k) is equal to (n m + n c + 2(n w + n b ))k max = 1 859 250. All the combinations algorithms/dominance rules of the previous configuration are tested with two variants of the A* algorithms. TLS-A* and MQLS-A* denote the variant where the estimated travel time for a node i to destination D is a constant (as for the previous configurations), whereas TLS-SD-A* and MQLS-SD-A* denote the variant where the estimated travel time for a node i to destination D is statedependent (see Section 5.6). Our reference algorithm, TLS with basic dominance rule, solves all instances in 215 ms in average with 239 499 touched labels which corresponds to a very moderate slowdown compared to the 3-state automaton. Globally the efficiency of the state-based dominance rule decreases even if the speed-ups are still significant for unidirectional algorithms (always more than 8.5%). However the efficiency of the bidirectional search is reduced. The speed-up compared to TLS and MQLS with the basic dominance rule is significant (17% and 26%, respectively). However, the A* search variants and the bidirectional search are very close. The state-dependent version of the A* search with the state-based dominance rule is even slightly faster than FB-MQLS. The leveling effect of the state-based dominance rule is also important since speed-ups compared to TLS never exceed 10%. We observe a positive but modest effect of the state-based A* search on CPU time compare to state-independent variants.

In conclusion, for the more complex automaton, the leveling effect of the basic and, to a lower extent, state-based dominance rules has to be underlined. The reference TLS algorithm with the basic dominance rule is still 17% slower than the bidirectional algorithm (without optimization of the backward automaton) with the state-based dominance rule which obtains a running time of 177 ms with 133 210 touched nodes. The improvement reaches 20% with the optimized backward automaton (160 ms and 114 370 touched nodes).

Although these times could be certainly reduced with further acceleration mechanisms, our experiments allow to answer positively to the question whether the BI-RegL-CSPP can be solved efficiently on a real urban network.

Concluding remarks and further extensions

We have proposed several algorithms to solve the single-source, single-destination biobjective multi-modal viable shortest path problem where path viability constraints are modeled by a finite state automaton. The considered objectives were the number of transfers and the total travel time. The proposed algorithms are all polynomial in the number of arcs and nodes of the transportation network and in the number of states of the finite state automaton. For each problem instance, the set of non-dominated solutions was found by all algorithms in an short CPU time, allowing their use inside an end-user application which is currently being developped by MobiGIS. On the largest configuration (an expanded graph of 1 859 250 nodes), we obtain a significant number of non-dominated shortest paths (3.5 on average) with average running times lower than 180 ms. The proposed state-based dominance rules allow to reduce significantly both the CPU times and the number of visited labels for all algorithms. We also observe that the basic and the state-based dominance rule have a positive leveling effect on the algorithm performance. The proposed bidirectional algorithm yields significant speed-ups for most configurations. This speed-up is sensitive to the complexity of the backward automaton. It results that benefits could be obtained by optimizing both forward and backward NFA. A goal-oriented version (A*) of the unidirectional algorithms has been developed, allowing better improvements when a state-based estimated travel time function is used.

A first extension would be to consider time-dependent travel times. A (fast) extension of bidirectional search to time-dependent shortest path (in mono-modal networks) has been recently proposed by Nannicini et al. [START_REF] Nannicini | Bidirectional A* search for timedependent fast paths[END_REF]. The concepts used in their study can be transposed without difficulty in our context under the FIFO assumption. For the forward or mono-directional search, we may simply replace t + d ij by a function a ij (t) which gives the arrival time at j when departing from i at t. For the backward search, Let b ij (t) denote the function giving the departure time at i if arrival time at j is t for an arc (i, j) and t a possible arrival time at j given by the transportation timetables. As the arrival time at D is not fixed, we cannot use b ij (t). Instead we define the travel time d ij such that td ij is an upper bound of b ij (t). d ij can be simply set to the minimal duration to traverse arc (i, j) given the timetable associated with (i, j). By using the timetables a ij (.) for the forward search and the lower bounds on the travel times d ij for the backward search, the time computed for a path issued from a connection is a lower bound of the actual duration. To apply the queue discarding rule, the actual travel time can be computed for each encountered connection by a traversal of the backward path given the arrival time at the connection node.

A second extension would be to design an efficient goal oriented scheme for the bidirectional search but a difficulty is to design an efficient queue discarding rule.

For futher research, more experimental studies have to be carried out to evaluate the influence of the finite state automaton structure on the efficiency of the algorithms and stronger dominance rules could be exhibited, for other special cases of the state automaton. Moreover, experiments on larger transportation networks have to be realized and further acceleration techniques (ALT, contraction hierarchies) can be implemented. Kirchler et al [START_REF] Kirchler | Wolfler Calvo UniALT for regular language constrained shortest paths on a multi-modal transportation network 11th[END_REF] recently proposed an efficient single-objective algorithm following these directions. Furthermore, as suggested by a referee, it is possible that implementation of the ideas presented in this paper with a label-correcting version with an appropriate data structure (perhaps partitioning or double-ended queue) could also yield improvements.

Other multi-objective problems in the multi-modal context are of interest and will be the subject of further research, although the complexity of the problem could increase. The case where public transportation does not have a fixed schedule and probability distributions may be associated to arrival of passengers and transportation lines at each node is also of practical interest. Finding an "optimal" strategy for a user (that minimizes expected travel times), has been tackled via the the hypergraph model and the shortest hyperpath problem, introduced by Nguyen and Pallottino in [START_REF] Nguyen | Hyperpaths and shortest hyperpaths[END_REF] for a single public transportation mode. This approach has been extended to the bi-objective "expected travel time"/"number of transfers" multi-modal viable networks in [START_REF] Lozano | Shortest viable hyperpath in multi-modal networks[END_REF] but no computational experiments where reported. Adapting our algorithms to the hypergraph model is also a promising research direction.

Appendix A: Comments on the Lozano and Storchi [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] approach

In [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF], the set of considered mode is {c, s, tr, o} where c i the private mode (car or motorbike), s is the subway mode, tr is a special mode representing a modal transfer and o represents other modes like bus and walking. In their example (similar to our scenario M 3 ) only c and s are constrained mode in the sense of modal restrictions. Figure 5 represents the corresponding NFA as presented in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] (b) if state s l path is using a constrained mode, then state s u path is using this mode or has never used it.

To clarify this theorem, we define the following terms. A "constrained mode" is a mode which is subject to constraints, i.e. private car (c) and subway (s) in Figure 5. A "state s path" is the Oi path represented by a label (i, s, k). "A mode m has been used" by a "state s path" means that at least one node j with m j = m is in the path Oi corresponding to label (i, s, k). A "state s path is using mode m" means that for label (i, s, k), m i = m.

The topological Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF] algorithm was extended by Lozano and Storchi to path viability modeled by a NFA using the preference theorem as a dominance rule for label discarding. The algorithm (MSVPP) iterates on the number of transfers from 0 to k max . At each iteration k, it searches for the shortest path with exactly k transfers. For that, the data structure Q for storing labels, is made of two priority queues Q now and Q next , where Q now contains labels with k transfers and Q next contains labels with k + 1 transfers. Initially, Q now contains only label (O, s 0 ) while Q next is empty. At a typical iteration, a label (i, s) is taken from Q now and its value t is is compared with lastlabel is , the shortest travel time found so far to reach node i in state s (i.e. with at most k transfers). If t is <lastlabel is , the label extension principle is applied and lastlabel is is updated. Each successor (j, s ′ ) such that t is + d ij < t js ′ is candidate for being updated. A dominance rule based on the preference theorem is applied. If label (j, s ′ ) has a longest length than all labels (j, s ′′ ) for all states s ′′ that are preferred to s ′ , label (j, s ′ ) is discarded. Otherwise, t js ′ is updated with t is + d ij . If arc (i, j) is not a transfer arc, the new label (j, s ′ ) is inserted in Q now . If arc (i, j) is a transfer arc, the label is inserted in Q next . When Q now is empty, the number of transfers is incremented. Q now is reinitialized with Q next . If Q now is empty or if a maximum number of transfers is reached, the algorithms stops. Note that MSVPP is a label correcting algorithm. Note also that, in this algorithm, a single label t is is used per node-state pair (i, s), while Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF] use two labels per nodes, which would give the two labels t now is and t next is . We now point out the following issues linked to the Lozano and Storchi preference theorem, the way the dominance rule is implemented and the way the topological Pallottino and Scutellà [START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF] algorithm was extended. We refer to the NFA displayed in Figure 5.

• The set of "constrained modes" used by each label is not fully determined by the label state.

Even if, for state s 1 , the set of used constrained modes is necessarily empty and if, for states s 2 and s 3 , the set of used constrained mode is necessarily singleton {c}, the set of constrained modes used by a label in state s 4 or s 5 can be one of the sets {s} or {s, c}. Consequently, to apply dominance rule of Theorem 7.1 for two labels (i, s) and (i, s ′ ), one should either build the partial path by a recursively accessing the predecessor labels p is and p is ′ to access the visited modes or, better, one may store, for each label, the set of visited constrained modes. However, both solutions raise computational issues.

• The application of the dominance rule to discard a label (i, s) in the Lozano and Storchi algorithm may consider a label as non-dominated while it could be discarded.

Consider the simple network of Figure 6 and the bi-objective shortest path problem from node x 0 to node x 6 . Consider also the three paths issued from x 0 and ending at x 5 . We have private car-bus path p (1) : x 0 → x 1 → x 3 → x 5 with 1 transfer and length 4 (shortest path). We have direct bus path p (2) : x 0 → x 5 with no transfer and length 6 (shortest path with 0 transfer). Last, we have subway-bus path p (3) : x 0 → x 2 → x 4 → x 5 with 1 transfer and length 5. Path p (3) , entering node x 5 in state s 5 , is dominated by path p (1) , entering node x 5 in state s 4 , as it has the same number of transfers, a larger length and less extension possibilities. Hence it should be discarded. In the Lozano and Storchi algorithm, path p (2) , entering node x 5 in state s 1 , is first found as the shortest path with 0 transfers. Suppose p (1) is first one found as the shortest path to x 5 with 1 transfer. When the dominated path p (3) is scanned, it is unfortunately not discarded as, according to the way the dominance rule is applied in the Lozano-Storchi algorithm, a label can only be discarded if it has a length larger than or equal to the one of all its preferred labels, not just one as in classical dominance checking. According to the preference theorem, both labels p (1) and p (2) are preferred to p (3) (as they both have more extension possibilities). However p (3) has shortest length than p (2) and so the algorithm does not discard it.

x 0 x 2 x 1 x 4 x 3 x 5 x 6 1(c) 2(s) 6(o) 2(o) 2(o) 1(o) 1(tr) 1(tr)
Figure 6: A dominated path is not discarded • Theorem 7.1 is not valid anymore if the NFA is slightly modified.

Consider the simple multimodal network displayed in Figure 7 and the NFA obtained by removing transition s 1 s → s 4 from the NFA of Figure 5. This may model the (unusual) preference that if the private car or the metro are not taken from the origin, the metro cannot be taken in any viable path. Hence, path x 0 → x 2 → x 3 → x 5 → x 6 → x 4 → x 7 with 2 transfers and a length of 12 is not feasible. The shortest path is x 0 → x 1 → x 2 x 3 → x 5 → x 6 → x 4 → x 7 of length 12 and 3 transfers corresponding to mode sequence private car, bus, subway, bus. The 0-transfer path x 0 → x 2 → x 3 → x 4 → x 7 taking only the bus has a length of 13. Let us apply the preference theorem to subpaths p (x 0 → x 2 ) and p ′ (x 0 → x 1 → x 2 ). p is in state s 1 while p ′ is in state s 3 . p has used no constrained modes while p ′ has used constrained mode p. Consequently s 1 s 3 for p ′ and p. As p is reached by the algorithm before p ′ , when p ′ is scanned by the algorithm it is discarded since it does not improve the length of any previously found path reaching x 2 in a preferred state (p is the only path with a state preferred to that of p ′ ). Since p ′ is discarded, arc (x 3 , x 5 ) will never be viable as node x 3 (in the modified automaton) will only be reached in state s 1 by extending p and that taking the subway is no more possible in state s 1 . As the shortest path will never be found, the dominance rule of Theorem 7.1 is not valid for this (slightly) modified NFA. Actually the dominance rule is valid for the example given in [START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF], as the subway can be reached by both states s 1 and s 3 but our simple counterexample shows that it cannot be directly generalized to different state transitions.

• A path with k transfers may not be extended because it has a longer length than a path with k + 1 transfers.

To illustrate this situation, let us consider the example given in Figure 8. When computing the shortest path from x 0 to x 4 with 0 transfer, the algorithm obtains labels (x

Q now and in Q next . x 0 x 2 x 3 x 4 x 1 1(o) 2(s) 2(s) 1(s) 1(tr)
Figure 8: The shortest path from x 0 to x 4 with 0 tranfer is not obtained

In this paper, we address all these issues by proposing a new state-based dominance rule and a different implementation of the TLS algorithm.

Multi-queue label setting algorithm (MQLS)

Algorithm 3 Multi-queue label setting algorithm (MQLS)

Require: Graph: G(V, E), NFA: A, Origin: O, Destination: D, Max. transfers: k max 1: Q = {Q 0 ← {(O, s 0 , 0)}}, t 0 0,s0 ← 0, p 0 O,s0 ← (O, s 0 , 0) 2: t 0 i,s ← ∞, ∀i ∈ V \ {O}, ∀s ∈ S 3: K ← k max 4: repeat 5:

(i, s, k) ← argmin{t k ′ i ′ ,s ′ |(i ′ , s ′ , k ′ ) ∈ Q} and Q k ← Q k \ {(i, s, k)} 6:
if i = D and s ∈ F then 7:

store t k i,s and p k i,s as the shortest path with k transfers.

8:

Discard all Q k ′ with k ′ ≥ k. LabelExtensionMQLS((i, s, k), Q)

12:

end if 13: until K < 0 or Q = ∅ Algorithm 4 LabelExtensionMQLS((i, s, k), Q) 1: M ark k is ← true 2: for j ∈ F S(i) do

Q k ′ ← Q k ′ ∪ {(j,
(i f , s f , k f ) ← argmin{f t k ′ i ′ ,s ′ |(i ′ , s ′ , k ′ ) ∈ FQ} 8: (i b , s b , k b ) ← argmin{bt k ′ i ′ ,s ′ |(i ′ , s ′ , k ′ ) ∈ BQ} {Direction setting} 9: if f t k f i f ,s f ≤ bt k b i b ,s b then 10: (i, s, k) ← (i f , s f , k f ), F Q k ← F Q k \ {(i f , s f , k f )} 11:
if i = D and s ∈ F F then 12: BackwardLabelExtension((i, s, k), FQ, BQ, k * ,BestCurrentSol)

BestCurrentSol k ← f t k is , k * ← k 13:
(i f , s f , k f ) ← argmin{f t k ′ i ′ ,s ′ |(i ′ , s ′ , k ′ ) ∈ FQ} 25: (i b , s b , k b ) ← argmin{bt k ′ i ′ ,s ′ |(i ′ , s ′ , k ′ ) ∈ BQ} 26: if k * = -1 and BestCurrentSol k * ≤ f t k f i f ,s f + bt k b i b ,s b then 27:
store BestCurrentSol k * as the shortest path with k * transfers.

28:

Discard all F Q k and BQ k with k ≥ k * .

29: The algorithm stops because there is no more label in Qnow even if the limit on the maximal number of transfers is not reached.

K ← k * -1, k * ←

Multi-queue label setting algorithm (MQLS)

Initialization: k = 0, Q 0 = {(x 1 , s 0 , 0)}, t 0 1s 0 = 0, kmax = 5 fixed label ; travel time reached label travel time Dom. rule Insert (x 1 , s 0 , 0); t 0 1s 0 = 0 (x 4 , s 0 , 0) The algorithm stops as the solution with 0 transfer has been obtained.

4 - Q 0 (x 2 , s 0 , 1) 1 - Q 1 (x 6 , s 1 , 1) 1 - Q 1 (x 2 ,

Bidirectional Multi-queue label setting algorithm (FB-MQLS)

For the proposed bidirectional algorithm, we consider the NFA given in

Figure 1 :

 1 Figure 1: Initial NFA for mode scenario M 3 = {w, b, c, s}

Figure 2 (

 2 Figure 2(a) shows an (unrealistic) multi-modal network with 7 nodes corresponding to mode scenario M 2 = {w, b, s}. Nodes x 2 and x 3 are bus (b) nodes; nodes x 1 , x 4 and x 5

  NFA for mode scenario M2 = {w, b, s}

Figure 2 :

 2 Figure 2: a Bi-RegL-CSPP with 7 nodes, 12 arcs, 3 modes and a 3 state-NFA

  b}, we can have the following transitions: δ(m, w, s 1 ) = s 1 and δ(m, w, s 5 ) = s 5 δ(m, b, s 1 ) = s 1 and δ(m, b, s 5 ) = s 5 δ(m, s, s 1 ) = s 4 and δ(m, s, s 5 ) = ∅ δ(m, c, s 1 ) = ∅ and δ(m, c, s 5 ) = ∅ (ie. the car mode cannot be used)As a preliminary remark, we can use preorder to reduce the number of states of the automaton.Proposition 5.2. If s s ′ and s ′ s, s and s ′ can be merged into a single state without modifying the viability constraints.

2 ( 1 , s ′ b 4 }

 214 (b)). In this figure, the initial state (at destination) is s ′ b D . Final states are s ′ b 1 (departure by walk or bus) and s ′ b departure by private car). Transition function δ b (m i , m j , s) gives a set of possible states. For example δ b (m D , w, s D ) = {s ′ b (where m D denotes the mode at the destination). This means what when arriving by walk at the destination, it could be that the subway was taken (state s ′ b 4 ) or was not taken (state s ′ b 1 ).

  regular expression corresponds to c*(w, b)*s*(w, b)* and the reverse regular expression corresponds to (w, b)*s*(w, b)*c*.

1 s b 4 .

 14 (b), there is no dominance relation between states in the sense of Theorem 5.1. For the deterministic automaton of Figure 4(c), we have s b The set of states that dominate a given forward (backward) state s is denoted D f (s) (D b (s)), respectively.

Figure 4 :

 4 Figure 4: Backward Automata for mode scenario for M 3

Theorem 5 . 2 (

 52 Forward/backward state compatibility). Forward state s f x and backward state s b y are compatible if s f x s f y in the forward automaton or if s b y s b x in the backward automaton. Proof. If one of the dominance relation holds, the concatenation of any m-terminated mode string accepted by s f x with any reversed m-terminated input string accepted by s b y is a valid string, yielding the desired compatibility.

F

  |CS F A→BA (s)| ≤ |S B |. Hence for the basic dominance rule, the complexity of the forward extension (Algorithm 6)) is O(|F S i |(k max + log(n|S F |)) for the deterministic backward automaton and O(|F S i |(k max s + log(n|S F |)) for the nondeterministic backward automaton. For the state based dominance rule, the complexity of forward extension is O(|F S i |(k max |S F | + log(n|S F |)) for the deterministic automaton and O(|F S i |(k max (|S F | + s) + log(n|S F |)) for the non-deterministic backward automaton. If the forward automaton is assumed to be deterministic, the complexity of the backward extension is always equal to O(|BS i |(k max + log(n|S B |)) for the basic dominance rule and to O(|F S i |(k max (|S B |) + log(n|S B |)) for the state-based dominance rule.

Figure 5 :

 5 Figure 5: Lozano and Storchi NFA In their paper Lozano and Storchi proposed a dominance rule (Preference theorem). We recall below the Lozano and Storchi Theorem 3 . Theorem 7.1 ([15]). State s u is preferred to state s l , s u s l , if the following sentences are valid: (a) the constrained modes used in state s u path, are a subset of the set of constrained modes used in state s l path;

3 :

 3 for s ′ ∈ δ(m i , m j , s) do 4: if m i = mj then

Algorithm 5

 5 Bidirectionnal multi-queue label setting algorithm (FB-MQLS) Bidirectional multi-queue label setting algorithm (FB-MQLS)Require: Graph G(V, E), NFA: F A, BA, Origin: O, Destination: D, Max. transfers: k max {Initial forward and backward labels}1: FQ ← {F Q 0 ← {(O, s 0 , 0)}}, f t 0 O,s0 ← 0, f p 0 O,s0 ← (0, s 0 , 0) 2: f t 0 i,s ← ∞, ∀i ∈ V , ∀s ∈ S F , (i, s) = (O, s 0 ) 3: BQ ← {BQ 0 ← {(D, s D , 0)}}, bt 0 D,s D ← 0, f p 0 D,s D ← (D, s D , 0) 4: bt 0 i,s ← ∞, ∀i ∈ V , ∀s ∈ S B , (i, s) = (D, s D ) {Initial minimal connection} 5: K ← k max , BestCurrentSol k ← ∞, ∀k, 0 ≤ k ≤ k max , k * ← -1{Main Loop: start by getting minimum time label among all priority queues} 6: repeat 7:

else 14 : 18 : 19 :

 141819 ForwardLabelExtension((i, s, k), FQ, BQ, k * ,BestCurrentSol) s, k) ← (i b , s b , k b ), BQ k ← BQ k \ {(i b , s b , k b )} if i = O and s ∈ F B then BestCurrentSol k ← bt k is , k * ← k

Q

  now = {(x 5 , s 0 , 4)}, t 4 5s 0 = 4, Q next = ∅ Iteration 5: k = 4 // Search solution with 4 transfers fixed label ; travel time reached label travel time Dom. rule Insert (x 5 , s 0 , 4); t 4 5s 0 = 4 Destination is reached

Figure 9 .

 9 Compatible states correspond to

Figure 9 : 0 = 0 ,5s b 2 = 0 ,

 90020 Figure 9: NFA for forward and backward stepsCS F A→BA (s f 0 ) = {s b D , s b 2 }, CS F A→BA (s f 1 ) = {s b 1 } and CS F A→BA (s f 2 ) = {s b 2 }.For the forward NFA, there is a dominance relation : s f 0 s f 2 and for the backward one, s b 2 s b D .

  as the previously encountered label cannot have more transfers. The complexity of the state-based dominance rule is in O(|S|): a given label (j, s ′ , k ′ ) obtain by extension of a label (i, s, k) is dominated if BestV alue j,s ′′ ≤ t k is + d ij for all states s ′′ such that s ′′ s ′ .

Table 1 :

 1 Network data

	Modes Nodes	Arcs
	Bus	3 085	6 646
	subway	38	72
	Street	59 896 146 280
	Transfer	-	6 370
	Parking	29	-
	Total	63 048 159 368

Table 2 :

 2 Solution characteristics

	Modes	Nb. Sol. nb Transf. av nb Transf. max Travel t. min Travel t. max
	M 3 = {w, b, c, s}	3.49	2.7	5.02	48	273
	M 2 = {w, b, s}	4.24	3.59	6.72	62	273
	M 1 = {w, b}	4.23	3.64	6.6	69	273

  The shortest path is discarded if the state automaton is changed previous value just obtained for (x 3 , s 4 ). It follows that label (x 3 , s 4 ) with 0 transfer is discarded. And, the algorithm doesn't find any solution with 0 transfer. The problem comes from the fact that, unlike in the original algorithm of Pallottino and Scutellà[START_REF] Pallottino | Shortest path algorithms in transportation models: Classical and innovative aspects[END_REF], a single label t is is used to update any label independently of the fact that is is stored in

		x 2	3(o)	x 3	4(0)	x 4
	3(o)		1(tr)		1(tr)	3(o)
	x 0	1(tr)	x 5	1(s)	x 6	x 7
	2(c)
		x 1
	Figure 7:

1 , s 1 ) with t x 1 s 1 = 1 and (x 2 , s 4 ) with t x 2 s 4 = 2 and stores them in Q now . Then, (x 1 , s 1 ) is dequeued and (x 3 , s 4 ) with 1 transfer is obtained and stored in Q next , updating t x 3 s 4 = 2. And, then (x 2 , s 4 ) is dequeued from Q now . Label (x 3 , s 4 ) with 0 tranfer is obtained but is travel time is equal to 4 which is greater than the

  if t k is + d ij < t k ′ js ′ then {Bellman condition does not hold } 11: if ∀s ′′ ∈ D s ′ , ∀k ′′ ≤ k ′ , t k is + d ij < t k ′′js ′′ then {Dominance rule does not apply}

	8:	end if
	9:	if not M ark k ′ js ′ then
	10:
	12:	t k ′ js

′ ← t k is + d ij , p k ′ js ′ ← (i, s, k) 13:

  s ′ , k ′ )}

	14:	end if
	15:	end if
	16:	end if
	17:	end for
	18: end for

  argmin k∈{0,...,K} BestCurrentSol k 30:end if 31: until K < 0 or FQ = BQ = ∅ now is empty : no solution with 1 transfer.Q now = {(x 4 , s 0 , 2), (x 5 , s 2 , 2), (x 5 , s 0 , 2)}, t 2 4s 0 = 2, t 2 5s 2 = 5, t 2 5s 0 = 6, Q next = ∅ , s 2 , 2); t 2 5s 2 = 5Destination is reachedQ now = {(x 3 , s 0 , 3), (x 7 , s 1 , 3)}, t 3 3s 0 = 3, t 3 7s 1 = 3, Q next = ∅ , s 0 , 3); t 3 3s 0 = 3 (x 5 , s 0 , 4) 3 Q next (x 7 , s 1 , 3); t 3 7s 1 = 3 (x 5 , s 2, 4) 4 state-Q now is empty : no solution with 3 transfers.

	Iteration 2: k = 1 // Search solution with 1 transfer
	fixed label ; travel time	reached label	travel time	Dom. rule	Insert
	(x 2 , s 0 , 1); t 1 2s 0 = 1	(x 3 , s 0 , 1) (x 4 , s 0 , 2)		6 2	-	already in Q now Q next
	(x 6 , s 1 , 1); t 1 6s 1 = 1	(x 4 , s 2 , 2) (x 7 , s 1 , 1)		6 4	state	-already in Q now
	(x 7 , s 1 , 1); t 1 7s 1 = 4 (x 3 , s 0 , 1); t 1 3s 0 = 5	(x 5 , s 2 , 2) (x 5 , s 0 , 2)		5 6	Q next Q next
	Q Iteration 3: k = 2 // Search solution with 2 transfers
	fixed label ; travel time	reached label	travel time	Dom. rule	Insert
	(x 4 , s 0 , 2); t 2 4s 0 = 2	(x 5 , s 0 , 2) (x 3 , s 0 , 3)		6 3	already in Q now Q next
		(x 7 , s 1 , 3)		3	Q next
	(x 5 Iteration 4: k = 3 // Search solution with 3 transfers
	fixed label ; travel time	reached label	travel time	Dom. rule	Insert
	(x 3

  , s 2 , 2); t 2 5s 2 = 5 Destination is reached. Suppress Q 2 and Q 3 (x 5 , s 0 , 0); t 0 5s 0 = 8 Destination is reached. Suppress Q 0 and Q 1

	s 0 , 1); t 1 2s 0 = 1	(x 3 , s 0 , 1) (x 4 , s 0 , 2)	6 2	--	Q 1 Q 2
	(x 6 , s 1 , 1); t 1 6s 1 = 1	(x 7 , s 1 , 1) (x 4 , s 2 , 2)	4 2	-state	Q 1 -
	(x 4 , s 0 , 2); t 2 2s 0 = 2	(x 5 , s 0 , 2) (x 3 , s 0 , 3)	6 3	--	Q 2 Q 3
		(x 7 , s 1 , 3)	3	-	Q 3
	(x 3 , s 0 , 3); t 3 3s 0 = 3 (x 7 , s 1 , 3); t 3 7s 1 = 3 (x 5 , s 0 , 4); t 4 5s 0 = 4 (x 7 , s 1 , 1); t 1 7s 1 = 4 (x 4 , s 0 , 0); t 0 4s 0 = 4	(x 5 , s 0 , 4) (x 5 , s 2 , 4) Destination is reached. Suppress Q 4 4 -4 state (x 5 , s 2 , 2) 5 -(x 5 , s 0 , 0) 8 (x 3 , s 0 , 1) 5 basic	Q 4 -Q 2 Q 0 -
	(x 3 , s 0 , 1); t 1 3s 0 = 5	(x 5 , s 0 , 2)	6	basic	-
	(x 5

Lozano and Storchi [15] referred to the problem as the multi-modal viable shortest-path problem

In[START_REF] Lozano | Shortest viable path algorithm in multi-modal networks[END_REF] impossible transitions were also represented but they can be guessed with the observation that any non represented transition is infeasible, e.g. subway, bus or waking cannot be taken from state s2

We replace notation R, used in the original theorem, by notation

Acknowledgements

The authors wish to thank Arnaud Fradin for his participation to the test campaign and implementation as well as Sandra Ulrich Ngueveu, Roberto Wolfler Calvo, Dominik Kirchler and Emmanuel Néron for fruitful discussions. The authors would also like to thank the referees for their valuable suggestions that contributed greatly to improve the quality of the paper. The research was partially supported by ANRT CIFRE research grant 424/2007 and by GdR Recherche Opérationnelle ARFRO.

7:

if (i = D or s ∈ F ) and t k is <BestLastSol then

8:

LabelExtensionTLS((i, s, k), Q now , Q next )

9:

end if

10:

until Q now = ∅ or (i = D and s ∈ F )

11:

if i = D and s ∈ F and t k is <BestLastSol then

12:

BestLastSol ← t k is 13:

store t k Ds and p k Ds (shortest path with k transfers).

14:

end if 15:

for s ′ ∈ δ(m i , m j , s) do

4:

if m i = m j then 5:

else 7:

8:

end if

9:

if not M ark k ′ js ′ then {Scan unmarked successor (j, s ′ , k ′ )} 10:

12:

if k ′ = k then

13:

BestV alue js ′ ← t k ′ js ′

14:

end if 15:

BestV alue js ′′ then {Dominance rule does not apply}

16:

if k ′ = k then 17:

18:

else 19:

20:

end if

21:

end if

22:

end if

23:

end if

24:

end for 25: end for Algorithm 6 ForwardLabelExtension((i, s, k), FQ, BQ, k * ,BestCurrentSol)

insertheap ← f alse {Connection with marked backward with 0 transfer} end for

25:

if insertheap then 26:

Iteration 1: k = 0 // Search solution with 0 transfer fixed label ; travel time reached label travel time Dom. rule Insert (x 1 , s 0 , 0);

Destination is reached

The algorithm stops as the solution with 0 transfer has been obtained.

Appendix D: detailed computational results