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

Автор(и)

  • А. V. Morozov Житомирський державний технологічний університет, Україна https://orcid.org/0000-0003-3167-0683
  • N. О. Kushnir Житомирський державний технологічний університет, Україна
  • Т. M. Loktikova Житомирський державний технологічний університет, Україна https://orcid.org/0000-0002-3525-0179

DOI:

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

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

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

Анотація

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

Біографії авторів

А. V. Morozov, Житомирський державний технологічний університет

А.В. Морозов

N. О. Kushnir, Житомирський державний технологічний університет

Н.О. Кушнір

Т. M. Loktikova, Житомирський державний технологічний університет

Т.М. Локтікова

Посилання

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##

Опубліковано

2016-12-22

Як цитувати

Morozov А. V., Kushnir N. О., & Loktikova Т. M. (2016). Про задачу побудови маршрутів пасажирських автобусів двох автопідприємств. Вісник ЖДТУ. Серія "Технічні науки", (3(78), 119–126. https://doi.org/10.26642/tn-2016-3(78)-119-126

Номер

Розділ

ІНЖЕНЕРІЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ.КОМП’ЮТЕРНА ІНЖЕНЕРІЯ