Open AccessChoice of the control variables of an isolated intersection by graph colouring
Author(s) -
Vladan Batanović,
Slobodan Guberinić,
Radivoj Petrović
Publication year - 2015
Publication title -
yugoslav journal of operations research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.221
H-Index - 21
eISSN - 1820-743X
pISSN - 0354-0243
DOI - 10.2298/yjor130813045b
Subject(s) - mathematics , chromatic scale , intersection (aeronautics) , combinatorics , graph , intersection graph , cardinality (data modeling) , discrete mathematics , computer science , line graph , data mining , aerospace engineering , engineering
This paper deals with the problem of grouping the traffic streams into some groups - signal groups on a signalized intersection. The fact that more traffic streams, which are not in a conflict, can be controlled by one sequence of traffic lights means that one control variable can be assigned to one signal group. 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 graphcoloring 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, which is equal to the chromatic number, is formulated as a linear programming problem where the values of variables belong to set {0,1}