PILOT Routing API (интерфейс маршрутизации)
Содержание:
|
Режим решения
Вход
Выход
Примеры
|
Заметки:
• ожидаемый порядок для всех массивов координат: [долгота, широта]
• все тайминги указаны в секундах
• все расстояния указаны в метрах
• объект time_window – это пара меток времени в форме [начало, конец]
• устаревшие ключи зачеркнуты
• значения затрат в выходных данных соответствуют целям оптимизации (в настоящее время равны продолжительности).
• «задача» — это работа, самовывоз или доставка
Режим решения
VRP по умолчанию
Режим решения по умолчанию принимает в качестве входных данных описание задачи маршрутизации транспортных средств и выводит набор маршрутов, соответствующих всем ограничениям.
Режим плана
Этот режим, активируемый с помощью -c, направлен на выбор ожидаемого времени прибытия для всех этапов маршрута. Он использует тот же формат ввода, но дополненный описанием ожидаемого маршрута для каждого транспортного средства. Все ограничения во входных данных неявно становятся мягкими ограничениями. Результатом является набор маршрутов, соответствующих ожидаемому описанию, с минимальными нарушениями синхронизации и сообщениями обо всех нарушениях ограничений.
Вход
Описание проблемы считывается из стандартного ввода или из файла (с помощью -i) и должно быть допустимым форматом json, как показано ниже.
|
Работа
Объект задания имеет следующие свойства:
|
Сообщается об ошибке, если два объекта задания имеют одинаковый идентификатор.
Отгрузки
Объект отгрузки имеет следующие свойства:
|
Shipment_step аналогичен объекту задания (за исключением редких ключей, уже присутствующих в доставке):
|
Сообщается об ошибке, если два объекта доставки (соответственно самовывоза) имеют одинаковый идентификатор.
Транспорт
Объект транспортного средства имеет следующие свойства:
|
Объект разрыва имеет следующие свойства:
|
Сообщается об ошибке, если два объекта перерыва имеют одинаковый идентификатор для одного и того же транспортного средства.
Объект vehicle_step имеет следующие свойства:
|
Заметки
Расположение задач
Для объектов задания, забора и доставки, если предоставлены настраиваемые матрицы:
• location_index является обязательным.
• местоположение необязательно, но его можно настроить для получения координат в ответе.
Если пользовательская матрица не указана:
• в механизм маршрутизации будет отправлен запрос к таблице
• местоположение обязательно
• location_index не имеет значения
Расположение транспортных средств
• ключи start и end необязательны для автомобиля, если присутствует хотя бы один из них
• если end не указан, результирующий маршрут остановится на последней посещенной задаче, выбор которой определяется процессом оптимизации
• если start не указан, результирующий маршрут будет начинаться с первой посещенной задачи, выбор которой определяется процессом оптимизации
• чтобы запросить поездку туда и обратно, просто укажите начало и конец с одними и теми же координатами
• в зависимости от того, предоставлены ли пользовательские матрицы, обязательные поля следуют той же логике, что и для ключей заданий, местоположения и местоположения_индекса.
Ограничения емкости
Используйте суммы (вместимость для транспортных средств, доставку и вывоз для работ, сумму для отгрузок), чтобы описать проблему с ограничениями вместимости. Эти массивы можно использовать для моделирования пользовательских ограничений сразу для нескольких показателей, например. количество элементов, вес, объем и т. д. Транспортному средству разрешается обслуживать набор задач, только если результирующая нагрузка на каждом этапе маршрута ниже соответствующего значения вместимости для каждого показателя. При использовании нескольких компонентов для сумм рекомендуется сначала ставить наиболее важные/ограничивающие показатели.
Предполагается, что все суммы, связанные с доставкой для работ, загружаются при запуске транспортного средства, а все суммы, связанные с получением работ, возвращаются в конце транспортного средства.
Навыки и умения
Используйте навыки для описания проблемы, когда не все задачи могут выполняться всеми транспортными средствами. Рабочие навыки являются обязательными, т. Е. Работа может выполняться только транспортным средством, которое имеет все необходимые навыки. Другими словами: работа j имеет право на транспортное средство v, если j.skills включены в v.skills.
Это определение подразумевает, в частности, что:
• задание без навыков может быть выполнено на любом транспортном средстве;
• машина без навыков может выполнять только задачи без особой необходимости (т.е. тоже без навыков).
Чтобы упростить моделирование проблем, не требующих навыков, не предоставляя ключ навыков по умолчанию для предоставления пустого массива.
Приоритеты задач
Полезно в ситуациях, когда не все задачи могут быть выполнены, чтобы получить некоторый контроль над тем, какие задачи не назначены. Установка значения высокого приоритета для некоторых задач будет способствовать их включению в решение в максимально возможной степени по сравнению с задачами с более низким приоритетом.
Время настройки задачи
Время установки служит средством описания времени, необходимого для начала выполнения задачи в заданном месте. Это моделирует продолжительность, которую не следует повторно применять для других задач, следующих в том же месте. Таким образом, общее «время действия» для задачи – это настройка + обслуживание по прибытии в новое место или обслуживание только при выполнении новой задачи в предыдущем местоположении транспортного средства
Временные окна
Пользователи сами решают, как описывать временные окна:
• относительные значения, например. [0, 14400] для временного окна продолжительностью 4 часа, начиная с начала горизонта планирования. В этом случае все время, указанное в выходных данных с помощью ключа прибытия, относится к началу горизонта планирования;
• абсолютные значения, «реальные» метки времени. В этом случае все время, указанное в выходных данных с помощью ключа прибытия, можно интерпретировать как временные метки.
Отсутствие временного окна во входных данных означает, что временное ограничение не применяется. В частности, транспортное средство без ключа time_window сможет обслуживать любое количество задач, а задача без ключа time_windows может быть включена в любое время на любом маршруте в той мере, в какой это разрешено другими ограничениями, такими как навыки, вместимость и другие. транспортные средства/задачи временные окна.
Шаги автомобиля
В режиме плана
Массив шагов точно описывает порядок маршрутов, который будет создан в ответ. Ключи service_* (необязательные) для объектовvehicle_step используются в качестве дополнительных жестких временных ограничений.
В режиме решения
Использование шагов для транспортных средств в режиме решения VRP по умолчанию — это способ принудительно начать поиск с соответствующего пользовательского решения, если оно допустимо. В отличие от поведения решения по умолчанию при выполнении нескольких одновременных поисков, это означает, в частности, что выполняется один путь поиска, начиная с предоставленного решения. Таким образом, очевидно, что итоговое качество будет сильно зависеть от заданной пользователем начальной точки.
В этом контексте:
• только шаги с type=job, pickup или delivery используются для определения начального порядка маршрутов
• ключи service_* не используются
Ошибка возникает, если для любого из транспортных средств предоставленные шаги описывают маршрут, который недействителен в отношении любого из ограничений.
Матрицы
Объект матрицы позволяет вводить (непустые) пользовательские матрицы для каждого профиля транспортного средства. Каждая матрица представляет собой массив массивов целых чисел без знака, хранящихся под ключом профиля, а затем под:
• продолжительность для пользовательской матрицы времени в пути, которая будет использоваться для всех проверок временных ограничений;
• затраты для пользовательской матрицы затрат, которая будет использоваться во всех оценках стоимости маршрута.
Если указано только значение длительности, подразумевается, что его также следует использовать для оценки затрат.
Пример описания различных матриц для разных профилей транспортных средств:
Если для всех необходимых значений профиля транспортного средства предоставлены настраиваемые матрицы, свойства местоположения, начала и конца становятся необязательными. Вместо координат во время оптимизации используются обозначения строк и столбцов, предоставленные ключами *_index.
Выход
Вычисленное решение записывается в формате json на стандартный вывод или в файл (с использованием -o) в следующем формате.
|
Код
Возможные значения кода состояния:
|
Резюме
Объект сводки имеет следующие свойства:
|
*: предоставляется при использовании флага -g .
Маршруты
Объект маршрута имеет следующие свойства:
|
*: предоставляется при использовании флага -g .
Шаги
Объект шага имеет следующие свойства:
|
*: предоставляется при использовании флага -g .
Нарушение
Объект нарушения имеет следующие свойства:
|
Возможные причины нарушения:
• «задержка», если фактический запуск службы не соответствует временному окну задачи и опаздывает на конец временного окна.
• "lead_time", если фактическое начало службы не соответствует временному окну задачи и происходит раньше начала временного окна.
• «загрузка», если загрузка транспортного средства превышает его грузоподъемность.
• "max_tasks", если у транспортного средства больше задач, чем значение max_tasks.
• «навыки», если транспортное средство не обладает всеми необходимыми навыками для выполнения задачи.
• «приоритет», если ограничение приоритета доставки не соблюдается (самовывоз без согласования доставки, доставка до/без согласования получения)
• «missing_break», если в пользовательском маршруте пропущена остановка транспортного средства.
Примечание о нарушениях: отчетность имеет смысл только при использовании -c для выбора ожидаемого времени прибытия для пользовательских маршрутов, описанных во входных данных, с использованием ключей шагов для транспортного средства. При использовании обычной оптимизации о нарушениях по-прежнему сообщается для согласованности, но они гарантированно недействительны, т. е. массивы нарушений пусты.
Примеры
Использование механизма маршрутизации (OSRM или Openrouteservice)
• Входной файл
• Возможный выходной файл
Использование пользовательских матриц
• Входной файл
• Возможный выходной файл
Использование -c для выбора ожидаемого времени прибытия и сообщения о нарушениях
Пример с маршрутом с избыточной пропускной способностью и один со временем выполнения заказа и задержками.
• Входной файл
• Возможный выходной файл