경로의존 이동 비용을 갖는 외판원 문제의 정수계획 모형|RISS 상세보기

국문 초록 (Abstract)

본 연구는 전형적인 차량경로 문제에서 각 노드간의 이동 시간이 일정하지 않은 특수한 경우의 상황에 대한 해법 절차를 제공한다. 본 연구는 상황에 따라 변화하 는 이동시간을 갖는 외판원 문제의 특별한 경우인 ‘한 노드까지 도달한 경로가 다 음 노드로 이동하는 데 걸리는 시간에 영향을 주는 외판원 문제’(경로의존 이동비 용을 갖는 외판원 문제(RDTSP: Route Dependent Travelling Salesman Problem)) 의 해법을 제시한다. RDTSP 문제의 해결을 위해 먼저 문제 상황을 묘사하는 정수 계획 모형을 개발 하였다. 본 연구에서 제시한 정수계획 모형에서는, 모든 가능한 경로에 대하여 각 각의 경로를 하나의 변수로 정의하고 이 변수들 중에서 하나를 선택하는 형태로 개발되었다. 이 모형에서는 변수에 해당하는 가능한 경로의 수가 노드수에 지수적 (exponentially)으로 증가하기 때문에, 처음부터 모든 변수를 문제에 포함시켜 풀 수 없게 된다. 그러나, 개발된 정수계획 모형의 변수를 실수로 완하시킨 선형완화 (LP relaxation) 문제에 대해서는 열 생성(column generation) 기법을 통해 그 해를구할 수 있다. 또한 본 연구의 결과가 PCB 조립 공정의 작업시간 최적화 문제에 어떻게 적용될 수 있는가를 제시한다.

번역하기

본 연구는 전형적인 차량경로 문제에서 각 노드간의 이동 시간이 일정하지 않은 특수한 경우의 상황에 대한 해법 절차를 제공한다. 본 연구는 상황에 따라 변화하 는 이동시간을 갖는 외판...

목차 (Table of Contents)

요약
I. 서론
Ⅱ. 정수계획 모형
1. 수리모형
2. 가능경로를 변수로 한 모형

요약
I. 서론
Ⅱ. 정수계획 모형
1. 수리모형
2. 가능경로를 변수로 한 모형
Ⅲ. 알고리즘
Ⅳ. 응용분야
1. PCB 조립 공정
2. 적용 예
Ⅴ. 결론
참고문헌
ABSTRACT

참고문헌 (Reference)

1 Malandraki, C., "Time Dependent Vehicle Routing Problems: Formulation, Properties and Heuristic Algorithms" 26 : 185-200, 1991

2 Lawler, E. L., "The travelling Salesman Problem" John Wiley & Sons 1986

3 Laporte, G., "The Travelling Salesman Problem: An Overview of Exact and Approximate Algorithms" 59 : 231-247, 1992

4 Reinelt, G., "TSPLIB-A Traveling Salesman Problem Library" 3 : 376-384, 1991

5 Shtub, A., "Role of similarity measure in PCB grouping procedures" 30 : 973-983, 1992

6 유성열, "PCB 조립 공정의 작업 투입 순서 및 부품함 배치 문제에 관한 연구" 한국산업경영시스템학회 29 (29): 63-71, 2006

7 Hashiba, S., "PCB Assembly Setup Reduction Using Group Technology" 21 : 453-457, 1991

8 Park, Y. B., "Modeling Intra-City Time_Dependent Travel Speeds for Vehicle Scheduling Problems" 43 : 343-351, 1997

9 Yu, S., "Integer programming approach to the printed circuit board grouping problem" 43 : 1667-1684, 2005

10 Nemhauser, G. L., "Integer and Combinatorial Optimizations" John Wiley & Sons 1989