Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Theoretical and Applied Economics
Reference:

Designing the transport and logistics systems resistant to structural failures

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
Other publications by this author
 

 
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
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
Other publications by this author
 

 

DOI:

10.25136/2409-8647.2020.1.32202

Received:

14-02-2020


Published:

21-02-2020


Abstract: This article is dedicated to designing of the transport and logistics systems with built-in resistance to structural failures. The sustainability indicators reflect the impact of the failure of one or several hubs (communication channels) upon working capacity of the already functioning system. In the process of designing the system, the sustainability indicators also provide opportunities for optimizing its structure from the perspective of set reliability expectations. The authors give attention to the modeling of the transportation and logistics system on the basis of theoretical-graph toolset, as well as propose sustainability indicators and articulation of optimization task. The structure of transportation and logistics system is described using the instruments of graph theory, definition of the task is presented using the criteria of optimization theory, and limitations are the feasible solutions on graphs are established in the matrix form. The authors suggest a theoretical-graph description of the structure of the transportation and logistics systems, propose multiobjective goal setting, and introduce the concept of structural stability based on the indexes and their threshold values. Proposal is made on the approach towards designing the transport and logistics systems with set parameters of structural stability and tried it on test data.


Keywords:

transport and logistics system, structural stability, graph, search for a solution, sustainability indicator, stability, structural failure, model, engineering, computer experiment


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. Заключение

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

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

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

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

References
1. Gavish B., Graves S. C. The travelling salesman problem and related problems. 1978. 30 p.
2. Cota P.M. et al. Time-indexed formulation and polynomial time heuristic for a multi-dock truck scheduling problem in a cross-docking center //Computers & Industrial Engineering. 2016. Vol. 95. pp. 135-143.
3. Roy S.K. Transportation problem with multi-choice cost and demand and stochastic supply // Journal of the Operations Research Society of China. 2016. Vol. 4. No. 2. pp. 193-204.
4. Ford L.R. Jr., Fulkerson D.R., Flows in Networks. Princeton University Press. 1962. 194 p.
5. Goldberg A.V., Tarjan R.E.. A new approach to the maximum-flow problem // Journal of the ACM. ACM Press. 1988. Vol. 35, No. 4. pp. 921-940.
6. Wagner S.M., Neshat N. Assessing the vulnerability of supply chains using graph theory // International Journal of Production Economics. 2010. Vol. 126. No. 1. pp. 121-129.
7. Speranza M.G. Trends in transportation and logistics // European Journal of Operational Research. 2018. Vol. 264. No. 3. pp. 830-836.
8. Jacyna I., Zak J. Selected aspects of the optimization the structure of logistic system // 2011 21st International Conference on Systems Engineering. IEEE. 2011. pp. 438-441.
9. Guze S. An application of the selected graph theory domination concepts to transportation networks modelling. Sci. J. Marit. Univ. Szczecin. 2017. No. 52 (124). pp. 97-102.
10. Kochkarov R.A., Kochkarov A.A., Yatskin D.V. Issledovanie effektivnosti reshenii transportnologisticheskikh zadach i voprosov strukturnoi ustoichivosti // Khronoekonomika. 2019. № 5 (18). S. 5-14.