Variational Genetic Algorithm and Its Application to Urban Traffic Flow Control

Elena Sofronova

Abstract


In dense urban road network, the influence of traffic lights at neighboring intersections becomes significant. Programs for switching the phases of traffic lights, which are called coordination plans, must agree. In the paper the problem of traffic flow control is considered as an optimal control problem. A universal recurrent traffic flow model based on the controlled networks theory is used. The mathematical model of the object is a system of recurrent finite-difference equations, which most closely corresponds to the system of differential equations applied in the optimal control theory. The proposed model allows to combine intersections, providing network extensibility. It is assumed that information about the state of the road network, maneuver parameters, input flows, restrictions on the capacity of vehicles on road sections and on the duration of traffic light phases, as well as the initial state of the traffic flow are known. It is necessary to find a control in the form of durations of phases of traffic lights at regulated intersections, taking into account the minimization of a given quality criterion. The solution of the problem is the optimal coordination plan for all regulated intersections of the network in a specific period of time. The optimal control problem of traffic flows is stated and a method for solving it by variational genetic algorithm is presented. The method uses the principle of small variations of the basic solution. According to this principle, one basic solution, the current coordination plan, is given and all other possible solutions are determined by the set of codes of small variations of the basic solution. A description of the variational genetic algorithm is provided. Examples of variations of the basic solution and the execution of basic genetic operations on them are presented. The proposed method is used to solve the optimal control problem for a group of traffic lights in the Northern Administrative District of Moscow.

Full Text:

PDF (Russian)

References


Aliev A.S., Strelnikov A.I., Shvetsov V.I., Shershevsky Yu.Z. Modeling of traffic flows in a large city with application to the Moscow agglomeration // Avtomat. i Telemekh., 2005, No. 11, 113–125.

Chao Q., Bi H., Li W., Mao T., Wang Z., Lin M.C., Deng Z. A Survey on Visual Traffic Simulation: Models, Evaluations, and Applications in Autonomous Driving. Computer Graphics Forum. 2019. doi:10.1111/cgf.13803.

Bekmagambetov M.M., Kochetkov A.V. Analysis of modern vehicle modeling software // Journal of Automotive Engineers, No. 6 (77), 2012.

Taleb T., Benslimane A., Letaief K.B. Toward an effective riskconscious and collaborative vehicular collision avoidance system, IEEE transactions on Vehicular Technology, vol. 59, no. 3, pp. 1474-1486, 2010.

Poczter S.L., Jankovic L.M. The google car: Driving toward a better future? Journal of Business Case Studies, vol. 10, no. 1, p.7, 2014.

Nippold R., Wagner P., Banse O., Rakow C. Investigation of the effect of autonomous vehicles (AV) on the capacity of an urban transport network, SUMO Conference Proceedings, 2, p. 53-65, 2022. doi:10.52825/scp.v2i.87.

Zhu L., Yu F.R., Wang Y., Ning B., Tang T. Big Data Analytics in Intelligent Transportation Systems: A Survey, IEEE Transactions on Intelligent Transportation Systems, 20, 1, 2019. doi: 10.1109/TITS.2018.2815678.

Iliashenko O., Iliashenko V., Lukyanchenko E. Big Data in Transport Modelling and Planning. Transportation Research Procedia. 54. 900-908. (2021) 10.1016/j.trpro.2021.02.145.

Nikolova E., Brand M., Karger D. Optimal Route Planning under Uncertainty. 131-141. Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, ICAPS 2006, Cumbria, UK, June 6-10, 2006.

Papageorgiou M., Diakaki C., Dinopoulou V., Kotsialos A., Wang Y.

Review of Road Traffic Control Strategies // Proceedings of the IEEE. v.91. 2003. pp. 2043 – 2067.

Wey W.M. Model formulation and solution algorithm of traffic signal control in an urban network // Computers Environment Urban

Systems, vol.24, no.4, pp.355-378, 2000.

Akelik R., Besley M., Chung E. An evaluation of scats master isolated control, Philossophy of Literature, vol.2, no.5372, pp.378-382, 1998.

Hounsell N., Landles J., Bretherton R., Gardner K. Intelligent systems for priority at traffic signals in London: the income project, In International Conference on Road Transport Information and Control, 1998, pp.90-94.

Bommes M., Fazekas A., Volkenhoff T., Oeser M. Video based

intelligent transportation systems state of the art and future development, Transportation Research Procedia, vol.14, pp.4495-504, 2016.

Lee J., Park B. Development and evaluation of a cooperative vehicle intersection control algorithm under the connected vehicles environment, IEEE Transactions on Intelligent Transportation Systems, vol.13, no.1, pp.81-90, 2012.

Sofronova E.A. Universal recurrent model of traffic flow control in the class of microscopic models. Vestnik VGU. Series: System Analysis and Information Technologies. 2021. 4. p. 3-29. doi: 10.17308/ sait.2021.4/3795.

Diveev A.I. Theory of controlled networks and its applications. M.: CC RAS, 2007. - 160 p.

Diveev A.I. Controlled networks and their applications. Computational Mathematics and Mathematical Physics, 48(8), 2008, P. 1428–1442. DOI: 10.1134/S0965542508080125.

Gasnikov A.V., Klenov S.L., Nurminskij E.A., Holodov Ya.A., Shamraj N.B. Introduction to mathematical modeling of traffic flows:

textbook. MIPT, 2010. 362 p. (in Russian)

Smirnov N.N., Kisilev A.B., Nikitin V.F., Yumashev M.V. Mathematical modeling of motor traffic flows. M.: Faculty of Mechanics and Mathematics of Moscow State University, 1999.

Shvetsov V.I. Mathematical modeling of traffic flows //Automation and Telemechanics. 2003. 11. P. 3–46.

Roughgarden T., Algorithms Illuminated. Part 4: Algorithms for NPHard Problems. Soundlikeyourself Publishing, LLC, 2020. — 273 p.

Nogin V.D. Decision making in a multicriteria environment: a quantitative approach. M.: FIZMATLIT, 2005. – 176 p.

Lotov A.V., Pospelova I.I. Multi-criteria decision-making problems: a tutorial. M.: MAKS Press, 2008. - 197 p.

Karpenko A.P. Population algorithms for global search optimization. Review of new and little-known algorithms //Information technologies. S7. 2012. p. 1–32.

Fonseca C.M, Fleming P.J. Genetic algorithms for multiobjective function optimization: Formulation, discussion and generalization. Proc. of the Fifth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kauffman. 1993. p.416–423.

Guliashki V., Toshev H., Korsemov Ch. Survey of Evolutionary Algorithms Used in Multiobjective Optimization // Problems of Engineering Cybernetics and Robotics, 2009. vol. 60. P. 42 –54.

Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multi-objective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. 2002. V.6. No. 2. P. 182–197. doi: 10.1109/ 4235.996017.

Diveev A.I. Small Variations of Basic Solution Method for Non-numerical Optimization. Proc. of 16th IFAC Workshop on Control Applications of Optimization, 2015, p. 28–33. doi: 10.1016/j.ifacol.2015.11.054.

Sofronova E., Diveev A. Universal approach to solution of optimization problems by symbolic regression. Appl. Sci. 2021, 11, 5081. doi: 10.3390/app11115081.

Pontryagin L.S., Boltyanskii V.G., Gamkrelidze R.V., Mishechenko

E.F. The Mathematical Theory of Optimal Processes. VIII + 360 S. New York/London 1962.

Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975.

Kureichik V.M. Genetic algorithms and their application. Taganrog RTU, 2002, - 244 p.

Sofronova E.A., Diveev A.I. Package for simulation and search for the optimal control program for groups of traffic lights using variational genetic algorithm. Certificate of state registration of the computer program No. 2020619911 dated August 25, 2020.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162