ON THE TASK OF BUILDING THE ROUTES OF PASSENGER BUSES OF TWO AUTOMOBILE COMPANIES

Abstract

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