라우팅 옵션

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

검색 한도

검색 한도는 다음과 같이 지정된 한도에 도달하면 솔버를 종료합니다. 최대 시간 또는 찾은 해의 수 검색 조건을 설정할 수 있습니다. 한계를 제어할 수 있습니다. 자세한 내용은 시간 제한을 예로 들 수 있습니다.

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

이름	유형	기본값	설명
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	원호 비용이 발생한다는 점을 제외하면 PATH_CHEAPEST_ARC와 유사합니다. 에 전달된 함수를 사용하여 평가됩니다. SetFirstSolutionEvaluator()
SAVINGS	저축 알고리즘 (Clarke &Wright). 참조 클라크, G. & 라이트, J.W. "중앙 차고에서 몇 개의 배송 지점으로 차량 스케줄링" , Operations Research, Vol. 12, 1964, pp. 568-581.
SWEEP	스윕 알고리즘 (Wren &Holliday). 앤서니 렌과 앨런 홀리데이 차량 스케줄링 운영 지점에 맞게 다양한 배송 지점까지 Quarterly Research Quarterly (1970-1977), Vol. 23, No. 3 (9월, 1972), pp. 333-344.
CHRISTOFIDES	크리스토피드 알고리즘 (실제로는 최댓값 대신 최대 일치를 사용하는 크리스토피데스 알고리즘 이는 근사치의 3/2 계수를 측정항목 이동 영업 담당자). 일반 차량 경로 모델에서 작동합니다. 노드를 삽입할 수 없을 때까지 경로를 연장하는 데 사용됩니다. 니코스 크리스토피데스 참조, 최악의 경우 출장 세일즈맨 문제, Report 388, Graduate School of 인더스트리얼 행정, CMU, 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	결합되지 않은 후속 노드가 있는 첫 번째 노드 선택 첫 번째 가용 노드에 연결합니다 이 코드는 CHOOSE_FIRST_UNBOUND 전략을 ASSIGN_MIN_VALUE과 결합 (참고: constraints_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	솔루션의 목표 값에 대해 Tabu 검색을 사용하여 로컬을 이스케이프 처리 최솟값.

전파 제어

이름	유형	기본값	설명
use_full_propagation	bool	true	전체 전파와 함께 제약조건 사용 (가벼운 전파에만 사용하는 대신) 라우팅 모델에서 비롯됩니다. 최대 깊이 우선 검색을 사용하거나 모델을 사용할 때만 전파가 필요합니다. 이 경우 보조 클러스터의 값을 확정하기 위해 강력하게 전파해야 합니다. 변수로 사용할 수 있습니다. 이 설정을 true로 변경하면 메모리 소비가 증가합니다.