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

Abstract

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

A simple method is proposed for finding optimal routes in the transport problem of linear programming. The task is solved using a set of criteria: the average total cost of transportation, the duration and reliability of plan. The task model is an oriented graph. The vertices of the graph correspond to intermediate points on a number of ways connecting production and consumption points. The arcs connecting the vertices of the graph are marked with numbers specifying the average cost of transporting a product unit through the route section corresponding to the arc, the average duration of transportation along this section and the probability of overcoming it. To solve the task, a measure efficiency use of plots is proposed, which has property of additivity, that is, the measure of result for combination of two sites is equal to the sum of the measures for these sections. The measure takes into account the values for all three criteria. A computational procedure is described that implements a method that does not require a combinatorial enumeration options and ensures the possibility of obtaining a compromise result quickly. The procedure is based on the use of proposed special operation for switching matrices. This operation provides the possibility calculating the effectiveness measure of all possible two-step, then three-step and further k-step paths. The operation is iteratively continued until a route measure connecting the start point to the end point is found. An important additional advantage of method is its ability to use it to find efficient routes in complex transport networks with a large number of intermediate points. In this case, if the transition from one point to another can be carried out through some intermediate point from some of their sets, then the method allows to find the best possible route. Examples of task for different formulations of multicriteria transport task are considered.