The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

논문 요약: 시간 창 (Time Windows) 제약이 있는 도둑 여행 문제 (TTPTW)

1. 문제 정의 (Problem Definition)

이 논문은 기존의 **도둑 여행 문제 (Traveling Thief Problem, TTP)**에 시간 창 (Time Windows) 제약을 추가한 새로운 변형 문제인 **TTPTW (Traveling Thief Problem with Time Windows)**를 제안하고 연구합니다.

• TTP 의 본질: TTP 는 외판원 문제 (TSP, 경로 최적화) 와 배낭 문제 (KP, 자원 선택 최적화) 가 서로 의존적으로 결합된 복합 최적화 문제입니다. 도둑은 도시를 순회하며 물건을 훔쳐 배낭에 담고, 배낭의 무게가 증가할수록 이동 속도가 느려져 총 이동 시간이 길어지고, 이에 따라 렌탈 비용이 증가하는 구조입니다.
• TTPTW 의 추가 제약: 각 도시는 방문 가능한 특정 시간 창 $[L_i, U_i]$을 가집니다.
  • 기대 도착 시간 ($t^*$): 이전 도시에서 이동한 시간과 현재 배낭 무게에 따른 속도로 계산된 도착 시간입니다.
  • 실제 도착 시간 ($t$): $t^*$가 시간 창 하한선 ($L_i$) 보다 빠르면 도둑은 기다려야 하므로 $L_i$가 실제 도착 시간이 됩니다. $t^*$가 상한선 ($U_i$) 을 초과하면 제약 위반 (Violation) 이 발생합니다.
  • 목표: 총 이익 (물건 가치 - 렌탈 비용) 을 최대화하면서 모든 시간 창 제약을 만족하는 경로와 배낭 계획을 찾는 것입니다.
• 난이도: 시간 창 제약은 탐색 공간을 극도로 좁혀 실현 가능한 해 (Feasible Solution) 를 찾는 것을 매우 어렵게 만듭니다. 특히 TTP 의 특성상 무게 증가로 인한 속도 저하가 시간 창 위반을 유발할 수 있어, 단순한 경로 최적화만으로는 해결이 불가능합니다.

2. 방법론 (Methodology)

저자는 기존 알고리즘의 한계를 극복하기 위해 새로운 벤치마크와 알고리즘을 개발했습니다.

가. 벤치마크 생성 (Benchmark Generation)

• 기존 TTP 벤치마크 (Polyakovskiy et al., 2014) 를 기반으로 시간 창을 추가했습니다.
• 시간 창 엄격도 (Tightness, $l$): $l$ 값을 변화시켜 ($100, 1000, -100, -1000$) 시간 창이 넓은 경우부터 매우 좁은 (Hard) 경우까지 다양한 난이도의 인스턴스를 생성했습니다.
• 인스턴스 유형: TSP 최적 경로로 시간 창을 생성한 Type A 와 무작위 경로로 생성한 Type B 로 구분하여, TSP 최적 경로가 TTP 에 항상 최적이지 않음을 검증했습니다.

나. 기존 알고리즘의 적용 및 한계 (Adaptation of Existing Approaches)

• 적용 대상: TTP 전용 알고리즘 (S4, S5, C5) 과 TSPTW 전용 알고리즘 (LKH-3, VSR-LKH-3) 을 TTPTW 에 적용했습니다.
• 결과: 대부분의 기존 알고리즘은 시간 창 제약으로 인해 실현 가능한 해를 전혀 찾지 못하거나 (Feasible Rate 0%), 매우 낮은 성공률을 보였습니다. 특히 도시 수가 100 개를 초과하는 대규모 인스턴스에서는 실패했습니다.

다. 제안된 알고리즘: 듀얼 서치 진화 알고리즘 (Dual Search Evolutionary Algorithm, DSEA)
기존 알고리즘의 실패 원인을 분석하고 새로운 알고리즘을 제안했습니다.

1. 경로 초기화 알고리즘 (Tour Initialization):

   • 기존 TTP 연구에서 주로 사용되던 Chained Lin-Kernighan (CLK) 은 시간 창 제약 하에서 실현 가능한 경로를 찾기 어렵고 계산 비용이 큽니다.
   • 제안: 메모리와 스코어링 (Scoring) 절차를 추가한 최단 이웃 (Nearest Neighborhood) 기반 초기화를 도입했습니다.
   • 동작: 다음 도시 방문 예상 시간을 계산하여 시간 창을 위반할 경우 페널티를 부여하고, 시간 창을 만족하는 도시를 우선적으로 선택하여 초기 경로를 생성합니다. 이는 탐색의 시작점을 실현 가능한 영역으로 유도합니다.

2. 이중 탐색 전략 (Dual Search Strategy):

   • 경로 최적화: 2-opt 기반의 Topo (Perturbation 포함) 와 삽입 (Insertion) 기반의 Rain (Random Insertion) 연산자를 결합하여 사용합니다.
   • 배낭 계획 최적화: PackIterative 알고리즘을 사용하되, 경로 변경 시마다 배낭 계획을 완전히 다시 계산하는 대신 효율성을 위해 선택적으로 업데이트합니다.

3. DSEA 변형체 (Variants):

   • DSEA1: 경로 최적화만 수행하고, 배낭 계획 수리 (Repair) 는 수행하지 않음.
   • DSEA2: Repack (삭제된 물건을 다시 채우는 방식) 을 사용하여 배낭 계획을 수리함.
   • DSEA3: 최적화 연산과 수리 과정을 통합 (Integration of Repair and Optimizer) 하여 효율적으로 배낭 계획을 조정함.

4. 제약 처리:

   • 목적 함수와 제약 위반 (Time Window Violation) 을 분리하여 평가하는 Constraint-Objective Value Separation 기법을 사용했습니다. 실현 불가능한 해는 목적 함수 값과 무관하게 실현 가능한 해보다 항상 열등하게 처리됩니다.

3. 주요 기여 (Key Contributions)

1. TTPTW 문제 정의 및 벤치마크 제시: 시간 창 제약이 있는 TTP 변형 문제를 공식적으로 정의하고, 다양한 엄격도와 크기를 가진 새로운 벤치마크 인스턴스를 공개했습니다.
2. 새로운 휴리스틱 알고리즘 (DSEA) 개발: 경로 초기화, 이중 탐색 연산자, 효율적인 배낭 계획 전략을 결합하여 시간 창 제약 하에서 높은 실현 가능성과 최적성을 달성하는 알고리즘을 제안했습니다.
3. 성능 비교 및 분석: 기존 TTP 및 TSPTW 알고리즘 (S4, S5, C5, LKH-3 등) 과의 비교를 통해, 시간 창 제약 하에서는 기존 알고리즘이 실패하며 DSEA 가 우월함을 입증했습니다.

4. 실험 결과 (Experimental Results)

• 실현 가능성 (Feasibility): 기존 알고리즘 (S4, S5, C5, LKH-3 등) 은 대부분의 인스턴스에서 실현 가능한 해를 찾지 못했습니다 (0% 성공률). 반면, DSEA 는 거의 모든 인스턴스에서 100% 에 가까운 실현 가능성을 보였습니다.
• 최적화 성능:
  • **DSEA1 (수리 없음)**이 대부분의 인스턴스에서 가장 좋은 목적 함수 값 (Objective Value) 을 기록했습니다. 이는 배낭 계획 수리 과정이 추가 계산 비용을 소모하고 지역 최적해에 갇히게 만드는 경향이 있기 때문입니다.
  • **DSEA3 (통합 수리)**는 매우 큰 인스턴스 (1000 도시) 나 특정 상관관계가 강한 인스턴스에서 DSEA1 보다 우수한 성능을 보이며, 수리 메커니즘이 특정 상황에서 유용함을 입증했습니다.
  • **DSEA2 (Repack)**는 계산 비용이 높아 성능이 가장 낮았습니다.
• 초기화 알고리즘의 효과: 기존 알고리즘 (S4, S5, C5) 에 제안된 경로 초기화 알고리즘을 적용하면 실현 가능한 해를 찾을 수 있게 되었으나, 최종 최적화 성능은 DSEA 에 미치지 못했습니다. 이는 초기화만으로는 충분하지 않고, 경로와 배낭을 동시에 최적화하는 강력한 탐색 전략이 필요함을 시사합니다.

5. 의의 및 결론 (Significance and Conclusion)

• 실제 문제 적용성: 응급 서비스, 의료 방문, 쓰레기 수거 등 시간 제약이 중요한 실제 물류 및 서비스 문제에 TTP 모델이 적용될 수 있음을 보여줍니다.
• 알고리즘적 통찰: 시간 창이 있는 복합 최적화 문제에서는 단순한 경로 최적화나 기존 TTP 알고리즘의 적용만으로는 부족하며, **실현 가능한 초기 해 생성 (Initialization)**과 경로 - 자원 간의 상호작용을 고려한 이중 탐색 (Dual Search) 전략이 필수적임을 증명했습니다.
• 향후 연구: 제안된 TTPTW 벤치마크와 DSEA 알고리즘은 향후 시간 제약이 있는 복합 최적화 문제를 연구하는 데 중요한 기준 (Baseline) 으로 활용될 수 있습니다.

요약하자면, 이 논문은 시간 창 제약 하에서 TTP 가 얼마나 까다로운 문제인지 규명하고, 이를 해결하기 위해 실현 가능한 초기 경로를 생성하는 전략과 **경로와 배낭 계획을 동시에 최적화하는 진화 알고리즘 (DSEA)**을 통해 기존 방법론의 한계를 극복하고 우수한 성능을 달성했음을 보여줍니다.