측정기준

라우팅 솔버는 측정기준이라는 객체를 사용하여 이동 시간 또는 차량이 픽업 및 배달을 하는 경우 운반하는 총 중량 에서 자세한 내용을 확인하실 수 있습니다. 라우팅 문제에 이러한 수량이 포함된 경우 제약 조건 또는 목표 함수를 사용하려면 측정기준을 정의하여 이를 지정해야 합니다.

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

측정기준의 예

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

  • VRPTW 예는 추적할 측정기준을 만듭니다. 각 차량의 누적 이동 시간을 나타냅니다. 솔버는 크기를 사용하여 차량이 위치의 지정할 수 있습니다

  • CVRP 예는 수령 (예: 배송물 중량 또는 부피): 경로를 따라 차량이 운반하는 누적 하중입니다. 솔버는 크기를 사용하여 차량의 하중 제약 조건을 적용합니다. 용량을 초과할 수 없습니다.

아래 예에서는 AddDimension 드림 메서드를 사용하여 축소하도록 요청합니다.

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 변수를 참고하세요. 확인하세요. 문제에 대기 시간이 없다면 일반적으로 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 변수

이것은 시간을 절약할 수 있습니다. 다음과 같이 가정해 보겠습니다. 차량이 경로의 한 단계에서 i 위치로부터 위치 j로 이동하는 경우:

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

차량이 도착 시 위치 i를 즉시 떠날 수 없거나 누적이 불가능합니다. 위치 j의 시간은 175가 됩니다. 대신, 차량이 대기 시간인 출발 전 위치 i 즉, 위치 i의 지연은 25입니다.

VRPTW에서는 차량이 대기해야 할 수 있으므로 VRPTW에서 슬랙을 허용해야 합니다. 특정 위치 방문 시 시간 제한으로 인해 발생합니다. 이와 같은 문제에서는 slack_max을 차량이 대기할 수 있는 최대 시간으로 설정합니다. 위치를 지정해야 합니다. 사용자가 slack_max를 매우 큰 수로 설정하면 됩니다.

반면 CVRP의 경우 누적 부하 i에서 j는 항상 i의 수요와 같으므로 지연이 없습니다. 다음과 같은 문제의 경우 이 경우 slack_max를 0으로 설정하면 됩니다.

다음으로 느슨함의 공식 정의를 알려 드리겠습니다. 내부적으로 측정기준은 경로를 따라 누적되는 수량과 관련된 두 가지 유형의 변수:

  • 대중교통 변수: 각 단계에서의 수량 증가 또는 감소 경로 i -> j가 경로의 한 단계인 경우 대중교통 변수는 i입니다. 대중교통 콜백의 경우 대중교통 매트릭스의 j 항목 또는 위치 i의 콜백 값 (콜백이 한 위치에만 의존하는 경우)
  • 누적 변수: 각 위치의 총 누적 수량입니다. 나 는 dimension_name.CumulVar(i) 예를 보려면 다음을 참조하세요. 기간 제약 조건 가상 현실을 볼 수 있습니다.

차량이 한 단계에서 i 위치에서 j 위치로 이동한다고 가정하면 Slack은 다음과 같이 이러한 변수와 관련이 있습니다. <ph type="x-smartling-placeholder">

slack(i) = cumul(j) - cumul(i) - transit(i, j)
</ph>

측정기준에 대한 자세한 내용은 다음을 참고하세요. RoutingDimension 드림 참조 섹션에 나와 있습니다.