Online Route Planning on Road Networks

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, traffic conditions vary enormously and unpredictable accidents significantly affect planned routes, which increase the problem complexity, even though current navigation systems use information about road distances and speed limits to find the fastest routes. Therefore, online decision-making strategies play an important role in solving traffic congestion problems. We consider an old online route planning problem, called the Canadian Traveller Problem (CTP), which finds practical applications in designing dynamic navigation systems. We study several generalizations of the CTP and propose deterministic algorithms with theoretical competitive ratio. We also present the first polynomial time randomized algorithm that surpasses the deterministic lower bound. Recently, we consider the electric vehicle (EV) routing problem that takes into consideration of possible battery charging or swapping operations. We develop efficient algorithms which can be implemented on an online EV routing map interface (more details).

This entry was posted in research. Bookmark the permalink.

Comments are closed.