# Urban Traffic Control

### Algorithms Revisited

Chinawat Isradisaikul, Class of 2009

Faculty Advisor: Sanjeev Khanna
CIS400/401: Senior Project

2008-2009 Academic Year

University of Pennsylvania

Philadelphia, Pennsylvania

**Links:**
Final Report |
Project Poster |
LaTeX

## Abstract

"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:
- Dispatch horizontal streets at odd time units and vertical streets at even time units.
- Only block vehicles when necessary, or always give a priority to horizontal streets.
- Only block vehicles when necessary, but alternately give a priority to streets in each direction.

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.