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... [ view full abstract ]

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.