Avoiding vehicle collisions in intersections using anomaly detection for the identification of chromatic index value in cubic graphs

Abstract In traffic management and urban planning, it is necessary to allocate time slots for the free flow of traffic on intersected roads so that no traffic is allowed to course on any two adjacent roads simultaneously, therefore avoiding collisions of vehicles on said intersections. This NP-complete problem can be modelled and solved via edge coloring of a graph representing a selected intersection system, where the number of needed time slots is equal to the number of colors required for conflict-free edge coloring of such a graph − a property called chromatic index of a graph. The work presented in the scope of this study focuses on the design and implementation of an anomaly detection process for the identification of the chromatic index of a selected subset of intersections represented by a cubic graph, where conventionally three colors suffice for proper coloring, but in rare (anomalous) cases four are needed. The main objective of the study is achieving lower computational requirements when compared to standard graph edge coloring. Eight approaches to the anomaly detection − isolation forest, one-class random forest, multilayer perceptron network, support vector machine, encoder, and three types of ensemble models − were applied to the selected problem and evaluated from the point of view of decision-making quality and the duration of computation. Based on the reached results, the simple model of a one class random forest and the ensemble model consisting of one class random forest, multilayer perceptron network, and support vector machine applying AND voting system, are the most fitting of the considered approaches with 97% and 99% respective recall values in anomaly identification. Both approaches also reach better time complexity of training and testing than standard edge-coloring methods of chromatic index identification.