The need for online route planning in road networks is the primary motivation for this study. Although current navigation systems use information about road distances and speed limits to find the fastest routes, traffic conditions are often unpredictable and vary enormously. Therefore, online decision-making strategies play an important role in solving traffic congestion problems.
The Canadian Traveller Problem (CTP), defined by Papadimitriou and Yannakakis in 1991, is to find the shortest path between a source and a destination, given incomplete information that is acquired in a dynamic manner. Consider a road network, the traveller is aware of the entire structure of the network in advance; however, some roads may be blocked by accidents, and a blockage becomes evident only when the traveller reaches a stop that is adjacent to the blocked road. The objective of this famous online routing problem is to plan an efficient route between a source and a destination under this uncertain scenario such that the competitive ratio is minimized. The competitive ratio represents the worst-case ratio of the distance cost of the planned route to the distance cost of the static shortest path in hindsight, where all blockages are known a priori. This problem finds practical applications in dynamic navigation systems designed to avoid traffic congestion.
Modern technologies such as Global Positioning Systems (GPS) and mobile communication have contributed to the development of dynamic navigation planning based on real-time information. However, unpredictable accidents significantly affect planned routes, and increase the complexity of the CTP. Moreover, the CTP is a single-round, two-player game in which the traveller only learns about traffic congestion upon reaching an adjacent site. In other words, the traveller cannot derive useful traffic information regarding future blockages using a chain of trials.
We first study a natural generalization of CTP [4], called the Double-valued Graph problem, which was also initiated by Papadimitriou and Yannakakis. Each road e is associated with two possible distances: original d(e) and jam d+(e). A traveller only learns about the real distance cost (d(e) or d+(e)) of a road e on arrival at one of its end sites. The goal is similar to that of the CTP, which is to develop an adaptive strategy with incomplete information about traffic conditions, so that the competitive ratio is minimized. We provide tight lower bounds for deterministic and randomized algorithms for Double-valued Graph. We also present a deterministic adaptive strategy that meets the proposed lower bound. The algorithm can also be applied directly to the Recoverable CTP in which each road is associated with a recovery time.
In addition, we also consider a generalization of the CTP [3], called the Covering CTP (CCTP) in an attempt to develop an efficient tour for a traveller visiting a set of locations and returning to the origin under the same uncertainty as that of the CTP. The CCTP is a variation of the Travelling Salesman Problem (TSP). We propose an online touring algorithm within an O(sqrt{k})-competitive ratio as well as a tight example, when the number of blockages is up to k.
In 2014 , we revisit the CTP [2] and show for the first time that a polynomial time randomized algorithm can beat the best deterministic algorithms, surpassing the deterministic lower bound of 2k+1 by a constant factor. Furthermore, we prove the randomized algorithm achieving a competitive ratio of about 1.7k +1 in pseudo-polynomial time. The proposed techniques can also be applied to implicitly represent multiple near-shortest paths.
Recently, we consider the electric vehicle (EV) routing problem that takes into consideration of possible battery charging or swapping operations. Because EVs have some serious limitations such as low energy capacity and long charging time, they are often used in urban areas. We develop efficient algorithms which can be implemented on an online EV routing map interface. We also consider several routing models and provide polynomial time approximation algorithms as well as upper bounds [1].
1. Chung-Shou Liao, Shang-Hung Lu, and Zuo-Jun Max Shen. The Electric Vehicle Touring Problem, Transportation Research Part B: Methodological, Vol. 86, (2016), pp. 163-180.
2. Erik Demaine, Yamming Huang, Chung-Shou Liao, and Kunihiko Sadakane. Canadians Should Travel Randomly, in Proc. the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), Copenhagen, Denmark.
3. Chung-Shou Liao and Yamming Huang. The Covering Canadian Traveller Problem, Theoretical Computer Science, Vol. 530(17) (2014), pp. 80–88.
4. Chung-Shou Liao and Yamming Huang. Generalized Canadian Traveller Problems, Journal of Combinatorial Optimization, published online (2013)