절약 알고리즘 (Clarke-Wright Savings Algorithm)
한 줄 정의: 경로를 합칠 때 줄어드는 거리(절약값)가 큰 순서로 경로를 병합하는 차량경로 휴리스틱입니다.
쉽게 풀면
처음에는 차량이 고객마다 따로 창고를 왕복한다고 가정합니다. 그다음 두 고객을 한 경로로 묶으면 거리가 얼마나 줄어드는지 계산해, 많이 줄어드는 쌍부터 차례로 묶습니다.
왜 중요한가
계산이 간단하고 빠르면서도 꽤 좋은 해를 주어 차량경로문제 연구에서 기준 해법이나 초기해로 널리 쓰입니다.
논문에서는 이렇게 쓰입니다
"초기해는 Clarke-Wright 절약 알고리즘으로 생성하고, 이후 타부탐색으로 개선하였다."
절약 알고리즘을 출발점으로 삼았다는 뜻입니다.
조금 더 깊게 보면
창고를 0, 두 고객을 i와 j라 하면 절약값은 d(0,i)+d(0,j)−d(i,j)입니다. 모든 고객 쌍의 절약값을 큰 순서로 정렬한 뒤, 차량 용량을 넘지 않고 경로 끝점끼리 연결 가능할 때 병합합니다. Clarke와 Wright가 1964년에 발표했습니다. 최적해를 보장하지는 않는 탐욕적 휴리스틱입니다.
주의할 점
경로최적화는 넓은 목표를 뜻하지만 절약 알고리즘은 그중 하나의 구체적인 구성형 휴리스틱입니다. 결과가 최적해라고 서술하지 않도록 주의하세요.