다중 경유지 최적 경로 탐색, 그 알고리즘에 대하여
TSP (Traveling Salesman Problem)
—
Ep.1
택배기사님이 100곳에 물건을 배송할 때, 기사님은 어떤 경로로 이동해야 가장 빠르게 배송할 수 있을까요? 기사님이 들리는 100곳의 경로 중, 우리 집은 어떤 방법을 통해 순서가 정해질까요? 택배가 언제쯤 도착할지 궁금해서 [실시간 배송 위치 조회]를 눌러 보신 분들이라면 여러 경유지를 들려 나에게까지 오는 기사님의 경로를 보신 적 있을 거예요.
이번 글은, 여러 경유지를 들려야 할 때 최적 경로를 탐색하는 알고리즘에 대해 이야기해보려 합니다.
택배 물류는 일반적으로 집하 -> 지역 대리점 -> 도시 터미널 -> 전국 허브 -> 도시 터미널 -> 지역 대리점 -> 고객(배송) 으로 분류되는 프로세스를 갖추고 있습니다.
대리점은 여러 위치로 방문해 물건을 집하 한 후, 그 물건들을 터미널로 전달하고, 터미널은 여러 대리점에서 수집 된 물건들을 모아 다시 허브로 전달합니다. 허브는 전국 각 지역 터미널에서 전달받은 물건들을 다시 배송 주소지 기준 관할 터미널별로 재 분류하는 역할을 하죠. 허브에서 분류가 완료된 우리의 택배는, 다시 터미널을 거쳐 지역 대리점에 도착해야 기사님을 통해 우리에게까지 배달될 수 있습니다.
이러한 택배 물류 프로세스에서 한 차량이 여러 경유지를 방문하는 경우는 지역 사무소 택배 기사님이 고객 위치를 방문할 때 입니다. 바쁜 기사님은 최소 비용과 한번의 운행으로 집하, 배송을 병행할 수 있는 경로를 고민하게 되죠.
이런 고민에 제시되는 해법이 물류 전문가의 TSP (Traveling salesman problem) — 최적 경로 탐색 알고리즘 입니다.
아이나비시스템즈에서는 TSP 알고리즘을 두가지 모델로 나누어 개발하고 있는데요. Picking Position으로 이동 후, 다중 방문지를 방문/배송하는 기본 모델과, 배송 중 On-demand 요청을 포함한 실시간 모델입니다. 이 글에서는 기본 모델에 대해서 우선 얘기해볼게요.
TSP는 전세계 도시를 최소 거리로 방문해야 하는 불쌍한 영업사원의 이야기로 유명합니다.
일반적으로 TSP 알고리즘은 NP-Hard 문제로 알려져 있습니다.
얼핏 보기에는 쉬워 보이지만 직접 계산하려면 답을 구하기 어려운, 그런 문제 말이예요. NP Hard 문제의 정답을 찾기 위해서는 인내심을 가지고 많은 양의 계산을 통해야 합니다. 그렇다보니 조금 더 효율적인 이유로, TSP 알고리즘은 수행 시간과 규칙의 틀을 정하고 이에 만족하는 가장 가까운 해답을 구하는 개념으로 실무에 적용되고 있습니다.
훨씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는데 만족하는거죠.
Distance Matrix TableTSP 알고리즘 수행 절차를 최대한 쉽게 풀어보면 다음과 같습니다.
도시 간 비행기로 이동할 수 있는 모든 거리를 Matrix 형태의 Table로 작성합니다.
(현재 영업사원의 위치도 포함해 작성해주세요.)
작성된 Table 위 출발지에서 방문할 임의의 도시 1개를 선택합니다.
선택한 도시에 도착했다고 가정하고, 다음 방문할 도시를 선택합니다.
위 과정을 반복해 모든 도시를 방문할 수 있는 경로 계획 하나를 완성합니다.
Ex. 영업사원이 1번에서 출발한다고 가정할 경우 임의로 산정한 경로 계획
: 1 -> 5 -> 2 -> 4 -> 8 -> 3 -> 7 -> 6
자, 이제 남은 일은 반복 입니다. 중복되지 않는 모든 경로 계획을 위 Matrix에서 조합해 정리하면 됩니다.
(8개의 도시를 방문할 경우, 중복되지 않는 모든 경로 계획 개수는 8! =8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320 이 되겠죠.)
위에서 작성되는 모든 도시간의 이동 거리를 정리한 Matrix를 전문용어로 Distance Matrix라고 합니다.
Distance Matrix는 특정 위치 간 거리를 기록하는 방식에 따라 가치가 달라지게 됩니다. 직선 거리로 작성하는 방법이 대표적이고, 지도의 도로 데이터를 기반으로 경로를 탐색해 실제 소요되는 (회전 정보, 교통정보가 반영된) 경로 거리를 기반으로 작성하는 방법도 있습니다. 이때 이동체의 종류에 따른 제약 조건, 즉 무게 지정 도로, 높이 지정 도로, 도로 폭 제약 등을 반영한 결과 거리를 기반으로 작성한다면 더 가치 있는 Distance Matrix가 되겠죠.
간단하게 문제를 풀자면, “Distance Matrix를 반영한 TSP 알고리즘을 통해, 모든 방문지의 전체 조합을 줄 세워 그 중 가장 짧은 거리를 갖는 방문 순서를 선택하면 그게 최적의 방문 순서입니다.” 일 것만 같습니다.
하지만 언제나 그렇듯 실제 서비스에 적용할 때는 다양한 이슈가 생기곤 하죠. 그래서 우리는, 물류시장의 TSP 이슈를 지도 데이터 구축, 경로탐색 및 GIS 전문가 입장에서 해법을 제시해보고자 연구를 계속하고 있습니다.
실제 경로 거리를 Distance Matrix로 만들어 TSP 알고리즘을 수행해본 결과 문제는 다음과 같았습니다.
1. 경로 탐색 결과로 만들어진 Distance Matrix의 거리 값은 도착지 도로의 방향성 탐색이 적용되어, 보이지 않는 거리가 더 부가되었습니다. 그렇다보니 자연스레 방문 순서에 대한 의문을 제기하게 되었죠.
2. 순수하게 경로 탐색 엔진을 기반으로 거리에 적용해보니, 골목길 등의 작은 도로는 지나가지 않도록 안내하는 기존의 (차량 주행 베이스의) 경로 탐색 엔진을 적용하기 어렵다는 점을 깨닫게 되었습니다. (우리의 배달 목적지는 대부분 골목길 안 어딘가에 위치해 있을 텐데 말이에요.)
3. TSP 알고리즘 수행 중, 가장 거리가 먼 방문지들의 경우 대부분 장거리 이동으로 산출되는 현상이 발생했습니다. 사람의 직관으로는 잘못된 결과처럼 판단되지만, 알고리즘의 원리로 따져보면 맞는 산출인 경우들이 있었죠. 하지만 실제 물류를 운송하는 분들은 기사님들, 즉 사람이다 보니 해당 결과를 받아들이기 어려울 것 같았습니다.
문제 1,2 참고 이미지
문제 3 참고 이미지우리는 이러한 이슈들을 개선하기 위해 아래와 같은 아이디어를 적용했습니다.
1. 1차로 양방향 도로에 방문지가 있는 경우, 무조건 2차로 양방향 이상 도로로 방문지 매칭
2. 방문지 위치에 따른 회전 가중치 설정
- 회전 가중치 : 회전시 거리를 더 길다고 논리적으로 부가하는 거리
위 그림과 함께, 회전 가중치에 대해 예시를 들어볼게요.
단순히 계산한다면, A에서 B까지의 물리적 도달 거리는 150M 입니다.
하지만 실제로 위 그림 속 거리를 주행한다면 우리는 좌회전 신호를 대기하게 됩니다.
이럴 때 발생하는 신호 대기 시간, 즉 논리적 거리를 회전 가중치로 설정합니다.
시속 30km/h로 주행 시 150M를 이동하는데 18초가 소요된다. (초속 8.33m)
평균 좌회전 대기 시간 (경험치) 은 1분 30초 이다. (90초)
좌회전 대기 시간을 포함한 A -> B의 도달 시간은 108초 이다.
108초를 거리 값으로 환산하면 900M 이다. (108초 * 8.33M)
이렇게 A -> B 의 논리적 거리를 900M로 설정해주는 거죠.
3–1. 유턴 제한 조건 조정
3-2. 경로 탐색 엔진에 적용된 도로 속도, 등급을 무시하거나 TSP 알고리즘에 맞는 전용 속도, 도로 등급을 재정의 해 밀집되어 있는 방문지들은 알고리즘에서 순차적으로 방문할 수 있도록 튜닝
이외에도 다양한 아이디어들을 시도하며 어느것이 가장 좋은 해답이 될 것인지 고민했고, 원하는 결과를 만들기 위해 경로 탐색의 사전 조건 및 실시간 조건 등을 시도하다 보니 드디어 어느정도 납득할 수 있는 TSP 알고리즘 결과를 얻기 시작했습니다.
TSP 알고리즘 — 직진 경로 위주의 배송 순서 산출 결과“아이나비시스템즈의 경로 탐색 엔진 기술로 TSP 엔진을 만들면 잘 만들 수 있지 않을까?” 라는 질문에서 시작된 ‘TSP 알고리즘 — 다중 경유지 최적 경로 탐색 개발기’는 이렇듯 가능성을 실현 중에 있습니다. 아직 완벽하지는 않습니다. 앞으로는 교통 정보 도로 속도를 반영하고, 도로의 특성을 이동체의 종류에 따라 다르게 평가해 Distance Matrix로 구성할 수 있도록 시도해보는 단계가 남았어요.
우리의 목표는 이 글에서 설명한 Distance Matrix API를 자랑스럽게 서비스하는 것 으로, 이를 위해 사용자로부터 이동체의 종류 및 제약 조건을 제공 받아 그에 대응하는 Matrix 결과를 산출해내야 합니다.
이러한 다양한 이슈 해결과 테스트를 거쳐 24년에는 On-demand 요청을 포함한 실시간 모델 출시가 가능하게끔 노력 중에 있습니다. 실시간 모델 출시를 알리는 그 날까지 아이나비시스템즈는 계속해서 질문을 던지고, 해답을 찾아가겠습니다.
—
by 아이나비시스템즈 자율주행기술그룹
