우선순위를 고려한 수송해법의 개발 : 서비스시간대와 지연비용을 고려한 TSP 해법 A Doubling-Up Algorithm for the Traveling Salesman Problem with Time Windows and Lateness Costs = Transportation Algorithm for Priority Dispatching

국문 초록 (Abstract)

기존의 서비스시간대가 있는 외판원문제에서는 하한시각(earliest time)과 상한시각(latest time)으로 이루진 서비스시간대 사이에서만 서비스가 허용되고 상한시각 이후에 도착하는 경우는 허용되지 않는다. 그러나 이러한 서비스시간대 제약조건으로 인하여 운송비용이 증가할 소지가 있고 현실에서는 엄격하게 상한시각을 적용하는 경우가 거의 없으므로 이에 적합한 해법이 제시되어야 한다. 본 논문은 Doubling-UP 알고리듬을 이용하여 상한시각 이후에 도착하는 경우를 허용하되 지연비용을 부과하는 좀 더 현실적인 모형을 제시하고 이를 위한 효율적인 수송해법을 개발하고자 한다.

다국어 초록 (Multilingual Abstract)

This paper presents a model for the Traveling Salesman Problem with Time Windows(TSPTW) and dynamic programming based algorithm to solve the problem. The main difference of our model compared to the previous ones lies in that the time windows we are concerned is far more flexible and realistic than the previous one. In the typical TSPTW, the service at a node must begin within the time grid called the time window that is defined by the earliest and the latest time to start the service at each node. But, in real business practice, a lateness cost is usually penalized when a vehicle arrives after a preferred time grid rather than the service is prohibited at all. Therefore, considering this characteristics, we develop a new time window to reflect the real world situation more precisely. Thus we consider a problem that allows arrival after the latest time and penalizes the late arrival by charging a lateness cost.

목차 (Table of Contents)

• 1.서론
• 1.1.연구의 배경과 목적
• 2.알고리듬의 개발
• 2.1.서비스지연을 허용하는 서비스시간대
• 2.2.기호의 정의
• 2.3.알고리듬의 개요
• 2.4.알고리듬의 절차
• 3.알고리듬의 수행 및 평가