The Covering Canadian Traveller Problem

The Canadian Traveller Problem (CTP) is to find the shortest route from a source to a destination under uncertain conditions. Some roads may be blocked by accidents, and a traveller only discovers a blockage upon reaching an adjacent site of the road. More precisely, the objective of this problem is to design an adaptive strategy against a malicious adversary who sets up road blockages in order to maximize the gap between the distance cost resulting from the strategy and the distance cost of the static shortest path in which all blockages are known a priori. This study investigates a variation of the Travelling Salesman Problem that involves finding the shortest tour, visiting a set of locations, and returning to the origin under the same uncertainty as that of the CTP. This online routing problem, called the Covering Canadian Traveller Problem (CCTP), has real applications in dynamic navigation systems such as delivery routing in express logistics. We study this problem from a competitive analysis perspective, and present an efficient touring strategy within an O(k)-competitive ratio, where the number of blockages is up to k. We also demonstrate the tightness of the competitive analysis.