OptaPlanner VRPPD с окнами трафика и времени

Question

Есть ли в настоящее время способ включить шаблоны трафика в OptaPlanner с проблемой VRP упаковки и доставки?

Например. Скажем, мне нужно оптимизировать 500 пикапов и доставок сегодня и завтра среди 30 автомобилей, где каждый пикап имеет временной интервал 1–4 часа. Я хочу по возможности избегать оживленных районов города в часы пик.

Новые пикапы также могут быть добавлены (или пока отменены).

Я уверен, что это обычная проблема. Есть ли достойное решение для этого в OptaPlanner?

Спасибо!

Answer 1

Пользователи часто так поступают, но готового примера нет.

Есть несколько способов сделать это, но один из них - добавить 3-е измерение к DistanceMatrix, указав время отправления. Обычно используется степень детализации 15 минут, 30 минут или 1 час.

Здесь есть 2 проблемы масштабирования:

• объем памяти. 15 минут означает 24 * 4 = 96 в день. Учитывая, что при двух измерениях, DistanceMatrix из 10 тыс. Ячеек использует почти 2 ГБ ОЗУ, очевидно, что память может стать проблемой.
• время предварительного расчета. Расчет матрицы расстояний может занять много времени. Здесь могут помочь "массовые алгоритмы". Например, сообщество графопперов не поддерживает массовые вычисления расстояний, но их корпоративная версия тоже поддерживает OSRM (которая бесплатна). Получение трехмерной матрицы из удаленного API Карт Google или удаленного корпоративного API Graphhopper может привести к проблемам с пропускной способностью (см. Выше, матрица расстояний может достигать размера в несколько ГБ, особенно в небинарных форматах, таких как JSON или CSV).

В любом случае, та, что есть 3-мерная матрица, это просто вопрос настройки примеров OptaPlanner. использовать .