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