Введение 3
Постановка задачи 4
Глава 1. Обзор предметной области 5
1.1. Перемещение между городами 5
1.2. Транспортные средства 5
1.3. Заказы 6
1.4. Расходы 7
1.5. Уникальные ограничения 8
1.6. 0-1 Целочисленное линейное программирование 8
Глава 2. Алгоритм на основе потоковой модели 10
2.1. Мотивация 10
2.2. Обозначения 10
2.3. Формальная модель 12
2.4. Препроцессинг 17
2.5. Эвристики 19
Глава 3. Алгоритм на основе задачи о назначениях 23
3.1. Мотивация 23
3.2. Генерация цепочек заказов 23
3.3. Итоговая модель 25
3.4. Эвристики 26
Глава 4. Детали имплементации 28
4.1. Парсер входных данных 28
4.2. Солвер для 0-1 целочисленного линейного программирования 28
4.3. Тестирование 29
Глава 5. Сравнение алгоритмов 30
Выводы 33
Заключение 33
Список литературы 35
Купить

Моделирование производственного плана движения транспортных средств для перевозок с полной загрузкой прицепа (далее будем называть FTL перевозки) — одна из бизнес задач, возникающих в транспортных компаниях. Одной из таких компаний является ООО «БиАйЭй-Технолоджиз». В рамках моей дипломной работы мне предстоит разработать решение этой бизнес задачи с дополнительными ограничениями, характерными для упомянутой выше компании.
Задачи из этой области начали появляться уже в 1959 году — так в задачу коммивояжёра (Travelling salesman problem) были до­бавлены новые ограничения, связанные с попытками приблизить модель к реальности. Но несмотря на это данная область активно развивается и до сих пор, например, диссертация, рассматривающая оптимизацию количества транспортных средств в задачах, схожих с моей, была опубликована в 2016 году. Для большинства задач из этой области характерно, что для них извест­ны алгортимы нахождения оптимального решения, но они не используются на практике, потому что работают слишком медленно на объемах данных, с которыми приходится иметь дело реальным компаниям. Из-за чего на прак­тике применяются эвристические подходы, которые уже не дают гарантий на оптимальность, но работают быстро на физических данных.
Открытых материалов по моей задаче нет, из-за специфики ограниче­ний, поэтому в последующих главах мной будут рассмотрены схожие задачи, и на основе анализа решений этих задач я разработаю решение поставленной задачи.
Постановка задачи
Целью данной работы является разработка программы для составле­ния плана движения транспортных средств для FTL [4] перевозок. Важно заметить, что составленный план не обязан максимизировать прибыль. Для тестирования скорости работы программы будет использована часть реальных данных компании ООО «БиАйЭй-Технолоджиз» за 2022 год. Для достижения этой цели были выделены следующие задачи:
1. Изучение подходов к решению схожих задач.
2. Разработка и имплементация алгоритма, который будет получать мак­симально возможную прибыль, для дальнейшего тестирования.
3. Разработка и имплементация эвристического алгоритма.
4. Разработка валидатора, при помощи которого будет проверяться кор­ректность решений, сгенерированных программой.
5. Имплементация парсера таблиц с входными данными в формате .xlsx .
Купить