Про задачу побудови маршрутів пасажирських автобусів двох автопідприємств
DOI:
https://doi.org/10.26642/tn-2016-3(78)-119-126Ключові слова:
задача про призначення, дводольний граф, алгоритм Кана-Мункреса.Анотація
У статті формулюється математична модель задачі пошуку n маршрутів руху автобусів між двома пунктами, які виконують рейси відповідного до заданого розкладу і при заданих тривалостях рейсів. Тривалість кожного маршруту складається з двох рейсів і часу простою, що визначається моментом завершення першого рейсу і моментом початку другого. Всього виконується 2n рейсів, які забезпечують доставку пасажирів n маршрутами. В розглядуваному206
варіанті задачі є додаткова умова, яка полягає у тому, що час виконання кожного маршруту не може перевищувати встановленого граничного нормативу d.
Для розв’язання сформульованої задачі пропонується процедура зведення її до задачі про призначення та модифікація алгоритму Кана-Мункреса, яка шукає розв’язок задачі про призначення на максимум. Запропонована обчислювальна схема представляє собою ітераційний процес, на кожному кроці якого будується вершинна розмітка.
Щоб адаптувати задачу до вигляду, який дозволяє застосувати модифікацію алгоритму Кана-Мункреса, пропонується розглядати дводольний граф, на якому будується досконале паросполучення з максимальною вагою ребер.
Посилання
Panishev, A.V. and Morozov, A.V. (2014), Modeli i metody optimizatsii zamknutykh marshrutov na transportnoy seti, ZhDTU, Zhitomir, 316 p.
Panishev, A.V. and Plechistyy, D.D. (2006), Modeli i metody optimizatsii v probleme kommivoyazhera, ZhDTU, Zhitomir, 300 p.
Morozov, A.V. (2015), «Pro matematychni modeli zadach klasiv lystonoshi ta komivojazhera», Visnyk ZhDTU, Vol. 2 (73), pp. 167–173.
Bronshteyn, E.M. and Zaiko, T.A. (2010) «Determenirovannye optimizatsionnye zadachi transportnoy logistiki», Avtomatika i telemekhanika, Vol. 10, pp. 133–147.
Maynika, E. (1981), Algoritmy optimizatsii na setyakh i grafakh, Mir, Moskva, 323 p.
Lovas, L. and Plammer, M. (1998), «Prikladnye zadachi teorii grafov». Teoriya parosochetaniy v matematike, fizike, khimii, Mir, Moskva, 653 p.
Papadimitriu, Kh. and Stayglits, K. «Kombinatornaya optimizatsiya. Algoritmy i slozhnost'», Mir, Moskva, 510 p.
Matsiy, O.B., Morozov, A.V. and Panishev, A.V. (2015), «The Recurrent Method to Solve the Assignment Problem», Cybernetics and Systems Analysis, Vol. 51, issue 6, pp. 939–946.
Matsiy, O.B., Morozov, A.V. and Panishev, A.V. (2016), «Fast Algorithm to Find 2-Factor of Minimum Weight», Cybernetics and Systems Analysis, Vol. 52, issue 3, pp. 467–474.
Matsiy, O.B., Morozov, A.V., Panishev, A.V. (2016), «A Recurrent Algorithm to Solve the Weighted Matching Problem», Cybernetics and Systems Analysis, Vol. 52, issue 5, pp. 748–757.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 А. V. Morozov, N. О. Kushnir, Т. M. Loktikova
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
Автор, який подає матеріали до друку, зберігає за собою всі авторські права та надає відповідному виданню право першої публікації, дозволяючи розповсюджувати даний матеріал із зазначенням авторства та джерела первинної публікації, а також погоджується на розміщення її електронної версії на сайті Національної бібліотеки ім. В.І. Вернадського та у відкритому доступі в електронному архіві університету та на сайті журналу.
