On the Complexity of Congestion Free Routing in Transportation Networks

Traffic congestion has been proven a difficult problem to tackle, particularly in big cities where the number of cars are steadily increasing while the infrastructure remains stagnant. Several approaches have been proposed to alleviate the effects of traffic congestion, however, so far congestion is still a big problem in most cities. In this work we investigate a new route reservation approach to address the problem which is motivated by air traffic control. This paper formulates the route reservation problem under different assumptions and examines the complexity of the resulting formulations. Two waiting strategies are investigated, (i) vehicles are allowed to wait at the source before they start their journey, and (ii) they are allowed to wait at every road junction. Strategy (i) though more practical to implement, results to an NP-complete problem while strategy (ii) results to a problem that can be solved in polynomial time but it is not easily implemented since the infrastructure does not have adequate space for vehicles to wait until congestion downstream is cleared. Finally, a heuristic algorithm (based on time-expanded networks) is derived as a solution to both proposed waiting strategies.