Как мы можем доказать, что технологии оптимизации Quintiq превосходят другие?

Мы нашли лучшие решения для одних из самых сложных задач оптимизации в мире. Вот несколько наших последних рекордов:

Задача маршрутизации транспорта с возможностью возврата и доставки товаров с временными ограничениями (Pickup and Delivery Problem with Time Windows)

Суть задачи

Задача маршрутизации транспорта с возможность возврата и доставки товаров с временными ограничениями (PDPTW) относится к области комбинаторной оптимизации. Она является развитием задачи маршрутизации транспорта с временными ограничениями (VRPTW). Различие заключается в том, что заявка клиента содержит не только конкретный пункт доставки, но и конкретный пункт сбора товара, который обычно отличается от депо.

Решением задачи PDPTW является набор маршрутов для парка машин. Он складывается из последовательности операций погрузки и доставки, причем посещать каждый пункт можно только в определенный интервал времени. Для каждой заявки на перевозку груза в операциях погрузки и доставки участвует одна и та же машина; при этом погрузка, что очевидно, происходит раньше доставки.

В сравнении с задачей VRPTW, здесь возникают дополнительные ограничения: связанность и очередность. Помимо этого, общий объем грузов, перевозимых каждой машиной, не должен превышать ее грузоподъемность. Первичная цель задачи — минимизировать общее количество задействованных машин; вторичная цель — минимизировать общее пройденное расстояние.

Научное сообщество заинтересовано задачей PDPTW с 1980-х годов; по этой теме опубликованы сотни работ. Как и в задаче VRPTW, для адекватного сравнения различных подходов к решению требуются тестовые наборы. В 2001 году Хайбин Ли и Эндрю Лим адаптировали хорошо известные наборов Соломона и Геринга-Хомбергера для задачи PDPTW. Частные постановки задач, рассмотренные Ли и Лимом, различаются количеством обслуживаемых клиентов (от 100 до 1000), а также другими параметрами: временные интервалы, потребности клиентов, грузоподъемность машин и географическое распределение пунктов.

Задача PDPTW характеризуется следующими условиями:

  • имеется центральное депо и набор отдаленных клиентов-потребителей;
  • каждый клиент указывает в заявке пункты погрузки и доставки;
  • каждому клиенту необходимо в определенный для него промежуток времени погрузить и доставить заказанный объем товара;
  • известны расстояния между пунктами и время в пути;
  • имеется парк машин, для каждой из них указана грузоподъемность.

Мировые рекорды Quintiq

В дополнение к тестовым наборам Геринга-Хомбергера для задачи VRPTW, специалисты Quintiq воспользовались тестовыми наборами Ли и Лима для задачи PDPTW. Решать задачи погрузки и доставки нашим клиентам часто приходится при повседневном планировании.

Вот несколько наших последних и наиболее впечатляющих успехов:


Предыдущий мировой рекорд Мировой рекорд Quintiq
Дата Постановка Количество маршрутов Общее расстояние Количество маршрутов Общее расстояние
28-Jan-2016Pickup and Delivery Problem with Time Windows, LRC2_4_2116303.36107424.72
21-Jan-2016Pickup and Delivery Problem with Time Windows, LRC2_4_696479.5696337.08
18-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_21810277.23189914.1
15-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_7197998.18197997.96
14-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_10178019.94177965.41
12-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_9189501188864.29
11-Jan-2016Pickup and Delivery Problem with Time Windows, LR2_4_5610185.14610084.11
04-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_3178728.3178718.22
04-Jan-2016Pickup and Delivery Problem with Time Windows, LC2_6_4178041.97177902.66
04-Jan-2016Pickup and Delivery Problem with Time Windows, LR2_4_967995.7367930.55
20-Oct-2015Pickup and Delivery Problem with Time Windows, LRC2_4_1127471.01127454.14
09-Oct-2015Pickup and Delivery Problem with Time Windows, LC1_4_9367452.21367451.2
08-Oct-2015Pickup and Delivery Problem with Time Windows, LC1_4_2388012.43388007.79
SINTEF — независимая исследовательская организация, которая отслеживает лучшие решения задач для предложенных Соломоном, Герингом и Хомбергером тестовых наборов. Мировые рекорды проверяются и фиксируются SINTEF на портале Transportation Optimization Portal.

Quintiq продолжает выделять время и средства на штурм новых мировых рекордов в области оптимизации. В ближайшее время мы ожидаем очередных хороших новостей. Следите за обновлениями!