복수순회외판원문제 경로분할모형의 최적화연구 (An Exact Algorithm for the Multiple Traveling Salesman Problem Based on Route-Splitting Formulation)

서지정보

· 발행기관 : 한국생산관리학회
· 수록지 정보 : 한국생산관리학회지 / 19권 / 2호 / 147 ~ 177페이지
· 저자명 : 강성민

초록

복수 순회외판원문제(이하 mTSP)는 단일의 출발지를 떠나 여러 도시를 방문하고 다시 출발지로 되돌아오는 복수의 외판원의 경로를 선정하는 문제로, 모든 도시는 각각 단 1인의 외판원에 의해 방문되며, 목표는 외판원들의 방문경로의 총 길이를 최소화하는 것이다. TSP에 비해서 mTSP는 복수의 외판원을 가정하는 보다 현실적인 모형으로, 이와 같은 상황은 다양한 경로탐색문제 및 일정계획문제에서 발생한다. 한편, mTSP는 보다 더 일반적인 로지스틱스모형 해법알고리듬의 하위문제로도 중요한 역할을 한다. 예를 들어 mTSP구조는 다양한 VRP모형의 공통분모이며 VRP의 해법개발을 위해서 mTSP모형 및 문제구조에 대한 연구가 유용하다.
본 연구의 목적은 mTSP문제의 경로분할모형을 소개하고, 분지열생성 알고리듬에 기반을 둔 최적화 프로세스의 실험을 통해, 특히 Kara와 Bektas의 MTZ유형의 제약식(이하 KB cut)에 관한 분석을 수행하는데 있다. 제한적인 규모의 연산실험에서 KB-cut은 LP하한값을 평균 0.8% 상승시켰으나, 연산시간을 증가시켰다. 결론적으로, 본 연구의 실험에서 KB-cut은 mTSP의 경로분할모형의 최적화를 촉진하지 못했다. 그러나 하한값 평균 0.8%의 상승은 하한값이 98%를 상회하는 상황에서 하한값이 99% 가까이 도달한다는 것을 뜻하므로 그 의미가 작지 않다고 판단된다. 또한 현재 LP 최적화 알고리듬은 여전히 진화중이며 향후 LP 최적화 속도가 충분히 빨라질 경우 하한값 상승의 효과가 나타날 것을 기대할 수 있다. 또한 향후 다양한 cut이 시도될 수 있을 것이다. 본 연구는 사전에 추가되는 제약식에 의한 경로분할모형의 최적화 촉진에 관한 이론적 토대를 제공한다.

영어초록

The multiple traveling salesman problem (mTSP) consists of determining a set of routes for multiple salesmen each of whom starts from and returns to a home city (depot) after visiting a group of other intermediate cities, such that each intermediate city is visited exactly once and the total distance of visiting all cities is minimized.
Compared to the TSP, the mTSP is more adequate to model real life situations, since it is capable of handling more than one salesman. These situations arise mostly in various routing and scheduling problems. The mTSP is also important in that it arises as a subproblem in the solution of more general problems. For example, the VRP instances arising in practice can be extremely difficult to solve, since the underlying mTSP is also complex in nature. This provides the need to efficiently solve the mTSP in order to attack large-scale VRPs arising in real-life situations.
The route-splitting model of the mTSP is introduced, and the exact solution algorithm based on the branch-and-price process is developed. Computational analysis shows that the Kara and Bektas' constraints improve LP lower bounds by about 0.8%. Even though Kara and Bektas' constraints' effect to expedite our branch-and-price optimization process developed for the route-splitting model of the mTSP was not confirmed in our experimentation, we expect to try other cuts afterwards. This work provides the theoretical framework of enhancing bounds with various pre-installed cuts in the route-splitting approach.

참고자료

· 없음