Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Faraz Dadgostari (Université Paris 1 Panthéon-Sorbonne, France) and Mahtab Hosseininia (Amirkabir University of Technology, Iran)

Source Title: Graph Theory for Operations Research and Management: Applications in Industrial Engineering

Copyright: © 2013
|Pages: 5
DOI: 10.4018/978-1-4666-2661-4.ch020

Chapter Preview

TopConsider an urban intersection; a road junction where two or more roads either meet or cross at the same level. Vehicles approaching this intersection prepare themselves to choose a path to traverse the intersection. Vehicles that choose the same path and form the same queue on an approach represent a “traffic stream”. A traffic stream can represent either vehicle or pedestrian flow. An intersection with six traffic streams is presented in Figure 1.

The path used by a traffic stream to traverse the intersection, may cross the one used by another traffic stream. In this case, these streams are in conflict and cannot simultaneously get the right of way. In contrast, when paths used by two different traffic streams do not cross, they are compatible and can get the right-of-way simultaneously. The intersection which is shown in Figure 1, traffic streams 3 and 6 are compatible while traffic streams 2 and 5 are in conflict.

Compatible traffic streams may face the green light at the same time, but those traffic streams which are in conflict with them, must be stopped by red light. A time interval during which each traffic stream gets a turn of green light is a complete traffic period (Zhu, 2001). The objective of traffic control by using traffic lights would be to assign to each traffic stream an interval of time during which it has the right of way (when faces a green light) such that the length of a complete traffic period is minimized. Through this chapter, we suppose each interval of green light is of unit length and the right of way can be given only once to any traffic stream.

This problem can be formulated as a graph theoretic model with different approaches. The first approach is based on vertex coloring and the second approach is based on circular coloring of a graph.

The scope of this chapter is limited to an isolated intersection where the influence of other signalized intersections to its performance is negligible (Flammini et al., 2006).

TopIn this approach, the intersection is represented by a graph called “conflict graph”. In this graph, each vertex represents a traffic stream and vertices are adjacent if there exists confliction between corresponding traffic streams. (when green light intervals do not overlap). Figure 2(b) presents the conflict graph of the intersection in Figure 2(a).

It is obvious that if we assign 5 different units length green light intervals to 5 traffic streams in Figure 2(a), total length of complete traffic period would be 5 units. But it can be improved by partitioning the graph into minimum number of independent sets with unit length interval of green light. Each independent set consists of compatible traffic streams which can get simultaneous green light interval. The minimum number of independent sets needed to cover all vertices is chromatic number of the graph. Accordingly in Figure 2(b) the chromatic number of conflict graph is 3. A 3-coloring of the graph is presented in Figure 3.

So the total length of complete traffic period equals 3 units. We can assign the green light interval (0, 1) to traffic streams 1 and 2, the interval (1, 2) to traffic streams 4 and 5 and the interval (2, 3) to traffic stream 3.

Search this Book:

Reset