Urban Traffic Control

Algorithms Revisited

Chinawat Isradisaikul, Class of 2009
Faculty Advisor: Sanjeev Khanna

Traffic Control Problem Instance

CIS400/401: Senior Project
2008-2009 Academic Year
University of Pennsylvania
Philadelphia, Pennsylvania

Links: Final Report | Project Poster | LaTeX


"Traffic jam" has been one of the most frequently heard phrases in urban areas. Why is there traffic jam? Bad street layout? Too many cars? Poor driving behaviors? Inefficient traffic control systems? All but the last problem seem difficult to solve, even though education helps solve the poor behaviors and public transportation intends to reduce the number of vehicles. Changing the existing roads sounds difficult. Improving traffic control systems using mathematical models, hence, appears most feasible.

In this project, we revisit several existing traffic controlling algorithms and analyze their efficiency. To make the problem manageable, we consider a special case where every vehicle travels eastward or southward only. Our finding is that the length of the longest route and the number of vehicles in the system play an important role in determining the efficiency of the algorithms.

Algorithm Overview

We considered three algorithms: For each algorithm, we consider the upper and lower bounds in maximum finish time. For the upper bound, we show that the algorithm in consideration never produces---in any instances---a maximum finish time more than the given bound. For the lower bound, we show that there exists an instance of a problem where the algorithm in consideration produces a maximum finish time of the given bound.

Valid HTML 4.01 Transitional Valid CSS!