Введение 5
Введение в предметную область 6
Постановка цели и задач 8
Обзор литературы 9
1. Выбор библиотеки для построение диаграммы Вороного .... 15
1.1. Функциональные требования и нефункциональные требова
ния к библиотеке для построения диаграммы Вороного ... 15
1.1.1 Функциональные требования 15
1.1.2 Нефункциональные требования 15
1.2. Неподходящие библиотеки 16
1.3. Сравнение библиотек проходящих по отсекающим требованиям 17
2. Проверка гипотезы о близости событий в ГСДВ 19
2.1. Gehring & Homberger benchmark 19
2.2. Sartori and Buriol benchmark 22
3. Сравнение конструктивных алгоритмов 24
3.1. Сравнение прототипов конструктивных алгоритмов 24
3.1.1 Базовый конструктивный алгоритм 24
3.1.2 Модификация базового алгоритма с использованием
информации из ДВ 24
3.1.3 Замеры производительности 25
3.2. Сравнение конструктивных алгоритмов 25
3.2.1 Функциональные и нефункциональные требования к ПО 25
3.2.2 Постановка задачи 26
3.2.3 Базовый конструктивный алгоритм 26
3.2.4 Модификация базового алгоритма с использованием
информации из ДВ 27
3.3. Датасеты и сравнение производительности 27
Заключение 31
Список литературы 32
Стремительное развитие рынка онлайн-магазинов и онлайн-платформ и рост конкуренции в этой сфере привели к увеличению затрат на важную составляющую - логистику.
Цена на товары в значительной степени определяется затратами на продвижение и логистику - доставку товаров до заказчика. Основными критериями при выборе логистического провайдера являются издержки и качество обслуживания: срок доставки, количество выполненных заказов, длительность цикла обслуживания и т. п.[1]
Логистическая задача маршрутизации транспортных средств (VRP) - задача о построение маршрутов для транспортных средств с учетом различных ограничений и условий. Решение VRP позволяет более эффективно использовать автопарк компании, что приводит к снижению эксплуатационных расходов, увеличению рентабельности и улучшению качества обслуживания.
VRP является NP-трудной, и для её решения на практике применяют различные эвристические подходы [2] [3] [4]. В рамках этой работы исследуются эвристики, использующие пространственно-временную диаграмму Вороного.
В рамках этой работы была повышена производительность конструктивных алгоритмов для решения задач маршрутизации транспортных средств за счёт использования пространственно-временной диаграммы Вороного.
Были выполнены следующие задачи:
1. Была подтверждена гипотеза о близости расположения в ГСДВ двух последовательных событий в маршрутах текущих лучших известных решений бенчмарков Gehring & Homberger и Sartori and Buriol.
2. Были реализованны два конструктивных алгоритма, решающих задачу маршрутизации ТС: алгоритм с использованием ДВ и без. Произведено сравнение на бенчмарках Gehring & Homberger. В результате суммарная производительность на всех датасетах из сравнения повысилась на 40.1%.
3. Были модифицированы конструктивные алгоритмы для решения задач маршрутизации ТС компании ООО «ВИИРОУТЕ РНД» за счёт использования пространственно-временной диаграммы Вороного.
4. Были произведены замеры качества и производительности конструктивных алгоритмов на академических датасетах и датасетах на основе клиентских данных компании ООО «ВИИРОУТЕ РНД». Медианная производительность модификации с использованием пространственновременной диаграммы Вороного выше на 37.42%, суммарно на всех датасетах из сравнения на 41.35%
