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

Размеры

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

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

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

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

В примере 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_max 0.
capacity : Максимум общего количества, накопленного на каждом маршруте. Используйте capacity для создания ограничений, как в CVRP . Если в вашей задаче нет такого ограничения, вы можете установить значение capacity , достаточно большое, чтобы не налагать ограничений на маршруты, например, сумму всех элементов матрицы или массива, используемых для определения обратного вызова.
fix_start_cumulative_to_zero : логическое значение. Если true, кумулятивное значение количества начинается с 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 в справочном разделе.