Введение 3
Обзор литературы 7
1 Задача транспортной маршрутизации 9
1.1 Математическая постановка задачи 9
1.2 Алгоритмы решения задачи VRPCD 11
2 Алгоритм Iterated Local Search 17
2.1 Описание работы алгоритма ILS 17
2.2 Применение алгоритма ILS 19
3 Динамическая адаптация алгоритма ILS 22
3.1 Временная состоятельность 22
3.2 Описание работы динамической адаптации 23
3.3 Применение динамической адаптации 24
Заключение 26
Список литературы 27
Приложения 29
Купить

История задачи транспортной маршрутизации (Vehicle Routing Prob­lem) начинается со статьи [1], где авторы в 1959 году поставили математи­ческую формулировку и решили задачу о поставке бензина на заправочные станции. На сегодняшний день эта задача является одной из самых извест­ных в области комбинаторной оптимизации.
Общий вид задачи VRP выглядит таким образом: m транспортных средств, первоначально находящихся в депо, должны доставить товар n покупателям. Цель задачи - уменьшить затраты на перевозку товара. Ре­шением классической задачи VRP является множество маршрутов, кото­рые начинаются и заканчиваются в депо, и удовлетворяют тому условию, что каждый клиент посещается только один раз. Затраты на перевозку могут быть уменьшены за счет оптимизации пройденной дистанции или использования меньшего количества транспорта.
Но большинство задач VRP на практике выглядят гораздо слож­нее, чем классическая, для них существует много ограничений. Эти задачи можно классифицировать следующим образом, как это сделали в статье [2]:
1) Задачи с ограниченной вместимостью автотранспорта (Capacitated VRP - CVRP). Каждое транспортное средство имеет определенную фикси­рованную грузоподъемность.
2) Задачи с ограничением времени обслуживания (VRP with Time Windows - VRPTW). При решении практических задач часто возникает необхо­димость учета временных окон. В этой модели каждый клиент имеет индивидуальный временной интервал (окно), в течение которого он мо­жет сделать заказ.
3) Задачи с возможностью частичного отказа от товара (VRP with Pick­Ups and Deliveries - VRPPD). При решении данной задачи нужно учи­тывать, что суммарный вес доставляемых до клиентов и возвращаемых от них в депо товаров не должен превышать допустимую грузоподъ­емность транспортного средства.
4) Задачи с возможностью возврата товара после завершения обслужива­ния всех клиентов (VRP with Backhauls - VRPB). Эта задача является модификацией предыдущей задачи VRPPD. При этом подразумевает­ся, что каждый транспорт сначала развозит все товары, а затем начи­нает принимать товар от клиентов.
5) Задачи с возможностью обслуживания одного клиента различным транс­портом (Split Delivery VRP - SDVRP). В классической задаче VRP все автомобили имеют одинаковую грузоподъемность, но на практике, ча­ще всего, автопарк состоит из разногабаритных грузовых автомобилей.
6) Задачи с возможностью доставки грузов в течение длительного пери­ода (Periodic VRP - PVRP). В классической задаче VRP обычный пе­риод планирования - один день. В задачах с периодической маршрути­зацией используется расширенный период планирования на несколько дней.
7) Задачи, в которых для описания поведения клиентов или транспорт­ных средств могут быть использованы случайные переменные (Stochastic VRP - SVRP). В этом случае одна или несколько переменных (клиен­ты, запросы или время) могут принимать случайное значение.
8) Задачи с возможностью использования транспортных средств из несколь­ких депо (Multiple Depot VRP - MDVRP). Чтобы справиться с увели­чивающимся количеством запросов на доставку товаров грузоперевозя­щие компании не только увеличивают автопарк, но и создают несколь­ко складов (депо). Как правило, каждый склад имеет свой автопарк и самостоятельно решает задачу маршрутизации автотранспорта. Но в общем случае можно рассматривать вариант, когда для погрузки каж­дый автомобиль компании может задействовать любой склад, имею­щий необходимый товар.
9) Задачи с возможностью дополнительной загрузки транспортного сред­ства по ходу следования (VRP with Satellite Facilities - VRPSF). Клас­сическая задача VRP предполагает, что из-за ограниченной грузоподъ­емности каждая машина после доставки всего груза, должна вернуться в депо за новой порцией товаров. Однако в некоторых случаях выгод­нее произвести дозагрузку на маршруте, без возврата в депо, используя для этого дополнительные транспортные средства.
10) Задачи, в которых используется кросс-докинг. (VRP with Cross-Docking - VRPCD).
В данной работе исследуется задача последнего типа, то есть выпол­няется условие, что склад, через который проходит товар, является кросс- доком. Кросс-докинг - относительно новая стратегия складирования в ло­гистике. Под ним понимают консолидацию товара, поступающего на склад, для упорядочения его для последующих транспортировок. То есть товар, доставленный от поставщиков, прегруппировывают и отправляют прямо к уходящему транспорту без задержки на складе. Загрузка на складе занима­ет, как правило, менее 24 часов, иногда менее часа. Таким образом, кросс­докинг не только предоставляет покупателям качественное обслуживание, но и дает существенные преимущества по сравнению с традиционным скла­дированием: снижение затрат на хранение, дополнительное пространство на складе, управление стоимостью и циклами обработки заказов.
Благодаря этим преимуществам, кросс-докинг широко распространен на практике. В том числе, успешное внедрение этой стратегии произвела компания Walmart - один из крупнейших в мире ритейлеров. В системе этой компании товары непрерывно поставляются на кросс-док, где их группи­руют и затем отправляют в магазины, при этом на складе они не задержи­ваются. Избегая затрат на хранение, кросс-докинг позволил Walmart под­держивать низкие цены и повысить прибыльность компании. CompUSA - другой важный пользователь кросс-докинга: 70 % товаров компании также проходит через кросс-док.
Задача VRPCD формулируется следующим образом. Товар доставля­ют от поставщиков несколькими одинаковыми транспортными средствами на кросс-док, там товар консолидируют и немедленно отправляют их ри­тейлерам теми же транспортными средствами. Примеры маршрута и кон­солидации товара на кросс-доке представлены на рис. 1 и 2 соответственно.
Одним из важных пунктов является одновременное прибытие транс­порта на склад. Если же они прибудут не одновременно, некоторым транс­портным средствам придется ждать разгрузки и загрузки. Следовательно, время поставок для всего транспорта должно быть синхронизировано, и товар должен быть правильно консолидирован. При правильной организации цепи поставок, товар должен доставляться от поставщика ритейлеру непрерывно, без задержек.
Рис. 1: Пример маршрута.
Рис. 2: Пример консолидации товара на кросс-доке.
Целью данной работы является разработка динамического алгорит­ма, построенного на основе уже существующего эвристического алгоритма, для нахождения оптимальных решений задачи.
Задачи работы:
• Исследование решений задачи транспортной маршрутизации, генери­руемых эвристическими методами;
• Разработка динамической адаптации эвристического алгоритма;
• Сравнительная оценка эвристики и динамической адаптации;
• Разработка программного обеспечения, реализующего указанные ме­тоды.
Купить