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. Furthermore, we present the first polynomial time randomized algorithm that surpasses the long-standing deterministic lower bound.
Recently, we also 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. The result demonstrates the effectiveness of the EV routes from both the theoretical and practical perspectives. Very recently, we extended route planning to sharing economy, i.e., the car-sharing problem (not only for cars, but also for other resources like bikes and shuttle-buses). For instance, there are several service stations in the city, in residential areas and downtown, at popular sightseeing spots, and so on. Customers can make a request with a pick-up time and place and a drop-off time and place. The decision for accepting or rejecting a request should be made in an online fashion, and the goal is to maximize the profit by accepting as many requests as possible.(more details)