Про задачу побудови маршрутів пасажирських автобусів двох автопідприємств

А. V. Morozov, N. О. Kushnir, Т. M. Loktikova

Анотація


У статті формулюється математична модель задачі пошуку n маршрутів руху автобусів між двома пунктами, які виконують рейси відповідного до заданого розкладу і при заданих тривалостях рейсів. Тривалість кожного маршруту складається з двох рейсів і часу простою, що визначається моментом завершення першого рейсу і моментом початку другого. Всього виконується 2n рейсів, які забезпечують доставку пасажирів n маршрутами. В розглядуваному
206
варіанті задачі є додаткова умова, яка полягає у тому, що час виконання кожного маршруту не може перевищувати встановленого граничного нормативу d.
Для розв’язання сформульованої задачі пропонується процедура зведення її до задачі про призначення та модифікація алгоритму Кана-Мункреса, яка шукає розв’язок задачі про призначення на максимум. Запропонована обчислювальна схема представляє собою ітераційний процес, на кожному кроці якого будується вершинна розмітка.
Щоб адаптувати задачу до вигляду, який дозволяє застосувати модифікацію алгоритму Кана-Мункреса, пропонується розглядати дводольний граф, на якому будується досконале паросполучення з максимальною вагою ребер.

Ключові слова


задача про призначення; дводольний граф; алгоритм Кана-Мункреса.

Повний текст:

PDF (English)

Посилання


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.


Пристатейна бібліографія ГОСТ






DOI: https://doi.org/10.26642/tn-2016-3(78)-119-126

Copyright (c) 2016 А. V. Morozov, N. О. Kushnir, Т. M. Loktikova

Це видання ліцензовано за ліцензією Creative Commons Із Зазначенням Авторства - Некомерційна 4.0 Міжнародна.