Введение 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
Приложения
Купить

История задачи транспортной маршрутизации (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 соответственно.
Одним из важных пунктов является одновременное прибытие транспорта на склад. Если же они прибудут не одновременно, некоторым транспортным средствам придется ждать разгрузки и загрузки. Следовательно, время поставок для всего транспорта должно быть синхронизировано, и товар должен быть правильно консолидирован. При правильной организации цепи поставок, товар должен доставляться от поставщика ритейлеру непрерывно, без задержек.
Целью данной работы является разработка динамического алгоритма, построенного на основе уже существующего эвристического алгоритма, для нахождения оптимальных решений задачи.
Задачи работы:
• Исследование решений задачи транспортной маршрутизации, генерируемых эвристическими методами;
• Разработка динамической адаптации эвристического алгоритма;
• Сравнительная оценка эвристики и динамической адаптации;
• Разработка программного обеспечения, реализующего указанные методы.
Обзор литературы
Большую часть исследований по кросс-докингу занимают его концепция, проектирование и определение местоположения сети. Napolitano в статье [3] рассмотрел различные сферы влияния кросс-дока, такие как производство, распределение, транспортировка, розничная торговля, и выделил все его преимущества. В статье [4] Ratliff, Vate и Zhang рассмотрели проектирование системы кросс-докинга для дистрибьюторской сети, а Apte и Viswanthan [5] описали эту систему как один из самых эффективных способов понижения стоимости транспортировки. Kreng, Chen в статье [6] рассмотрели два подхода к планированию производства и распределения: стратегию традиционного складирования и кросс-докинга, и подтвердили эффективность второй.
Первая версия задачи транспортной маршрутизации при условии кросс-докинга была предложена Lee, Jung, Lee в 2006 [7]. В их рассмотрении все транспортные средства начинают процесс разгрузки товара одновременно после того, как последний автомобиль прибывает на кросс-док. Целью было минимизировать транспортные и операционные издержки, учитывая ограничения транспортного средства по грузоподъемности и временные ограничения поставщиков и ритейлеров. Также они предложили математическую модель данной задачи и эвристический алгоритм Tabu Search.
Wen, Larsen, Clausen, Cordeau и Laporte [8] предложили похожую на предыдущую модель формулировку, однако сняли ограничения на одно-временную консолидацию товаров на кросс-доке. Они также предложили Tabu Search и применили его на реальных данных. В результате было найдено решение, уменьшающее функцию затрат на 5 %. Tarantilis [9] обратился к этой же модели и предложил эвристический алгоритм Adaptive Multi-Restart Procedure, связанный с Tabu Search. Алгоритм, предложенный Tarantilis, нашел лучшее решение для 14 из 20 оцениваемых случаев.
Другая версия задачи была предложена Santos, Mateus и da Cunha [10], в которой они не рассматривали временные ограничения поставщиков и ритейлеров. Так же, как и в статье [7], транспортные средства начинают процесс консолидации только после прибытия всех автомобилей. Их основной вклад - новая математическая модель и разработка алгоритма Branch-and-
Price. Для некоторых узлов было получено улучшенное решение.
Позже Santos, Mateus, da Cunha [11] рассмотрели новый тип задачи транспортной маршрутизации - Pickup and Delivery Problem with Cross¬Docking. В данной модели рассматриваются два типа маршрутов: поставщик - кросс-док - ритейлер и поставщик - ритейлер. В первом случае транспорт начинает маршрут из кросс-дока, забирает товар у поставщиков, возвращается на кросс-док и затем везет товар ритейлерам. Во втором же случае транспорт едет из кросс-дока к поставщикам, и после последней загрузки едет к ритейлерам, не заезжая при этом на склад. Они также сформулировали математическую модель и применили алгоритм Branch- and-Price, что привело к улучшению результата на 2.5 %.
Также Morais, Mateus, Noronha [12] опираясь на модель, рассмотренной в статье [8], предложили алгоритм Iterated Local Search. Главное отличие данного алгоритма от предыдущих состоит в том, что здесь рассматриваются только возможные решения, что делает данный алгоритм более эффективным.
Dondo, Mendez и Cerda в работе [13] сформулировал задачу транспортной маршрутизации при использовании кросс-докинга как задачу целочисленного программирования, в которой в смешанной многоступенчатой сети распределения товары доставляются от поставщика к ритейлеру, используя непосредственно стратегию складирования и/или кросс-докинг.

Купить