복수순회외판원문제 경로분할모형의 최적화연구
An Exact Algorithm for the Multiple Traveling Salesman Problem Based on Route-Splitting Formulation
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
복수 순회외판원문제(이하 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이 시도될 수 있을 것이다. 본 연구는 사전에 추가되는 제약식에 의한 경로분할모형의 최적화 촉진에 관한 이론적 토대를 제공한다.
Abstract
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.
참고문헌 (32)
- 강성민, "비대칭차량경로문제의 경로분할모형에 관한 연구", 한국생산관리학회지, 18(4), pp.3~31 (2007)
- 강성민, "복수순회외판원문제:MTZ-cut으로 강화한 경로분할모형", 산업경영연구, 15, pp.61~76 (2007)
- Ali, A. I., "The Asymmetric M-traveling Salesman Problem:A Duality Based Branch-and-bound Algorithm", Discrete Applied Mathematics, 13, pp.259~276 (1986)
- Angel, R. D., "Computer Assisted School Bus Scheduling", Management Science, 18, pp.279~288 (1972)
- Baldacci, R., "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation", Operations Research, 52(5), pp.723~738 (2004)
- Bektas, T., "The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures", Omega, 34, pp.209~219 (2006)
- Bixby, R., "The Evolution of Optimization in Business and SCM, 서울 강연", ~ (2007)
- CPLEX Optimization, "Using the CPLEX Callable Library and CPLEX Mixed Integer Library" (1992), Incline Village
- Calvo, R. W., "A Heuristic Approach to the Overnight Security Service Problem", Computers and Operations Research, 1(30), pp.1269~1287 (2003)
- Carter, A. E., "Scheduling Pre-printed Newspaper Advertising Inserts Using Genetic Algorithms", Omega, 30, pp.415~421 (2002)
- Christofides, N., "Exact Algorithms for the Vehicle Routing Problem, Based on Spanning Tree and Shortest Path Relaxations", Mathematical Programming, 20, pp.255~282 (1981)
- Dantzig, G. B., "Solution of a Large-scale Traveling Salesman Problem", Operations Research, 2, pp.393~410 (1954)
- Finke, G., "A Two-commodity Network Flow Approach to the Traveling Salesman Problem", Congress Numerantium, 41, pp.167~178 (1984)
- Gavish, B., "A Note on the Formulation of the M-salesman Traveling Salesman Problem", Management Science, 22(6), pp.704~705 (1976)
- Gorenstein, S., "Printing Press Scheduling for Multi-edition Periodicals", Management Science, 16(6), pp.373~383 (1970)
- Kang, S., "Lotsizing and Scheduling on Parallel Machines with Sequence-Dependent Setup Costs", Management Science, 45(2), pp.273~289 (1999)
- Kara, I., "Integer Linear Programming Formulations of Multiple Salesman Problems and Its Variations", European Journal of Operational Research, 174, pp.1449~1458 (2006)
- Kulkarni, R. V., "Integer Programming Formulations of Vehicle Routing Problems", European Journal of Operational Research, 20, pp.58~67 (1985)
- Laporte, G., "A Cutting Planes Algorithm for the M-salesman Problem", Journal of the Operation Research Society, 31, pp.1017~1023 (1980)
- Lensta, J. K., "Some Simple Applications of the Traveling Salesman Problem", Operations Research Quarterly, 26, pp.717~733 (1975)
- Miller, C. E., "Integer Programming Formulation of Traveling Salesman Problems", Journal of Association for Computing Machinery, 7, pp.326~329 (1960)
- Mole, R. H., "Combinatorial Analysis for Route First-cluster Second Vehicle Routing", Omega, 11(5), pp.507~512 (1985)
- Nemhauser, G. L., "The Age of Optimization: Solving Large-Scale Real World Problems", Operations Research, 42, pp.5~13 (1994)
- Okonjo-Adigwe, C., "An Effective Method of Balancing the Workload amongst Salesman", Omega, 16(2), pp.159~163 (1988)
- Ralphs, T. K., "Parallel Branch and Cut for Capacitated Vehicle Routing", Parallel Computing, 29, pp.607~629 (2003)
- Ruland, K. S., "The Pickup and Delivery Problem", Computers and Mathematics with Applications, 33(12), pp.1~13 (1997)
- Sherali, H. D., "Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems", Operations Research, 46, pp.396~405 (1998)
- Sherali, H. D., "On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems", Operations Research, 50(4), pp.656~669 (2002)
- Svestka, J. A., "Computational Experience with an M-salesman Traveling Salesman Algorithm", Management Science, 19(7), pp.790~799 (1973)
- Tang, L., "A Multiple Traveling Salesman Problem Model for Hot Rolling Scheduling in Shangai Baoshan Iron & Steel Complex", European Journal of Operational Research, 124, pp.267~282 (2000)
- Vigo, D., "VRPLIB: A Vehicle Routing Problem Library", http:, www.or.deis.unibo.it, pp.research_pages, ORinstances[DOI]
- Zhang, T., "Team Scheduling by Genetic Search", Proceedings of the Second International Conference on Intelligent Processing and Manufacturing of Materials, 2, pp.839~844 (1999)