클라크와 라이트의 절감 기법으로 배송 경로를 손으로 계산할 수 있게 되다

1964년, 맨체스터의 협동도매조합(Cooperative Wholesale Society)과 함께 일하던 G. 클라크와 J. W. 라이트는 《Operations Research》에 'Scheduling of Vehicles from a Central Depot to a Number of Delivery Points'를 발표했다. 그들의 목표는 댄치히와 램저가 1959년에 정식화한 경로 문제였으며, 이 문제는 정확한 해법으로는 계산하기에 너무 느렸다.

그들의 절감 알고리즘은 거의 민망할 정도로 단순하다. 모든 고객에 대해 각각 별도의 왕복 경로로 시작한 뒤, 각 고객 쌍에 대해 두 번의 운행 대신 한 번의 운행으로 서비스할 때 절약되는 거리를 계산하고, 차량 용량이 허용하는 한 가장 큰 절감 순서대로 쌍을 병합한다. 남덴마크대학교의 한 강좌에서는 여전히 이를 용량 제약 차량 경로 문제의 고전적 구성적 휴리스틱으로 가르치고 있다.

이 방법은 정확한 방법이 해내지 못한 곳에서 통했다. 경로를 손으로 또는 초기 컴퓨터로 계산할 수 있었고, 이 방법은 표준적인 구성 요소가 되었다. 즉, 이후 2-opt, 타부 탐색, 유전 알고리즘 같은 메타휴리스틱이 개선해 나가는 강력한 출발 해법이 되었다.

가장 많은 거리를 절약하는 쌍을 먼저 병합한다

절감 척도 덕분에 탐욕적 선택이 올바른 선택이 되었다

값비싼 컴퓨팅 성능 없이도 실행되었다

용량 제약은 병합 과정에서 자연스럽게 처리되었다

그 결과물은 수십 년간 더 나은 알고리즘들의 출발점이 되었다

정확한 답이 너무 많은 비용을 요구할 때, 올바른 척도('절감')에 기반한 탐욕적 규칙은 가치의 대부분을 얻어낸다. 그리고 그것은 오늘날에도 계산할 수 있다.

클라크-라이트 절감 알고리즘은 차량 경로 문제에서 가장 많이 인용된 아이디어 중 하나가 되었고, 오늘날에도 교과서와 소프트웨어에서 기준선으로 남아 있으며, 흔히 배송 차량의 경로 최적화를 위한 출발점으로 쓰인다.