경로의존 이동 비용을 갖는 외판원 문제의 정수계획 모형
Integer Programming Model to the Travelling Salesman Problems with Route Dependent Travel Cost
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
본 연구는 전형적인 차량경로 문제에서 각 노드간의 이동 시간이 일정하지 않은특수한 경우의 상황에 대한 해법 절차를 제공한다. 본 연구는 상황에 따라 변화하는 이동시간을 갖는 외판원 문제의 특별한 경우인 ‘한 노드까지 도달한 경로가 다음 노드로 이동하는 데 걸리는 시간에 영향을 주는 외판원 문제’(경로의존 이동비용을 갖는 외판원 문제(RDTSP: Route Dependent Travelling Salesman Problem))의 해법을 제시한다. RDTSP 문제의 해결을 위해 먼저 문제 상황을 묘사하는 정수 계획 모형을 개발하였다. 본 연구에서 제시한 정수계획 모형에서는, 모든 가능한 경로에 대하여 각각의 경로를 하나의 변수로 정의하고 이 변수들 중에서 하나를 선택하는 형태로개발되었다. 이 모형에서는 변수에 해당하는 가능한 경로의 수가 노드수에 지수적(exponentially)으로 증가하기 때문에, 처음부터 모든 변수를 문제에 포함시켜 풀수 없게 된다. 그러나, 개발된 정수계획 모형의 변수를 실수로 완하시킨 선형완화(LP relaxation) 문제에 대해서는 열 생성(column generation) 기법을 통해 그 해를구할 수 있다. 또한 본 연구의 결과가 PCB 조립 공정의 작업시간 최적화 문제에어떻게 적용될 수 있는가를 제시한다.
Abstract
In this study, we propose a solution procedure to solve travelling salesman problem(TSP) with special cost function, route dependent travelling salesman problem(RDTSP). First, we develop an integer programming model to describe the problem. In the model, a variable means a possible route. And, the number of variables in this model are extremely large. So, we develop a LP relaxation problem of the IP model and solve the relaxation problem by a column generation technique. The relaxation problem does not guarantee the optimal solution. If we get an integer solution in the ralaxation problem, then the solution is an optimal one. But, if not, we cannot get an optimal solution. So, we approach a branch and price technique. The overall solution procedure can be applied a printed circuit board(PCB)assembly process.
참고문헌 (14)
- Bhaskar, G., "Grouping PCBs for set-up reduction: a maximum spanning tree approach", International Journal of Production Research, 34, pp.621~632 (1996)
- Daskin, M. S., "Grouping components in printed circuit board assembly with limited component staging capacity and single card setup: problem characteristics and solution procedure", International Journal of Production Research, 35, pp.1617~1638 (1997)
- Hashiba, S., "PCB Assembly Setup Reduction Using Group Technology", Computers and Industrial Engineering, 21, pp.453~457 (1991)
- Laporte, G., "The Travelling Salesman Problem: An Overview of Exact and Approximate Algorithms", European Journal of Operational Research, 59, pp.231~247 (1992)
- Lawler, E. L., "The travelling Salesman Problem" (1986), John Wiley & Sons
- Maimon, O., "Grouping Methods for Printed Circuit Board Assembly", International Journal of Production Research, 29, pp.1379~1390 (1991)
- Malandraki, C., "Time Dependent Vehicle Routing Problems: Formulation, Properties and Heuristic Algorithms", Transportation Science, 26, pp.185~200 (1991)
- Nemhauser, G. L., "Integer and Combinatorial Optimizations" (1989), John Wiley & Sons
- Park, Y. B., "Modeling Intra-City Time_Dependent Travel Speeds for Vehicle Scheduling Problems", Journal of OR Society,Vol.43,pp.343-351., 43, pp.343~351 (1997)
- Reinelt, G., "TSPLIB-A Traveling Salesman Problem Library", ORSA Journal of Computing, 3, pp.376~384 (1991)
- Shtub, A., "Role of similarity measure in PCB grouping procedures", International Journal of Production Research, 30, pp.973~983 (1992)
- Wolsey, L. A., "Integer Programming" (1998), John Wiley & Sons
- Yu, S., "Integer programming approach to the printed circuit board grouping problem", International Journal of Production Research, 43, pp.1667~1684 (2005)
- 유성열, "PCB 조립 공정의 작업 투입 순서 및 부품함 배치 문제에 관한 연구", 산업경영시스템학회지, 29(1), pp.63~71 (2006), 한국산업경영시스템학회