The graph usage to solving logistic problems
Table of contents
Share
Metrics
The graph usage to solving logistic problems
Annotation
PII
S265838870007441-8-1
DOI
10.33276/S265838870007441-8
Publication type
Article
Status
Published
Authors
Maria Burilina 
Affiliation: CEMI RAS
Address: Russian Federation, Moscow, Nakhimovsky prospekt, 47
Edition
Abstract

The international community and a number of countries have come forward to be partners and territorial units in the construction of this path. The aim of this work is to analyze the use of graph theory to solve logistic problems and propose a methodology for using graphs to build the New Silk Road.

Keywords
one belt - one way, silk road, graph, transport network, logistics.
Received
17.12.2019
Date of publication
07.02.2020
Number of characters
11577
Number of purchasers
11
Views
225
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

1 Введение
2 Данная методология предполагает, что при построении нового шелкового пути необходимо учитывать уже имеющиеся города и поселения, границы государств и уникальность географического рельефа. Помимо этого, с помощью построения графов до ближайших поселений и источников водоемов можно создавать новые уникальные природно-реакционные и туристические зоны.
3 Ранее в работе [2] предлагалось создать особые зоны, которые привлекут новую рабочую силу и создадут уникальную экономическую зону на территории Евразийского континента, однако это может быть применительно и для нового шелкового пути. Китайские власти инвестируют в этот проект с 2014г., однако до сих пор ведутся споры об окончательном маршруте и его географии. В основе исследования были изучены теоретические методы построения методологии, такие как анализ, обобщение, методы моделирования логистической цепи на графах и другие.
4 В работе [3] рассматривают городскую сеть транспорта. Вершины графов строятся следующим образом: к ним применяют микро- и микрорайонирование. За микрорайонирование принимается вершина - центр района. В результате исследования была построена математическая модель транспортной задачи на графах, авторы работы уверены, что это позволит применять систему компьютерного моделирования для решения проблемы оптимизации перевозок грузов.
5 В работе [4] в качестве модели пространственной структуры крупномасштабной транспортной сети (КТС) используются предфрактальные графы, в основе которых лежит принцип масштабной инвариантности. В основе КТС лежит принцип иерархической организации территорий. При исследовании КТС в масштабах страны, на первом этапе рассматриваются дороги, связывающие округа. На втором этапе рассматривается сеть дорог, соединяющих субъекты округов. На третьем этапе рассматриваются дороги, связывающие определенные районы выбранного округа, а на последнем- дороги в масштабе населенных пунктов. В результате исследования обосновано преимущество использования предфрактальных графов в моделировании структуры КТС.
6 Теория графов находит применение в геоинформационных системах (ГИС), ведь именно с создания графа дорожной сети начинается технология построения сети логистических маршрутов, частным случаем которого является общественный транспорт. Из имеющихся линий городского транспорта формируется граф транспортной развязки и городских дорог, с вершинами в местах пересадках, с дугами в качестве маршрутных линий.
7 В работе [5] авторы используют метод построения графов дорожной сети, в качестве визуализации используется OpenStreetMap. В качестве инфраструктурного объекта выбран городской транспорт Тюменской области. Данные об общественном транспорте были оцифрованы: остановки городского транспорта преставляли вершины: а ребрами выступали маршрутные линии городского транспорта. Таким образом, можно было выявить наиболее транспортно-развитые районы и районы с низкой занятостью городского транспорта и труднодоступные. С помощью полученного графа авторы рекомендуют строить маршруты удаленности и доступности в городе Тюмень.
8 Для построения графа транспортной сети в работе [6] также используются визуализация OpenStreetMap с базой данных о транспортной сети, однако уже на примере Омского региона. Изначально граф включал в себя боле 14 тыс. узлов, но из-за недостаточности информации его количество узлов авторы сократили до 37 тыс., что по-прежнему делает его довольно массивным. Авторы прибегают к методу кросс-ассоциаций и сжатии данных согласно принципу минимизации (а именно minimum description length).
9 В качестве результатов авторы выдвигают кластеризацию графа, расположенную на главной диагонали матрицы, всего таких кластеров 15 кластеров, они являются основными транспортно-развитыми районами Омской области, помимо этого в ходе исследования было построено древо Штейнера. Свойство этого древа- построение на неориентированном графе с заданными n концевыми узлами. При анализе структуры транспортной сети был применен кластерный анализ: авторы работы пришли к тому, что лежащие на главной диагонали матрицы кластеры могут выступать логистическими центрами.
10 Одной из наиболее актуальных задач, стоящих перед компаниями, занимающимися производством, транспортировкой и продажей различных видов товаров, является задача формирования оптимальных расписаний перевозок между оптовыми складами при наличии ограничений.В процессе работы осуществляется поиск рациональных решений методом модельных событий. В работе [7] решение задачи базируется на использовании двух графов: 1-й граф соответствует реальной логистической сети, в вершинах графа организуются: обслуживание транспортной сети, очереди на обслуживание, план пополнения. 2-й граф – граф модельных событий. Вершины соответствуют настоящим событиям, дуги показывают планирование следующих событий. Оптимизация осуществляется эвристическим алгоритмом на уровне правил принятия решений по планированию тех или иных событий. Транспортный граф в исходных данных задается в формате JSON. Метод модельных событий позволяет относительно быстро построить набор допустимых расписаний и выбрать из них наилучшее.
11 В работе [8] авторы поднимают вопрос оптимизации в доставке товаров железнодорожным транспортом. Задачей является составить железнодорожное расписание с целью минимизации опоздания доставки грузов. Железнодорожный транспорт не привержен погодным условиям, однако из-за пополняемости линий на определенных отрезках дороги, могут случаться задержки. При фиксированных расписаниях предполагается, что маршруты движения грузовых составов также фиксированы. Для постановки задачи авторами используется пространственно-временной направленный граф.
12 Согласно [9] универсальность метода исследования структуры с применением сетевого графа характеризует использование показателей различного измерения, теоретическую значимость. Перед построением модели авторы разделили логистические объекты на различные категории кластеры, после чего была применена их методика. Граф считается сложным, когда в нем одновременно рассматривается несколько категорий и кластеров. Авторы в своей работе апробируют, что предложенная ими модель может применяться на различных видах транспорта с терминально-складской инфраструктурой.
13 В работе [10] граф применяют для построения деталей и выявления ошибок, связанных с их изготовлением для конечного образца продукции. В качестве частного случая каждой детали изделия принимается дерево – конечный связный неориентированный граф, не имеющий циклов, в то время как совмещенный граф и будет графом технологических размерных цепей.
14 В работе [11] были рассмотрены основные понятия и задачи по теме решения транспортных задач графами. В том числе и задача семи мостов Кенигсберга. Эйлер однажды задумался: «Можно ли перейти из любой части города Кенигсберга через каждый из мостов только один раз, и вернуться в отправную точку?» Ответ Эйлера был отрицательным. Он отметил отдельные части города вершинами, а мосты сделал связью между ними. Тем самым, он создал граф, сам того не зная. Однако, помимо этого существует проблема китайского почтальона, суть которой состоит в том, что почтальон хочет перемещаться по любой дороге в городе, для чтобы разноса писем в самый короткий срок. По такому же принципу сводят к минимуму количество километров в пути снегоуборочной машины. При помощи графов можно оптимизировать время и затраты на доставку многих видов продукции.
15 Авторы работы [12] утверждают, что метод графов чаще всего используется для оптимального планирования перевозок грузов при минимизации затрат и времени, а так же для оптимального коэффициента разделения объемов производства, прибыли и дохода. Допустим, у нас есть взвешенная диаграмма с определенным набором вершин и дуг. Если речь идет о двудольной и полной транспортной сети, то все ее вершины разделяются на две группы: узлы доставки и узлы приема. Основной вопрос состоит в том, чтобы определить размер транспорта, который сведет к минимуму общую стоимость перевозки. По мнению авторов, данная проблема может быть решена симплекс-методом, но в этом случае это будет неэффективно. Чаще всего используется метод северо-западного угла. Он нужен для того, чтобы найти базовое решение проблемы.
16 Основной темой статьи [13] является применение алгоритма Дейкстры при построении логистических маршрутов. Алгоритм работает пошагово - на каждом шаге он посещает одну вершину. Предпоследней посещается вершина, выбранная с минимальной меткой (расстоянием до выбранной ранее), далее авторами рассматривается длина ребра и его расстояния до соседней вершины: после чего алгоритм повторяется заново.
17 В работе [14] был описан метод критического планирования. Он представляет собой метод управления проектами и его сроками. Метод широко используются в промышленности, а также в крупных строительных проектах.
18 В работе [15] произведена количественная имитационная модель порта, включающая в себя 5 фаз его развития:
  • Традиционный порт.
  • Порт с участием навалочного груза.
  • Наличие в порту укрупненных грузовых единиц (УГЕ).
  • Наличие в порту транзитного терминал.
  • Специализация терминалов по типам продукции.
Не смотря на разнообразие транспортных вопросов, решаемых при помощи графов, рассмотренных выше, остается несомненным тот факт, что при проектировании транспортных узлов «Один пояс - Один путь» необходимо использовать комплекс математических моделей, в том числе для поиска оптимальных вершин графа, в которых будет располагаться остановочный пункт, включающий в себя особую торговую зону, необходимо учитывать следующие показатели:
  • Удаленность от имеющихся населенных пунктов
  • Покупательскую способность ближайших населенных пунктов
  • Разнообразие транспортной сети вокруг потенциальной вершины графа (в которой будет остановочный и распределительный пункт транспортной сети)
  • Географический рельеф, позволяющий проложить наиболее удобный скоростной транспорт
  • Безопасность региона.
19 Выводы
20 В рамках развития транспортной сети и анализа регионального развития следует рассматривать метод микро- и макрорайонирования, выделяя вершинами графа- центры новых образований и городских поселений, которые могут возникнуть в ходе строительства нового шелкового пути как на территории РФ, так и на территории других стран. Такие вершины можно будет оценить с точки зрения насыщенности ребрами и выявить дополнительные маршруты к центрам вершин. Это позволит создать не только перевалочные или разгрузочные зоны, но и ускорить поставку товаров другим видом транспорта. В настоящий момент карта железных дорог имеет структуру, позволяющую развивать и дополнять различными отрезками (ребрами графа) транспортную сеть, не только «горизонтально» с востока на запад, но и «вертикально» с юга на север, это позволит создать на крайнем Севере РФ все условия для нового порта перегрузки товаров из Китая, при этом создаст новые высокооплачиваемые рабочие места в труднодоступном регионе.

References

1. Sovmestnoe stroitel'stvo «Odnogo poyasa, odnogo puti»: ideya, praktika i vklad Kitaya. – maj 2017 g. – [ehlektronnyj resurs] //URL:https://www.yidaiyilu.gov.cn/wcm.files/upload/CMSydylyw/201705/201705110545004.pdf (data obrascheniya 31.10.2019)

2. Burilina M.A. Kontseptsiya razvitiya otnoshenij i umen'shenie tarifov dlya aviakompanij, vkhodyaschikh v sostav transgranichnykh territorij. Strategicheskoe planirovanie i razvitie predpriyatij. Sektsiya 1: Materialy Semnadtsatogo vserossijskogo simpoziuma. Moskva 12-13 aprelya 2016. / Pod red. Chl.-korr. RAN G.B. Klejnera.- M.:TsEhMI RAN, 2016.-166 s., s.26-27.

3. Alekseeva Ya.A. Modelirovanie transportnoj zadachi na grafakh // Vitebsk, VGTU. URL: https://cyberleninka.ru/article/n/modelirovanie-krupnomasshtabnoy-transportnoy-seti-predfraktalnymi-grafami (data obrascheniya 21.04.2019)

4. Pavlov D. A. Modelirovanie Krupnomasshtabnoj transportnoj seti predfraktal'nymi grafami // Nauchnyj zhurnal KubGAU, №131(07), 2017. URL: https://cyberleninka.ru/article/v/modelirovanie-krupnomasshtabnoy-transportnoy-seti-predfraktalnymi-grafami (data obrascheniya 21.04.2019)

5. Krektunova M.A Prostranstvennyj analiz seti obschestvennogo transporta na primere goroda Tyumeni // TGU Institut nauk o zemle, 2017. URL: http://www.tmnlib.ru/jirbis/files/upload/books/VKR/2017/InZem/Krektunova_VKR.pdf (data obrascheniya 21.04.2019).

6. M.O. Solntseva, B.G. Kukharenko Primenenie metodov klasterizatsii uzlov na grafakh s razrezhennymi matritsami smezhnosti v zadachakh logistiki // Trudy MFTI, tom 5, №3, 2013. URL: https://mipt.ru/upload/d8d/75-83-arphj8g0g1k.pdf (data obrascheniya 21.04.2019).

7. Bakhtin V.A., Bogdanov I.P. Optimizatsiya perevozok odnorodnoj produktsii mezhdu optovymi skladami // IPM RAN. URL: http://keldysh.ru/papers/2018/prep2018_65.pdf (data obrascheniya 21.04.2019).

8. Lazarev A.A., Musatova E.G. Teoriya raspisanij. Zadachi zheleznodorozhnogo planirovaniya // IPU RAN, 2012. URL: https://www.ipu.ru/sites/default/files/publications/16555/2639-16555.pdf (data obrascheniya 21.04.2019).

9. Malikov O.B., Pokrovskaya O.D. Metodika postroeniya setevogo grafa struktury logisticheskogo ob'ekta // Mir transporta, tom 15, №1, 2017. URL: https://mirtr.elpub.ru/jour/article/viewFile/1115/1391 (data obrascheniya 21.04.2019)

10. Psigin Yu.V. Matematicheskoe modelirovanie v mashinostroenii // Uchebnoe posobie. – Ul'yanovsk: UlGTU, 2014. URL: http://venec.ulstu.ru/lib/disk/2015/9.pdf (data obrascheniya 21.04.2019)

11. Parlinska M., Parlinska A. Graph theory and agribusiness // Warsaw University of Live Sciences, 2018. URL: http://llufb.llu.lv/conference/economic_science_rural/2018/Latvia_ESRD_47_2018-476-482.pdf (data obrascheniya 21.04.2019).

12. Zbigniew T. Ekonometria. Zagadnienie transportowe. URL: http://tarapata.strefa.pl/p_ekonometria/download/ekonometria_cz3_4.pdf (data obrascheniya 21.04.2019).

13. Liu Xiao-Yan, Chen Yan-Li. Application of Dijkstra Algorithm in Logistics Distribution Lines // Henan Polytechnic University,JiaoZuo, China, 2010. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.403.7842&rep=rep1&type=pdf (data obrascheniya 21.04.2019)

14. Network models. The critical-path method // Cambridge, MA USA. URL: http://web.mit.edu/15.053/www/AMP-Chapter-08.pdf (data obrascheniya 21.04.2019).

15. Galin Aleksandr Valentinovich Obobschennaya imitatsionnaya model' protsessa razvitiya portov // Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova. 2015. №6 (34). URL: https://cyberleninka.ru/article/n/obobschennaya-imitatsionnaya-model-protsessa-razvitiya-portov (data obrascheniya: 05.11.2019).