Анотація:
У статті формулюється математична модель задачі пошуку n маршрутів руху автобусів між двома пунктами, які виконують рейси відповідного до заданого розкладу і при заданих тривалостях рейсів. Тривалість кожного маршруту складається з двох рейсів і часу простою, що визначається моментом завершення першого рейсу і моментом початку другого. Всього виконується 2n рейсів, які забезпечують доставку пасажирів n маршрутами. В розглядуваному
варіанті задачі є додаткова умова, яка полягає у тому, що час виконання кожного маршруту не може перевищувати встановленого граничного нормативу d.
Для розв’язання сформульованої задачі пропонується процедура зведення її до задачі про призначення та модифікація алгоритму Кана-Мункреса, яка шукає розв’язок задачі про призначення на максимум. Запропонована обчислювальна схема представляє собою ітераційний процес, на кожному кроці якого будується вершинна розмітка.
Щоб адаптувати задачу до вигляду, який дозволяє застосувати модифікацію алгоритму Кана-Мункреса, пропонується розглядати дводольний граф, на якому будується досконале паросполучення з максимальною вагою ребер.
Анотація (англ.):
The article formulates a mathematical model search of n bus routes between the two
points, which carry out cruises corresponding to the specified schedule, and with specified
duration. The duration of each route consists of two cruises and idle hours, which are
determined by the moment of the completion of the first cruise and the moment of the
beginning of the second. Totally, 2n cruises are performed and provide the passenger transportation
by n cruises. In this specific version of the problem is the additional condition,
that the execution time of each route shall not exceed the established limit of a standard d.
Offered framework for the solution of the problem of procedure to the task assignment
and modification of Kuhn-Munkres algorithm, which is looking for a solution of the problem
of assignment to the maximum. The proposed numerical scheme is an iterative process, each
step of which provides the topmost layout. To adapt the task to form, which allows to apply
the modification of Kuhn-Munkres algorithm, to consider the bichromatic graph, which
builds perfect matching with a maximum weight of the ribs.
