측정기준

라우팅 솔버는 측정기준이라는 객체를 사용하여 이동 시간 또는 차량이 승차 및 배송하는 경우 운송 중인 총 중량 등 차량 경로에 따라 누적되는 수량을 추적합니다. 제약 조건 또는 목표 함수에서 라우팅 문제에 이러한 수량이 포함된 경우 이를 지정하는 차원을 정의해야 합니다.

이 섹션에서는 측정기준을 정의하고 사용하는 방법을 설명합니다.

측정기준의 예

다음은 이전 섹션의 측정기준 예입니다.

  • VRPTW 예에서는 각 차량의 누적 이동 시간을 추적하는 측정기준을 만듭니다. 솔버는 측정기준을 사용하여 차량이 해당 위치의 기간 내에 있는 위치만 방문할 수 있다는 제약 조건을 적용합니다.

  • CVRP 예시는 수요에 관한 측정기준 (예: 수령할 패키지의 중량 또는 수량)을 만들어 차량이 경로를 따라 이동하는 누적 로드를 추적합니다. 솔버는 측정기준을 사용하여 차량 하중이 용량을 초과할 수 없다는 제약 조건을 적용합니다.

아래 예에서는 AddDimension 메서드를 사용하여 VRPTW의 측정기준을 정의합니다.

Python

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

C++

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

자바

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

C#

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 참조 페이지를 참고하세요.

솔루션 시간 창을 목록 또는 배열에 저장 섹션에는 목록 또는 배열의 차원에 누적 데이터를 저장하는 함수가 표시됩니다.

Slack 변수

다음은 이동 시간과 관련된 문제의 Slack 변수를 보여주는 예입니다. 차량이 경로의 한 단계에서 위치 i에서 위치 j로 이동한다고 가정해 보겠습니다.

  • i에서 차량의 누적 이동 시간은 100분입니다.
  • j에서 차량의 누적 이동 시간은 200분입니다.
  • i에서 j까지 이동하는 데 걸리는 시간은 75분입니다.

차량이 도착하는 즉시 위치 i를 떠날 수 없거나 위치 j의 누적 시간이 175가 됩니다. 대신, 차량은 출발 전에 위치 i에서 25분 동안 대기해야 합니다. 즉, 위치 i의 느슨함은 25입니다.

시간 제한으로 인해 차량이 특정 위치를 방문하기 전에 기다려야 할 수 있으므로 VRPTW에서 Slack을 허용해야 합니다. 이와 같은 문제에서 slack_max을 차량이 다음 위치로 이동하기 전에 특정 위치에서 기다리도록 허용할 최대 시간으로 설정합니다. 대기 시간이 중요하지 않다면 slack_max를 매우 큰 숫자로 설정하면 됩니다.

반면 CVRP의 경우 누적 부하가 i에서 j로 변경되어도 항상 i의 수요와 같으므로 슬랙이 없습니다. 이러한 문제의 경우 slack_max를 0으로 설정하면 됩니다.

이제 slack의 공식 정의를 살펴보겠습니다. 내부적으로 측정기준은 경로를 따라 누적되는 수량과 관련된 두 가지 유형의 변수를 저장합니다.

  • 운송 변수: 경로의 각 단계에서 수량의 증가 또는 감소 i -> j가 경로의 한 단계인 경우 대중교통 변수는 대중교통 매트릭스의 i 또는 j 항목이거나 위치 i의 콜백 값(콜백이 하나의 위치에만 종속되는 경우)입니다.
  • 누적 변수: 각 위치의 총 누적 수량입니다. dimension_name.CumulVar(i)로 위치 i의 누적 변수에 액세스할 수 있습니다. 예를 보려면 VRPTW 예의 기간 제한을 참고하세요.

한 단계에서 차량이 i 위치에서 j 위치로 이동한다고 가정하면 Slack이 다음과 같이 이러한 변수와 관련이 있습니다. 

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

측정기준에 관한 자세한 내용은 참조 섹션의 RoutingDimension를 참고하세요.