배송 최적경로 — '최단거리 = 최소비용'을 의심하고 간선 가중치를 다시 설계했다

분류는 자동화됐는데, 마지막 한 구간은 사람의 감이었다

택배 물동량은 20년 사이 40배가 됐다. 그런데 지역터미널에서 각 집까지의 경로는 여전히 기사가 알아서 정하고 있었다.

2017년 국내 연간 택배 물동량은 23억 1,946만 상자였다. 1998년 5,795만 상자에서 20년이 채 되지 않아 40배 가까이 늘어난 수치다.

물량을 처리하는 앞단은 이미 자동화되어 있었다. 국내 물동량의 43%를 담당한다는 CJ대한통운을 보면 허브앤스포크 방식으로 하루 평균 270만 개를 집화하고, 간선 수송 트럭 2,500대로 옮긴 뒤, 대분류 허브터미널 5곳과 소분류 지역터미널 270곳을 거쳐 배송기사 15,000명이 배달한다. 거점 29곳은 정량·정성 평가와 시뮬레이션으로 선정했다고 한다.

그런데 지역터미널에서 각 도착지까지, 마지막 한 구간의 경로만은 기사가 스스로 정하고 있었다. 2018년 4월 CJ대한통운 택배기사 인터뷰에는 어디가 언제 막히는지, 시기별로 어느 구역에 어떤 물건이 많이 오는지를 몸으로 익혀야 물량을 늘려 갈 수 있다는 취지의 말이 나온다. 지리적·상황적 맥락을 오랜 기간의 노하우로 습득해야 효율이 나는, 주먹구구식 경로 선택 구조였다.

산업공학은 시스템에서 비효율을 찾아 개선하는 학문이라고 배웠는데 정작 가장 끝단이 개인의 경험에 맡겨져 있었다. 이 과제는 거기서 출발했다.

'최단거리 = 최소비용'이라는 가정을 문제로 세우다

교과서의 최단경로는 거리만 본다. 실제 배송비는 길이 막히는 정도, 싣는 짐의 무게, 좌회전인지 우회전인지에 따라 달라진다.

기존 방법론은 경로 길이와 차량 용량을 주로 다뤘다. 그 밑에는 최단거리로 가면 비용도 최소라는, 따로 검증하지 않는 가정이 깔려 있다. 이 가정을 문제 삼는 데서 과제를 시작했다.

문제를 다시 세웠다. 대상은 한 대의 차량이 도는 한 경로가 아니라 여러 대의 차량이 한 지역을 나눠 배송할 때 시스템 전체의 운영비를 최소화하는 문제이고, 이를 간선에 비용 가중치가 달린 가중 그래프 위의 문제로 옮겼다. 이렇게 놓으면 질문이 달라진다. 어느 길이 가장 짧은가가 아니라 어느 길이 가장 싼가이며, 두 답이 같다는 보장은 없다.

가중값에 넣기로 한 것은 세 가지였다.

1. 구간별 교통상황(정체·서행·원활)에 따른 구간거리별 평균 시속, 즉 소요시간
2. 차량 적재량과 화물 무게에 따른 가중치 — 무거울수록 연료를 더 쓴다
3. 좌회전보다 우회전 우선 — 우회전은 회전신호를 고려하지 않아 적색일 때도 진행할 수 있다

제약조건은 차량별 용량 한정, 샘플 지역은 서울시청 부근으로 정했다. 미리 적어 두면 이 세 가지 중 실제로 그래프에 들어간 것은 첫 번째 하나뿐이었다. 나머지 둘이 왜 빠졌는지는 뒤에서 따로 적는다.

선행 연구 — VRP 아홉 갈래와, 거기 없던 것

차량경로문제는 1959년부터 갈라져 나온 계보가 있었다. 조사해 보니 제약은 대부분 거리와 용량, 시간창에 몰려 있었다.

차량경로문제(VRP)는 1959년 George Dantzig와 John Ramser의 알고리즘에서 시작해 1964년 Clarke and Wright가 그것을 중심으로 발전시켰다. 이후 어떤 제약을 추가하느냐에 따라 아래처럼 갈라졌다.

택배는 고객이 정한 기한 제약이 없고 차량 용량은 제한적이라는 가정에 해당하므로 두 갈래를 더 파고들겠다고 적어 놓고, 실제로는 VRP·CVRP에 VRPTW까지 셋을 정리했다. VRPTW는 각 노드에 허용 시간대를 달고 소요시간과 대기시간의 합을 최소화하는 문제다.

최단경로 쪽으로는 다섯 가지를 조사해 요약했다.

• MST-SP — 최소신장트리로 무방향 그래프의 점대점 최단거리를 찾는다. 각 노드의 유입 호 길이를 계산해 최소 호를 고르고, 사이클을 만드는 유출 호는 삭제하며 노드를 확장한다. 목적지 노드의 유입 최소 가중치 호가 두 개 선택되면 종료.
• 유전자 알고리즘 — 출발·도착·중간 노드의 유클리드 거리로 개체를 만들고 선택·교차 연산으로 새 개체를 생성해 적합도 조건에 대입, 중간 경로 노드를 뽑는다.
• 시뮬레이티드 어닐링 — 현재해 x에서 p-value만큼 변경한 이웃해 y를 만든다. 참고한 연구는 p-value 5%, 즉 총 물동량의 5%를 같은 차량 경로 안에서 순서만 바꾸거나 다른 차량 경로로 옮기는 식으로 이웃해를 만들었다. 목적함수는 총 차량운행시간(운반 작업수행시간 + 공차 이동시간)이다.
• Sulee SP — 경로 노드의 유출·유입 최소 가중치 호를 모아 단절 없는 경로를 구성한다.
• 타부 서치 — 다음 절에서 따로 다룬다.

국내 허브 네트워크 설계 연구는 조용훈의 택배산업의 네트워크 최적화에 관한 연구에 정리된 계보(윤문길 2000, 추창엽 2001, 정기호·고창성 2002, 정승주 2003, 김동규 외 2006)를 재인용했다.

실무의 배송계획 분류도 함께 봤다. 다이어그램 배송은 배송범위 30km 이내에 1일 2회 또는 1.5회, 경로 배송은 60km 이상에 1일 1회, 적합 배송은 숙련된 배차담당자가 적재율을 보고 정하는 방식이다. 세 번째는 결국 사람의 판단이다.

조사를 마치고 남은 판단은 이랬다. 기존 연구는 수리적 모형 중심이고 추가된 조건은 용량 제약과 운송거리에 몰려 있다. 교통상황에 따른 시간 조건과 지역별로 다른 리드타임을 간선 가중치에 복합적으로 얹은 연구는 찾지 못했다. 그래서 그래프에 가중치를 복합적으로 넣는 쪽으로 방향을 잡았다.

남의 구현부터 돌려 봤다 — 공개된 VRP 예제

직접 짜기 전에, 이미 있는 구현이 무엇을 입력으로 받고 무엇을 내놓는지부터 확인했다.

구글 디벨로퍼가 공개한 경로 최적화 예제를 가져다 실험 설계의 뼈대로 삼았다. 예제는 지점을 블록 단위 좌표로 두고, 평균적인 도시 블록 크기 114m × 80m를 곱해 실제 좌표로 환산한다.

지점은 17개다. 첫 지점이 depot이고 택배로 옮기면 서브터미널, 나머지 16개가 배송 도착지이며 배송 차량은 4대다. 지점 사이 거리는 유클리드가 아니라 맨해튼 거리 — 두 좌표의 x 차이와 y 차이의 절대값을 더한 값 — 로 잰다. 도심의 격자 도로를 가정한 셈이다.

용량 제약이 붙는 CVRP로 넘어가면 여기에 각 지점의 수요를 돌려주는 계산이 하나 더 붙고, 그 수요를 차량 용량과 대조해 경로를 자른다. 이 구조를 보고 정리한 것이 하나 있다 — 내 문제에서는 거리를 재는 자리에 두 배송지 사이의 소요시간을 실시간 교통정보에서 받아 오는 계산을 끼워 넣으면 된다.

Greedy와 Tabu Search — 793과 637

여러 대의 총 운영비를 줄이는 쪽에 가장 가까운 기존 해법이 타부 서치였다. 두 해를 실제로 뽑아 비교했다.

타부 서치는 인접해로 반복 이동하며 개선하되, 최근에 고려한 해를 금기 목록에 넣어 같은 지역을 맴돌거나 지역 최적에 갇히지 않게 하는 지역탐색 기법이다. 이기종 차량경로문제에서 고정비까지 포함한 총 운영비를 줄이는 데 쓰인다는 점이, 여러 대로 한 지역을 나눠 배송하는 내 문제 설정과 가장 가까웠다. 예로 든 방식은 이렇다. A와 B가 붙어 있고 C가 멀리 있으면 A·B를 먼저 돌고 C로 가는 편이 짧다. 타부 서치는 가장 가까운 이웃으로 만든 초기해에서 시작해 두 지점의 방문 순서를 바꿔 총 이동거리를 비교하고, 이미 지나온 해는 금기 목록에 넣어 되돌아가지 않게 한다.

참고한 타부서치와 집합 분할을 이용한 차량경로문제의 발견적 기법은 여기에 한 단계를 더 붙였다. 경로 사이에서 지점을 교환하는 것을 반복한 뒤, 그렇게 변동된 적재량을 실을 수 있는 최소 차량을 다시 할당해 전체 총비용을 줄이는 방식이다.

배송지 30개, 차량 5대 설정에서 greedy 해와 타부 서치 해를 각각 뽑았다.

총비용은 793.0에서 637.0으로 156.0, 19.7% 줄었다. 두 해가 방문한 지점 집합은 1번부터 30번까지로 같고 달라진 것은 차량별 부하 배분이다. 차량당 방문 지점 수가 7·8·7·6·2에서 7·5·6·7·5로 고르게 바뀌었다. 8곳을 맡던 1번 차량이 5곳으로 줄고, 2곳만 맡던 4번 차량이 5곳으로 늘었다.

표를 그대로 옮기면서 눈에 걸린 것이 하나 있다. 타부 해의 0번 차량 경로에는 출발지 0이 겹쳐 찍혀 있다. 방문 집합 자체는 유효하다. 구해 온 구현은 분량이 많아 보고서에 첨부하지 못했고, 이 비교는 실행 결과만 남았다.

배송망을 가중 그래프로 옮기다

정점은 배송지와 터미널, 간선은 경로. 여기까지는 정의이고, 실제로 정할 일은 이 그래프가 어떤 그래프인지였다.

그래프는 정점과 간선으로 객체 사이의 관계를 나타내는 자료구조다. 택배로 옮기면 배송지와 터미널이 정점이고 배송경로가 간선이다. 같은 방식으로 교통시스템은 정거장이 정점, 정거장 사이의 도로가 간선인 교통그래프가 된다.

내 문제의 그래프가 어느 쪽인지부터 정리했다.

• 간선의 방향성 — 방향그래프와 무방향그래프. 이 과제에서는 A에서 B로 가는 시간과 B에서 A로 오는 시간이 같다고 두고 무방향으로 다뤘다.
• 정점과 간선의 수 — 완전(모든 정점이 서로 연결)·다중(두 정점 사이 간선이 둘 이상)·연결(모든 정점 사이에 경로가 있음)·희소(정점이 간선보다 많음)·밀집(간선이 정점보다 많음)·부분그래프
• 간선에 값이 붙으면 가중그래프. 배송에서는 그 값이 경로의 길이나 소요시간이 된다.

트리는 사이클이 없는 연결그래프이고, 신장트리는 정점이 n개일 때 간선 n-1개로 모든 정점을 잇는 부분그래프다. 가중값의 총합이 최소인 신장트리가 최소비용 신장트리다. 배송그래프에 지리적·시간적 가중값을 넣으면 그 합이 최소인 트리를 찾는 문제가 된다.

먼저 네이버 지도 캡처 위에 서브터미널 0번과 배송 도착지 16곳을 놓고 정점 사이를 직선으로 이어 간선으로 삼았다. 직선은 표현을 쉽게 하기 위한 것이고, 실제로는 정점에서 정점으로 가는 도로를 똑같이 거치는 것으로 보고 거리 가중값을 준다. 보고서는 이 배치를 네이버 지도에서 임의로 가정했다고만 적었다. 다만 이 글을 쓰면서 앞 절 예제의 그림과 겹쳐 보니 17개 정점의 상대 위치가 예제의 좌표와 하나씩 대응한다. 0번이 (4, 4), 왼쪽 아래 15번이 (0, 8), 오른쪽 위 2번이 (8, 0)이다. 임의로 찍었다기보다 예제 좌표를 그대로 옮겨 온 것으로 보이지만, 보고서 본문에는 그런 언급이 없다.

제거하는 Kruskal, 더하는 Kruskal, 그리고 Prim·Dijkstra·Floyd

다섯 알고리즘을 방식과 종료조건 기준으로 정리하고, 작은 부분그래프에 손으로 적용해 두 Kruskal이 같은 답을 내는지 확인했다.

Kruskal 1과 2가 같은 트리를 내는지 작은 부분그래프로 확인했다. 앞의 배송 그래프에서 정점 1·3·4와 간선 (1,3)=15, (1,4)=7, (3,4)=3만 떼어 왔다. 내림차순 목록 15, 7, 3에서 가장 큰 (1,3)을 제거하면 간선이 3-1=2개 남아 종료된다. 오름차순 목록 3, 7, 15에서 (3,4)와 (1,4)를 차례로 추가해도 같은 두 간선이 남는다.

Kruskal과 Prim은 최소비용 신장트리를, Dijkstra와 Floyd는 최단경로를 낸다. 둘은 답의 형태가 다르다. 신장트리는 모든 정점을 잇는 최소 트리이지 한 대의 차가 돌고 돌아오는 순회 경로가 아니다. 이 차이가 마지막에 이 과제의 한계로 돌아온다.

실험 — 서울시청 부근 다섯 정점과 TOPIS

본론에 들어가면서 그래프를 다시 잡았다. 서울시청 부근의 실제 지도와 실시간 교통데이터 위에 정점 다섯 개다.

본론의 문제 정의를 다시 적으면 이렇다.

• 가중값에 넣을 것 — 구간별 교통상황(정체·서행·원활)에 따른 구간거리별 평균 시속과 소요시간, 적재량·화물 무게에 따른 가중치, 좌회전보다 우회전 우선
• 제약조건 — 차량별 용량 한정
• 샘플 지역 — 서울시청 부근 지역 배송경로
• 데이터 — 서울특별시 교통정보 시스템 TOPIS(topis.seoul.go.kr)의 실시간 교통정보. 구간거리와 그에 따른 평균시속을 조사할 수 있었다

TOPIS 화면에서는 구간의 소통 상태가 색으로 구분된다. 그 위에 배송지 4곳과 지역터미널 1곳, 모두 다섯 개 정점을 잡고 A부터 E까지 이름을 붙였다. A가 지역터미널이다. 간선은 배송지 사이의 경로로, 화면에는 직선으로 그렸지만 실제로는 도로 경로를 지나는 것으로 본다.

간선은 7개다. 정점 5개의 완전그래프라면 10개여야 하니 B–D, B–E, C–D 세 쌍은 간선으로 잡지 않은 셈이다. 즉 이 그래프는 완전그래프가 아니라 희소한 부분그래프이고, 뒤의 인접행렬에서 이 세 쌍이 무한대로 들어간다.

가중치 ① 거리를 시간으로 바꾸다

같은 거리라도 막히는 구간은 시간이 더 든다. 그리고 그 시간이 인건비와 연료비다.

거리를 그대로 가중값에 넣는 대신 실시간 교통정보에 따른 소요시간을 가중값으로 뒀다. 수집 절차는 단순했다. 간선 하나에 대응하는 두 지점의 주소를 네이버 지도 길찾기에 넣고, 자동차 기준으로 안내되는 소요시간과 거리를 그대로 읽어 지도 위에 적었다. 화면에는 택시비와 주유비도 함께 표시되므로 같이 기록해 두었다.

• B–C — 종로구 관수동 161-7 → 중구 을지로2가 203. 오후 3:31 조회에 12분 1.9km, 택시비 3,000원, 주유비 210원. 교통상황 때문에 곧장 가지 않고 서쪽으로 크게 돌아가는 경로가 안내됐다.
• D–E와 같은 값(8분 1.3km)이 찍힌 조회는 롯데백화점 본점 → 종로구 공평동 17이었다. 오후 3:21 조회에 택시비 3,000원, 주유비 189원.

이렇게 일곱 간선을 채운 결과가 아래 표다.

표를 채우고 나니 순위가 어긋나는 지점이 보였다. C–E는 거리로는 세 번째로 짧은데 시간으로는 다섯 번째다. D–E와 A–B가 그 앞으로 올라온다. Kruskal도 Prim도 정렬된 순서대로 간선을 고르는 알고리즘이니, 이 뒤집힘은 곧 다른 트리를 뜻한다.

보고서는 시간 가중치로만 트리를 구했다. 이 글을 쓰면서 같은 표의 거리 열로 다시 정렬해 보니 실제로 트리가 갈렸다. 거리 기준 트리는 A–C, A–D, C–E, A–B로 합이 4.36km이고 시간 기준 트리는 A–C, A–D, D–E, A–B로 합이 30분이다. 간선 하나가 C–E에서 D–E로 바뀐다. 시간 기준 트리를 거리로 다시 재면 4.46km, 거리 기준 트리를 시간으로 다시 재면 32분이다. 0.10km를 더 달리는 대신 2분을 아끼는 선택이다.

차이가 크다고는 못 한다. 정점 5개짜리 그래프에서 간선 하나가 바뀌었을 뿐이다. 그래도 최단거리와 최소시간이 같은 답을 준다는 보장이 없다는 것은 이 작은 그래프에서도 확인됐다.

쓰지 못한 두 가중치 — 화물 무게와 회전 방향

설계한 세 가중치 중 둘은 그래프에 들어가지 못했다. 하나는 계산해 보고 스스로 버렸고, 하나는 옮길 방법을 찾지 못했다.

두 번째 가중치는 화물 무게였다. 배송지마다 무게를 임의로 정해 그래프에 적었다. D 5kg, E 10kg, B 20kg, C 35kg으로 합 70kg이다. 배송 순서가 바뀌면 각 간선을 지날 때의 적재 중량도 달라지므로 원래 의도는 이것을 간선 가중치에 반영하는 것이었다.

그전에 무게가 연비에 주는 영향의 크기부터 확인했다. 승용차의 중량변화에 따른 연비연구에 따르면 1인 탑승과 3인 탑승, 즉 131kg 차이일 때 50km 주행에서 연료비 차이는 196원이었다. 이 그래프에서 가장 긴 간선이 2km이고 전체 화물이 70kg이다. 유의한 영향을 주지 않을 것으로 판단해 무게를 가중치에서 뺐다. 결과적으로 무게는 그래프에 표기만 되고 계산에는 들어가지 않았다. 다만 이 판단은 승용차 논문의 수치를 택배 차량에 그대로 옮긴 것이라, 적재 중량 범위가 훨씬 큰 실제 배송 차량에도 같은 결론이 나오는지는 확인하지 못했다.

세 번째는 회전 방향이었다. 우회전은 좌회전과 달리 회전신호를 고려하지 않아 적색일 때도 진행할 수 있으니 같은 교차로라도 손실 시간이 다르다는 것이 근거다. 실제 사례로 UPS를 조사했다. 운전석이 좌측에 있는 국가 기준으로 좌회전 비율을 10%까지 낮추는 노선 설계 소프트웨어를 만들었고, 발표된 수치는 아래와 같다.

미국 TV 프로그램 미스버스터즈에서 이 정책의 실효성을 측정해 좌회전을 하지 않을 때 연료가 절감되는 것이 입증됐다는 기록도 함께 정리했다. 그런데 여기서 멈췄다. 우회전 선호를 간선 가중치로 옮기려면 각 간선이 어느 교차로에서 어느 방향으로 도는지를 알아야 하는데, 네이버 지도 길찾기 화면에서 읽어 낸 소요시간과 거리에는 그 정보가 없다.

회전 방향 가중치는 실험 그래프에 들어가지 못하고 보고서 마지막의 향후 연구과제 네 번째 항목으로 밀렸다. 문제 정의에는 세 가지 가중치를 적었지만 그래프에 실제로 들어간 것은 시간 하나였다.

손으로 돌린 Kruskal, 인접행렬로 돌린 Dijkstra

다섯 정점 일곱 간선이면 종이에서 끝까지 갈 수 있었다. 두 Kruskal이 같은 트리로 수렴하는지부터 확인했다.

시간 가중치를 내림차순으로 목록화하면 13 (A,E), 12 (B,C), 10 (E,C), 9 (A,B), 8 (D,E), 7 (A,D), 6 (A,C)이다. Kruskal 1은 여기서 가장 큰 (A,E)부터 제거한다. 이어 (B,C)와 (E,C)를 제거하면 간선이 5-1=4개 남아 더 제거할 것이 없어 종료된다. Kruskal 2는 같은 목록을 뒤집어 오름차순으로 놓고 작은 것부터 추가한다.

최종 트리는 A–C 6, A–D 7, D–E 8, A–B 9로 합 30분이다. 지역터미널 A에서 C·D·B로 직접 가고 E는 D를 거쳐 간다. 두 방향의 Kruskal이 같은 트리로 수렴했다.

Dijkstra는 인접행렬을 만들어 돌렸다. 가는 것과 오는 것이 둘 다 가능하고 그에 따른 시간도 동일하다는 전제로 진행했으므로 행렬은 대칭이고, 간선이 없는 세 쌍은 무한대다.

출발 정점 A를 집합 S의 초기값으로 두고 인접 정점의 가중값을 배열의 초기값으로 설정한 뒤, 가장 가까운 C를 S에 넣고 그로 인해 단축되는 경로가 있는지 확인하는 식으로 진행했다. 여기까지는 손 계산으로 문제없이 끝났다.

네 알고리즘을 옮기다 만 자리

Kruskal·Dijkstra·Prim·Floyd를 코드로 정리했다. 실행까지는 이어지지 못했다.

실제 교통정보와 운송장 데이터를 받아 실험하는 것은 무리라고 판단하고, 소요시간을 가중치 행렬에 채우는 구조와 네 알고리즘을 정리하는 데까지 갔다. 거리를 재는 자리에는 두 배송지 사이의 소요시간을 실시간 교통정보에서 받아 오는 계산을 두기로 했고, 간선끼리는 가중값의 차로 비교해 오름차순으로 정렬하도록 했다.

네 알고리즘이 쓴 자료구조와 시간복잡도를 정리하면 이렇다.

다시 읽으면 걸리는 곳이 몇 군데 있다. Dijkstra는 도달할 수 없는 정점이 남으면 처리하지 못한다 — 연결그래프를 가정하고 짠 것이다. Floyd는 배송 그래프가 아니라 정점 7개짜리 교재 예제에 그대로 얹혀 있어, 이 과제의 그래프에는 한 번도 적용되지 않았다. 그리고 보고서 본문은 Kruskal 1(내림차순 제거)을 먼저 설명하는데, 실제로 옮긴 것은 오름차순으로 정렬해 추가하는 Kruskal 2 방식이다.

네 알고리즘을 묶어 한 번에 실행하는 부분은 만들면 될 것 같다는 문장으로 끝난다. 결국 다섯 정점 실험은 손으로 계산한 결과이고 코드는 통합 실행되지 않았다. 확인한 것과 확인하지 못한 것을 나누자면, 가중값을 시간으로 바꾸면 트리가 달라진다는 것은 손 계산으로 확인했고, 그것이 배송지 수백 개 규모에서도 유지되는지는 확인하지 못했다. 정점 5개에서는 O(n²) Dijkstra와 O(n³) Floyd가 아무 문제를 일으키지 않지만, 실제 지역터미널 하나가 맡는 배송지 수를 생각하면 우선순위 큐 기반으로 다시 짜야 한다는 것도 이 시점에서는 정리만 해 뒀다.

가중치가 8분 만에 바뀌었다 — greedy의 전제가 흔들린 지점

같은 출발지와 도착지를 몇 분 간격으로 다시 조회했더니 소요시간이 12분에서 18분이 됐다.

과제를 마무리하며 같은 구간을 다시 조회했다. B–C 구간, 종로구 관수동 161-7에서 중구 을지로2가 203까지다.

8분 사이에 같은 구간의 가중값이 12에서 18로 올랐다. 같은 시각으로 표시된 두 캡처 사이에서도 18분 3.3km와 10분 1.2km로 갈린다. 서울 도심에서는 실시간 교통정보가 이 정도로 움직인다는 것을 과제를 하면서 처음 체감했다.

이것이 알고리즘의 전제를 건드린다. Kruskal도 Prim도 Dijkstra도 greedy 기법이고, 가중값이 고정되어 있다는 전제 위에서 지금 가장 좋은 간선을 고른다. 실행 도중 가중값이 바뀌면 앞서 확정한 선택이 더 이상 최적이 아니다. 위 표대로라면 B–C는 12에서 18로 올라 A–E(13)와 순위가 뒤집히고, 앞 절에서 Kruskal 1이 두 번째로 제거했던 간선이 달라진다.

보고서는 이 문제를 향후 과제 첫 번째로 적었다. 실시간 값을 그대로 쓰는 대신 빅데이터 분석으로 평균적인 교통흐름을 예측해 가중값에 넣자는 것이다. 이 과제에서 그것까지는 하지 못했다.

남은 것 — 최소비용 신장트리는 순회 경로가 아니다

가중치를 다시 설계한 데까지는 갔다. 그런데 최소비용 신장트리는 애초에 배송기사가 도는 경로가 아니었다.

이 과제로 얻은 것은 배송 경로를 자동으로 찾아 주는 프로그램이 아니라, 실시간 교통정보와 배송지 데이터를 받아 경로를 지정하는 프로그램의 기본 알고리즘 스케치다. 지역터미널에서 각 집까지의 경로 선택을 기사의 지리적 경험에 맡기지 않고 자동화할 수 있으리라는 기대까지가 결론이었다.

보고서 안에서 스스로 지적한 한계가 하나 있다. 이런 알고리즘으로 최소비용 신장트리를 찾더라도 다시 돌아오는 비용과 여러 대의 차량을 운영하는 총 비용을 생각하면 더 많은 비용이 들 수 있다는 것이다. 신장트리는 모든 정점을 잇는 최소 트리이지 한 대의 차량이 출발지로 돌아오는 순회 경로가 아니다. 문제를 MST로 옮긴 순간 답의 형태가 문제의 형태와 어긋났다. 타부 서치를 따로 조사한 것도 이 어긋남 때문이었는데 조사에서 그쳤다.

향후 과제로 네 가지를 적었다.

1. 실시간 값 대신 빅데이터 분석으로 예측한 평균 교통흐름을 가중값에 넣기
2. 로켓배송처럼 시간 제약이 있을 때, 제약을 만족하면서 최단시간·최소비용을 찾는 알고리즘
3. 오르막·내리막 같은 지리 정보를 연료 소모 기준으로 가중값에 넣기
4. 좌회전 대기시간과 좌회전 시 사고 발생 가능성을 가중값에 넣기

세 번째와 네 번째는 본론에서 넣으려다 넣지 못한 가중치를 다시 적어 둔 것이다. 결과만 보면 시간 가중치 하나로 정점 5개짜리 트리를 하나 얻은 것이 전부지만, 자료구조와 알고리즘을 직접 짚어 본 경험이 남았고 이 과제를 계기로 빅데이터융합학과 복수전공을 결심했다.