차고 및 A, B, C 간의 거리는 다음 표와 같다. 차고에서 출발하여 A, B, C 3개의 수요지를 각각 1대의 차량이 방문하는 경우에 비해, 1대의 차량으로 3개의 수요지를 모두 방문하고 차고지로 되돌아오는 경우 수송 거리가 최대 몇, km 감소되는가?
화물운송론| 구분 | A | B | C |
|---|---|---|---|
| 차고 | 10 | 13 | 12 |
| A | - | 5 | 10 |
| B | - | - | 7 |
- ①30
- ②32
- ③34
- ④36
- ⑤38
선지를 골라 바로 채점해 보세요.
정답 ④ — 각 수요지를 개별 왕복 운행할 때의 총 운송 거리는 이고, 한 대로 세 지점을 순회 방문하는 최적 경로의 거리는 이므로 최대 의 수송 거리가 감소합니다.
선지별 오답 이유
- ① 최적 순회 경로가 아닌 우회 경로를 선택하거나 절약치 합산에서 오류가 발생했을 때 도출되는 수치로 옳지 않습니다.
- ② 다른 경로 조합을 적용했을 때의 거리 차이이거나 계산 과정에서 감축량이 과소평가된 값으로 오답입니다.
- ③ 차고지와 세 수요지를 최적 순회할 때 소요되는 최소 총 이동 거리가 이며, 이는 감소된 거리가 아니라 단일 차량의 실제 운행 거리이므로 틀립니다.
- ④ 개별 왕복 운송 거리의 합인 에서 최적 순회 경로(차고-A-B-C-차고)의 운송 거리 를 차감하면 최대 가 감소하므로 정답입니다.
- ⑤ 삼각부등식을 위배하여 발생할 수 없는 절약치이거나 계산상 상한을 초과한 수치이므로 옳지 않습니다.
관련 개념
차량 경로 문제(VRP)에서 절약법(Clarke-Wright Savings Algorithm)은 거점과 각 수요지를 개별 왕복할 때와 두 수요지를 연결하여 통합 순회할 때 발생하는 거리 단축분을 계산하는 기법입니다.
두 지점을 묶어 순회 경로를 구성할 때 발생하는 절약치는 각 지점의 왕복 거리 합에서 두 지점 사이의 직접 거리를 뺀 값으로 도출됩니다.
순회 경로를 구성할 때 절약치가 큰 연결 구간부터 우선적으로 결합하면 전체 운송 거리를 최소화하고 최대 단축 거리를 얻을 수 있습니다.
두 지점을 묶어 순회 경로를 구성할 때 발생하는 절약치는 각 지점의 왕복 거리 합에서 두 지점 사이의 직접 거리를 뺀 값으로 도출됩니다.
순회 경로를 구성할 때 절약치가 큰 연결 구간부터 우선적으로 결합하면 전체 운송 거리를 최소화하고 최대 단축 거리를 얻을 수 있습니다.
출처: 한국산업인력공단, Q-Net 자료실 · 공공누리 제1유형 · AI 해설 · 자동 검증 통과