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

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

Задача маршрутизации транспорта с ограничением по времени

Суть задачи

Задача маршрутизации транспорта с ограничением по времени (VRPTW) относится к числу наиболее изученных в области комбинаторной оптимизации. Это одна из разновидностей задачи маршрутизации транспорта (VRP), впервые описанная в статье Данцига и Рамсера в 1959 году. Решением задачи VRPTW является набор маршрутов, по которым машины объезжают клиентов; при этом каждый клиент обслуживается в определенный интервал времени. Общий объем грузов, развозимых по каждому маршруту, не должен превышать грузоподъемность машины. Сложность заключается в нахождении решения, при котором общее число задействованных машин и пройденное ими расстояние сводятся к минимуму.

Задача VRPTW вызывает повышенный интерес научного сообщества с 70-х годов. Были опубликованы сотни работ с описанием методов ее решения. Для адекватного сравнения предложенных подходов Геринг, Хомбергер и Соломон определили ряд тестовых наборов, которые обеспечивают сравнение результатов независимо от применяемой методики.

Существует несколько вариаций тестовых наборов Соломона и Геринга-Хомбергера. Герингом и Хомбергером рассмотрены несколько частных случаев, различающихся количеством обслуживаемых клиентов — от 200 до 1000. Другие параметры, в том числе состав заказов и расстояния, также варьируются в зависимости от конкретной ситуации.

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

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

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

Специалисты Quintiq начали с тестового набора Геринга и Хомбергера для 1000 клиентов, частный случай C1_10_4. После этого решения задачи были найдены для множества других частных случаев. Мы выбрали задачу с 1000 клиентов как самую большую и сложную для решения, поскольку она близка по своему масштабу к тем, которые встречаются у наших пользователей в реальной жизни.



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

бывший мировой рекорд мировой рекорд Quintiq
Дата рекорд количество маршрутов общее расстояние количество маршрутов общее расстояние
17-Oct-2017Vehicle Routing Problem with Time Windows, R2_4_1085791.7985791.7
17-Oct-2017Vehicle Routing Problem with Time Windows, RC1_4_5368185.21368172.64
06-Oct-2017Vehicle Routing Problem with Time Windows, RC2_6_4117076.49117067.77
03-Oct-2017Vehicle Routing Problem with Time Windows, RC1_4_3367534.43367533.05
03-Oct-2017Vehicle Routing Problem with Time Windows, RC1_4_9367737.54367733.81
25-Sep-2017Vehicle Routing Problem with Time Windows, RC2_4_785336.5885334.72
07-Sep-2017Vehicle Routing Problem with Time Windows, R1_4_8367275.13367257.28
07-Sep-2017Vehicle Routing Problem with Time Windows, RC1_6_75516145.645516077.12
14-Aug-2017Vehicle Routing Problem with Time Windows, C1_6_85614429.485614389.82
14-Aug-2017Vehicle Routing Problem with Time Windows, R2_6_4118029.37118018.59
14-Aug-2017Vehicle Routing Problem with Time Windows, R2_6_8117574.39117572.76
31-Jul-2017Vehicle Routing Problem with Time Windows, C1_8_97224389.57224300.21
12-Jul-2017Vehicle Routing Problem with Time Windows, RC1_8_107228631.457228554
29-Jun-2017Vehicle Routing Problem with Time Windows, C2_6_3177523.12177520.66
02-Jun-2017Vehicle Routing Problem with Time Windows, C1_8_27227058.997226612.83
02-Jun-2017Vehicle Routing Problem with Time Windows, C1_8_37224278.187224253.11
26-Jan-2017Vehicle Routing Problem with Time Windows, C1_10_109039933.069039858.64
26-Jan-2017Vehicle Routing Problem with Time Windows, C1_10_99040570.69040360.33
26-Jan-2017Vehicle Routing Problem with Time Windows, C1_6_65916345.445915847.61
26-Jan-2017Vehicle Routing Problem with Time Windows, C1_6_75814816.555715752.95
23-Dec-2016Vehicle Routing Problem with Time Windows, R1_4_9368698.63368696.88
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_105515702.515515675.99
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_25515956.215515920.75
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_355152195515204.64
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_45514794.245514777.67
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_55516640.225516566.24
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_65516531.815516504.25
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_85515932.655515914.91
23-Dec-2016Vehicle Routing Problem with Time Windows, RC1_6_95515847.165515826.24
09-Dec-2016Vehicle Routing Problem with Time Windows, R1_4_10368100.62368094.1
16-Oct-2016Vehicle Routing Problem with Time Windows, RC2_4_884793.0684792.75
27-Sep-2016Vehicle Routing Problem with Time Windows, R1_10_110053501.3910053473.26
05-Sep-2016Vehicle Routing Problem with Time Windows, C1_10_89244092.749243029.97
14-Aug-2016Vehicle Routing Problem with Time Windows, C2_6_9177958.26177921.18
08-Jul-2016Vehicle Routing Problem with Time Windows, C2_8_1023109812310977.36
08-Jul-2016Vehicle Routing Problem with Time Windows, C2_8_92311645.222311605.35
07-Jul-2016Vehicle Routing Problem with Time Windows, C2_10_102815944.722815943.34
07-Jul-2016Vehicle Routing Problem with Time Windows, C2_6_8177547.67177539.73
22-Jun-2016Vehicle Routing Problem with Time Windows, RC1_4_1368576.97368573.96
22-Jun-2016Vehicle Routing Problem with Time Windows, RC1_4_4367310.35367308.55
01-Jun-2016Vehicle Routing Problem with Time Windows, R1_4_2368926.7368923.5
01-Jun-2016Vehicle Routing Problem with Time Windows, R1_4_5369242.43369226.21
01-Jun-2016Vehicle Routing Problem with Time Windows, R1_4_6368373.71368372.91
25-Nov-2015Vehicle Routing Problem with Time Windows, C1_8_77726492.647726486.14
23-Nov-2015Vehicle Routing Problem with Time Windows, C1_10_29042278.459042247.05
18-Nov-2015Vehicle Routing Problem with Time Windows, R1_4_3367821.95367819.09
19-Oct-2015Vehicle Routing Problem with Time Windows, C1_4_9367043.74367042.53
17-Sep-2015Vehicle Routing Problem with Time Windows, C1_10_39040239.239040101.36
04-Sep-2015Vehicle Routing Problem with Time Windows, C1_8_107224090.17224070.17
06-May-2015Vehicle Routing Problem with Time Windows, R1_4_7367641.22367619.04
18-Mar-2015Vehicle Routing Problem with Time Windows, C2_6_4176911.35176909.58
18-Mar-2015Vehicle Routing Problem with Time Windows, C2_8_82311292.12311288.01
09-Mar-2015Vehicle Routing Problem with Time Windows, C2_8_62313150.632312551.09
28-Oct-2014Vehicle Routing Problem with Time Windows, C1_8_47223841.117223824.17
09-Oct-2014Vehicle Routing Problem with Time Windows, C1_8_87425293.097326684.02
15-Sep-2014Vehicle Routing Problem with Time Windows, C1_8_67928665.577927202.7
05-Sep-2014Vehicle Routing Problem with Time Windows, C1_10_69944108.349943830.21
11-Apr-2014Vehicle Routing Problem with Time Windows, C1_10_79744806.739743772.66
13-Sep-2013Vehicle Routing Problem with Time Windows, C1_6_45613563.175613558.93
01-Apr-2013Vehicle Routing Problem with Time Windows, C1_10_49039641.469039468.6
посмотреть все

Узнайте, как наша группа оптимизации решила задачу VRPTW
SINTEF — независимая исследовательская организация, которая отслеживает лучшие решения задач для предложенных Соломоном, Герингом и Хомбергером тестовых наборов. Мировые рекорды проверяются и фиксируются SINTEF на портале Transportation Optimization Portal.

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