Transport automation research Transport automation research Автоматика на транспорте 2412-9186 52788 10.20295/2412-9186-2022-8-03-287-295 Электронное моделирование Electronic simulation Электронное моделирование Review on optimization models and methods for shuttle urban and main transport timetables and traffic schedules Обзор моделей и методов оптимизации расписаний и графиков движения маршрутного городского и магистрального транспорта Горбачев Алексей Михайлович Gorbachev Aleksey Mihaylovich

кандидат технических наук;

candidate of technical sciences;

 Петербургский государственный университет путей сообщения Императора Александра I Россия Emperor Alexander I St. Petersburg State Transport University Russian Federation 13 09 2022 13 09 2022 8 3 287 295 13 09 2022 https://izvestiapgups.editorum.ru/en/nauka/article/52788/view

В статье опубликован обзор используемых в настоящее время моделей и методов построения и оптимизации маршрутных расписаний городского и магистрального транспорта, рассмотрены основные отличия технологии построения расписаний и графиков движения в России от зарубежного опыта. В статье осуществлен поэтапный анализ подходов к планированию работы городского транспорта. Рассмотрены вопросы разбиения транспортной сети города на маршруты, проблемы распределения транспортных средств между ними, приведены математические модели расписаний движения маршрутного транспорта, назначения реальных транспортных средств определенных типов на наряды и распределения водителей между ними на каждую дату, указаны основные причины использования апериодических расписаний городского транспорта на постсоветском пространстве. Изложена история развития программных комплексов автоматизации построения расписаний движения городского транспорта, рассмотрены основные подходы к разработке современных информационных систем такого назначения, реализующих автоматизацию построения периодических, апериодических и гибридных расписаний и графиков движения.

Review for used at the moment models and methods for the creation and optimization of shuttle timetables for urban and main transport is given in the article, major differences between post-Soviet and foreign experience in the technology of timetable and traffic schedule creation are considered. The article contains phased analysis of approaches to planning the work of urban transport. The issues of dividing the city transport network into routes, the problems of vehicle distribution between them are given, the mathematical models of shuttle transport timetables, the assignments of real vehicles of certain types to squads and drivers distribution between them for each date are presented, major reasons for using aperiodic urban transport traffic schedules on post-Soviet area are pointed. The history of the development of software automation systems for urban transport traffic schedules is narrated, there’re considered major approaches, implementing an automation for the creation of periodic, aperiodic and hybrid timetables and traffic schedules, for to develop modern informational systems for the being considered purposes.

 расписание маршрутного транспорта модель периодического расписания модель апериодического расписания гибридная модель городской транспорт shuttle transport schedule periodic traffic schedule model aperiodic traffic schedule model hybrid traffic schedule model urban transport

Никищенков С. А., Фокеев А.Б. Эмулятор графиков движения поездов и работы станций // Автоматика на транспорте. - 2016. - Том 2. - №1. - С. 35-46. Nikischenkov S. A., Fokeev A.B. Emulyator grafikov dvizheniya poezdov i raboty stanciy // Avtomatika na transporte. - 2016. - Tom 2. - №1. - S. 35-46. Odijk M. A. A constraint generation algorithm for the construction of periodic railway timetables. // Transportation Research Part B, 30(6) - Great Britain: Elsevier. - 1996, p. 455-464. Odijk M. A. A constraint generation algorithm for the construction of periodic railway timetables. // Transportation Research Part B, 30(6) - Great Britain: Elsevier. - 1996, p. 455-464. Cacchiani V., Toth P. Nominal and robust train timetabling problems. // European Journal of Operational Research, 219, - Elsevier. - 2012, p. 727-737. Cacchiani V., Toth P. Nominal and robust train timetabling problems. // European Journal of Operational Research, 219, - Elsevier. - 2012, p. 727-737. X. Geng., M. Hu, “Simulated Annealing Method-Based Flight Schedule Optimization in Multiairport Systems”, Mathematical Problems in Engineering Volume 2020, Article ID 4731918. - DOI: 10.1155/2020/4731918. X. Geng., M. Hu, “Simulated Annealing Method-Based Flight Schedule Optimization in Multiairport Systems”, Mathematical Problems in Engineering Volume 2020, Article ID 4731918. - DOI: 10.1155/2020/4731918. Lei L., Zhao D., Liu H., Guo D. “Flight Schedule Strategy of Airport Group”. IOP Conf. Series: Materials Science and Engineering 790 (2020), UK, 2020. - DOI: 10.1088/1757-899X/790/1/012102 Lei L., Zhao D., Liu H., Guo D. “Flight Schedule Strategy of Airport Group”. IOP Conf. Series: Materials Science and Engineering 790 (2020), UK, 2020. - DOI: 10.1088/1757-899X/790/1/012102 Сафронов А. И., Лысенко Е. В. Моделирование плана перевозочного процесса в утренний час «пик» на замкнутой большой кольцевой линии московского метрополитена // Автоматика на транспорте. - 2021. - Том 7. - №4. - С. 584-616. - DOI: 10.20295/2412-9186-2021-7-4-584-616. Safronov A. I., Lysenko E. V. Modelirovanie plana perevozochnogo processa v utrenniy chas «pik» na zamknutoy bol'shoy kol'cevoy linii moskovskogo metropolitena // Avtomatika na transporte. - 2021. - Tom 7. - №4. - S. 584-616. - DOI: 10.20295/2412-9186-2021-7-4-584-616. Горбачев А. М. Математическая модель маршрутных расписаний наземного городского электрического транспорта // Автоматика на транспорте. - 2020. - Том 6. - №4. - С. 499-517. - DOI: 10.20295/2412-9186-2020-6-4-499-517. Gorbachev A. M. Matematicheskaya model' marshrutnyh raspisaniy nazemnogo gorodskogo elektricheskogo transporta // Avtomatika na transporte. - 2020. - Tom 6. - №4. - S. 499-517. - DOI: 10.20295/2412-9186-2020-6-4-499-517. Плотников Д. Г. Применение коротких кольцевых маршрутов для оптимизации транспортной сети района / Д. Г. Плотников, Д. Р. Стахин, А. В. Баните // Транспорт России: проблемы и перспективы - 2020 : Материалы Юбилейной международной научно-практической конференции, Санкт-Петербург, 10-11 ноября 2020 года / © ФГБУН Институт проблем транспорта им. Н. С. Соломенко Российской академии наук, 2020 © Коллектив авторов, 2020. - Санкт-Петербург: Институт проблем транспорта им. Н.С. Соломенко РАН, 2020. - С. 41-45. - EDN YKEEMC. Plotnikov D. G. Primenenie korotkih kol'cevyh marshrutov dlya optimizacii transportnoy seti rayona / D. G. Plotnikov, D. R. Stahin, A. V. Banite // Transport Rossii: problemy i perspektivy - 2020 : Materialy Yubileynoy mezhdunarodnoy nauchno-prakticheskoy konferencii, Sankt-Peterburg, 10-11 noyabrya 2020 goda / © FGBUN Institut problem transporta im. N. S. Solomenko Rossiyskoy akademii nauk, 2020 © Kollektiv avtorov, 2020. - Sankt-Peterburg: Institut problem transporta im. N.S. Solomenko RAN, 2020. - S. 41-45. - EDN YKEEMC. Gorbachev A. Model of Hybrid Timetables for High Speed Urban Tramway Movement / A. Gorbachev // 2020 IEEE East-West Design and Test Symposium, EWDTS 2020 - Proceedings, Varna, 04-07 сентября 2020 года. - Varna, 2020. - P. 9225145. - DOI 10.1109/EWDTS50664.2020.9225145. - EDN OFKWJH. Gorbachev A. Model of Hybrid Timetables for High Speed Urban Tramway Movement / A. Gorbachev // 2020 IEEE East-West Design and Test Symposium, EWDTS 2020 - Proceedings, Varna, 04-07 sentyabrya 2020 goda. - Varna, 2020. - P. 9225145. - DOI 10.1109/EWDTS50664.2020.9225145. - EDN OFKWJH. Gorbachev A. “Review of Urban Transport Timetables Math Models”, Proceedings of Petersburg State Transport University, № 3. 15, PSTU, St. Petersburg, 2018, pp. 366-370. Gorbachev A. “Review of Urban Transport Timetables Math Models”, Proceedings of Petersburg State Transport University, № 3. 15, PSTU, St. Petersburg, 2018, pp. 366-370. Schmidt M. E. “Integrating Routing Decisions in Public Transport Problems”, Springer Optimization and Its Applicaions 89, Springer Science + Business Media, New York, 2014, 386 p. Schmidt M. E. “Integrating Routing Decisions in Public Transport Problems”, Springer Optimization and Its Applicaions 89, Springer Science + Business Media, New York, 2014, 386 p. Никифоров О. А. О цифровизации маршрутов передвижения маломобильных групп населения / О. А. Никифоров, С. М. Мочалин, К. Э. Сафронов // III Бетанкуровский международный инженерный форум : Сборник трудов, Санкт-Петербург, 02-03 декабря 2021 года. - Санкт-Петербург: Петербургский государственный университет путей сообщения Императора Александра I, 2021. - С. 49-51. - EDN NDOGLS. Nikiforov O. A. O cifrovizacii marshrutov peredvizheniya malomobil'nyh grupp naseleniya / O. A. Nikiforov, S. M. Mochalin, K. E. Safronov // III Betankurovskiy mezhdunarodnyy inzhenernyy forum : Sbornik trudov, Sankt-Peterburg, 02-03 dekabrya 2021 goda. - Sankt-Peterburg: Peterburgskiy gosudarstvennyy universitet putey soobscheniya Imperatora Aleksandra I, 2021. - S. 49-51. - EDN NDOGLS. Schöbel A., Schmidt M. E. “The Complexity of Integrating Routing Decisions in Public Transportation Models” - 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10), Liverpool, 2010, pp. 156-169. Schöbel A., Schmidt M. E. “The Complexity of Integrating Routing Decisions in Public Transportation Models” - 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS ’10), Liverpool, 2010, pp. 156-169. Markevich A. V. Automation of Scheduling for Drivers of the Subway Rolling Stock / A. V. Markevich, V. G. Sidorenko // 2021 IEEE East-West Design and Test Symposium, EWDTS 2021 - Proceedings, Batumi, 10-13 сентября 2021 года. - Batumi, 2021. - DOI 10.1109/EWDTS52692.2021.9580990. - EDN SIOWLH. Markevich A. V. Automation of Scheduling for Drivers of the Subway Rolling Stock / A. V. Markevich, V. G. Sidorenko // 2021 IEEE East-West Design and Test Symposium, EWDTS 2021 - Proceedings, Batumi, 10-13 sentyabrya 2021 goda. - Batumi, 2021. - DOI 10.1109/EWDTS52692.2021.9580990. - EDN SIOWLH. Rockafellar R. T. “Network Flows and Monotropic Optimization”, Athena Scientific, Belmont, 1998 - 634 p. Rockafellar R. T. “Network Flows and Monotropic Optimization”, Athena Scientific, Belmont, 1998 - 634 p. Serafani P., Ukovich W. “A mathematical Model for Periodic Scheduling Problems”, SIAM J. Disc. Math 2 (4), Society for Industrial and Applied Mathematics, USA, 1989, pp. 550-581. Serafani P., Ukovich W. “A mathematical Model for Periodic Scheduling Problems”, SIAM J. Disc. Math 2 (4), Society for Industrial and Applied Mathematics, USA, 1989, pp. 550-581. Даценко Н. В. Применение муравьиного алгоритма для решения задачи составления расписания движения городского общественного транспорта / Н. В. Даценко, А. В. Хатунцев // Моделирование энергоинформационных процессов : IX Национальная научно-практическая конференция с международным участием, Воронеж, 22-24 декабря 2020 года. - Воронеж: Воронежский государственный университет инженерных технологий, 2021. - С. 145-150. - EDN QWEAUP. Dacenko N. V. Primenenie murav'inogo algoritma dlya resheniya zadachi sostavleniya raspisaniya dvizheniya gorodskogo obschestvennogo transporta / N. V. Dacenko, A. V. Hatuncev // Modelirovanie energoinformacionnyh processov : IX Nacional'naya nauchno-prakticheskaya konferenciya s mezhdunarodnym uchastiem, Voronezh, 22-24 dekabrya 2020 goda. - Voronezh: Voronezhskiy gosudarstvennyy universitet inzhenernyh tehnologiy, 2021. - S. 145-150. - EDN QWEAUP. Liebchen C., Proksch M., and Wagner F. H. Performance of algorithms for periodic timetable optimization. In G. Fandel, W. Trockel, M. Hickman, P. Mirchandani, and S. Voß, editors, Computeraided Systems in Public Transport, volume 600 of Lecture Notes in Economics and Mathematical Systems, p. 151-180. Springer. Berlin Heidelberg, 2008. Liebchen C., Proksch M., and Wagner F. H. Performance of algorithms for periodic timetable optimization. In G. Fandel, W. Trockel, M. Hickman, P. Mirchandani, and S. Voß, editors, Computeraided Systems in Public Transport, volume 600 of Lecture Notes in Economics and Mathematical Systems, p. 151-180. Springer. Berlin Heidelberg, 2008. Горбачев А. М. Автоматизация планирования движения городского скоростного легкорельсового транспорта / А. М. Горбачев, П. А. Василенко // Транспорт Российской Федерации. - 2021. - № 5-6(96-97). - С. 43-46. - EDN DPDYAU. Gorbachev A. M. Avtomatizaciya planirovaniya dvizheniya gorodskogo skorostnogo legkorel'sovogo transporta / A. M. Gorbachev, P. A. Vasilenko // Transport Rossiyskoy Federacii. - 2021. - № 5-6(96-97). - S. 43-46. - EDN DPDYAU. Мирончук А. А. Координация расписания городских и пригородных маршрутов наземного пассажирского транспорта / А. А. Мирончук, И. Ю. Солодовченко // Мир транспорта и технологических машин. - 2021. - № 2(73). - С. 49-56. - DOI 10.33979/2073-7432-2021-73-2-49-56. - EDN CAVZCG. Mironchuk A. A. Koordinaciya raspisaniya gorodskih i prigorodnyh marshrutov nazemnogo passazhirskogo transporta / A. A. Mironchuk, I. Yu. Solodovchenko // Mir transporta i tehnologicheskih mashin. - 2021. - № 2(73). - S. 49-56. - DOI 10.33979/2073-7432-2021-73-2-49-56. - EDN CAVZCG. Антошвили М. Е., Либерман С. Ю., Спирин И. В. «Оптимизация городских автобусных перевозок», М. Транспорт. 1985. - 102 с. Antoshvili M. E., Liberman S. Yu., Spirin I. V. «Optimizaciya gorodskih avtobusnyh perevozok», M. Transport. 1985. - 102 s. Антошвили М. Е., Варелопуло Г. А., Хрущев М. В. «Организация городских автобусных перевозок с применением математических методов и ЭВМ», М. Транспорт. 1974. - 104 с. Antoshvili M. E., Varelopulo G. A., Hruschev M. V. «Organizaciya gorodskih avtobusnyh perevozok s primeneniem matematicheskih metodov i EVM», M. Transport. 1974. - 104 s.