Метод поэлементной многокритериальной композиции оптимальных маршрутов в транспортных сетях

Анотація

Запропоновано простий метод відшукання оптимальних маршрутів у транспортній задачі лінійного програмування. Задача вирішена із використанням сукупності критеріїв: середня сумарна вартість перевезень, тривалість та надійність виконання плану. Модель задачі – орієнтований граф. Вершинам графа відповідають проміжні пункти на множині магістралей, що з’єднують пункти виробництва і споживання. Дуги, що з’єднують вершини графа, розмічені числами, які задають середню вартість транспортування одиниці продукту через ділянку маршруту, що відповідають дузі, середній тривалості транспортування вздовж цієї ділянки та ймовірності подолання маршруту. Для вирішення задачі запропонована міра ефективності використання ділянок, що має адитивні властивості, тобто міра результату об’єднання двох ділянок дорівнює сумі мір цих ділянок. Міра враховує значення для всіх трьох критеріїв. Описана обчислювальна процедура, що реалізуює метод та не вимагає комбінаторного перебору варіантів і забезпечує можливість швидкого отримання компромісного результату. Процедура заснована на використанні запропонованої спеціальної операції комутації матриць. Ця операція забезпечує можливість розрахунку міри ефективності всіх можливих двокрокового, потім трикрокового і далі k-крокових шляхів. Операція ітераційно триває до тих пір, поки не буде знайдена міра маршруту, що з’єднує початковий пункт із кінцевим. Важливою додатковою перевагою методу є можливість його використання для відшукання ефективних маршрутів в складних транспортних мережах з великою кількістю проміжних пунктів. При цьому, якщо перехід від одного з пунктів в інший може бути здійснений через будь-який проміжний пункт з деякої їх множини, то метод дозволяє знайти найкращий із можливих маршрутів. Розглянуто приклади розв’язання задачі для різних формулювань багатокритеріальної транспортної задачі.