Open access peer-reviewed chapter

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

Written By

Davood Shiri and F. Sibel Salman

Submitted: May 29th, 2019 Reviewed: July 21st, 2019 Published: October 23rd, 2019

DOI: 10.5772/intechopen.88741

From the Edited Volume

Probability, Combinatorics and Control

Edited by Andrey Kostogryzov and Victor Korolev

Chapter metrics overview

View Full Metrics

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.

Keywords

• multi-agent k-CTP
• online strategies
• deterministic strategies
• competitive ratio
• undirected graphs

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 kblocked 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=VEkdenote an undirected graph with O as the source and D as the destination in which the costs of kedges 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 edgesand 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=VEkand 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 Lagents, 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 firstagent and (2) the lastagent 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 kvehicles 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 optimumsolution. 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 ratiohas 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 kon 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+1and k+1on 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 backtrackstrategy. Xu et al. [5] also considered the k-CTP and presented two online strategies, the greedyand the comparisonstrategy, and proved competitive ratios of 2k+11and 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+1in 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 2k1L1+1and 2kL+1on the competitive ratio of deterministic online strategies for the cases with limited and complete communication, respectively. Note that in the proposed lower bounds Ldenotes the total number of agents and L1 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 knumber 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 stageof the problem.

2. If any kedges 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 Mwould 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, stagesof the problem. That is, there are kstages 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 pathsand which do not have uncertain edges deterministic paths. Let Didenote the shortest deterministic path at the ith stage and dii=12kdenote its corresponding cost. If there are more than one shortest deterministic path at the ith stage, one of them can be selected as Diarbitrarily. 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 pathas 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 pathat 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 pii=12k. That is, π1 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 πk+1, i.e., πk+1is the offline optimum and pk+1is 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 Gwith a given source node O and a destination node D, such that any two distinct O-D paths in Gare 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 mind1/p12k1.

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 k1visited uncertain edges equals Mand the cost of the last visited uncertain edge equals 0. Hence, the cost of the offline shortest path equals p1. 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 D1 (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 D1, and equals 0, if the agent does not take D1 in the strategy. Suppose that the agent has taken inumber of uncertain paths before taking D1 when αequals 1. In this case, the competitive ratio of deterministic strategies on the special graph shown in Figure 1 can be formulated as 2ip1+αd1+1αp1p1(i=0,1,2,,k1). Note that in the adverse instance, the agent has to incur a cost equal to 2p1 in her first k1trials 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 p1 in her kth trial at the uncertain paths and reaches D. Now, we present our proof by considering two cases.

• Case 1. d1p12k1. We consider this case for α=0and α=1separately.

α=1. In this case the competitive ratio of the corresponding strategies can be formulated as 2ip1+d1p1(i=0,1,,k1). The minimum competitive ratio equals d1p1, when i=0, which matches the proposed lower bound of the problem.

α=0. In this case the minimum competitive ratio of the corresponding strategies equals 2k1, which is greater than or equal to the lower bound of the problem.

•Case 2. d1p1>2k1. We also consider this case for α=0and α=1separately.

α=1. In this case the competitive ratio of the corresponding strategies can be formulated as 2ip1+d1p1(i=0,1,,k1). The minimum competitive ratio equals d1p1, when i=0, which is greater than the proposed lower bound of the problem.

α=0. In this case the minimum competitive ratio of the corresponding strategies equals 2k1, which matches the lower bound of the problem.

Since we proved that the competitive ratios of all of the deterministic strategies for this special instance are greater than or equal to mind1/p12k1, the proof is complete.

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

3.1 Pessimistic strategy

• Initialization. Put i=0, where idenotes 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 piis nondecreasing in i, where piis the cost of the optimistic shortest O-D path at the beginning of the ith iteration. Let cidenote the cost of the uncertain edge which is learned at the ith iteration. Note that pi+1is computable immediately after the agent observes ci. Let Sdenote the set of the uncertain edges in the graph.

• Step 1. Compute d1, p1, and mind1/p12k1. If the minimum is d1/p1, take D1, otherwise go to step 2.

• Step 2. If (i=k1), then go to step 3; otherwise, put i=i+1and find πi. If it does not contain uncertain edges, the agent takes it to reach D. Otherwise, take πito reach the ith visited uncertain edge, observe ci, set the value of the newly visited uncertain edge equal to ci, 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

2j=1i1pj+pi+cipi+1<2k1E1

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 ci, Di+1and di+1are computable. Check if

2i=1ipi+di+1pi+1<2k1,E2

and then go back to O and take Di+1. Otherwise, return to O and go to the beginning of step 2.

• Step 3. Take πkand observe ck. Then compare

A=2i=1kpi+pk+1pk+1E3

and

B=2i=1k1pi+pk+ckpk+1.E4

If A<Breturn to O and take the shortest path πk+1; 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 minABin step 3. Thus, it is enough to show that either Aor Bdoes not exceed the proposed lower bound of the problem, if the strategy ends in step 3. We consider three different scenarios for πk+1to show the optimality of the pessimistic strategy, if the strategy ends in step 3.

• Scenario 1. πk+1contains the uncertain edge which is visited in the kth iteration. In this case, we show that Bmeets the proposed lower bound of the problem. Since both πk+1and πk(i.e., πk+1πk) contain the kth visited uncertain edge, pk+ckequals pk+1. Hence we can replace pk+ckby pk+1in the numerator of B. We can also replace pivalues for i=12k1by pk+1in the numerator of B, since piis nondecreasing in i. In this case, Bwould be at most 2k1which equals the lower bound of the problem.

Here, we note that πk+1does not contain the kth visited uncertain edge in the next two scenarios.

• Scenario 2. πk+1contains the uncertain edge which is visited in the k1th iteration. Note that k2in this scenario, since πk+1does not contain the kth visited uncertain edge and contains the k1th visited uncertain edge. In this case, we show that Ameets the proposed lower bound of the problem. Consider condition 1 in step 2 at the k1th iteration. Since we have assumed that the strategy ends in step 3, we have

2i=1k2pi+pk1+ck1pk>2k1.E5

Since, both πk+1and πk1(i.e., πk+1πk1) contain the k1th visited uncertain edge, pk1+ck1is less than or equal to pk+1. Hence, we can replace pk1+ck1by pk+1in the numerator above. We can also replace pivalues for i=12k2by pkin the numerator since piis nondecreasing in i. We obtain 2k4pk+pk+1>2k1pk; hence, pk+1>3pk.

Now, we replace pivalues for i=12kby pkin the numerator of A. We obtain

A=2kpk+pk+1pk+1.E6

Now, we can replace 2kpkby 2k3pk+1in the numerator of A. In this case, Awould be at most 2k3+1which is less than or equal to the lower bound for k2since we are comparing 2k3+1and mind1/p12k1for k2. Note that since the strategy ends in step 3, mind1/p12k1equals 2k1.

• Scenario 3. πk+1does not contain the uncertain edges which are visited in the k1th and the kth iterations. In this case, we show that Ameets the proposed lower bound of the problem. Note that when k2, πk+1=D1in this scenario. Thus, the strategy ends in step 1 when k2. For k3, consider condition 2 in step 2 at the k2th iteration. We have

2i=1k2pi+dk1pk1>2k1.E7

Since πk+1does not contain the uncertain edges which are visited in the k1th and the kth iterations, πk+1is equivalent to Dk1. Hence we can replace dk1by pk+1in the numerator above. We can also replace pivalues for i=12k2by pk1in the numerator since piis nondecreasing in i. We obtain 2k4pk1+pk+1>2k1pk1. Thus, pk+1>3pk1. Now, we replace pivalues for i=12k1by pk1in the numerator of A. We obtain

A=2k2pk1+2pk+pk+1pk+1.E8

Now, we can replace 2k2pk1by 2k23pk+1in the numerator of A. We also replace pkby pk+1, since piis nondecreasing in i. In this case, Awould be at most 2k23+3, which is less than or equal to the lower bound for k3.

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 (D1), and path 1-2-6 is the shortest optimistic path (π1) at the initial stage, i.e., d1=11and p1=3. When step 1 of the pessimistic strategy is implemented, the agent compares d1p1=113with 2k1=3. Since 113>3, the strategy enters step 2. Next, the agent takes the shortest optimistic path π1 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., c1=3. Then she checks if p1+c1p2<2k1. Since 66<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.

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 Ldenotes the number of agents in the graph in these problems. We assume that there is no distinction between the Lagents 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 mind1/p12kL+1and mind1/p12kL+1, 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 D1 (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 2kL+1and 2kL+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 2kLp1to discover the costs of LkLnumber of uncertain edges and backtrack to O. The agents have to incur p1 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 p1 in the adverse instance, the competitive ratio of deterministic strategies when none of the agents take D1 would be at least 2kLp1+p1p1, which is equal to 2kL+1.

• M-k-CTP-U-l. In this problem, it takes a cost of at least 2kLp1to explore the costs of all of the kuncertain edges and backtrack the agents to O. It takes at least p1 for all of the agents to take the shortest path and arrive at D. Since the cost of the shortest path is p1 in the adverse instance, the competitive ratio of deterministic strategies when none of the agents take D1 would be at least 2kLp1+p1p1, which is equal to 2kL+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 D1. 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. d1p12kL+1. In this case, the competitive ratio of the strategies in which the first arrival of the agents at D is via D1 is at least d1p1, which is greater than or equal to mind1/p12kL+1. 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 2kL+1, which matches the proposed lower bound of the problem.

2. Case 2. d1p1<2kL+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 2kL+1, which is greater than the proposed lower bound of mind1/p12kL+1. The competitive ratio of the strategies in which the first arrival of the agents at D is via D1 is at least d1p1, 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. d1p12kL+1. In this case, the competitive ratio of the strategies in which the last arrival of the agents at D is via D1 is at least d1p1which is greater than or equal to mind1/p12kL+1. 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 2kL+1, which matches the proposed lower bound of the problem.

2. Case 2. d1p1<2kL+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 2kL+1which is greater than the proposed lower bound of mind1/p12kL+1. The competitive ratio of the strategies in which the last arrival of the agents at D is via D1 is at least d1p1which 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 mind1/p12kL+1and mind1/p12kL+1, 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.

References

1. 1. Sleator D, Tarjan R. Amortized efficiency of list update and paging rules. Communications of the ACM. 1985;28:202-208
2. 2. Papadimitriou C, Yannakakis M. Shortest paths without a map. Theoretical Computer Science. 1991;84:127-150
3. 3. Bar-Noy A, Schieber B. The Canadian Traveler Problem. In: SODA ‘91 Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms; 1991. pp. 261-270
4. 4. Westphal S. A note on thek-Canadian Traveler Problem. Information Processing Letters. 2008;106:87-89
5. 5. Xu Y, Hu M, Su B, et al. The Canadian Traveler Problem and its competitive analysis. Journal of Combinatorial Optimization. 2009;18:185-205
6. 6. Bender M, Westphal S. An optimal randomized online algorithm for thek-Canadian Traveller Problem on node-disjoint paths. Journal of Combinatorial Optimization. 2015;30:87-96
7. 7. Shiri D, Salman FS. On the randomized online strategies for thek-Canadian Traveler Problem. Journal of Combinatorial Optimization. 2019;1:1-14
8. 8. Zhang H, Xu Y, Qin L. Thek-Canadian Travelers Problem with communication. Journal of Combinatorial Optimization. 2013;26:251-265
9. 9. Shiri D, Salman FS. On the online multi-agent O-Dk-Canadian Traveler Problem. Journal of Combinatorial Optimization. 2017;34:453-461
10. 10. Shiri D, Salman FS. Competitive analysis of randomized online strategies for the onlinek-Canadian Traveler Problem. Journal of Combinatorial Optimization. 2019;37:848-865
11. 11. Xu Y, Zhang H. How much the grid network and rescuers’ communication can improve the rescue efficiency in worst-case analysis. Journal of Combinatorial Optimization. 2015;30:1062-1076

Written By

Davood Shiri and F. Sibel Salman

Submitted: May 29th, 2019 Reviewed: July 21st, 2019 Published: October 23rd, 2019