Проектирование транспортно-логистических систем, устойчивых к структурным разрушениям

Кочкаров Азрет Ахматович кандидат физико-математических наук доцент, департамент анализа данных и принятия решений, Финансовый университет при Правительстве РФ 125993, Россия, г. Москва, Ленинградский пр., 49 Kochkarov Azret Ahmatovich PhD in Physics and Mathematics Docent, the department of Data Analysis and Decision-Making , Financial University under the Government of the Russian Federation 125993, Russia, g. Moscow, Leningradskii pr., 49 akochkar@gmail.com Другие публикации этого автора     Яцкин Данил Владиленович аспирант, Московский физико-технический институт (национальный исследовательский университет) 141701, Россия, Московская область, г. Долгопрудный, пер. Институтский, 9 Yatskin Danil Vladilenovich Postgraduate student, Moscow Institute of Physics and Technology (National Research University) 141701, Russia, Moskovskaya oblast', g. Dolgoprudnyi, per. Institutskii, 9 danil@frtk.ru

Кочкаров Расул Ахматович кандидат экономических наук доцент, департамент анализа данных и принятия решений, Финансовый университет при Правительстве РФ 125993, Россия, г. Москва, Ленинградский пр., 49 Kochkarov Rasul Ahmatovich PhD in Economics Docent, the department of Data Analysis and Decision-Making, Financial University under the Government of the Russian Federation 125993, Russia, g. Moscow, Leningradskii pr., 49 rasul_kochkarov@mail.ru Другие публикации этого автора

Работа выполнена при поддержке РФФИ (проект КОМФИ № 18-00-01103).

1. Введение

С увеличением масштаба транспортно-логистических систем приобретают актуальность новые для исследователей задачи. Раньше в фокусе изучения находились в основном поиск оптимального решения транспортно-логистических задач и задач выделения оптимальных товаропотоков. В работе Gavish B. и Graves S.C. ^[1] исследуется классическая постановка задачи коммивояжера и новые постановки - задача коммивояжера с несколькими путешественниками, задача доставки груза, задача школьного автобуса и др. Для их решения используется метод множителей Лагранжа, который имеет ограничения - применяется для однокритериальных задач и предполагается выделение достаточных условий условного экстремума, требующих выделения как минимум вторых производных функции Лагранжа. Статья Cota P.M. ^[2] посвящена планированию грузовых перевозок с учетом затрат времени на перегрузочных станциях, сформулирована двухэтапная задача с целью минимизации общего времени - доставки и перегрузки. Постановка задачи представлена в виде целочисленной задачи линейного программирования, предложен эвристический полиномиальный алгоритм. В статье Roy S.K. ^[3] анализируется стохастическая транспортная задача с множественным выбором, где стоимостные коэффициенты целевой функции и параметры системы ограничений представляются в виде параметров для множественного выбора. И является попыткой сформулировать многокритериальную задачу в постановке задач линейного программирования. В итоге сформулирована нелинейная детерминированная модель и получено оптимальное решение реальной транспортной задачи с фактическими данными на програмном обеспечении Lingo. В классической книге Ford L.R. и Fulkerson D.R. сформулировали основы задачи потоков в сетях, предложенные модели и алгоритмы решения в настоящее время используются в разных областях - транспортных системах, производство и планирование запасов, обработка интернет трафика и др. Авторами Goldberg A.V. и Tarjan R.E. предложен новый метод решения задачи поиска максимального потока с предварительным анализом потоков методом Карзанова. Новый алгоритм показал улучшенные оценки трудоемкости, также для него была предложена параллельная реализация. Вместе с этим, на первый план выходят проблемы, связанные с построением самих транспортно-логистических структур. В современных условиях ведения бизнеса предъявляются более строгие требования к целостности цепочки поставок. Так как сбои в цепочке поставок происходят чаще и с серьезными последствиями для поставщиков, задача структурной устойчивости является крайне актуальной. В исследовании ^[6] предлагается теоретико-графовый подход снижения уязвимости цепочки поставок, рассматриваются количественные оценки. В ^[7] исследуется развитие траспортно-логистических систем с момента их появления до настоящего времени, а также обозначаются основные тренды в этом направлении. В частности, предполагается интеграция транспортно-логистических систем разного уровня и технологий, что приводит к появлению многокритериальных задач на больших данных и соответственно большим вычислениям, отдельной проблемой является появление все большего количества задач, относимых к классу NP-трудных, для исследования которых требуются новые подходы.

В настоящей работе авторами используется инструментарий теории графов для моделирования структуры транспортно-логистической сети, что позволит формулировать многокритериальные постановки транспортных задач и предлагать полиномиальные алгоритмы для их решения. В том числе для некоторых индивидуальных теоретико-графовых задач класса NP-трудных задач существуют эффективные алгоритмы решения.

Основное внимание в исследовании уделяется устойчивости к структурным разрушениям (в терминологиях теории графов и многокритериальной оптимизации на графах). Оценка структурной устойчивости позволит понять, насколько сильно влияет на построенную на систему отказ одного из её узлов или каналов связи и наоборот – как можно изменить структуру системы для того, чтобы она стала работать эффективнее с точки зрения определенных представлений об эффективности и оптимальности.

Практическая ценность оценки и исследования структурной устойчивости транспортно-логистических систем несомненна, однако научные методы к решению подобных задач начали применяться сравнительно недавно ^[8,9]. Исследования проводятся для отдельных задач с собственным набором ограничений, допущений и начальных условий. Однако уровень фундаментальных исследований, касающихся проблемы, не позволяет даже сформировать единую методологию оценки такого понятия, как структурная устойчивость.

Еще более важной задачей является формирование принципов построения транспортно-логистических систем, соответствующих определенным требования к структурной устойчивости, формализованными при помощи выработанной авторами настоящей работы методологии оценки структурной устойчивости. Подход, основанный на этих принципах, позволит строить транспортно-логистические системы, отвечающие актуальным вызовам современного рынка.

2. Математическое описание транспортно-логистических систем и сравнение решений задач на них

Поскольку транспортно-логистическая система представляет из себя множество логистических узлов и связей между ними, представляется естественным описывать такие системы при помощи инструментария теории графов ^[10]. Система представляется в виде графа `G(v,e)`, в роли вершин `{v}` которого будут выступать узлы логистической сети, а в роли ребер `{e}`– связи между ними (каналы). В таком случае основной спектр задач, решаемый на данном графе сводится к поиску на графе определенных структур, обладающих конкретными свойствами потоков, путей, маршрутов, циклов и т.п.

При задании условий каждой задачи, рассматривается множество из `M` элементов задачи, соответствующих объектам, на доставку которых и ориентирована конкретная транспортно-логистическая задача. Для элементов задачи определяется набор из `P` признаков – весовых коэффициентов рёбер графа, важных для решения задачи оптимизации пути.

Начальные условия удобно представлять в виде одной матрицы `I`, представляющей из себя четырехмерную матрицу, состоящую из элементов `I_(ijmp)`, где `i=1,2,...,N,` `j=1,2,...,N,` `m=1,2,...,M,` `p=1,2,...,(P+1)`. Индексы `i` и `j` служат для задания ребер (в том числе и петель), `m` – элемента задачи, для которого на данном ребре определяется один из признаков, определяемых индексом `p`. При этом к изначально рассматриваемым признакам `P` добавляется еще один – пропускная способность соответствующего ребра по отношению к элементу задачи. Для каждой задачи рассматривается поток элементов задачи `f->`, задающий численные значения, соответствующие каждому элементу задачи. Соответственно, критерий оптимизации может быть записан как `K(I,f->)`, а задача будет представляться в виде`K(I,f->)->min`.

Для каждого потока элементов задачи `f->` может быть найдено решение `s->(I,f->)` транспортно-логистической задачи. Решение представляет из себя некую графовую структуру, как правило – путь на графе, прохождение по которому решает исходную задачу доставки товара между точками, формализованную при помощи аппарата теории графов. В общем случае рассматривается общий путь для всех элементов задачи, однако при возможности поиска для каждого элемента своего пути, задача превращается в вырожденную для каждого из M элементов задачи и происходит совокупное решение M аналогичных задач с вырожденными условиями (с рассмотрением только одного элемента задачи), что порождает упрощение задач вследствие понижения размерности матрицы `I`.

Следует отметить, что такое представление допустимо и отдельно – для задачи поиска наименее затратного пути, и, отдельно – для задачи поиска оптимального потока по каналам с определённой пропускной способностью. Такие задачи рассматриваются как частный, вырожденный случай более общей задачи.

С точки зрения устойчивости системы к структурным разруешниям, имеет смысл рассматривать не `K(I,f->)`, а непосредственно `K(s->)`. Тогда оптимальное решение `(s_(opt))->` будет соответствовать максимальному значению критерия оптимизации `K_(opt)=K(s_(opt)->)`. Кроме того, `s_(opt)->` будет соответствовать решению описанной ранее задачи `K(I,f->)->max`.

В таком случае эффективности каждого решения может быть сравнена с эталонным при помощи вычисления коэффициента эффективности `k_(эфф)=(K(s->))/(K_(opt))`. Аналогичным образом можно сравнить любые `2`решения.

В каждой транспортно-логистической задаче, как правило, представляет интерес именно оптимальное решение и его изменение. Соответственно, можно обозначить изначальное оптимальное решение как `s_(0)->`. В таком случае если после структурного изменения оптимальное решение изменилось на `s_(1)->`, можно говорить о влиянии такого структурного изменения. Влияние оценивается коэффициентом влияния, аналогичным коэффициенту эффективности решения: `k_(вл)=(K(s_(1)->))/K(s_(0)->)).`

Следует отметить, что в общем случае `k_(вл)` принимает значения в интервале `[[0,+oo)]`. Однако при рассмотрении процессов структурного разрушения, величина `K(s_(1)->)` не может превысить `K(s_(0)->)`, а значит, значения `k_(вл) ` лежат на отрезке от нуля до единицы.

3. Понятие структурной устойчивости

По своей сути все процессы структурного разрушения можно представить как суперпозицию элементарных процессов разрушения графовых структур – удаления ребер и/или вершин. При этом в общем случае для систем, описываемых динамическими графами, можно рассматривать также структурные изменения, связанные с добавлением новые ребер и вершин в комбинации с удалением, но именно для транспортно-логистических задач такое представление не имеет смысла. Также стоит отдельно отметить процессы изменения веса рёбер – они оказывают влияние на решения транспортно-логистических задач, но называть их процессами структурного разрушения некорректно. Однако предлагаемый в рамках работы подход применим в том числе и для процессов изменения веса ребер, при которых новое оптимальное решение поставленной транспортно-логистической задачи `k_(вл)=(K(s_(1)->))/K(s_(0)->))` находятся на отрезке от нуля до единицы.

Операции удаления вершины `v_(i)` и удаления ребра `e_(ij)` соответствует изменение значений `I_(ijmp)` на `0` или `oo` в зависимости от смысла соответствующего значения `p` (например, время доставки по соответствующему каналу становится бесконечным, а пропускная способность - нулевой). Стоит отметить, что эти операции могут быть актуальными только для некоторых элементов задачи `m`.

Для каждого такого процесса можно в результате поиска оптимальных решений на соответствующих графовых структурах рассчитать коэффициент влияния соответствующего процесса на транспортно-логистическую задачу `k_(вл)`.

Рассмотрим два пограничных случая ( `k_(вл)=0` и `k_(вл)=1`).

Очевидно, что если удаляемые рёбра никак не связаны с найденным оптимальным решением, не лежат на заданных этим решением оптимальных маршрутах и критических путях, никакого влияния на найденное решение процессы такого разрушения оказывать не будут. Оптимальное решение останется прежним и систему можно будет назвать устойчивой к такому виду структурных разрушений ( `k_(вл)=1` ).

С другой стороны, процессы структурного разрушения могут произойти таким образом, что буде невозможным нахождение какого бы то ни было решения – то есть `k_(вл)=0`, система неустойчива к разрушениям подобного рода.

Гораздо более часто встречается случай, при котором значения `k_(вл)in(0;1)`, то есть, структурное разрушение изменяет оптимальное решение, но нахождение решения всё ещё возможно. В таком случае необходимо эвристически определить барьер `k_(бар)` – такое значение коэффициента влияния, что для каждого процесса структурного разрушения при `k_(вл)<k_(бар)` транспортно-логистическая система будет считаться неустойчивой к таким структурным разрушениям, а при `k_(вл)>=k_(бар)` – устойчивой. При этом, поскольку процессы структурного разрешения являются случайными, не имеет большого смысла рассматривать устойчивость системы по отношению к конкретному структурному разрушению.

Наибольшей практической ценностью обладает определение структурной устойчивости по отношению к какому-то типу структурных разрушений (например, удалению `N` вершин/рёбер). В таком случае исследуются все возможные процессы разрушения такого типа на выбранной структуре и в качестве `k_(вл)` выбирается наименьшее значение, что соответствует наибольшему влиянию разрешения на изменение эффективности оптимального решения.

4. Проектирование транспортно-логистических систем с заданными параметрами структурной устойчивости

О структурной устойчивости транспортно-логистических систем не имеет смысла говорить без определения конкретной задачи, которая в этой системе решается `K(I,f->)->min`, а также без определенного барьерного значения `k_(бар)`, превращающего оценку влияния того или иного процесса структурного изменения на решение задачи `s->` в бинарную операцию, делается вывод об устойчивости или неустойчивости системы для данной конкретной задачи.

Тем не менее, более актуальной является обратная задача – построение систем, устойчивых к процессам структурного разрушения. Как правило, подобные системы создаются не для одной задачи, поэтому говорить об определенных потоках элементов задачи `f->` не имеет смысла. Тем не менее, при определённом `k_(бар)` для каждого `f->` можно сделать вывод об устойчивости той или иной системы `I` к определенным процессам структурного разрешения при решении задачи `K(I,f->)->min`. Для того, чтобы произвести подобные оценки в общем виде, необходимо избавиться от необходимости знания точных значений `f->`.

Поток элементов задачи `f->` представляет из себя числовые значения, соответствующие каждому элементу задачи, а также начальные и конечные точки для этих элементов. Иными словами, на практике с помощью `f->` определяется (или задается) точка отправления и точка назначения определенного груза и количество этого груза в неких условных единицах.

Можно показать, что функция `K(I,f->)` является строго неубывающей при фиксации всех параметров и переменных, кроме числовых значений, определяемых потоком `f->`. Таким образом, при увеличении числовых значений, а иначе говоря, при увеличении необходимого к перевозке объема товара, значение коэффициента оптимизации остается прежним или возрастает, и наоборот – при уменьшении становится ближе к оптимуму. Таким образом, если транспортно-логистическая система является устойчивой для определённого потока элементов задачи `f->`, она будет устойчивой также и для потока `f_(0)->`, если соответствующие числовые значения для потока `f_(0)->` не больше, чем для потока `f->`.

На практике уместно говорить о максимальных логистических потоках товаров, которые способна выдерживать транспортно-логистическая система. Представление о них можно получить при исследовании системы уже не на структурную устойчивость, а на устойчивость к масштабированию потоков товаров. При этом направление потоков (точки отправления и назначения товаров), при заранее неизвестных условиях задачи, может быть любым.

Таким образом, для того, чтобы утверждать, что построенная система `I` устойчива к процессам структурного разрушения для соответствующих максимальных объемах потоков товаров и при заданном значении `k_(бар)`, необходимо исследовать решения задачи `K(I,f->)->min` и оценивать соответствующую величину `k_(вл)` для значений `f->` с числовыми значениями, соответствующих максимальным объемам потоков товаров для всех возможных маршрутов перемещения этих товаров (точек отправления и назначения).

Был проведен компьютерный эксперимент, в рамках которого было случайным образом сгенерировано (посредством генерации значений `{I_(ijmp)})`более `1000000` транспортно-логистических систем с числом вершин от `50` до `100`.

Проведенный компьютерный эксперимент показывает, что значительная часть транспортно-логистических систем (более 88% при выбранном значении `k_(бар)=0,81`) устойчивы к процессам элементарных структурных разрушений (удаление ребер или вершин). При этом наилучшие результаты показали системы, в которых изначально существовало 1 и более непересекающихся c оптимальным по вершинам решений для которых `K(s->)` отличается от оптимального не более, чем на `5,1%` для соответствующих задач. Среди таких систем неустойчивых не оказалось. Среди систем, в которых для решения конкретных задач находится 2 и более непересекающихся по ребрам решений, процент устойчивых составил `99,99%`.

Поскольку процессы структурного разрушения можно представлять как суперпозицию процессов элементарных структурных разрушений (соответствующих итераций), на основании компьютерного эксперимента можно сделать важный вывод.

Для построения системы, устойчивой к определенным процессам структурных разрушений, необходимо, чтобы на каждой итерации разрушения в системе между каждыми двумя вершинами решение задачи `K(I,f->)->min` для максимальных значений потока элементов задачи существовал как минимум один путь, не пересекающийся с оптимальным по вершинам, для которого `K(s->)` отличается от оптимального не более, чем на `5,1%`.

5. Заключение

В работе предложен способ оценки структурной устойчивости транспортно-логистических систем, позволяющий учитывать явления структурной динамики при изучении таких систем. Введен критерий классификации систем на устойчивые и неустойчивые по отношению к определенному типу структурных изменений и/или разрушений соответственно.

Исследована проблема построения динамических систем с заданными характеристиками устойчивости к определенным воздействиям. Проведен компьютерный эксперимент, на базе которого сформулирован принцип построения транспортно-логистических систем, позволяющий соблюдать заранее определенные требования таких систем к показателям структурной устойчивости.

Полученные результаты закладывают фундамент для исследований зависимости показателей устойчивости систем к тем или иным структурным разрушениям как от характеристик самих систем, так и от значений максимального объема товаров, для которого рассматривается структурная устойчивость транспортно-логистических систем.

Данная работа может представлять интерес исследователям в области структурно-динамического моделирования транспортно-логистических систем, многокритериальной теоретико-графовой оптимизации и оценки структурной устойчивости задач и их решений. С практической точки зрения, предложенный инструментарий, может быть применен специалистами на фактических данных для оценки структурной устойчивости транспортно-логичестической системы.