Route Planning Algorithms for Urban Environment

Abstract

This thesis introduces solutions to two route planning problem for urban environment. The first is the probe allocation problem where a team of agents is deployed to monitor traffic condition in an urban environment such that accurate estimation of traffic condition along all roads can be made. The second is the bus route planning problem where public transportation is optimized such that commuter travel time is minimized. The performances of these solutions are studied both analytically and through simulations.

Surveillance problem in a variety of scenarios such as hostile environments, environmental monitoring and law enforcement missions (i.e. border patrol) etc have been widely studied. However, monitoring of traffic conditions in urban environments by deploying a team of agents is a novel problem not found in any existing literature. This problem is termed as the probe allocation problem. In light of the recent developments of automated cars, studies of such surveillance problems in urban environments will prove to be useful. Two sets of algorithms are proposed for this problem, each pertaining to a different deployment strategy.

In addition, it is shown that the probe allocation problem is very similar to the bus route planning problem. In the bus route planning problem, bus routes are being optimized such that the total travel time of every commuter is minimized in addition to other factors such as the number of transfers made etc. A novel algorithm (a modified version from one of the algorithms originally proposed for the probe allocation problem) is proposed for the bus route planning problem. The proposed algorithm for the bus route planning problem outperforms many existing bus route planning solutions when compared against the well known Mandl's Benchmark.