1 Introduction

The route choice problem (Bovy and Stern 1990) is to find an optimal way to travel between two places, with minimal travel time, distance, or cost. In a deterministic or static environment, it can be modeled as the well known and studied classical Shortest Path Problem (SPP) (Yu and Yang 1998). However, in practice, it usually should be considered in a nondeterministic or dynamic environment due to the traffic variations over time. In live traffic circumstances, the chosen route may become unavailable since of some blocked nodes caused by unforeseen accidents or other uncertain disruptions; and meanwhile, the travel times along the arcs of the traffic network also cannot be accurately predicted in advance. Therefore, we investigate the route choice problem on a network with uncertain travel times and possible blocked nodes in this paper. Two kinds of nondeterministic factors are combined to be considered simultaneously while making the route choice: one is concerned with the uncertain travel times along the arcs of the network, and the other is related to the possible blocked nodes.

Considering the successively observed blocked nodes, if we should make real-time responses and dynamically adjust the route decision, the route choice decision is a typical online SPP (Papadimitriou and Yannakakis 1991; Waller and Ziliaskopoulos 2002). In the traditional online SPP, it aims at computing the shortest path (with minimal travel time, distance, or cost) based on live traffic circumstances. For example, some nodes in the traffic network may be blocked and thus paths getting through these nodes cannot be passed anymore. If the blocked nodes appear successively, or the information of the blocked nodes is received incrementally, one piece at a time, how to get a shortest path with no secure knowledge of future possible blocked nodes?

Another kind of nondeterministic factor considered in this paper is the uncertain property concerning the travel times experienced by travelers along the arcs of the network. Since travel times are not always deterministic in real applications, and some researchers believed that they conform to randomness or fuzziness, the probability theory or fuzzy set theory was introduced into SPP. Consequently, the notions of stochastic SPP (Ji 2005; Wang et al. 2016; Jafari and Boyles 2017) and fuzzy SPP (Okada and Gen 1994; Okada and Soper 2000; Niroomand et al. 2017) were proposed, respectively.

However, it has been illustrated by many investigations (Liu 2007, 2012; Kahneman and Tversky 2013) that it is inappropriate to describe the nondeterministic phenomena as randomness or fuzziness in some scenarios, particularly those involving human beings’ subjective judgements. In the practical route choice problem, travelers’ route choices are usually made relying on their personal experiences and subjective judgements with the aid of some real traffic information (Dia 2002; Ben-Elia et al. 2008). While making the route choice, the travel times are hard to be accurately predicted in advance, particularly for the situations suffering accidental disruptions. Even if adequate historical data or real-time information is provided to make informed decisions at the beginning of their trips, each traveler’s actual travel time may vary from case to case due to different vehicles, personal driving habits, psychological effects (Ben-Elia and Avineri 2015) or other factors. Therefore, the travel times estimated by individual travelers are usually associated with their subjective beliefs. In this case, probability theory or fuzzy set theory is no longer suitable for modeling their subjective beliefs on the uncertain travel times, whereas uncertainty theory proposed by Liu (2007) provides a new powerful tool to rationally deal with this type of uncertain quantities.

Therefore, following from the uncertainty theory, in this paper, we investigate the route choice problem on a network with uncertain travel times along the arcs and possible blocked nodes, called the Online Uncertain Route Choice (OURC) problem. It can be treated as a natural extension of the traditional online SPP by considering that the travel times are assumed to be uncertain variables. The objective is to seek an optimal (shortest) path in the uncertain network without knowing the online releasing blocked nodes in advance. For this OURC problem, online algorithms are introduced to make real-time responses to the successively observed blocked nodes ; and accordingly, an uncertain competitive analysis framework, taking expected competitive ratio as the metric, is proposed to evaluate the performances of the online algorithms associated with uncertain travel times. Following from the proposed framework, two typical online strategies, i.e., reset strategy and greedy strategy, are adopted to develop online algorithms for the OURC problem, and their performances are analyzed in detail as well.

The remainder of this paper is organized as follows. Section 2 briefly reviews the related work. Section 3 describes the traditional online SPP as well as the OURC problem. In Sect. 4, an uncertain competitive analysis framework is proposed. Then, the reset strategy and greedy strategy based online algorithms and their performances are discussed in Sects. 5 and 6, respectively. Finally, conclusions are given in Sect. 7.

2 Literature review

Route choice problem has received much attention and plenty of studies due to its importance to people’s daily lives and the traffic management. In this paper, we focus on the optimal route choice decisions for individual travelers, rather than modelling route choice behaviors as well as their impacts on traffic equilibrium (e.g., Dia 2002; Yang and Jiang 2014; Xu et al. 2017).

For the route choice problem considered in nondeterministic or dynamic environments, different approaches have been proposed in the literature, among which the most popular methodology is formulating the problem as a stochastic model based on assumptions about the distributions of the relevant uncertain quantities, such as travel times along the arcs of the network, the time and locations of the blocked nodes that may appear. For instance, considering stochastic arc length, Ji (2005) proposed the concepts of expected shortest path, \(\alpha\)-shortest path and the most shortest path as well as their solution algorithms for stochastic SPP, according to different decision criteria. Jafari and Boyles (2017) further investigated the multi criteria stochastic SPP. Moreover, Chen et al. (2013) proposed the reliable SSP on networks with stochastic travel times, and the corresponding dominance conditions as well as solution algorithms of this problem were presented. Wang et al. (2016) studied the SPP with stochastic correlated link travel times, considering flow balance and side constraints as well as the unique link selection constraint. Concerning the adaptive route choices with respect to the dynamic traffic conditions, Gao et al. (2010) presented a route choice model based on prospect theory to capture travelers strategic behavior in a stochastic network.

However, these stochastic optimization approaches, which aim to optimize the outcomes in average or with some confidence levels, or the probability of achieving some predetermined goals, may yield some online solutions (decisions made before getting the accurate information) that are far from the relevant optimal offline solutions (decisions made after the realizations of uncertain factors being observed) under some scenarios. Furthermore, it is usually hard to accurately estimate the probability distributions of such uncertain quantities, especially for the blocked nodes caused by unforeseen accidents. In this situation, the probabilistic analysis based approach is no longer applicable for handling this type of problem, whereas competitive analysis approach proposed by Sleator and Tarjan (1985) provides an alternative appropriate framework to deal with them. Following from the idea of competitive analysis, Papadimitriou and Yannakakis (1991) originally proposed the online decision version of the SPP without a map, in which the information about the graph was acquired in a dynamic manner, and proved that there is no bounded worst-case ratio for general graphs. Following that, Kalyanasundaram and Pruhs (1993) studied the problem of exploring an initially unknown weighted graph and proposed a constant competitive algorithm. Ma and Chen (2005) and Ma et al. (2008) discussed the online SPP and the most reliable path problem as well as their competitive algorithms on a fuzzy network. Recently, instead of finding optimal solutions or strategies according to some decision criteria like that in stochastic optimization and competitive analysis approaches, Schmidt et al. (2017) discussed the dominance relations between strategies for the route choice problem with uncertain disruptions. For results on the more generalized online routing problem, readers may refer to Jaillet and Wagner (2008), Harks et al. (2009), and Zheng et al. (2017).

On the other hand, as previously mentioned, since the route choice decision is usually associated with traveler’s subjective judgements on the traffic conditions, we assume that the travel times along the arcs of the network are uncertain variables, estimated by the travelers according to their personal experiences and some real traffic information, in this paper. For networks with uncertain arc lengths which are formulated as uncertain variables, three types of uncertain programming models were proposed by Liu (2010b) to address the SPP. Subsequently, Gao (2011) further discussed the uncertainty distributions of the length of the shortest path and proposed effective solution approaches to find the \(\alpha\)-shortest path and the most shortest path. Following from the notion of uncertain \(\alpha\)-shortest path, the inverse SPP on an uncertain network was discussed by Zhou et al. (2014) to make a predetermined path become the shortest one with minimal modification on the arc lengths. Recently, Zhang et al. (2015) investigated the uncertain multi-modal SPP with bi-objectives. Besides SPP, some other traditional network optimization problems, such as minimum spanning tree problem (Zhou et al. 2015, 2016), also have been revisited in the literature and some new properties were proposed with consideration of the new feature that arc lengths of the networks were formulated as uncertain variables.

In this paper, we consider online route choices, with the capability of adapting to possible blocked nodes, on a network with uncertain travel times along the arcs. This study differs from the above related work in the following two aspects. First, two kinds of nondeterministic factors are considered simultaneously in the route choice problem, which makes the performance of the route choice decision be not only subject to the responses to the successively observed blocked nodes, but also influenced by the uncertain travel times along the arcs. Second, the competitive analysis approach and the uncertainty theory are integrated to handle the presented OURC problem. Some theoretical results with respect to the proposed uncertain competitive analysis framework and two typical online strategies are presented as well.

3 Problem description

In this section, we briefly introduce the traditional online SPP first. Then the OURC problem is proposed, which is an extension of the traditional problem by considering it on a network with uncertain arc lengths representing the uncertain travel times.

3.1 Traditional online shortest path problem

Given a connected network, we can easily find the shortest path between any pair of nodes in the network by employing the classical shortest path algorithms such as the Dijkstra algorithm (Dijkstra 1959). However, if some blocked nodes appear in the network, indicating that these nodes cannot be passed, then how to find the shortest path between a given pair of nodes?

Obviously, this problem can be considered in the following two cases:

  1. 1.

    If all the blocked nodes are known in advance, how to choose the route to minimize the total travel time between the origin and destination nodes?

  2. 2.

    If the blocked nodes appear successively, and they can be observed only if their adjacent nodes are reached, then how to choose the route on condition that we only have the previous information about the observed blocked nodes?

It is clear that the problem (1) is an offline problem whereas (2) is an online problem. The difference between them lies on the complete or incomplete information concerning the blocked nodes. Taking the network shown in Fig. 1 for example, which consists of 10 nodes and 19 arcs. The values on the arcs denote the arc lengths representing the travel times. The gray nodes d and h are blocked nodes and thus cannot be passed. For the problem (1), the blocked nodes are known before making the decision. Therefore, we can remove the blocked nodes as well as the arcs directly connected to these nodes (denoted by dashed lines in the figure), and then find out the shortest path between a given pair of nodes. For instance, the shortest path from a to j is that starting from a, and then sequentially passing the nodes c, e, and i, and finally reaching j. This path can be denoted by the sequence of reached nodes as \(a\rightarrow c\rightarrow e\rightarrow i\rightarrow j.\) Obviously, the offline problem can be easily solved by classical shortest path algorithms, since complete information is available while making the decision.

Fig. 1
figure 1

An illustration of the traditional online shortest path problem

Full size image

The problem (2) is called the online SPP. For example, we want to travel from a to j in the network shown in Fig. 1. While determining the travelling path, the blocked nodes are not observed. Generally, we may take the shortest path between a and j as a good solution. Without consideration of the blocked nodes (we know nothing about the possible blocked nodes at the beginning), the shortest path is \(a\rightarrow b\rightarrow d\rightarrow g\rightarrow i\rightarrow j.\) However, after we reached b, it is observed that the node d is blocked and thus cannot be passed. Then we have to adjust the route. If we replan the route and take the shortest path between the currently reached node and the destination (namely, b and j), the new route is \(b\rightarrow f\rightarrow h\rightarrow j.\) After we reached f, it is found again that h is blocked. The online version of the SPP therefore becomes more complex because of the significant effects of the sequence of blocked nodes on the optimal solution.

In the online SPP, we know nothing about the future possible blocked nodes. An algorithm is said to be online if it dynamically adjusts its route and makes real-time responses to the successively observed blocked nodes. In general, due to the absence of complete information, it is hard to make an online algorithm respond to the incrementally received information in an optimal fashion. Following from the idea of competitive analysis, the performance of an online algorithm can be measured against that of the optimal offline algorithm, which knows complete information when making its decision and thus it can be optimized. Formally, the approach of competitive analysis and the notion of competitive algorithm are presented as below.

Definition 1

(Borodin and El-Yaniv 1998) Let I be an input sequence which denotes the future uncertain events, and \(C_\mathrm {ON}(I)\) and \(C_\mathrm {OPT}(I)\) be the costs paid by an online algorithm ON and the optimal offline algorithm OPT in processing the input sequence I, respectively. The algorithm ON is called a competitive algorithm if there exist constants \(\alpha\) (\(\alpha \ge 1\)) and \(\beta\) such that

$$\begin{aligned} C_{\mathrm {ON}}(I)\le \alpha \cdot C_{\mathrm {OPT}}(I)+\beta , \end{aligned}$$
(1)

holds for any possible input sequences I. The constant \(\alpha\) is called the competitive ratio.

A competitive algorithm with competitive ratio \(\alpha\) is also called an \(\alpha\)-competitive algorithm, which implies that the cost of the online algorithm will not exceed \(\alpha\) times of the optimal offline cost for any inputs. It is clear that this performance measure provides very robust statements about the performance of an online algorithm, against all possible future scenarios.

3.2 Online uncertain route choice problem

In the traditional online SPP, the arc lengths (representing the travel times along these arcs) of the network on which the problem is considered are assumed to be deterministic. However, they are not always deterministic in real applications due to the traffic variations over time. As discussed in the section of Introduction, while planning their traveling routes, the travel times estimated by the travelers are usually associated with their subjective judgements on the traffic conditions based on some real traffic information. Therefore, we assume the nondeterministic travel times are uncertain variables, and consider the traditional online SPP on a network with uncertain arc lengths, called the online uncertain route choice problem.

Let \(N=(V,A,{{\varvec{\xi }}})\) denote a connected network, where \(V=\{v_1, v_2, \ldots , v_n\}\) is a finite set of nodes, \(A=\{a_1, a_2,\ldots , a_m\}\) is the set of arcs, and \({{\varvec{\xi }}}=(\xi _1, \xi _2, \ldots , \xi _m)\) is the uncertain arc length vector. In general, it is assumed that all the uncertain variables \(\xi _i\), \(i=1,2,\ldots , m\), are independent throughout this paper. For simplicity, a path between a pair of origin-destination nodes (O, D), \(O,D\in V\) and \(O\ne D\), is represented by the set of arcs contained in this path and denoted as \(P_{(O,D)}.\) Then the travel time of a path P can be formulated as:

$$\begin{aligned} L\left( P_{(O,D)},{{\varvec{\xi }}}\right) =\sum _{a_i\in P_{(O,D)}}\xi _i. \end{aligned}$$
(2)

Let \(I=\{c_1,c_2,\ldots ,c_k\}\) denote a sequence of blocked nodes in the network \(N=(V,A,{{\varvec{\xi }}})\), where \(c_i\in V\) (\(0\le i\le k\)) is the ith blocked node and \(k\ge 0\) is the total number of the blocked nodes. If \(k=0\), the online problem degenerates to an offline problem, which implies that all the information having impacts on the optimal decision is known in advance.

For a given pair of origin-destination nodes (O, D), the OURC problem is to find a path from the origin O to the destination D in the uncertain network \(N=(V,A,{{\varvec{\xi }}})\) to minimize the total travel time on condition that the information about the possible blocked nodes is received in an online fashion. Moreover, we assume that: the origin and destination nodes for traveler’s route planning would never be blocked; the network is still connected after the blocked nodes and their directly connected arcs are removed; the blocked nodes can be observed only if one of their adjacent nodes is reached; once a node is blocked, it remains blocked and can not be passed in the whole decision process.

The OURC problem can be found in many real application scenes, such as people’s daily travels when suffering accidental disruptions and the emergency relief logistics distribution in natural disasters. Taking the latter case for instance, while suffering from disasters (e.g., earthquake, hurricane, and flood), the traffic network may be destroyed and the information about the latest traffic condition cannot be acquired immediately. Therefore, travel times along the roads in disaster areas are hard to be accurately predicted. In order to make quick responses, we can distribute the relief logistics based on some evaluations about the traffic condition made by experts. However, what is worse, the roads may be completely blocked at some spots and this information would be acquired incrementally while exploring on the roads. Then, how to make an adaptive strategy considering the uncertain traffic condition in this situation? The problem in this case becomes an online route choice problem as presented above.

In the following sections, we propose an uncertain competitive analysis framework to analyze the OURC problem following from the uncertainty theory founded by Liu (2007, 2010a). Then online algorithms for this problem and their performances are discussed in detail.

4 An uncertain competitive analysis framework

In the OURC problem, since the arc lengths \(\xi _i\), \(i=1, 2, \ldots , m\), are uncertain variables, the travel time of a path is an uncertain variable as well. Consequently, the cost associated with an algorithm (namely, the total travel time of the planned route) is uncertain, which makes the definitions of competitive algorithm and competitive ratio (see Definition 1) in the traditional framework of competitive analysis useless for the uncertain version of the online SPP. Therefore, an uncertain competitive analysis framework is proposed in this section as follows.

4.1 Expected optimal offline algorithm

In order to evaluate the performance of an online algorithm by comparing it with the optimal offline one, the concept of optimal offline algorithm involving uncertain variables should be explicitly defined first.

Generally, for a given pair of origin–destination nodes, there exist more than one path from the origin to the destination. In order to explicitly define a shortest path with uncertain arc lengths, it is natural to determine the shortest one by comparing the expected values of travel times of all possible paths between the given pair of nodes. Based on this idea, the notion of expected shortest path was proposed by Liu (2010b).

Definition 2

(Liu 2010b, Expected shortest path) Given a connected uncertain network \(N=(V,A,{{\varvec{\xi }}})\) and a pair of origin-destination nodes (O, D), \(O,D\in V\), a path \(P^0\) between O and D is called an expected shortest path if

$$\begin{aligned} E\left[ L\left( P^0_{(O,D)},{{\varvec{\xi }}}\right) \right] \le E\left[ L\left( P_{(O,D)},{{\varvec{\xi }}}\right) \right] , \end{aligned}$$
(3)

holds for any path P between O and D , where \(E[L(P^0_{(O,D)},{{\varvec{\xi }}})]\) and \(E[L(P_{(O,D)},{{\varvec{\xi }}})]\) are the expected values of the travel times of path \(P^0\) and P, respectively. \(E[L(P^0_{(O,D)},{{\varvec{\xi }}})]\) is called the expected shortest travel time between O and D.

In the following discussion, we denote the expected shortest travel time between O and D by \(\overline{L}^0_{(O,D)}\) for simplicity. That is \(\overline{L}^0_{(O,D)}=E[L(P^0_{(O,D)},{{\varvec{\xi }}})].\)

Given an uncertain network with blocked nodes, it is clear that both the total travel times travelled by an online algorithm and an offline algorithm are uncertain variables, due to the uncertainty of the arc lengths. For the offline algorithms, we define the expected optimal offline algorithm as follows.

Definition 3

(Expected optimal offline algorithm) Given a connected uncertain network \(N=(V,A,{{\varvec{\xi }}})\) and a sequence of blocked nodes I, let \(T_\mathrm{OPT}(I)\) and \(T_\mathrm{OFF}(I)\) be the total travel times from O to D in the network N with blocked nodes I along the routes planned by the offline algorithms OPT and OFF, respectively. Then the algorithm OPT is called an expected optimal offline algorithm if:

$$\begin{aligned} E\left[ T_{\mathrm {OPT}}(I)\right] \le E\left[ T_{\mathrm {OFF}}(I)\right] , \end{aligned}$$
(4)

holds for any offline algorithm OFF, where \(E[T_\mathrm{OPT}(I)]\) and \(E[T_\mathrm{OPT}(I)]\) are the expected values of the travel times experienced by the algorithms OPT and OFF, respectively. \(E[T_\mathrm{OPT}(I)]\) is called the expected optimal offline solution.

Concerning the expected optimal offline algorithm for the uncertain SPP, it is easy to get the following conclusion.

Theorem 1

Given a connected uncertain network \(N=(V,A,{{\varvec{\xi }}})\) with a sequence of blocked nodes I , let \(N'\) denote the new network obtained by removing the blocked nodes in the sequence I and their directly connected arcs from N . The expected optimal offline algorithm for finding a shortest path from O to D in the network N with I is to take the expected shortest path between O and D in the network \(N'.\)

Proof

Since the offline algorithms know all the blocked nodes when they schedule the routes, the offline uncertain SPP on the network N with blocked nodes I is actually to find a shortest path in the network \(N'.\) Therefore, it is obvious that the expected optimal offline algorithm is to take the expected shortest path of the new network \(N'\), in which the blocked nodes and unavailable arcs are removed, because its expected travel time does not exceed any other paths. \(\square\)

4.2 Expected competitive ratio

Following from the concept of expected optimal offline algorithm, the performance of an online algorithm for the OURC problem can be evaluated by comparing the expected value of the total travel time experienced by this algorithm with the expected optimal offline solution. Consequently, the notion of expected competitive ratio is proposed as follows.

Definition 4

(Expected competitive ratio) Let I be an input sequence of blocked nodes in the uncertain network \(N=(V,A,{{\varvec{\xi }}})\), and \(T_\mathrm{ON}(I)\) be the total travel times from O to D in the network N with blocked nodes I along the route planned by an online uncertain algorithm ON. The algorithm ON is called an expected competitive algorithm if there exist deterministic constants \(\alpha\) (\(\alpha \ge 1\)) and \(\beta\) such that:

$$\begin{aligned} E\left[ T_{\mathrm {ON}}(I)\right] \le \alpha \cdot E\left[ T_{\mathrm {OPT}}(I)\right] +\beta , \end{aligned}$$
(5)

holds for any possible input sequences I, where \(E[T_{\mathrm {ON}}(I)]\) is the expected value of the travel time experienced by the algorithms ON, and \(E[T_{\mathrm {OPT}}(I)]\) is the expected optimal offline solution. The constant \(\alpha\) is called the expected competitive ratio.

Concerning the expected competitive ratio of an online algorithm for the OURC problem, we have the following theorem.

Theorem 2

(Equivalent counterpart of expected competitive algorithm) Given a connected uncertain network\(N=(V,A,{{\varvec{\xi }}})\)with blocked nodes, an online algorithm ON is an\(\alpha\)-expected competitive algorithm for the online uncertain route choice problem on the networkN, if and only if the route travelled by the algorithm ON is an\(\alpha\)-competitive solution for the traditional online shortest path problem on a deterministic network\(\overline{N}=(V,A,E[{{\varvec{\xi }}}])\), where the deterministic arc length vector\(E[{{\varvec{\xi }}}]\)is:

$$\begin{aligned} E[{{\varvec{\xi }}}]=\left( E[\xi _1], E[\xi _2], \ldots , E[\xi _m]\right) . \end{aligned}$$
(6)

Proof

Let \(N'\) and \(\overline{N}'\) denote the networks obtained by removing the blocked nodes and unavailable arcs from N and \(\overline{N}\), respectively. It is clear that \(N'\) and \(\overline{N}'\) have the same node set and arc set, and the arc length vector of \(\overline{N}'\) is the expected value of the uncertain arc length vector of \(N'.\) According to Definition 3, the expected optimal offline solution to the uncertain SPP on the network N with blocked nodes is to take the expected shortest path of the network \(N'\), which is denoted as \(P^0.\) Then \(E[L(P^0)]\le E[L(P)]\) holds for any path P. Since the arc lengths \(\xi _i\), \(i=1,2,\ldots ,m\), are independent uncertain variables, following from the linearity of expected value operator for independent uncertain variables (Liu 2010a), we have:

$$\begin{aligned} E[L(P^0)]=E\left[ \sum ^{}_{e_i\in P^0}\xi _i\right] =\sum _{e_i\in P^0}E[\xi _i]. \end{aligned}$$
(7)

Similarly,

$$\begin{aligned} E[L(P)]=\sum _{e_j\in P}E[\xi _j]. \end{aligned}$$
(8)

Therefore, \(E[L(P^0)]\le E[L(P)]\) holds if and only if \(\sum _{e_i\in P^0}E[\xi _i]\le \sum _{e_j\in P}E[\xi _j]\) is true, which implies that \(P^0\) is the expected shortest path of the network \(N'\) if and only if \(P^0\) is the shortest path of the deterministic network \(\overline{N}'.\) In other words, the expected optimal offline solution to the uncertain SPP on the network N with blocked nodes is same with the optimal offline solution to the problem on the determinist network \(\overline{N}.\)

Let \(T_\mathrm{ON}(I)\) and \(T_\mathrm{OPT}(I)\) denote the total travel times from O to D in the network N with blocked nodes I along the route planned by an online uncertain algorithm ON and the expected optimal offline algorithm OPT, respectively. Then we have \(E[T_\mathrm{OPT}(I)]=E[L(P^0)]=\sum _{a_i\in P^0}E[\xi _i].\) Denote by R the route travelled by an online uncertain algorithm ON from O to D. Note that R may contain some repeated arcs, since the online traveler should continually adjust its route while reaching a blocked node. Without loss of generality, we can represent R by listing the arcs being successively travelled as a sequence \(R=\{a_{R1},a_{R2},\ldots ,a_{R\lambda },\}\), where \(\lambda\) is the count of its travelled arcs. Correspondingly, the arc lengths are \(\xi _{R1},\xi _{R2},\ldots ,\xi _{R\lambda }.\) Similarly, according to the linearity of expected value operator for independent uncertain variables (Liu 2010a), we have

$$\begin{aligned} \begin{array}{l} \ E\left[ T_{\mathrm {ON}}(I)\right] \le \alpha \cdot E\left[ T_{\mathrm {OPT}}(I)\right] +\beta \\ \quad \Leftrightarrow E\left[ \sum _{1\le i\le \lambda }\xi _{Ri}\right] \le \alpha \cdot E\left[ \sum _{e_i\in P^0}\xi _i\right] +\beta \\ \quad \Leftrightarrow \sum _{1\le i\le \lambda }E\left[ \xi _{Ri}\right] \le \alpha \cdot \sum ^{}_{e_i\in P^0}E[\xi _i]+\beta , \end{array} \end{aligned}$$
(9)

where \(\sum _{1\le i\le \lambda }E[\xi _{Ri}]\) is the total travel time of the route R from O to D in the deterministic network \(\overline{N}\) playing against the blocked nodes I, and \(\sum ^{}_{e_i\in P^0}E[\xi _i]\) is the optimal offline solution to the problem on \(\overline{N}\) with I.

According to Definition 1, the last inequality in (9) implies that the route R is an \(\alpha\)-competitive solution for online SPP on the network \(\overline{N}=(V,A,E[{{\varvec{\xi }}}]).\) The theorem is proved. \(\square\)

So far we have proposed an uncertain competitive analysis framework to analyze the OURC problem, in which the performance of an online algorithm is evaluated by the expected competitive ratio. It is shown that the competitive analysis for the OURC problem which involves uncertain variables can be handled in the framework of traditional online SPP via its equivalent counterpart on a deterministic network.

In order to develop effective online algorithms for the OURC problem, two typical strategies (namely, reset strategy and greedy strategy) and their performances in the sense of competitive analysis are discussed following from the proposed uncertain competitive analysis framework in the following sections, respectively.

5 Reset strategy based online algorithm

Firstly, we adopt the reset strategy to address the problem. Roughly speaking, the reset strategy always chooses the expected shortest path from the origin to the destination with the known information about the blocked nodes. Whenever a blocked node is met, it goes back to the origin and then travels along the new expected shortest path. In other words, it resets the problem and starts a new cycle whenever new information about the blocked nodes is learned.

Formally, the reset strategy based online algorithm for the OURC problem is presented as follows.


Algorithm RS: Reset strategy based online algorithm

For the online uncertain route choice problem on a given uncertain network \(N=(V,A,{{\varvec{\xi }}})\) with blocked nodes, the RS algorithm travels from the origin O to the destination D as follows.

  1. Step 1.

    Calculate \(E[\xi _i]\), \(i = 1, 2, \ldots , m\), respectively, and then obtain a corresponding deterministic network \(\overline{N}=(V,A,E[{{\varvec{\xi }}}]).\)

  2. Step 2.

    Use the Dijkstra algorithm to find the shortest path from O to D in the network \(\overline{N}\), which is also the expected shortest path from O to D in the network N, and then travels along this path until a blocked node is found on its adjacent node. Denote the current location by H.

  3. Step 3.

    Go back to the origin O from H along the path which has been travelled when going from O to H.

  4. Step 4.

    Remove the blocked node and its directly connected arcs from the network \(\overline{N}.\)

  5. Step 5.

    Repeat Steps 2, 3, and 4 until the destination D is arrived.

The uncertain network shown in Fig. 2 is taken for example to illustrate the proposed algorithm. It consists of 13 nodes and 23 arcs. The grey nodes f, g and h are blocked nodes and thus cannot be passed. The unavailable arcs, which are directly connected to the blocked nodes, are denoted by dashed lines. However, the information about blocked nodes is not known by the online traveler. The couples (x, y) and triplets (x, y, z) labeled on the arcs denote that the corresponding arc lengths are uncertain variables with linear distributions \({\mathcal L} (x, y)\) and zigzag distributions \({\mathcal Z}(x, y, z)\) (Liu 2010a), respectively. Note that the expected value of a linear uncertain variable \(\xi \sim {\mathcal L} (a,b)\) can be calculated as

$$\begin{aligned} E[\xi ] =\frac{a+b}{2}, \end{aligned}$$
(10)

while the zigzag uncertain variable \(\xi \sim {\mathcal Z}(a,b,c)\) has an expected value

$$\begin{aligned} E[\xi ] =\frac{a+2b+c}{4}. \end{aligned}$$
(11)
Fig. 2
figure 2

An uncertain network \(N=(V,A,{{\varvec{\xi }}})\)

Full size image

The algorithm RS addresses the OURC problem on this network as follows.

Firstly, according to (10) and (11), a corresponding deterministic network \(\overline{N}=(V,A,E[{{\varvec{\xi }}}])\) can be obtained as shown in Fig. 3. The shortest path from O to D in the network \(\overline{N}\) is \(O\rightarrow d\rightarrow f\rightarrow g\rightarrow D\), which is also the expected shortest path from O to D in the network N.

Fig. 3
figure 3

The corresponding deterministic network \(\overline{N}=(V,A,E[{{\varvec{\xi }}}])\)

Full size image

Then, the online traveler travels along this path from O to D. However, after he reaches the node d, f is found blocked and thus the formerly planned path is not passable. According to the reset strategy, he goes back to the origin O and recomputes the shortest path from O to D in the network \(\overline{N}\) on condition that the blocked node f and its directly connected arcs have been removed. The new shortest path is \(O\rightarrow a\rightarrow g\rightarrow D.\) Then he travels along this new path until a blocked node is found again. These steps are repeated until the destination D is finally arrived.

As a result, the route travelled by the online traveler from O to D according to the algorithm RS is \(O\rightarrow d\rightarrow O\rightarrow a\rightarrow O \rightarrow e\rightarrow i\rightarrow j\rightarrow k\rightarrow D.\) The total travel time of this route on the network \(\overline{N}\) is \(5+5+8.25+8.25+5+4+5+5+5=50.5,\) which is also the expected value of the total travel time of this route on the uncertain network N.

On the other hand, it is easy to get the expected optimal offline solution of the uncertain SPP on the network N, since the offline traveler knows the information about the blocked nodes while making his decision. As mentioned in the proof of Theorem 2, the expected optimal offline solution is same with the optimal offline solution to the problem on the corresponding deterministic network \(\overline{N}.\) In this example, the expected optimal offline solution is \(O \rightarrow e\rightarrow i\rightarrow j\rightarrow k\rightarrow D\) with expected total travel time \(5+4+5+5+5=24.\) It can be seen that the total travel time experienced by the online traveler according to the algorithm RS is \(\frac{50.5}{24}\approx 2.1\) times of the expected optimal offline solution.

Next, we analyze the performance of the online algorithm RS theoretically, following from the uncertain competitive analysis framework. For the expected competitive ratio of the algorithm RS, we have the following theorem.

Theorem 3

For the online uncertain route choice problem on a given uncertain network\(N=(V,A,{{\varvec{\xi }}})\)withk (\(k\ge 1\)) blocked nodes, the online algorithm RS is an expected competitive algorithm with expected competitive ratio\(2k-1.\)

Proof

For convenience, we denote the sequence of the j (\(0\le j\le k\)) blocked nodes found by the online traveler as \(I_j\), i.e., \(I_j=\{c_1,c_2,\ldots ,c_j\}.\) Let \(T_\mathrm{RS}(I_j)\) and \(T_\mathrm{OPT}(I_j)\) be the total travel times from O to D along the routes planned by the algorithm RS and the expected optimal offline algorithm, respectively, on condition that the observed blocked node sequence is \(I_j.\) Note that there are k blocked nodes in total, but not all of them may affect the traveler’s decision. Then if there is not any blocked node found on the online traveler’s route (\(j=0\)), the expected shortest path is the solution of the algorithm RS, which is also the expected optimal offline solution. That is:

$$\begin{aligned} E\left[ T_\mathrm{RS}(I_0)\right] =E\left[ T_\mathrm{OPT}(I_0)\right] =\overline{L}^0_{(O,D)}\ , \end{aligned}$$
(12)

where \(\overline{L}^0_{(O,D)}\) is the expected shortest travel time between O and D in the network N without blocked node.

When the first blocked node comes, without loss of generality, assume it is found at the node \(H_1\) (the pervious node of the blocked one). According to the algorithm RS, for this case the online traveler needs to go back the origin O from \(H_1\), and then chooses another expected shortest path from O to D in the new network in which the blocked node and its directly connected arcs are removed away. It is clear that the online solution \(T_\mathrm{RS}(I_1)\) for this case with only one observed blocked node satisfies the following inequality (13), since \(\overline{L}^0_{(O,H_1)}=\overline{L}^0_{(H_1,O)}\le \overline{L}^0_{(O,D)}.\)

$$\begin{aligned} \begin{array}{ll} E\left[ T_\mathrm{RS}(I_1)\right] &{}=\overline{L}^0_{(O,H_1)}+\overline{L}^0_{(H_1,O)}+E\left[ T_\mathrm{OPT}(I_1)\right] \\ &{}\le \overline{L}^0_{(O,D)}+\overline{L}^0_{(D,O)}+E\left[ T_\mathrm{OPT}(I_1)\right] \\ &{}= E\left[ T_\mathrm{OPT}(I_1)\right] +2\overline{L}^0_{(O,D)}. \end{array} \end{aligned}$$
(13)

If the second blocked node comes, assume that it is found at the node \(H_2.\) Denote by \(\overline{L}(O,H_2)\) the expected travel time between O and \(H_2\) along the path planned in the last step. \(\overline{L}(O,H_2) = \overline{L}(H_2,O)\le E[T_\mathrm{OPT}(I_1)]\) holds. Then we have

$$\begin{aligned} E\left[ T_\mathrm{RS}(I_2)\right]&=\overline{L}^0_{(O,H_1)}+\overline{L}^0_{(H_1,O)}+\overline{L}(O,H_2)\\&\quad + \overline{L}(H_2,O)+E\left[ T_\mathrm{OPT}(I_2)\right] \\&\le E\left[ T_\mathrm{OPT}(I_2)\right] +2E\left[ T_\mathrm{OPT}(I_1)\right] +2\overline{L}^0_{(O,D)}. \end{aligned}$$
(14)

Similarly, for \(2\le j\le k\), we have

$$\begin{aligned} \begin{array}{l} E\left[ T_\mathrm{RS}(I_j)\right] \\ \quad \le E\left[ T_\mathrm{OPT}(I_j)\right] +2\sum _{i=1}^{j-1} E\left[ T_\mathrm{OPT}(I_i)\right] +2\overline{L}^0_{(O,D)}. \end{array} \end{aligned}$$
(15)

According to the algorithm RS, every time the traveler gets back to the origin, the current expected shortest path (blocked nodes and unavailable arcs are removed) is chosen. Therefore, for any \(i\le j\), \(E[T_\mathrm{OPT}(I_i)]\le E[T_\mathrm{OPT}(I_j)]\) holds. By substituting it into (15), we have

$$\begin{aligned} \begin{array}{rl} E\left[ T_\mathrm{RS}(I_j)\right] &{}\le E\left[ T_\mathrm{OPT}(I_j)\right] +2(j-1) E\left[ T_\mathrm{OPT}(I_j)\right] \\ &{}\quad +2\overline{L}^0_{(O,D)}\\ &{}=(2j-1)E\left[ T_\mathrm{OPT}(I_j)\right] +2\overline{L}^0_{(O,D)}. \end{array} \end{aligned}$$
(16)

Since there are k blocked nodes in total, it is easy to verify that

$$\begin{aligned} E\left[ T_\mathrm{RS}(I_j)\right] \le (2k-1)E\left[ T_\mathrm{OPT}(I_j)\right] +2\overline{L}^0_{(O,D)} \end{aligned}$$
(17)

holds for any possible sequence \(I_j\), \(0\le j\le k\), where \(2\overline{L}^0_{(O,D)}\) is a constant with respect to the network N.

According to Definition 4, the algorithm RS is an expected competitive algorithm and the expected competitive ratio is \(2k-1.\)\(\square\)

6 Greedy strategy based online algorithm

For the OURC problem, since the online traveler does not know the information about the blocked nodes until their adjacent nodes have been reached, it is natural to adopt greedy strategy to develop the online algorithm. Roughly speaking, the greedy strategy always chooses the expected shortest path from the current location to the destination based on the known information. Whenever a blocked node is found, it recomputes the new expected shortest path from the current location to the destination until the destination is finally arrived.

Formally, the greedy strategy based online algorithm for the OURC problem is presented as follows.


Algorithm GS: Greedy strategy based online algorithm

For the online uncertain route choice problem on a given uncertain network \(N=(V,A,{{\varvec{\xi }}})\) with blocked nodes, the GS algorithm travels from the origin O to the destination D as follows.

  1. Step 1.

    Calculate \(E[\xi _i]\), \(i = 1, 2, \ldots , m\), respectively, and then obtain a corresponding deterministic network \(\overline{N}=(V,A,E[{{\varvec{\xi }}}]).\)

  2. Step 2.

    Use the Dijkstra algorithm to find the shortest path from O to D in the network \(\overline{N}\), which is also the expected shortest path from O to D in the network N, and then travels along this path until a blocked node is found on its adjacent node. Denote the current location by H.

  3. Step 3.

    Remove the blocked node and its directly connected arcs from the networks N and \(\overline{N}.\)

  4. Step 4.

    Use the Dijkstra algorithm to find the shortest path from H to D in the network \(\overline{N}\) in which found blocked nodes and unavailable arcs have been removed, which is also the expected shortest path from H to D in the new network N, and then travels along this new path until another blocked node is found. Denote the current location by H.

  5. Step 5.

    Repeat Steps 3 and 4 until the destination D is arrived.

Similarly, we take the uncertain network shown in Fig. 2 for instance to illustrate the proposed algorithm GS. Firstly, the online traveler travels along the expected shortest path \(O\rightarrow d\rightarrow f\rightarrow g\rightarrow D.\) After he reaches the node d, f is found blocked. Then according to the greedy strategy, he recomputes the shortest path from d to D in the network \(\overline{N}\) on condition that the blocked node f and its directly connected arcs have been removed. It is \(d\rightarrow a\rightarrow g\rightarrow D.\) Next, he travels along this new path. After he reaches the node a, g is found blocked again. Then he recomputes the shortest path from a to D on condition that all the formerly found blocked nodes and unavailable arcs have been removed, and travels along this new path until another blocked node is found. These steps are repeated until the destination D is finally arrived.

As a result, the route travelled by the online traveler from O to D according to the algorithm GS is \(O\rightarrow d\rightarrow a\rightarrow b\rightarrow c\rightarrow b\rightarrow a\rightarrow d\rightarrow e\rightarrow i\rightarrow j\rightarrow k\rightarrow D.\) The expected value of the total travel time of this route on the uncertain network N is \(5+5+5+5+5+5+5+5+4+5+5+5=59.\) It is \(\frac{59}{24}\approx 2.5\) times of the expected optimal offline solution.

Concerning the expected competitive ratio of the algorithm GS, we have the following theorem.

Theorem 4

For the online uncertain route choice problem on a given uncertain network\(N=(V,A,{{\varvec{\xi }}})\)withk (\(k\ge 1\)) blocked nodes, the online algorithm GS is an expected competitive algorithm with expected competitive ratio\(2^{k+1}-1.\)

Proof

Similarly, we denote the sequence of the j (\(0\le j\le k\)) blocked nodes found by the online traveler as \(I_j\), i.e., \(I_j=\{c_1,c_2,\ldots ,c_j\}.\) Let \(T_\mathrm{GS}(I_j)\) and \(T_\mathrm{OPT}(I_j)\) be the total travel times from O to D along the routes planned by the algorithm GS and the expected optimal offline algorithm, respectively, on condition that the found blocked node sequence is \(I_j.\) Then if there is not any blocked node found on the online traveler’s route (\(j=0\)), the expected shortest path is the solution of the algorithm GS, which is also the expected optimal offline solution. That is

$$\begin{aligned} E\left[ T_\mathrm{GS}(I_0)\right] =E\left[ T_\mathrm{OPT}(I_0)\right] =\overline{L}^0_{(O,D)}, \end{aligned}$$
(18)

where \(\overline{L}^0_{(O,D)}\) is the expected shortest travel time between O and D in the network N without blocked node.

When the first blocked node comes, without loss of generality, assume that it is found at the node \(H_1.\) According to the algorithm GS, for this case the online traveler need to recompute the expected shortest path from \(H_1\) to D in the new network in which the blocked node and its directly connected arcs are removed away. Denote by \(\overline{L}(H_1, D)\) the expected travel time between \(H_1\) and D along the new planned path. It is clear that \(\overline{L}_{(H_1,D)}\le \overline{L}^0_{(H_1,O)}+ E[T_\mathrm{OPT}(I_1)]\) holds. Then, there are two cases to be discussed.

  1. 1)

    If there is not any blocked node on the planned path from \(H_1\) to D, then we have

    $$\begin{aligned} \begin{array}{ll} E\left[ T_\mathrm{GS}(I_1)\right] &{}=\overline{L}^0_{(O,H_1)}+\overline{L}_{(H_1,D)}\\ &{}\le \overline{L}^0_{(O,H_1)}+\overline{L}^0_{(H_1,O)}+E\left[ T_\mathrm{OPT}(I_1)\right] \\ &{}\le E\left[ T_\mathrm{OPT}(I_1)\right] +2\overline{L}^0_{(O,D)}. \end{array} \end{aligned}$$
    (19)
  2. 2)

    If another blocked node appears on the planned path from \(H_1\) to D, which is found when the traveler reaches the node \(H_2\), then the algorithm GS recompute the expected shortest path from \(H_2\) to D in the new network in which the blocked node and unavailable arcs are removed again. Then the above steps are repeated. Without loss of generality, it is assumed that there are j blocked nodes found by the online traveler. Denote by \(H_1, H_2,\ldots , H_j\) the nodes where the j blocked nodes are found (adjacent nodes to the observed blocked nodes). Following from the above analysis, we have

$$\begin{aligned} \begin{array}{ll} E\left[ T_\mathrm{GS}(I_j)\right] &{}=\overline{L}^0_{(O,H_1)}+\overline{L}_{(H_1,H_2)}+\cdots \\ &{}\quad +\overline{L}(H_{j-1},H_j)+\overline{L}(H_j,D). \end{array} \end{aligned}$$
(20)

For the planned path from \(H_j\) to D, we have

$$\begin{aligned} \begin{array}{rl} \overline{L}_{(H_j,D)}&{}\le \overline{L}^0_{(O,H_1)}+\overline{L}_{(H_1,H_2)}+\cdots \\ &{}\quad +\overline{L}(H_{j-1},H_j)+E\left[ T_\mathrm{OPT}(I_j)\right] . \end{array} \end{aligned}$$
(21)

By substituting (21) into (20), we have

$$\begin{aligned} \begin{array}{ll} E\left[ T_\mathrm{GS}(I_j)\right] &{}\le 2\left( \overline{L}^0_{(O,H_1)}+\overline{L}_{(H_1,H_2)}+\cdots \right. \\ &{}\quad +\overline{L}(H_{j-1},H_j)\Big )+E\left[ T_\mathrm{OPT}(I_j)\right] \\ &{}\le 2\left( \overline{L}^0_{(O,H_1)}+\cdots +\overline{L}(H_{j-2},H_{j-1})\right. \\ &{}\quad +\overline{L}(H_{j-1},D)\Big )+E\left[ T_\mathrm{OPT}(I_j)\right] . \end{array} \end{aligned}$$
(22)

Similarly, for the planned path from \(H_i\) (\(1< i<j\)) to D, we also have

$$\begin{aligned} \begin{array}{rl} \overline{L}_{(H_i,D)}&{}\le \overline{L}^0_{(O,H_1)}+\overline{L}_{(H_1,H_2)}+\cdots \\ &{}\quad +\overline{L}(H_{i-1},H_i)+E\left[ T_\mathrm{OPT}(I_i)\right] . \end{array} \end{aligned}$$
(23)

By substituting (23) into (22) and repeating this step, we can get

$$\begin{aligned} \begin{array}{ll} E\left[ T_\mathrm{GS}(I_j)\right] \!&{}\le 2\left[ 2\left( \overline{L}^0_{(O,H_1)}+\sum _{i=2}^{j-1}\overline{L}(H_{i-1},H_i)\right) \right. \\ &{}\quad +E\left[ T_\mathrm{OPT}(I_{j-1})\right] \Big ]+E\left[ T_\mathrm{OPT}(I_j)\right] \\ &{}\le 2\left[ 2\left( \overline{L}^0_{(O,H_1)}+\sum _{i=2}^{j-1}\overline{L}(H_{i-1},H_i)\right) \right. \\ &{}\quad +E\left[ T_\mathrm{OPT}(I_j)\right] \Big ]+E\left[ T_\mathrm{OPT}(I_j)\right] \\ &{}\quad \cdots \\ &{}\le E\left[ T_\mathrm{OPT}(I_j)\right] \cdot \sum _{i=0}^j2^i\\ &{}\le (2^{j+1}-1)\cdot E\left[ T_\mathrm{OPT}(I_j)\right] \\ \end{array} \end{aligned}$$
(24)

Since there are k blocked nodes in total,

$$\begin{aligned} E\left[ T_\mathrm{GS}(I_j)\right] \le (2^{k+1}-1)E\left[ T_\mathrm{OPT}(I_j)\right] \end{aligned}$$
(25)

holds for any possible sequence \(I_j\), \(0\le j\le k.\)

According to Definition 4, the algorithm GS is an expected competitive algorithm and the expected competitive ratio is \({2^{k+1}-1}. \quad\quad\quad\quad \square\)

Comparing the expected competitive ratios of the algorithms RS and GS, it can be seen that the reset strategy performs better than the greedy strategy in the sense of competitive analysis. Note that the expected competitive ratio defined in the proposed uncertain competitive analysis framework is a worst-case measure with respect to the possible blocked nodes, and thus the performances measured by this ratio tend to be pessimistic and conservative. However, it provides very robust statements about the performances of the online strategies against all possible scenarios, so it can be used as an effective or at least alternative measure to estimate the route choice decision. In this paper, it is assumed that we know nothing about the future possible blocked nodes, and these nondeterministic factors are coped with by utilizing worst-case based competitive analysis. If more information about the possible blocked nodes can be acquired while making the route choice decision, such as the probabilities of the nodes to be blocked, the performances of the online strategies can be much improved. This would be our future work.

7 Conclusion

Since the travel times in a traffic network are not always deterministic in real applications, the online route choice problem was considered on an uncertain network where the arc lengths (representing travel times) were assumed to be uncertain variables. Due to the uncertainty of the travel time associated with the route chosen by an online algorithm, the traditional competitive analysis approach cannot be utilized directly to analyze the online routing problems involving uncertain variables. Therefore, an uncertain competitive analysis framework was proposed following from the uncertainty theory founded by Liu (2007, 2010a), in which the performance of an online uncertain algorithm was evaluated by its expected travel time against that of the optimal offline algorithm. Following from this framework, it was shown that the competitive analysis for the OURC problem could be handled in the framework of traditional online SPP via its equivalent counterpart on the corresponding deterministic network. Furthermore, the typical reset strategy and greedy strategy for route choice decision-making were analyzed as well. The proposed analysis approach is also applicable for decision-makers to design and analyze their real-time response strategies for future uncertain events in other decision-making activities.