New Variations of the Online k-Canadian Traveler Problem: Uncertain Costs at Known Locations

Abstract

In this chapter, we study new variations of the online k-Canadian Traveler Problem (k-CTP) in which there is an input graph with a given source node O and a destination node D. For a specified set consisting of k edges, the edge costs are unknown (we call these uncertain edges). Costs of the remaining edges are known and given. The objective is to find an online strategy such that the traveling agent finds a route from O to D with minimum total travel cost. The agent learns the cost of an uncertain edge, when she arrives at one of its end-nodes and decides on her travel path based on the discovered cost. We call this problem the online k-Canadian Traveler Problem with uncertain edges. We analyze both the single-agent and the multi-agent versions of the problem. We propose a tight lower bound on the competitive ratio of deterministic online strategies together with an optimal online strategy for the single-agent version. We consider the multi-agent version with two different objectives. We suggest lower bounds on the competitive ratio of deterministic online strategies to these two problems.

1. Introduction

The online k-Canadian Traveler Problem (k-CTP) is a well-known navigation problem within the field of combinatorial optimization. In the online k-CTP, the objective is to reach a destination in a network within minimum travel time under uncertainty of some information. Uncertain information is revealed, while one or more travelers (agents) discover the information during their travels. In the k-CTP and its variants studied in the literature, uncertainty is on the locations of blocked edges in the input graph. That is, it is known that there are at most k blocked edges, but their locations are not known. In this study, we consider new variations of the k-CTP where a known set of edges have unknown (uncertain) travel times (costs). To the best of our knowledge, this variant of the k-CTP with given locations of edges that have unknown traveling costs has not been studied yet in the literature.

Uncertainty in travel times arises in various situations, such as following a disaster or in daily urban traffic systems. After a disaster, uncertainty in travel times arises due to both damage on road segments and traffic congestion on some parts of the road network. We typically know which roads are likely to have damage and to be congested, but the actual travel times can be estimated more accurately when we observe the situation right on the spot. Regarding urban traffic systems, problematic road segments can be detected beforehand since in most current traffic management systems, data indicating locations with high accident frequency are available, but it is difficult to predict the time of occurrence or the intensity of the accident accurately. Also, we usually know where there is a high likelihood of heavy traffic, but travel times show variability. Moreover, nowadays navigation applications indicate which locations have heavy traffic, but the travel times are still not known with certainty, and the situation evolves dynamically as we reach the locations themselves.

In many real-world emergency operations, including response to disasters and daily medical or fire emergencies, operations managers must give dispatching decisions urgently under uncertain travel times. Therefore, it is useful to develop online strategies beforehand. For example, for effective disaster response, these strategies can be adopted before the disaster so that they can be implemented in the shortest time after the disaster. Likewise, when traveling in traffic, in order to reach the desired destination in the shortest time, we need a strategy defined on a network which answers the following questions: when to arrive at the end-node of an uncertain edge to learn its travel cost and when to avoid visiting it; when the travel time of an uncertain edge is learned, whether to take it or change the travel route; and if there exists a route to the destination without any uncertain edges, whether to take it or not. In this chapter, we focus on both developing effective online strategies that answer these questions and analyzing their performances theoretically to reveal their worst-case behavior. We next define our problem and its variants formally.

1.1 The online k-CTP with uncertain edges

Let $G=\left(V,E,k\right)$ denote an undirected graph with O as the source and D as the destination in which the costs of k edges with given locations in the graph are unknown and a traveling agent can only discover their costs when she reaches an end-node of them. The costs of the remaining edges are known and deterministic. We call the edges with unknown costs uncertain edges and the edges with known costs deterministic edges. The objective is to provide an online strategy such that the traveling agent who is located at O initially receives $G=\left(V,E,k\right)$ and the known costs as input and targets to reach D with minimum total travel cost under uncertainty. Since the problem is a new variation of the k-CTP, we call this problem the single-agent k-CTP with uncertain edges, in short the S-k-CTP-U. We also study the multi-agent version of this problem where there are L agents, who are initially located at O. We assume that the agents have the capability to transmit their location and edge cost information to the other agents in real time. We consider the multi-agent version of the problem with two different objectives, where the traveling agents follow an online strategy to ensure that the time when (1) the first agent and (2) the last agent arrive at D is minimum. We call these problems the M-k-CTP-U-f and the M-k-CTP-U-l, respectively. In real-life applications mentioned before, e.g., disaster response, the objective of the M-k-CTP-U-f is applicable when search-and-rescue teams try to reach a target in the shortest time, whereas the objective of the M-k-CTP-U-l is applicable when a convoy of k vehicles delivers aid to a point of distribution.

1.2 Competitive analysis

The key concept in analyzing an online strategy is to compare a solution produced by the online strategy with the best possible solution under complete information, which is called the offline optimum solution. An offline strategy is to solve the same problem as an online strategy, except that all information about the problem inputs is revealed to an offline strategy from the beginning. An optimal offline strategy is the optimal strategy in the presence of complete input information which produces the offline optimum solution. To analyze the performance of online strategies, competitive ratio has been introduced in [1] and used by many researchers. The competitive ratio is the maximum ratio of the cost of the online strategy to the cost of the offline strategy over all instances of the problem. In our problems, the costs of the uncertain edges are known in the offline counterparts. Hence, the offline problems reduce to the shortest path problem.

Next, we discuss related work in the literature. Then, we state our contributions to the defined problems later on in this section.

1.3 Previous studies

We focus on studies on the k-CTP which are conducted from the online optimization and the competitive analysis perspective, since these are the most related works to our survey. First, we review the literature for the single-agent variants. Next, we discuss the relevant studies on the multi-agent versions.

1.3.1 Single-agent k-CTP and variants

The CTP was defined first in [2]. Papadimitriou and Yannakakis [2] proved that devising an online strategy with a bounded competitive ratio is PSPACE-complete for the CTP. Bar-Noy and Schieber [3] also considered the CTP and its variants. They introduced the k-CTP, where an upper bound k on the number of blocked edges is given as input. They showed that for arbitrary k, the problem of designing an online strategy that guarantees the minimum travel cost is PSPACE-complete.

Westphal [4] considered the k-CTP from the competitive ratio perspective. He showed the lower bounds of $2k+1$ and $k+1$ on the competitive ratio of deterministic and randomized online strategies, respectively. He also presented an optimal deterministic online strategy for the k-CTP which is called the backtrack strategy. Xu et al. [5] also considered the k-CTP and presented two online strategies, the greedy and the comparison strategy, and proved competitive ratios of $2^{k+1}-1$ and $2k+1$ , respectively, for these strategies. Bender and Westphal [6] presented a randomized online strategy for the k-CTP which meets the lower bound of $k+1$ in special cases. Shiri and Salman [7] modified the strategy given in [7] and proposed an optimal randomized online strategy for the k-CTP on O-D edge-disjoint graphs.

1.3.2 Multi-agent k-CTP and variants

A generalization of the k-CTP with multiple agents was first considered by Zhang et al. in [8]. They analyzed the multi-agent k-CTP in two scenarios, with limited and complete communication. They proposed lower bounds of $2⌊\frac{k-1}{L_1}⌋+1$ and $2⌊\frac{k}{L}⌋+1$ on the competitive ratio of deterministic online strategies for the cases with limited and complete communication, respectively. Note that in the proposed lower bounds L denotes the total number of agents and L ₁ denotes the number of agents who benefit from complete communication. They also proposed an optimal deterministic online strategy when there are two agents in the graph. Shiri and Salman [9] also investigated the multi-agent k-CTP. They provided an updated lower bound on the competitive ratio of deterministic online strategies for the case with limited communication. They also presented a deterministic online strategy which is optimal in both cases with complete and limited communication on O-D edge-disjoint graphs. Randomized online strategies for the multi-agent k-CTP are investigated in [10], where lower bounds on the expected competitive ratio together with optimal randomized online strategies on O-D edge-disjoint graphs are proposed for the cases with limited and complete communication.

Xu and Zhang [11] focused on a real-time rescue routing problem from a source node to an emergency spot in the presence of online blockages. They analyzed the problem with the objective to make all the rescuers arrive at the emergency spot with minimum total cost. They studied the problem in two scenarios, without communication and with complete communication. They investigated both of the scenarios on the grid networks and general networks, respectively. They showed that the consideration of both the grid network and the rescuers’ communication can significantly improve the rescue efficiency.

1.4 Our contributions

In the literature, the common unknown information in the k-CTP variants is the locations of the blocked edges in the graph. In fact, in all of the versions of the online k-CTP, all of the edges are equally likely to be blocked, and the agents have to explore the blockages in the graph to identify a route from the source node to the destination node with minimum total travel cost. However, in many real-world instances, assuming that all of the edges are equally likely to be congested or blocked ignores valuable information. In other words, there might exist many edges in the graph in which the agent is assured that they are not blocked before she starts her travel. Hence, considering all of the edges to be blocked with equal chance is not a realistic assumption in some of the real-world applications of the k-CTP.

As discussed at the beginning of this section, it is possible to identify the potential locations of the blocked edges in the graph in many real-world instances, such as in the urban traffic and post-disaster response. We introduce a new variation of the k-CTP with at most k number of uncertain edges with given locations and unknown traveling costs. We call this new problem the online k-Canadian Traveler Problem with uncertain edges. We consider both single-agent and multi-agent versions of this problem. In the multi-agent version of the problem, we analyze the problem with two different objectives, where the agents aim to ensure the first and the last arrival of the agents at D with minimum travel cost, respectively. The main contributions of our study are detailed below:

1. We introduce new variations of the online k-CTP which find applications in real-world problems, namely, the S-k-CTP-U, the M-k-CTP-U-f, and the M-k-CTP-U-l.

2. We provide a tight lower bound on the competitive ratio of deterministic online strategies for the S-k-CTP-U and introduce an optimal deterministic online strategy.

3. We derive lower bounds on the competitive ratio of deterministic online strategies for the M-k-CTP-U-f and the M-k-CTP-U-l.

The rest of this chapter is organized as follows. In Section 2, we describe the assumptions and give preliminaries. In Section 3, we analyze the single-agent version of the problem and provide a tight lower bound and an optimal strategy to this problem. In Section 4, we suggest lower bounds on the competitive ratio for the multi-agent versions of the problem. Finally, we conclude in Section 5.

2. Preliminaries

We consider the single-agent and the multi-agent problems defined in Section 1.1 with the following assumptions [1]:

1. The agent(s) are initially located at O. We call this stage the initial stage of the problem.

2. If any k edges are removed from the graph, there still exists a path between the source and the destination node. This is a standard assumption in the literature.

3. The cost of the uncertain edges can take any value between 0 and M. An uncertain edge with explored cost equal to M would be considered as a blocked edge.

4. Once the cost of an uncertain edge is learned, it remains the same whenever the traveler visits that edge. In other words the cost is not assumed to be time-dependent.

5. We call the time periods in which the cost of a new uncertain edge is identified, stages of the problem. That is, there are k stages in the problem, i.e., stage 1 corresponds to the time period starting at the initial stage and ending at the moment before the cost of the first uncertain edge is learned.

We apply the following symbols and definitions to describe our results. We call the O-D paths which contain uncertain edges uncertain paths and which do not have uncertain edges deterministic paths. Let D_i denote the shortest deterministic path at the ith stage and d_i $\left(i=1,2,\dots ,k\right)$ denote its corresponding cost. If there are more than one shortest deterministic path at the ith stage, one of them can be selected as D_i arbitrarily. Note that at any stage of the problem there exists at least one deterministic O-D path based on Assumption 2.

We define the optimistic cost of the O-D path as the cost of the O-D path after setting the costs of the unvisited uncertain edges on it equal to 0. The optimistic shortest O-D path at the ith stage of the problem is denoted by π_i , which corresponds to the shortest O-D path after setting the costs of the remaining uncertain edges equal to 0. We denote its corresponding cost by p_i $\left(i=1,2,\dots ,k\right)$ . That is, π ₁ is the optimistic shortest O-D path at the initial stage of the problem. We denote the shortest path after the status of all of the uncertain edges is explored by ${\pi }_{k+1}$ , i.e., ${\pi }_{k+1}$ is the offline optimum and $p_{k+1}$ is its corresponding cost.

3. Single-agent k-CTP with uncertain edges

In this section, we analyze the single-agent problem, namely, the S-k-CTP-U. We present a lower bound to this problem and prove its tightness by introducing a simple strategy. To suggest a lower bound on the competitive ratio of deterministic strategies, we need to analyze the performance of all of deterministic strategies on a special instance. Below, we propose our lower bound on the S-k-CTP-U, by analyzing an instance of O-D edge-disjoint graphs. Note that an O-D edge-disjoint graph is an undirected graph G with a given source node O and a destination node D, such that any two distinct O-D paths in G are edge-disjoint, that is, they do not have a common edge.

Theorem 1.1 For the S-k-CTP-U, there is no deterministic online strategy with competitive ratio less than $\mathit{min}\left\{d_1/p_1,2k-1\right\}$ .

Proof. Consider the special graph in Figure 1. For each of deterministic strategies, we consider the instance when the cost of all of the first $k-1$ visited uncertain edges equals M and the cost of the last visited uncertain edge equals 0. Hence, the cost of the offline shortest path equals p ₁. For a strategy, we call this instance the adverse instance. In the special graph in Figure 1, any deterministic strategy corresponds to a permutation which specifies in which order the uncertain paths and D ₁ (not necessarily all of them) are going to be selected. For each of these strategies, consider the adverse instance. We define α as a binary coefficient which equals 1, if the agent takes D ₁, and equals 0, if the agent does not take D ₁ in the strategy. Suppose that the agent has taken i number of uncertain paths before taking D ₁ when α equals 1. In this case, the competitive ratio of deterministic strategies on the special graph shown in Figure 1 can be formulated as $\frac{2i\left(p_1\right)+\alpha \left(d_1\right)+\left(1-\alpha \right)p_1}{p_1}$ ( $i=\mathrm{0,1,2},\dots ,k-1$ ). Note that in the adverse instance, the agent has to incur a cost equal to 2p ₁ in her first $k-1$ trials at the uncertain paths, since she has to come back to O after finding the uncertain edges blocked. However, since the cost of the kth visited uncertain edge equals 0, the agent incurs p ₁ in her kth trial at the uncertain paths and reaches D. Now, we present our proof by considering two cases.

• Case 1. $\frac{d_1}{p_1}\le 2k-1$ . We consider this case for $\alpha =0$ and $\alpha =1$ separately.

◦ $\alpha =1$ . In this case the competitive ratio of the corresponding strategies can be formulated as $\frac{2i\left(p_1\right)+d_1}{p_1}$ ( $i=0,1,\dots ,k-1$ ). The minimum competitive ratio equals $\frac{d_1}{p_1}$ , when $i=0$ , which matches the proposed lower bound of the problem.

◦ $\alpha =0$ . In this case the minimum competitive ratio of the corresponding strategies equals $2k-1$ , which is greater than or equal to the lower bound of the problem.

•Case 2. $\frac{d_1}{p_1}>2k-1$ . We also consider this case for $\alpha =0$ and $\alpha =1$ separately.

◦ $\alpha =1$ . In this case the competitive ratio of the corresponding strategies can be formulated as $\frac{2i\left(p_1\right)+d_1}{p_1}$ ( $i=0,1,\dots ,k-1$ ). The minimum competitive ratio equals $\frac{d_1}{p_1}$ , when $i=0$ , which is greater than the proposed lower bound of the problem.

◦ $\alpha =0$ . In this case the minimum competitive ratio of the corresponding strategies equals $2k-1$ , which matches the lower bound of the problem.

Figure 1.

A special graph.

Since we proved that the competitive ratios of all of the deterministic strategies for this special instance are greater than or equal to $\mathit{min}\left\{d_1/p_1,2k-1\right\}$ , the proof is complete.

Now, we introduce a new deterministic strategy which meets the presented lower bound. We call this strategy the pessimistic strategy since the agent avoids to explore more than one uncertain edge at each iteration.

3.1 Pessimistic strategy

• Initialization. Put $i=0$ , where i denotes the iteration number. At each iteration the agent starts her travel from O and explores the cost of one uncertain edge or will reach D without visiting any unvisited uncertain edge. If the agent reaches D, then the strategy ends. Otherwise, she backtracks to O or reaches D without visiting any other unvisited uncertain edge. In the latter case when the agent reaches D, the strategy ends. Note that each iteration corresponds to one of the stages of the problem, because at each iteration the cost of one of the uncertain edges is learned. That is, the first iteration corresponds to stage 1 of the problem. Also note that p_i is nondecreasing in i, where p_i is the cost of the optimistic shortest O-D path at the beginning of the ith iteration. Let c_i denote the cost of the uncertain edge which is learned at the ith iteration. Note that $p_{i+1}$ is computable immediately after the agent observes c_i . Let S denote the set of the uncertain edges in the graph.

• Step 1. Compute d ₁, p ₁, and $\mathit{min}\left\{d_1/p_1,2k-1\right\}$ . If the minimum is $d_1/p_1$ , take D ₁, otherwise go to step 2.

• Step 2. If ( $i=k-1$ ), then go to step 3; otherwise, put $i=i+1$ and find π_i . If it does not contain uncertain edges, the agent takes it to reach D. Otherwise, take π_i to reach the ith visited uncertain edge, observe c_i , set the value of the newly visited uncertain edge equal to c_i , and remove it from S. That is, it is not considered as an uncertain edge hereafter. Next, check the following conditions.

• Condition 1. Check if

$$\frac{2\left({\sum }_{j=1}^{i-1}{p}_j\right)+p_i+c_i}{p_{i+1}}<2k-1$$ E1

and there exists no uncertain edge in the selected path, and proceed to reach D. Otherwise, check condition 2.

• Condition 2. Note that immediately after the agent observes c_i , $D_{i+1}$ and $d_{i+1}$ are computable. Check if

$$\frac{2\left({\sum }_{i=1}^i{p}_i\right)+d_{i+1}}{p_{i+1}}<2k-1,$$ E2

and then go back to O and take $D_{i+1}$ . Otherwise, return to O and go to the beginning of step 2.

• Step 3. Take π_k and observe c_k . Then compare

$$A=\frac{2\left({\sum }_{i=1}^k{p}_i\right)+p_{k+1}}{p_{k+1}}$$ E3

and

$$B=\frac{2\left({\sum }_{i=1}^{k-1}{p}_i\right)+p_k+c_k}{p_{k+1}}.$$ E4

If $A<B$ return to O and take the shortest path $\left({\pi }_{k+1}\right)$ ; otherwise, travel through the uncertain edge in the kth uncertain path and reach D.

Below we show that our strategy is optimal by using the inequalities which are presented in different steps of the pessimistic strategy.

Theorem 1.2 The pessimistic strategy is optimal for the S-k-CTP-U.

Proof. Note that if the strategy ends in either step 1 or 2, the competitive ratio would be less than or equal to the lower bound. Hence, we just need to analyze the cases where the strategy ends in step 3. Note that the competitive ratio of the strategy would not exceed $\mathit{min}\left\{A,B\right\}$ in step 3. Thus, it is enough to show that either A or B does not exceed the proposed lower bound of the problem, if the strategy ends in step 3. We consider three different scenarios for ${\pi }_{k+1}$ to show the optimality of the pessimistic strategy, if the strategy ends in step 3.

• Scenario 1. ${\pi }_{k+1}$ contains the uncertain edge which is visited in the kth iteration. In this case, we show that B meets the proposed lower bound of the problem. Since both ${\pi }_{k+1}$ and π_k (i.e., ${\pi }_{k+1}\ge {\pi }_k$ ) contain the kth visited uncertain edge, $p_k+c_k$ equals $p_{k+1}$ . Hence we can replace $p_k+c_k$ by $p_{k+1}$ in the numerator of B. We can also replace p_i values for $\left(i=1,2,\dots ,k-1\right)$ by $p_{k+1}$ in the numerator of B, since p_i is nondecreasing in i. In this case, B would be at most $2k-1$ which equals the lower bound of the problem.

Here, we note that ${\pi }_{k+1}$ does not contain the kth visited uncertain edge in the next two scenarios.

• Scenario 2. ${\pi }_{k+1}$ contains the uncertain edge which is visited in the $\left(k-1\right)$ th iteration. Note that $k\ge 2$ in this scenario, since ${\pi }_{k+1}$ does not contain the kth visited uncertain edge and contains the $\left(k-1\right)$ th visited uncertain edge. In this case, we show that A meets the proposed lower bound of the problem. Consider condition 1 in step 2 at the $\left(k-1\right)$ th iteration. Since we have assumed that the strategy ends in step 3, we have

$$\frac{2\left({\sum }_{i=1}^{k-2}{p}_i\right)+p_{k-1}+c_{k-1}}{p_k}>2k-1.$$ E5

Since, both ${\pi }_{k+1}$ and ${\pi }_{k-1}$ (i.e., ${\pi }_{k+1}\ge {\pi }_{k-1}$ ) contain the $\left(k-1\right)$ th visited uncertain edge, $p_{k-1}+c_{k-1}$ is less than or equal to $p_{k+1}$ . Hence, we can replace $p_{k-1}+c_{k-1}$ by $p_{k+1}$ in the numerator above. We can also replace p_i values for $\left(i=1,2,\dots ,k-2\right)$ by p_k in the numerator since p_i is nondecreasing in i. We obtain $\left(2k-4\right)p_k+p_{k+1}>\left(2k-1\right)p_k$ ; hence, $p_{k+1}>3p_k$ .

Now, we replace p_i values for $\left(i=1,2,\dots ,k\right)$ by p_k in the numerator of A. We obtain

$$A=\frac{2k\left(p_k\right)+p_{k+1}}{p_{k+1}}.$$ E6

Now, we can replace $2k\left(p_k\right)$ by $\frac{2k}{3}\left(p_{k+1}\right)$ in the numerator of A. In this case, A would be at most $\frac{2k}{3}+1$ which is less than or equal to the lower bound for $k\ge 2$ since we are comparing $\frac{2k}{3}+1$ and $\mathit{min}\left\{d_1/p_1,2k-1\right\}$ for $k\ge 2$ . Note that since the strategy ends in step 3, $\mathit{min}\left\{d_1/p_1,2k-1\right\}$ equals $2k-1$ .

• Scenario 3. ${\pi }_{k+1}$ does not contain the uncertain edges which are visited in the $\left(k-1\right)$ th and the kth iterations. In this case, we show that A meets the proposed lower bound of the problem. Note that when $k\le 2$ , ${\pi }_{k+1}=D_1$ in this scenario. Thus, the strategy ends in step 1 when $k\le 2$ . For $k\ge 3$ , consider condition 2 in step 2 at the $\left(k-2\right)$ th iteration. We have

$$\frac{2\left({\sum }_{i=1}^{k-2}{p}_i\right)+d_{k-1}}{p_{k-1}}>2k-1.$$ E7

Since ${\pi }_{k+1}$ does not contain the uncertain edges which are visited in the $\left(k-1\right)$ th and the kth iterations, ${\pi }_{k+1}$ is equivalent to $D_{k-1}$ . Hence we can replace $d_{k-1}$ by $p_{k+1}$ in the numerator above. We can also replace p_i values for $\left(i=1,2,\dots ,k-2\right)$ by $p_{k-1}$ in the numerator since p_i is nondecreasing in i. We obtain $\left(2k-4\right)p_{k-1}+p_{k+1}>\left(2k-1\right)p_{k-1}$ . Thus, $p_{k+1}>3p_{k-1}$ . Now, we replace p_i values for $\left(i=1,2,\dots ,k-1\right)$ by $p_{k-1}$ in the numerator of A. We obtain

$$A=\frac{\left(2k-2\right)p_{k-1}+2p_k+p_{k+1}}{p_{k+1}}.$$ E8

Now, we can replace $\left(2k-2\right)p_{k-1}$ by $\frac{2k-2}{3}\left(p_{k+1}\right)$ in the numerator of A. We also replace p_k by $p_{k+1}$ , since p_i is nondecreasing in i. In this case, A would be at most $\frac{2k-2}{3}+3$ , which is less than or equal to the lower bound for $k\ge 3$ .

Since we showed that the competitive ratio of the pessimistic strategy is less than or equal to the lower bound, the proof is complete.

As an illustrative example for the pessimistic strategy, consider the instance given in Figure 2 which represents a part of the Gulf Coast area of the United States. In Figure 2, the nodes represent the cities, and the numbers on the edges denote the edge travel times (per hour) in a post-disaster scenario. The edges (2,6) and (5,6) are the uncertain edges whose costs are not known at the beginning. The traveling agent is initially at node 1 and node 6 is the destination node. Path 1-3-6 is the shortest deterministic path (D ₁), and path 1-2-6 is the shortest optimistic path (π ₁) at the initial stage, i.e., $d_1=11$ and $p_1=3$ . When step 1 of the pessimistic strategy is implemented, the agent compares $\frac{d_1}{p_1}=\frac{11}{3}$ with $2k-1=3$ . Since $\frac{11}{3}>3$ , the strategy enters step 2. Next, the agent takes the shortest optimistic path π ₁ and arrives at node 2 after traversing edge (1,2). We assume that the costs of the uncertain edges (2,6) and (5,6) are 3 and 2, respectively. When the agent arrives at node 2, she learns the traveling time of edge (2,6), i.e., $c_1=3$ . Then she checks if $\frac{p_1+c_1}{p_2}<2k-1$ . Since $\frac{6}{6}<3$ , the agent takes edge (2,6) to arrive at node 6 and the strategy ends. Note that the cost of the offline optimum is 6. Therefore, the competitive ratio of the pessimistic strategy is one in the described scenario.

Figure 2.

A scenario from the Gulf Coast area of the United States network with Atlanta as the source node and Wilmington as the destination node.

4. Multi-agent k-CTP with uncertain edges

In this section, we study the M-k-CTP-U-f and the M-k-CTP-U-l. Note that L denotes the number of agents in the graph in these problems. We assume that there is no distinction between the L agents and all of the agents benefit from complete communication in the sense that they can transmit their locations and explored uncertain edges’ cost information to the other agents in real time. By considering an instance of O-D edge-disjoint graphs, we derive lower bounds on the competitive ratio of deterministic online strategies to the M-k-CTP-U-f and the M-k-CTP-U-l.

Theorem 1.3 For the M-k-CTP-U-f and the M-k-CTP-U-l, there is no deterministic online strategy with competitive ratio less than $\mathit{min}\left\{d_1/p_1,2\left(⌊\frac{k}{L}⌋\right)+1\right\}$ and $\mathit{min}\left\{d_1/p_1,2\left(⌈\frac{k}{L}⌉\right)+1\right\}$ , respectively.

Proof. We again consider the special graph in Figure 1. In this case, any deterministic strategy corresponds to a permutation which describes in which order the uncertain paths and D ₁ (not necessarily all of them) are going to be selected by the agents. For all of these strategies, consider the adverse instance which is defined in the proof of Theorem 1.1. Note that the agents will not reach D via uncertain paths unless the costs of all of the uncertain edges are specified. Before we present the rest of our proof, we need to propose the following lemma.

Lemma 1.4 In the adverse instance, the competitive ratio of the strategies in which the arrivals of the agents at D is via the uncertain paths is at least $2⌊\frac{k}{L}⌋+1$ and $2⌈\frac{k}{L}⌉+1$ , for the M-k-CTP-U-f and the M-k-CTP-U-l, respectively.

Proof. Note that the agents will not reach D via the uncertain paths unless the costs of all of the uncertain edges are specified since we are considering the adverse instance. Now we present our proof for each claim separately.

• M-k-CTP-U-f. In this problem, the agents have to incur a cost of at least $2\left(⌊\frac{k}{L}⌋\right)p_1$ to discover the costs of $L\left(⌊\frac{k}{L}⌋\right)$ number of uncertain edges and backtrack to O. The agents have to incur p ₁ to learn the costs of the remaining uncertain edges and deliver at least one of the agents to D. Since the cost of the shortest path is at least p ₁ in the adverse instance, the competitive ratio of deterministic strategies when none of the agents take D ₁ would be at least $\frac{2\left(⌊\frac{k}{L}⌋\right)p_1+p_1}{p_1}$ , which is equal to $2⌊\frac{k}{L}⌋+1$ .

• M-k-CTP-U-l. In this problem, it takes a cost of at least $2\left(⌈\frac{k}{L}⌉\right)p_1$ to explore the costs of all of the k uncertain edges and backtrack the agents to O. It takes at least p ₁ for all of the agents to take the shortest path and arrive at D. Since the cost of the shortest path is p ₁ in the adverse instance, the competitive ratio of deterministic strategies when none of the agents take D ₁ would be at least $\frac{2\left(⌈\frac{k}{L}⌉\right)p_1+p_1}{p_1}$ , which is equal to $2⌈\frac{k}{L}⌉+1$ .

Note that since we are considering the arrivals of the agents at D via the uncertain paths, the performance of the strategies will not be improved if one or more agents take D ₁. The proof is complete.

Now, we present the rest of our proof for each problem separately:

• M-k-CTP-U-f. We present our proof by considering two cases:

  1. Case 1. $\frac{d_1}{p_1}\ge 2⌊\frac{k}{L}⌋+1$ . In this case, the competitive ratio of the strategies in which the first arrival of the agents at D is via D ₁ is at least $\frac{d_1}{p_1}$ , which is greater than or equal to $\mathit{min}\left\{d_1/p_1,2\left(⌊\frac{k}{L}⌋\right)+1\right\}$ . The competitive ratio of deterministic strategies in which the first arrival of the agents at D is via the uncertain paths would be at least $2⌊\frac{k}{L}⌋+1$ , which matches the proposed lower bound of the problem.

  2. Case 2. $\frac{d_1}{p_1}<2⌊\frac{k}{L}⌋+1$ . In this case, the competitive ratio of deterministic strategies in which the first arrival of the agents at D is via the uncertain paths would be at least $2⌊\frac{k}{L}⌋+1$ , which is greater than the proposed lower bound of $\mathit{min}\left\{d_1/p_1,2\left(⌊\frac{k}{L}⌋\right)+1\right\}$ . The competitive ratio of the strategies in which the first arrival of the agents at D is via D ₁ is at least $\frac{d_1}{p_1}$ , which matches the proposed lower bound of the problem.

• M-k-CTP-U-l. We present our proof by considering two cases:

  1. Case 1. $\frac{d_1}{p_1}\ge 2⌈\frac{k}{L}⌉+1$ . In this case, the competitive ratio of the strategies in which the last arrival of the agents at D is via D ₁ is at least $\frac{d_1}{p_1}$ which is greater than or equal to $\mathit{min}\left\{d_1/p_1,2\left(⌈\frac{k}{L}⌉\right)+1\right\}$ . The competitive ratio of deterministic strategies in which the last arrival of the agents at D is via the uncertain edges would be at least $2⌈\frac{k}{L}⌉+1$ , which matches the proposed lower bound of the problem.

  2. Case 2. $\frac{d_1}{p_1}<2⌈\frac{k}{L}⌉+1$ . In this case, the competitive ratio of deterministic strategies in which the last arrival of the agents at D is via the uncertain paths would be at least $2⌈\frac{k}{L}⌉+1$ which is greater than the proposed lower bound of $\mathit{min}\left\{d_1/p_1,2\left(⌈\frac{k}{L}⌉\right)+1\right\}$ . The competitive ratio of the strategies in which the last arrival of the agents at D is via D ₁ is at least $\frac{d_1}{p_1}$ which matches the proposed lower bound of the problem.

We just proved that the competitive ratio of deterministic strategies in the adverse instance is not better than $\mathit{min}\left\{d_1/p_1,2\left(⌊\frac{k}{L}⌋\right)+1\right\}$ and $\mathit{min}\left\{d_1/p_1,2\left(⌈\frac{k}{L}⌉\right)+1\right\}$ , for the M-k-CTP-U-f and the M-k-CTP-U-l, respectively. Hence, we conclude that the competitive ratio of the problems cannot be better than the proposed lower bounds.

5. Conclusions

We introduced new variants of the online k-CTP which find various important real-life applications. In these variants, the locations of the uncertain edges are known, where the traveling costs of these edges are unknown. We investigated both the single-agent and the multi-agent versions of the problem. We proposed a tight lower bound on the competitive ratio of deterministic online strategies and an optimal strategy for the single-agent problem that we call the S-k-CTP-U. We derived lower bounds on the competitive ratio of deterministic online strategies for the multi-agent problems called as the M-k-CTP-U-f and the M-k-CTP-U-l. Providing optimal strategies for the M-k-CTP-U-f and the M-k-CTP-U-l which match the proposed lower bounds can be considered as a future research direction. Analyzing the problem on special networks such as grid networks is another future research direction for these new variations.