배송 드론 모델링: VRP 접근 vs 계획 모델

이 글에서 다룰 것

1. 모델링

2. 드론 배송 모델링하는 몇 가지 방법

 

모델링을 설명하려는 데 최소 대학교 3년 수준이라 쉽게 설명할 것이지만 그래도 마음의 준비는 해두시기 바랍니다.

 

모델링이라는 것은 통계적 모델링, 수치적 모델링, 시뮬레이션등 다양하게 있겠지만, 우선 실제 우리가 살고있는 환경을 "수학적"으로 "단순화"하여 그럴듯하게 "모사(Simulate)"하는 것을 모델링이라고 합니다. 모든 것을 고려한 것이 아니고, 이것을 통해 중요하다고 생각하는 변수가 전체 시스템에 어떠한 영향을 미치는 가를 확인하고자 하는 방법입니다. 물론 실제로 다 시행착오를 거치면서나온 경험과 지식이 더 유용하고 값질수 있지만, 그에 따른 시간과 비용을 절약하는 방법으로 모델링을 활용하고 있습니다. 그래서 이번 포스팅에서는 드론과 관련된 모델링을 소개해 볼까 합니다.

TSP와 VRP의 차이점을 간단하게 도식화

우선 Vehicle Routing Problem (VRP) 모델에 대해 설명해보겠습니다. 한국말로 풀면 경로계획법 정도로 표현할 수 있겠습니다. 즉, 택배를 배송하는 쿠팡맨이 고객들을 찾아가는 과정에서 어떤 순서로 방문해야, 시간적으로 (혹은 비용적으로) 가장 저렴한가를 푸는 문제인데유. 이것은 Travelling Salesman Problem (TSP)이라는 문제에서 쿠팡맨 차에 들어갈 수 있는 최대 택배개수나 혹은 쿠팡맨도 퇴근해야하니 최대 업무 시간 등을 고려해서 파생된 문제라고 할 수 있습니다. 이 문제들은 손으로 푸는 것이 아니라, 컴퓨터로 계산을해야하는데 이 마저도 정확한 답을 구하기가 힘들어요. 왜냐하면 실제로 가장 빠른 경로를 찾는 다는 것은, 모든 경로의 경우의 수를 하나 하나 찾아서 비교해야하는데 이것을 계산하는데 어마어마한 시간과 노력이 필요하기 때문입니다. 꽤 좋은 컴퓨터로도 불과 15개의 도시를 방문하기 위한 문제를 정확하게(무식하게) 풀려면 17일이나 걸리는 무지막지한 계산이 필요합니다. 그래서 이런 계산을 어떻게 하면 빠르고 손쉽게하는 것이 하나의 연구의 분야이고, 그러한 환경에서 여러 변수들을 고려해서 전체 시스템을 모사(시뮬레이션)하여 영향을 파악하는 것도 마찬가지로 하나의 분야라고 대략적으로 설명할 수 있겠습니다. 

 

두 번째 접근 방식인 계획 모델은 마찬가지로 모델링의 일종인데, 보통 관계식을 통해 수치적 모델링을 하는 것을 말하며, 이 중에서 소개된 VRP와 TSP의 개략화 모델(Continuum approximation, Distance approximation, TSP tour length approximation)을 활용하게 됩니다. 정확한 값을 바탕으로 모델링을 한다기 보다, 방문지의 개수에 따른 예상가능한 평균적인 거리를 미리 도출된 공식을 활용하여 알아낸후 모델링하는데 응용하는 방법입니다.

 

이런 모델들을 통해 1) 드론의 속도를 늘리거나/줄이면 전체 시스템의 비용에 얼마나 변화를 주겠는가? 2) 마포구를 커버하기 위한 드론의 개수얼마나 필요하고 비용은 얼마나 들 것인가? 3) 드론의 배터리 충전비용이 얼마나 줄어야 현재 트럭배송에 비용적인 우위가 생기느냐등 목적에 따라 다양한 결론을 알아볼 수 있습니다.

 

참고

1. Lucas, P. R Program to Estimate Time Consumption of Brutal Force in TSP. 2018