Multiple Canadians on the road: minimizing the distance competitive ratio

The online k-Canadian Traveller Problem (\(k\)-CTP), known to be PSPACE-complete, asks for the best strategy a traveller has to follow in order to traverse with minimum distance a graph from s to t where at most k edges are blocked. A blocked edge is revealed when the traveller visits one of its endpoints. It is proven that for any deterministic strategy, the competitive ratio is larger than \(2k+1\). Indeed, the distance traversed by the traveller is potentially greater than \(2k+1\) times the optimal journey. For randomized strategies, this ratio becomes \(k+1\). We complement the work of Zhang et al. on \(k\)-CTP with multiple travellers by evaluating the distance competitive ratio of deterministic and randomized strategies for complete and partial communication. We compare these ratios with two other communication levels: when travellers do not communicate at all and when they communicate only before beginning to move. Eventually, we provide a wide picture of the distance competitiveness reachable for the \(k\)-CTP in function of the number of travellers and communication levels.