Web-приложение для составления оптимального по затратам плана перевозок груза по транспортной сети

Транспортная логистика – это система по организации доставки, а именно по перемещению каких-либо материальных предметов, веществ и пр. из одной точки в другую [1]. Она является важным звеном товарооборота на всех его стадиях, от производства товара (доставка сырья, комплектующих и т.д.) до доставки готовой продукции конечному потребителю [2].

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

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

Актуальность транспортных проблем подтверждается тем, что до 50 % всех затрат на логистику связано с транспортными издержками [4]. Одним из способов сокращения данных затрат является оптимизация плана перевозок. В комбинаторной оптимизации данная задача несет название «Проблема маршрутизации транспорта» (Vehicle Routing Problem, далее – VRP). В данной проблеме задается вопрос: «Каков оптимальный набор маршрутов для парка транспортных средств, которые необходимо пройти для доставки груза заданному набору клиентов?» Целью VRP является минимизация общей стоимости маршрута.

Применение оптимизации маршрутизации транспорта с помощью автоматизированного программного обеспечения дает хорошие результаты. Существует множество применений в промышленности реальных приложений, которые решают задачу VRP. Большое количество таких приложений, как в Северной Америке, так и в Европе, показали, что автоматизация планирования процесса перевозок может обеспечить экономию в размере 5–30% от глобальных транспортных расходов [5].

Целью данной выпускной квалификационной работы (далее – ВКР) является разработка web-приложения, составляющего оптимальный по затратам план перевозок с помощью методов решения задачи маршрутизации транспорта.

Для достижения поставленной цели необходимо:

1) определить постановку задачи,

2) составить математическую модель,

3) изучить существующие методы решения,

4) реализовать алгоритм решения поставленной задачи,

5) определить функциональные требования к приложению,

6) разработать серверную часть приложения и интегрировать в неё реализованный алгоритм,

7) разработать клиентскую часть приложения для ввода входных данных и вывода результата работы алгоритма,

8) протестировать разработанное приложение,

9) провести исследование работы алгоритма в приложении и проанализировать полученные результаты.

ВВЕДЕНИЕ..................................................................................................... 3

1. Обзор литературы....................................................................................... 5

1.1. Определение задачи маршрутизации транспорта.................................. 5

1.2. Варианты задачи маршрутизации транспорта....................................... 6

1.3. Постановка задачи.................................................................................... 7

1.4. Математическая модель........................................................................... 8

1.4. Методы решения поставленной задачи................................................. 10

1.4.1. Точные методы..................................................................................... 10

1.4.2. Эвристические и мета-эвристические методы..................................... 10

2. Реализация алгоритма............................................................................... 12

2.1. Описание алгоритма............................................................................... 12

2.2. Программная реализация алгоритма.................................................... 14

3. Функциональные требования к приложению........................................... 21

4. Разработка серверной части приложения................................................ 23

4.1. Используемые технологии..................................................................... 23

4.2. Структура базы данных......................................................................... 24

4.3. Работа с базой данных........................................................................... 25

4.4. Реализация API....................................................................................... 27

4.5. Интеграция разработанного алгоритма................................................ 28

5. Разработка клиентской части приложения............................................... 29

5.1. Используемые технологии..................................................................... 29

5.2. Архитектура приложения...................................................................... 30

6. Тестирование приложения........................................................................ 37

7. Исследование работы алгоритма.............................................................. 39

ЗАКЛЮЧЕНИЕ............................................................................................. 43

СПИСОК ЛИТЕРАТУРЫ............................................................................. 48

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ.................. 50

ПРИЛОЖЕНИЕ................................................................................................... 51

1) Макаров, М. А. Транспортная логистика / М. А. Макаров, А. В. Мартынюк, А. В. Зарецкий. - Текст : электронный // Актуальные проблемы гуманитарных и естественных наук - 2012. - № 12. - С. 194-198. - URL: https://cyberleninka.ru/article/n/transportnaya-logistika (дата обращения: 09.05.2023).

2) Ачкасова, Л. М. Место и роль транспортной логистики в общей логистической системе / Л. М. Ачкасова. - Текст : электронный // Экономика транспортного комплекса - 2017. – вып. 30. - С. 15-32. - URL: https://cyberleninka.ru/article/n/mesto-i-rol-transportnoy-logistiki-v-obschey- logisticheskoy-sisteme (дата обращения: 09.05.2023).

3) Statista : [сайт] - URL: https://www.statista.com/topics/4383/last-mile- delivery/ (дата обращения: 10.04.2023) - Текст : электронный.

4) Международный журнал экспериментального образования : [сайт] - URL: https://expeducation.ru/ru/article/view?id=11000 (дата обращения: 10.04.2023) - Текст : электронный.

5) Хасл, Г. Геометрическое моделирование, численное моделирование и оптимизация: Прикладная математика в SINTEF : учебник / Г. Хасл, К. А. Ли, Э. Квак. – Берлин : Спрингер Верлаг, 2007. – 398 с. - ISBN 978-3-540-68783-2. - URL: https://books.google.ru/books?id=UMI5GzcNd8wC&q=%22vendors+of+routing+t ools%22&redir_esc=y#v=snippet&q=%22vendors%20of%20routing%20tools%22 &f=false (дата обращения: 10.04.2023) - Текст : электронный.

6) Тот, П. Проблема маршрутизации транспорта : монография / П. Тот, Д. Виго. - Филадельфия: Общество промышленной и прикладной математики, 2002. - 367 с. - ISBN 0-89871-579-- URL: https://industri.fatek.unpatti.ac.id/wp-content/uploads/2019/03/002-The-Vehicle- Routing-Problem-Monograf-on-discrete-mathematics-and-applications-Paolo- Toth-Daniele-Vigo-Edisi-1-2002.pdf (дата обращения: 10.04.2023) - Текст : электронный.

7) Нассер, Э. С. Маршрутизация транспортных средств с временными окнами: обзор точных, эвристических и метаэвристических методов / Э. С. Нассер. - Текст : электронный // Журнал Университета короля Сауда - Наука - 2010. - Т. 22 вып. 3. - С. 123-131. - URL: https://doi.org/10.1016/j.jksus.2010.03.002 (дата обращения: 10.04.2023).

8) Бейкер, Б. М. Генетический алгоритм решения задачи маршрутизации транспортных средств / Б. М. Бейкер, М. А. Айехью. - Текст : электронный // Компьютеры и исследования операций - 2003. - Т. 30 - вып. 5.

- С. 787-800. - URL: https://doi.org/10.1016/S0305-0548(02)00051-5 (дата

обращения: 10.04.2023).

9) MachineLearning.ru : [сайт] - URL: http://www.machinelearning.ru/wiki/index.php?title=Генетический_алгоритм (дата обращения: 10.04.2023) - Текст : электронный.

10) Habr : [сайт] - URL: https://habr.com/en/sandbox/27224/ (дата обращения: 10.04.2023) - Текст : электронный.

11) Habr : [сайт] - URL: https://habr.com/ru/companies/productivity_inside/articles/505430/ (дата обращения: 09.05.2023) - Текст : электронный.