라우팅 옵션

이 섹션에서는 라우팅 솔버의 몇 가지 옵션을 설명합니다.

검색 한도

검색 한도는 최대 시간 또는 발견된 솔루션 수와 같은 지정된 한도에 도달한 후 솔버를 종료합니다. 문제 해결사의 검색 매개변수를 통해 검색 한도를 설정할 수 있습니다. 예시는 시간 제한을 참조하세요.

다음 표에서는 가장 일반적인 검색 한도를 설명합니다.

이름	유형	기본	설명
solution_limit	int64	Kint64max	검색 중에 생성되는 솔루션 수를 제한합니다.
time_limit.seconds	int64	Kint64max	검색에 소요된 시간으로 초 단위로 제한합니다.
lns_time_limit.seconds	int64	100	소요 시간(초): 시간: 각 로컬 검색 인접 항목의 검색 완료.

첫 번째 솔루션 전략

첫 번째 솔루션 전략은 문제 해결사가 초기 솔루션을 찾기 위해 사용하는 방법입니다. 다음 표에는 first_solution_strategy의 옵션이 나와 있습니다.

옵션	설명
AUTOMATIC	솔버가 해결되는 모델에 따라 사용할 전략을 감지하도록 합니다.
PATH_CHEAPEST_ARC	경로 '시작' 노드에서 시작하여 최저 경로 세그먼트를 만드는 노드에 연결한 후 경로에 추가된 마지막 노드를 반복하여 경로를 확장합니다.
PATH_MOST_CONSTRAINED_ARC	PATH_CHEAPEST_ARC와 유사하지만 원호는 비교 기반 선택기로 평가되며 가장 제한적인 원호를 우선으로 합니다. 라우팅 모델에 선택기를 할당하려면 ArcIsMoreConstrainedThanArc() 메서드를 사용합니다.
EVALUATOR_STRATEGY	원호 비용은 SetFirstSolutionEvaluator()에 전달된 함수를 사용하여 평가된다는 점을 제외하면 PATH_CHEAPEST_ARC와 유사합니다.
SAVINGS	저축 알고리즘 (Clarke & Wright) 참조 클라크, G. & Wright, J.W. '중앙역에서 출발하여 여러 배송 지점까지의 차량 예약', 운영 연구, Vol. 12, 1964, pp. 568-581.
SWEEP	스윕 알고리즘 (렌, 홀리데이). 분기별 (1970~1977년), Vol. 23, No. 3 (9월), Nothony Wren & Alan Holliday 1972), pp. 333-344.
CHRISTOFIDES	Christodides 알고리즘 (실제로 최대 일치 대신 최대 일치를 사용하는 Christofides 알고리즘의 변형으로, 측정항목 이동 영업 담당자에게 근사치의 3/2 계수를 보장하지 않음) 노드를 삽입할 수 없을 때까지 경로를 확장하여 일반 차량 라우팅 모델에서 작동합니다. 니코 크리스토피데스, 여행 영업사원의 새로운 휴리스틱에 대한 최악의 사례, 보고서 388, 산업경영대학원, 1976년
ALL_UNPERFORMED	모든 노드를 비활성화합니다. 노드가 선택사항인 경우에만 (유한 페널티 비용이 있는 분리 제약조건의 요소) 솔루션을 찾습니다.
BEST_INSERTION	가장 저렴한 위치에 가장 저렴한 노드를 삽입하여 솔루션을 반복적으로 빌드합니다. 삽입 비용은 라우팅 모델의 전역 비용 함수를 기준으로 합니다. 2012년 2월 현재 선택적 노드가 있는 모델에서만 작동합니다 (유한 페널티 비용 적용).
PARALLEL_CHEAPEST_INSERTION	가장 저렴한 위치에 가장 저렴한 노드를 삽입하여 솔루션을 반복적으로 빌드합니다. 삽입 비용은 원호 비용 함수를 기준으로 합니다. BEST_INSERTION보다 빠릅니다.
LOCAL_CHEAPEST_INSERTION	각 노드를 가장 저렴한 위치에 삽입하여 솔루션을 반복적으로 빌드합니다. 삽입 비용은 원호 비용 함수를 기준으로 합니다. 삽입을 위해 선택한 노드에 따라 PARALLEL_CHEAPEST_INSERTION와 다릅니다. 여기에서는 노드가 생성 순서대로 고려됩니다. PARALLEL_CHEAPEST_INSERTION보다 빠릅니다.
GLOBAL_CHEAPEST_ARC	가장 저렴한 경로 세그먼트를 생성하는 두 노드를 반복적으로 연결합니다.
LOCAL_CHEAPEST_ARC	후속 바인딩이 없는 첫 번째 노드를 선택하고 가장 저렴한 경로 세그먼트를 생성하는 노드에 연결합니다.
FIRST_UNBOUND_MIN_VALUE	결합되지 않은 후속 항목이 있는 첫 번째 노드를 선택하고 사용 가능한 첫 번째 노드에 연결합니다. 이는 ASSIGN_MIN_VALUE와 결합된 CHOOSE_FIRST_UNBOUND 전략 (constraint_solver.h)과 동일합니다.

검색 상태

라우팅 모델의 status 메서드를 사용하여 검색 상태를 반환할 수 있습니다. 다음은 검색 상태를 출력하는 Python 코드입니다.

print("Solver status: ", solver.status())

이렇게 하면 다음 의미를 가진 정수가 출력됩니다.

가치	설명
0	ROUTING_NOT_SOLVED: 문제가 아직 해결되지 않았습니다.
1	ROUTING_SUCCESS: 문제가 해결되었습니다.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: RoutingModel.Solve()를 호출한 후 문제가 해결되었습니다. 단, 로컬 최적화에 도달하지 못했습니다. 더 많은 시간을 두면 솔루션을 개선할 수 있습니다.
3	ROUTING_FAIL: 문제에 대한 해결책을 찾을 수 없습니다.
4	ROUTING_FAIL_TIMEOUT: 솔루션을 찾기 전에 제한 시간에 도달했습니다.
5	ROUTING_INVALID: 모델, 모델 매개변수 또는 플래그가 잘못되었습니다.
6	ROUTING_INFEASIBLE: 문제를 해결할 수 없는 것으로 확인되었습니다.

지역 검색 옵션

다음 표에는 로컬 검색 전략 (메타유리학이라고도 함) 옵션이 나열되어 있습니다. 이러한 옵션을 설정하는 예는 검색 전략 변경을 참고하세요.

옵션	설명
AUTOMATIC	문제 해결사가 메타온을 선택하도록 합니다.
GREEDY_DESCENT	로컬 최솟값에 도달할 때까지 지역 검색 인접 항목의 개선 (비용 절감)을 허용합니다.
GUIDED_LOCAL_SEARCH	가이드가 있는 지역 검색을 사용하여 지역 최솟값을 제외합니다. (안내 지역 검색 참조) 이는 일반적으로 차량 라우팅에 가장 효율적인 메타 태그입니다.
SIMULATED_ANNEALING	시뮬레이션된 어닐링을 사용하여 국소 최솟값을 이스케이프합니다 (시뮬레이션된 어닐링 참고).
TABU_SEARCH	Tabu 검색을 사용하여 로컬 최솟값을 참조합니다 (예: Tabu Search).
GENERIC_TABU_SEARCH	솔루션의 객관적 값에 대한 테이블 검색을 사용하여 로컬 최솟값을 이스케이프합니다.

전파 제어

이름	유형	기본	설명
use_full_propagation	bool	true	라우팅 모델에서 전파 전파만 사용하는 대신 전체 전파를 통해 제약 조건을 사용합니다. 전체 전파는 깊이 우선 검색을 사용하거나 보조 변수의 값을 확정하기 위해 강력한 전파가 필요한 모델에만 필요합니다. 이 설정을 true로 변경하면 대부분의 경우 검색 속도가 느려지고 모든 경우에 메모리 사용량이 증가합니다.