Choice of the Control Variables of an Isolated Intersection by Graph Colouring

Vladan Batanović, Slobodan Guberinić, Radivoj Petrović

This paper deals with the problem of grouping traffic streams into signal groups on a signalized intersection. Determination of the complete sets of signal groups, i.e. the groups of traffic streams on one intersection, controlled by one control variable is defined in this paper as a graph-coloring problem. The complete sets of signal groups are obtained by coloring the complement of the graph of identical indications. It is shown that the minimal number of signal groups in the complete set of signal groups is equal to the chromatic number of the complement of the graph with identical indications. The problem of finding all complete sets of signal groups with minimal cardinality is formulated as a linear programming problem where the values of variables belong to a set {0,1}.