Файл: Решение логистических задач при помощи графов Бурилина Мария Алексеевна Центральный экономикоматематический институт ран.pdf

Вестник ЦЭМИ 2013-2023
ISSN 2079-8784
URL - http://ras.jes.su
Все права защищены
Выпуск 3 Том . 2019 1
Выпуск 3 Том - 2019
Решение логистических задач при помощи графов
Бурилина Мария Алексеевна
Центральный экономико-математический институт РАН
Российская Федерация, Москва, Нахимовский проспект, 47
Аннотация
Стремительное развитие товаропотока из Китая в Европу задает тенденции к развитию транспортной инфраструктуры и технологическому прорыву в строительстве нового пути. Председатель КНР Си Цзиньпин выдвинул инициативу осенью 2013г. по совместному строительству «Один пояс, один путь» [1] - название которого целенаправленно было взято из истории, чтобы привлечь внимание общественности и таким образом подчеркнуть масштабность данного проекта. Международное сообщество и ряд стран выдвинулись быть партнерами и территориальными единицами в строительстве данного пути. Целью данной работы является провести анализ применения теории графов для решения логистических задач и предложить методологию использования графов для построения Нового шелкового пути.
Ключевые слова:
один пояс- один путь, шелковый путь, графы, транспортная сеть,
логистика.
Дата публикации:
07.02.2020
Источник финансирования:
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект №17-06-00463 А.
Ссылка для цитирования:
Бурилина М. А. Решение логистических задач при помощи графов // Вестник ЦЭМИ –
2019. – Выпуск 3 [Электронный ресурс]. URL: https://cemi.jes.su/S265838870007441-8-1
(дата обращения: 06.06.2023). DOI: 10.33276/S265838870007441-8
Введение

2 3
4 5
6 7
8
Данная методология предполагает, что при построении нового шелкового пути необходимо учитывать уже имеющиеся города и поселения, границы государств и уникальность географического рельефа. Помимо этого, с помощью построения графов до ближайших поселений и источников водоемов можно создавать новые уникальные природно-реакционные и туристические зоны.
Ранее в работе [2] предлагалось создать особые зоны, которые привлекут новую рабочую силу и создадут уникальную экономическую зону на территории Евразийского континента, однако это может быть применительно и для нового шелкового пути.
Китайские власти инвестируют в этот проект с 2014г., однако до сих пор ведутся споры об окончательном маршруте и его географии. В основе исследования были изучены теоретические методы построения методологии, такие как анализ, обобщение, методы моделирования логистической цепи на графах и другие.
В работе [3] рассматривают городскую сеть транспорта. Вершины графов строятся следующим образом: к ним применяют микро- и микрорайонирование. За микрорайонирование принимается вершина - центр района. В результате исследования была построена математическая модель транспортной задачи на графах, авторы работы уверены, что это позволит применять систему компьютерного моделирования для решения проблемы оптимизации перевозок грузов.
В работе [4] в качестве модели пространственной структуры крупномасштабной транспортной сети (КТС) используются предфрактальные графы, в основе которых лежит принцип масштабной инвариантности. В основе КТС лежит принцип иерархической организации территорий. При исследовании КТС в масштабах страны, на первом этапе рассматриваются дороги, связывающие округа. На втором этапе рассматривается сеть дорог, соединяющих субъекты округов. На третьем этапе рассматриваются дороги,
связывающие определенные районы выбранного округа, а на последнем- дороги в масштабе населенных пунктов. В результате исследования обосновано преимущество использования предфрактальных графов в моделировании структуры КТС.
Теория графов находит применение в геоинформационных системах (ГИС), ведь именно с создания графа дорожной сети начинается технология построения сети логистических маршрутов, частным случаем которого является общественный транспорт.
Из имеющихся линий городского транспорта формируется граф транспортной развязки и городских дорог, с вершинами в местах пересадках, с дугами в качестве маршрутных линий.
В работе [5] авторы используют метод построения графов дорожной сети, в качестве визуализации используется OpenStreetMap. В качестве инфраструктурного объекта выбран городской транспорт Тюменской области. Данные об общественном транспорте были оцифрованы: остановки городского транспорта преставляли вершины: а ребрами выступали маршрутные линии городского транспорта. Таким образом, можно было выявить наиболее транспортно-развитые районы и районы с низкой занятостью городского транспорта и труднодоступные. С помощью полученного графа авторы рекомендуют строить маршруты удаленности и доступности в городе Тюмень.
Для построения графа транспортной сети в работе [6] также используются визуализация OpenStreetMap с базой данных о транспортной сети, однако уже на примере
Омского региона. Изначально граф включал в себя боле 14 тыс. узлов, но из-за недостаточности информации его количество узлов авторы сократили до 37 тыс., что по- прежнему делает его довольно массивным. Авторы прибегают к методу кросс-ассоциаций и сжатии данных согласно принципу минимизации (а именно minimum description length).

9 10 11 12 13 14
В качестве результатов авторы выдвигают кластеризацию графа, расположенную на главной диагонали матрицы, всего таких кластеров 15 кластеров, они являются основными транспортно-развитыми районами Омской области, помимо этого в ходе исследования было построено древо Штейнера. Свойство этого древа- построение на неориентированном графе с заданными n концевыми узлами. При анализе структуры транспортной сети был применен кластерный анализ: авторы работы пришли к тому, что лежащие на главной диагонали матрицы кластеры могут выступать логистическими центрами.
Одной из наиболее актуальных задач, стоящих перед компаниями,
занимающимися производством, транспортировкой и продажей различных видов товаров,
является задача формирования оптимальных расписаний перевозок между оптовыми складами при наличии ограничений.В процессе работы осуществляется поиск рациональных решений методом модельных событий. В работе [7] решение задачи базируется на использовании двух графов: 1-й граф соответствует реальной логистической сети, в вершинах графа организуются: обслуживание транспортной сети,
очереди на обслуживание, план пополнения. 2-й граф – граф модельных событий.
Вершины соответствуют настоящим событиям, дуги показывают планирование следующих событий. Оптимизация осуществляется эвристическим алгоритмом на уровне правил принятия решений по планированию тех или иных событий. Транспортный граф в исходных данных задается в формате JSON. Метод модельных событий позволяет относительно быстро построить набор допустимых расписаний и выбрать из них наилучшее.
В работе [8] авторы поднимают вопрос оптимизации в доставке товаров железнодорожным транспортом. Задачей является составить железнодорожное расписание с целью минимизации опоздания доставки грузов. Железнодорожный транспорт не привержен погодным условиям, однако из-за пополняемости линий на определенных отрезках дороги, могут случаться задержки. При фиксированных расписаниях предполагается, что маршруты движения грузовых составов также фиксированы. Для постановки задачи авторами используется пространственно- временной направленный граф.
Согласно [9] универсальность метода исследования структуры с применением сетевого графа характеризует использование показателей различного измерения,
теоретическую значимость. Перед построением модели авторы разделили логистические объекты на различные категории кластеры, после чего была применена их методика. Граф считается сложным, когда в нем одновременно рассматривается несколько категорий и кластеров. Авторы в своей работе апробируют, что предложенная ими модель может применяться на различных видах транспорта с терминально-складской инфраструктурой.
В работе [10] граф применяют для построения деталей и выявления ошибок,
связанных с их изготовлением для конечного образца продукции. В качестве частного случая каждой детали изделия принимается дерево – конечный связный неориентированный граф, не имеющий циклов, в то время как совмещенный граф и будет графом технологических размерных цепей.
В работе [11] были рассмотрены основные понятия и задачи по теме решения транспортных задач графами. В том числе и задача семи мостов Кенигсберга. Эйлер однажды задумался: «Можно ли перейти из любой части города Кенигсберга через каждый из мостов только один раз, и вернуться в отправную точку?» Ответ Эйлера был отрицательным. Он отметил отдельные части города вершинами, а мосты сделал связью между ними. Тем самым, он создал граф, сам того не зная. Однако, помимо этого

15 16 17 18 19 20
существует проблема китайского почтальона, суть которой состоит в том, что почтальон хочет перемещаться по любой дороге в городе, для чтобы разноса писем в самый короткий срок. По такому же принципу сводят к минимуму количество километров в пути снегоуборочной машины. При помощи графов можно оптимизировать время и затраты на доставку многих видов продукции.
Авторы работы [12] утверждают, что метод графов чаще всего используется для оптимального планирования перевозок грузов при минимизации затрат и времени, а так же для оптимального коэффициента разделения объемов производства, прибыли и дохода. Допустим, у нас есть взвешенная диаграмма с определенным набором вершин и дуг. Если речь идет о двудольной и полной транспортной сети, то все ее вершины разделяются на две группы: узлы доставки и узлы приема. Основной вопрос состоит в том, чтобы определить размер транспорта, который сведет к минимуму общую стоимость перевозки. По мнению авторов, данная проблема может быть решена симплекс-методом,
но в этом случае это будет неэффективно. Чаще всего используется метод северо- западного угла. Он нужен для того, чтобы найти базовое решение проблемы.
Основной темой статьи [13] является применение алгоритма Дейкстры при построении логистических маршрутов. Алгоритм работает пошагово - на каждом шаге он посещает одну вершину. Предпоследней посещается вершина, выбранная с минимальной меткой (расстоянием до выбранной ранее), далее авторами рассматривается длина ребра и его расстояния до соседней вершины: после чего алгоритм повторяется заново.
В работе [14] был описан метод критического планирования. Он представляет собой метод управления проектами и его сроками. Метод широко используются в промышленности, а также в крупных строительных проектах.
В работе [15] произведена количественная имитационная модель порта,
включающая в себя 5 фаз его развития:
Традиционный порт.
Порт с участием навалочного груза.
Наличие в порту укрупненных грузовых единиц (УГЕ).
Наличие в порту транзитного терминал.
Специализация терминалов по типам продукции.
Не смотря на разнообразие транспортных вопросов, решаемых при помощи графов,
рассмотренных выше, остается несомненным тот факт, что при проектировании транспортных узлов «Один пояс - Один путь» необходимо использовать комплекс математических моделей, в том числе для поиска оптимальных вершин графа, в которых будет располагаться остановочный пункт, включающий в себя особую торговую зону,
необходимо учитывать следующие показатели:
Удаленность от имеющихся населенных пунктов
Покупательскую способность ближайших населенных пунктов
Разнообразие транспортной сети вокруг потенциальной вершины графа (в которой будет остановочный и распределительный пункт транспортной сети)
Географический рельеф, позволяющий проложить наиболее удобный скоростной транспорт
Безопасность региона.
Выводы
В рамках развития транспортной сети и анализа регионального развития следует рассматривать метод микро- и макрорайонирования, выделяя вершинами графа- центры

новых образований и городских поселений, которые могут возникнуть в ходе строительства нового шелкового пути как на территории РФ, так и на территории других стран. Такие вершины можно будет оценить с точки зрения насыщенности ребрами и выявить дополнительные маршруты к центрам вершин. Это позволит создать не только перевалочные или разгрузочные зоны, но и ускорить поставку товаров другим видом транспорта. В настоящий момент карта железных дорог имеет структуру, позволяющую развивать и дополнять различными отрезками (ребрами графа) транспортную сеть, не только «горизонтально» с востока на запад, но и «вертикально» с юга на север, это позволит создать на крайнем Севере РФ все условия для нового порта перегрузки товаров из Китая, при этом создаст новые высокооплачиваемые рабочие места в труднодоступном регионе.
Библиография:
1. Совместное строительство «Одного пояса, одного пути»: идея, практика и вклад Китая.
– май 2017 г. – [электронный ресурс]
//URL:
https://www.yidaiyilu.gov.cn/wcm.files/upload/CMSydylyw/201705/201705110545004.pdf
(дата обращения 31.10.2019)
2. Бурилина М.А. Концепция развития отношений и уменьшение тарифов для авиакомпаний, входящих в состав трансграничных территорий. Стратегическое планирование и развитие предприятий. Секция 1: Материалы Семнадцатого всероссийского симпозиума. Москва 12-13 апреля 2016. / Под ред. Чл.-корр. РАН Г.Б.
Клейнера.- М.:ЦЭМИ РАН, 2016.-166 с., с.26-27.
3. Алексеева Я.А. Моделирование транспортной задачи на графах // Витебск, ВГТУ. URL:
https://cyberleninka.ru/article/n/modelirovanie-krupnomasshtabnoy-transportnoy-seti- predfraktalnymi-grafami
(дата обращения 21.04.2019)
4. Павлов Д. А. Моделирование Крупномасштабной транспортной сети предфрактальными графами // Научный журнал КубГАУ, №131(07), 2017. URL:
https://cyberleninka.ru/article/v/modelirovanie-krupnomasshtabnoy-transportnoy-seti- predfraktalnymi-grafami
(дата обращения 21.04.2019)
5. Кректунова М.А Пространственный анализ сети общественного транспорта на примере города Тюмени // ТГУ Институт наук о земле, 2017. URL:
http://www.tmnlib.ru/jirbis/files/upload/books/VKR/2017/InZem/Krektunova_VKR.pdf
(дата обращения 21.04.2019).
6. М.О. Солнцева, Б.Г. Кухаренко Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ, том 5, №3,
2013. URL: https://mipt.ru/upload/d8d/75-83-arphj8g0g1k.pdf
(дата обращения 21.04.2019).
7. Бахтин В.А., Богданов И.П. Оптимизация перевозок однородной продукции между оптовыми складами // ИПМ РАН. URL: http://keldysh.ru/papers/2018/prep2018_65.pdf
(дата обращения 21.04.2019).
8. Лазарев А.А., Мусатова Е.Г. Теория расписаний. Задачи железнодорожного планирования // ИПУ РАН, 2012. URL:
https://www.ipu.ru/sites/default/files/publications/16555/2639-16555.pdf
(дата обращения
21.04.2019).

9. Маликов О.Б., Покровская О.Д. Методика построения сетевого графа структуры логистического объекта // Мир транспорта, том 15, №1, 2017. URL:
https://mirtr.elpub.ru/jour/article/viewFile/1115/1391
(дата обращения 21.04.2019)
10. Псигин Ю.В. Математическое моделирование в машиностроении // Учебное пособие.
– Ульяновск: УлГТУ, 2014. URL: http://venec.ulstu.ru/lib/disk/2015/9.pdf
(дата обращения
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
(дата обращения 21.04.2019).
12. Zbigniew T. Ekonometria. Zagadnienie transportowe. URL:
http://tarapata.strefa.pl/p_ekonometria/download/ekonometria_cz3_4.pdf
(дата обращения
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
(дата обращения 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
(дата обращения 21.04.2019).
15. Галин Александр Валентинович Обобщенная имитационная модель процесса развития портов // Вестник государственного университета морского и речного флота им.
адмирала С.О. Макарова. 2015. №6 (34). URL:
https://cyberleninka.ru/article/n/obobschennaya-imitatsionnaya-model-protsessa-razvitiya- portov
(дата обращения: 05.11.2019).

The graph usage to solving logistic problems
Maria Burilina
CEMI RAS
Russian Federation, Moscow, Nakhimovsky prospekt, 47
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.
Publication date:
07.02.2020
Citation link:
Burilina M. The graph usage to solving logistic problems // Vestnik CEMI – 2019. – Issue 3
[Electronic resource]. URL: https://cemi.jes.su/S265838870007441-8-1 (circulation date:
06.06.2023). DOI: 10.33276/S265838870007441-8
Код пользователя: 0; Дата выгрузки: 06.06.2023; URL - http://ras.jes.su/cemi/s265838870007441-8-1 Все права защищены.