경로 의존 이동 비용을 갖는 외판원 문제의 정수계획 해법 및 응용

국문 초록 (Abstract)

잘 알려진 조합최적화 문제중의 하나인 외판원 문제(TSP)는 두 도시간의 이동 비용의 특성에 따라 크게 두 가지 유형으로 구분 된다.
첫 번째는 두 노드간의 이동 비용이 고정된 경우이고, 두 번째는 두 노드간의 이동 비용이 상황에 따라 달라지는 경우이다.

본 연구는 두 번째 유형의 외판원 문제 중 지금까지 다루어지지 않았던 새로운 유형의 차량경로문제 및 그 응용분야를 다룬다. 이동 비용이 상황에 따라 달라지는 경우, 지금까지 진행되어 온 연구의 대부분은 특정한 노드 a의 도착(혹은 출발) 시간에 따라 다음 노드로의 이동 비용이 달라지는 경우를 다루는 것이었다.

그러나, 실제 이동 시간이 변동될 수 있는 다른 중요한 경우가 존재한다. 이는, 두 노드간의 이동 시간이 특정 노드의 도착(혹은 출발)시간 뿐 만 아니라. 차량이 어떠한 경로를 통해서 특정 노드까지 도착하였는가에 따라서 달라질 수 있다는 것이다.

예를 들어, n가지의 유형의 서로 다른 PCB를 여러대의 표면실장기가 직렬로 이루어진 조립공정에서 생산하고자 하는 경우를 살펴보자. 각각의 PCB에 조립할 부품들은 PCB 생산이 시작되기 앞서 부품함(component feeders)에 담긴 형태로 표면실장기상의 슬롯(slot)이라고 하는 정해진 위치에 놓이게 된다. 이 때 표면실장기에 한번에 놓여질 수 있는 부품함의 개수는 한정되어 있다. 보통 한 종류의 PCB만을 생산 할 경우, 주어진 PCB에 필요한 부품함들은 모두 표면실장기에 설치될 수 있으나, 주어진 상황처럼 여러 종류의 PCB를 하나의 조립 라인에서 동시에 생산하는 경우, PCB 유형이 바뀌었을 ？？ 두 개의 연속적인 PCB 종류에 모두 필요한 부품함의 수가 각 기계에 장착 가능한 부품함의 수보다 커지는 경우가 발생할 수 있다. 이 경우에는 앞선 PCB의 작업이 종료된 직후, 다음 PCB의 작업을 진행하기 전에 일부 부품함들의 설치를 변경해야 한다. 이러한 상황에서, 각각의 PCB를 기계에서 조립하는데 걸리는 시간이 주어졌다고 가정할 ？？, 주어진 가지 타입의 PCB를 생산하는데 필요한 시간을 최소화하는 문제는 결국 부품함 교체를 위한 시간을 최소화하는 문제와 동일하다. 실제 전체 부품함 교체 시간은 투입되는 PCB의 순서에 따라 결정되며, 이는 차량경로문제의 특수한 경우인 외판원 문제와 동일한 문제가 된다. 이를 일반화하여, 여러 PCB들을 그룹으로 나누고, 각각의 그룹에 대한 투입 순서를 결정하는 경우로 확대하면 이는 차량경로문제가 된다. 이 때, 각각의 그룹내에 포함된 PCB 종류들간의 부품 교체에 필요한 시간은 앞서 생산 PCB들의 생산 순서에 따라 달라지게 된다. 이러한 경우 연속된 두 PCB간의 부품 교체 시간은 앞선 모든 PCB들을 어떤 순서로 생산했느냐에 따라서 달라지며, 이는 본 연구에서 다루고자 하는 경로의존비용을 갖는 차량경로문제로 모형화할 수 있다.

본 연구의 해법절차로써는 최적해를 구하기 위한 열생성기법(column generation)을 활용한 정수계획모형을 개발하고 이를 구현한다.