Эта страница переведена с помощью Cloud Translation API.

Dimensions

Решатель маршрутов использует объект, называемый измерением , для отслеживания величин, которые накапливаются на маршруте транспортного средства, например время в пути или, если транспортное средство осуществляет погрузку и доставку, общий вес, который оно перевозит. Если задача маршрутизации включает в себя такую величину либо в ограничениях, либо в целевой функции, вам необходимо определить размерность, чтобы указать их.

В этом разделе объясняется, как определять и использовать размеры.

Примеры размеров

Вот несколько примеров размеров из предыдущих разделов.

В примере VRPTW создается измерение для отслеживания совокупного времени в пути каждого транспортного средства. Решатель использует это измерение, чтобы обеспечить соблюдение ограничения, согласно которому транспортное средство может посещать местоположение только в пределах временного окна местоположения.
В примере CVRP создается измерение потребностей (например, вес или объем забираемых упаковок), которое отслеживает совокупную нагрузку, которую транспортное средство перевозит по своему маршруту. Решатель использует размер, чтобы обеспечить соблюдение ограничения, согласно которому нагрузка транспортного средства не может превышать его грузоподъемность.

В приведенных ниже примерах измерение для VRPTW определяется с помощью метода AddDimension .

Питон

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

С++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Ява

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

С#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

Метод AddDimension имеет следующие входные данные:

callback_index : индекс обратного вызова, который возвращает количество. Индекс, который является внутренней ссылкой решателя на обратный вызов, создается такими методами, как RegisterTransitCallback или RegisterUnitaryTransitCallback .
slack_max : Максимум для Slack , переменная, используемая для представления времени ожидания в локациях. Подробности см. в разделе Slack-переменные ниже. Если проблема не связана со временем ожидания, обычно вы можете установить для slack_max значение 0.
capacity : Максимум общего количества, накопленного по каждому маршруту. Используйте capacity для создания ограничений, подобных тем, которые предусмотрены в CVRP . Если ваша задача не имеет такого ограничения, вы можете установить capacity на достаточно большое значение, чтобы не накладывать никаких ограничений на маршруты — например, сумму всех записей матрицы или массива, используемых для определения обратного вызова.
fix_start_cumulative_to_zero : логическое значение. Если это правда, совокупное значение количества начинается с 0. В большинстве случаев для этого параметра следует установить значение True . Однако из-за VRPTW или проблем с ограничениями ресурсов некоторым транспортным средствам, возможно, придется запуститься после времени 0 из-за ограничений временного окна, поэтому для этих проблем вам следует установить fix_start_cumulative_to_zero в значение False .
dimension_name : строка имени измерения, например 'Distance' , которую можно использовать для доступа к переменным в другом месте программы.

Программа CVRP создает измерение немного другого типа, используя метод AddDimensionWithVehicleCapacity . Этот метод использует массив мощностей с одной записью для каждого транспортного средства. (Напротив, AddDimension принимает одно значение capacity , поэтому предполагается, что все транспортные средства имеют одинаковую вместимость.)

См. справочную страницу RoutingModel для получения информации о других методах создания измерений.

В разделе «Сохранение окон времени решения в списке или массиве» представлены функции, которые сохраняют совокупные данные в измерении в списке или массиве.

Слабые переменные

Вот пример, иллюстрирующий резервные переменные для задачи, связанной со временем в пути. Предположим, что транспортное средство движется из пункта i в пункт j за один этап своего маршрута и что:

Совокупное время поездки транспортного средства в точке i составляет 100 минут.
Совокупное время поездки транспортного средства в точке j составляет 200 минут.
Время в пути от i до j составляет 75 минут.

Транспортное средство не может покинуть точку i сразу по прибытии, иначе его совокупное время в точке j будет равно 175. Вместо этого транспортное средство должно подождать 25 минут в точке i, прежде чем отправиться в путь; другими словами, резерв в позиции i равен 25.

Вам необходимо разрешить резерв VRPTW, поскольку транспортным средствам, возможно, придется ждать перед посещением определенного места из-за ограничений временного окна. В подобной проблеме установите slack_max максимальное время, в течение которого транспортные средства могут ждать в определенном месте, прежде чем перейти к следующему месту. Если не имеет значения, как долго они будут ждать, просто установите slack_max очень большое значение.

С другой стороны, для CVRP изменение накопленной нагрузки от i до j всегда равно спросу в точке i , поэтому резерва нет. Для подобных проблем вы можете установить slack_max на 0.

Далее мы дадим формальное определение слабины. Внутри измерения хранятся два типа переменных, связанных с количествами, которые накапливаются по маршрутам:

Транзитные переменные : увеличение или уменьшение количества на каждом этапе маршрута. Если i -> j — это один шаг маршрута, транзитная переменная — это либо запись i , j транзитной матрицы (для транзитного обратного вызова), либо просто значение обратного вызова в местоположении i (если обратный вызов зависит только от одного местоположения). ).
Кумулятивные переменные : общее накопленное количество в каждом месте. Вы можете получить доступ к накопительной переменной в местоположении i с помощью dimension_name.CumulVar(i) . Для примера см. ограничения временного окна в примере VRPTW.

Предполагая, что транспортное средство перемещается из места i в место j за один этап, резерв связан с этими переменными следующим образом:

slack(i) = cumul(j) - cumul(i) - transit(i, j)

Дополнительные сведения об измерениях см. в разделе RoutingDimension справочного раздела.