Learning to Solve Orienteering Problem with Time Windows and Variable Profits

Each language version is independently generated for its own context, not a direct translation.

🍕 비유: "피자 배달 아저씨의 고민"

상상해 보세요. 한 피자 배달 아저씨가 (로봇) 여러 고객의 집에 피자를 배달해야 합니다. 하지만 이 상황은 단순하지 않습니다.

시간 창 (Time Windows): 어떤 고객은 "오후 2 시부터 3 시 사이에만 문을 열어줘"라고 하고, 다른 고객은 "오후 4 시 이후에만 가능"하다고 합니다.
가변적 보상 (Variable Profits): 여기서 핵심은 보상입니다.
- 보통은 "한 번 배달하면 1 만 원"이지만, 이 문제에서는 **고객이 피자를 받아주는 데 걸리는 시간 (서비스 시간)**에 따라 보상이 달라집니다.
- 예를 들어, 고객이 피자를 잘 받아주고 팁을 많이 주려면 아저씨가 5 분 동안 기다려야 할 수도 있고, 그냥 급하게 넘기면 1 분 만에 끝날 수도 있습니다. 더 오래 기다릴수록 (서비스 시간 증가) 보상은 더 많아집니다.
시간 제한: 아저씨에게는 총 1 시간이라는 제한 시간이 있습니다.

이 아저씨의 목표는 무엇일까요?

"어떤 집을 방문할지 (경로)"와 "각 집에서 얼마나 기다릴지 (서비스 시간)"를 동시에 결정해서, 1 시간 안에 받을 수 있는 총 팁 (보상) 을 최대로 만드는 것입니다.

이 문제는 **"어디로 갈지 (이산적 결정)"**와 **"얼마나 오래 있을지 (연속적 결정)"**가 서로 얽혀 있어서 매우 어렵습니다. 한 집을 더 방문하면 다른 집에 갈 시간이 부족해지고, 한 집에서 너무 오래 있으면 다른 집을 못 가게 되죠.

🚀 이 논문이 제안한 해결책: "DeCoST (데코스트)"

이 논문은 이 복잡한 문제를 해결하기 위해 DeCoST라는 두 단계짜리 지능형 시스템을 만들었습니다. 마치 **유능한 팀장 (AI)**이 직원을 지휘하는 방식과 비슷합니다.

1 단계: "대략적인 루트와 초기 계획 세우기" (Parallel Decoding)

상황: 팀장은 먼저 "어떤 순서로 방문할지"와 "각 집에서 대략 얼마나 기다릴지"를 한 번에 예측합니다.
특이점: 기존 방법들은 "일단 경로만 정하고 나중에 기다리는 시간을 조절했다"면, 이 방법은 경로와 기다리는 시간을 동시에 고려합니다.
비유: 마치 "오늘 오후 2 시에 A 집, 3 시에 B 집으로 가자. A 집에서는 5 분, B 집에서는 10 분 정도 기다려보자"라고 초안을 잡는 것입니다. 이때 "어떤 집이 팁이 더 많이 나올지"를 미리 계산해서 계획을 세웁니다.

2 단계: "수학적으로 완벽한 시간 조정" (Service Time Optimization)

상황: 1 단계에서 정해진 방문 순서 (경로) 는 그대로 두고, 각 집에서 정확히 얼마나 기다려야 총 보상이 최대가 되는지를 수학적으로 계산합니다.
방법: 이 단계는 **선형 프로그래밍 (LP)**이라는 강력한 수학 공식을 사용합니다.
핵심: 이 논문은 이 2 단계 계산이 전 세계적으로 가장 좋은 (최적의) 답을 보장한다는 것을 수학적으로 증명했습니다.
비유: "순서는 그대로 A → B → C 로 가자. 하지만 A 집에서는 5 분이 아니라 4 분 30 초, B 집에서는 12 분 10 초로 조절하면 총 팁이 더 많이 나온다"라고 미세 조정을 해주는 것입니다.

🎁 추가 꿀팁: "피드백 시스템" (pTAR)

AI 가 처음에 계획을 세울 때, "시간을 너무 많이 쓰지 말고 효율적으로 써야 해"라는 신호를 줍니다.
비유: "너무 오래 기다리면 다른 집을 못 가니까, **시간 대비 팁 효율 (pTAR)**이 좋은 곳에만 집중해라"라고 AI 에게 가르쳐 주는 것입니다. 이렇게 하면 AI 가 나중에 2 단계에서 시간을 조정할 때 더 좋은 결과를 낼 수 있습니다.

🏆 왜 이 방법이 특별한가요? (결과)

기존의 방법들 (사람이 만든 규칙이나 다른 AI) 과 비교했을 때 DeCoST 는 다음과 같은 장점이 있습니다.

더 많은 팁 (높은 점수): 같은 시간 안에 더 많은 보상을 얻습니다.
더 빠른 속도: 복잡한 계산을 6.6 배나 더 빠르게 합니다.
- 비유: 다른 방법이 10 분 걸려서 답을 찾으면, 이 방법은 1 분도 안 걸려서 더 좋은 답을 찾습니다.
큰 문제도 해결 가능: 집이 500 개나 되는 거대한 도시에서도 빠르게 작동합니다.

💡 결론

이 논문은 **"어디로 갈지"**와 **"얼마나 오래 있을지"**라는 두 가지 어려운 결정을 분리해서 생각하되, 서로 연결해서 최적의 답을 찾는 새로운 방법을 개발했습니다.

마치 유능한 배달 팀장이 "경로는 대략 정하고, 세부적인 대기 시간은 수학적으로 딱 맞춰서" 최고의 효율을 내는 것과 같습니다. 이 기술은 공장 로봇, 드론 배송, 긴급 구조 활동 등 시간과 자원이 제한된 현실 세계의 문제를 해결하는 데 큰 도움이 될 것입니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의: 시간 창 및 가변 이익이 있는 오리엔티어링 문제 (OPTWVP)

배경: 오리엔티어링 문제 (OP) 는 주어진 시간 예산 내에서 방문할 노드의 부분집합을 선택하여 총 보상 (이익) 을 최대화하는 조합 최적화 문제입니다. 이는 물류, 로봇 계획, 공장 스케줄링 등 다양한 실세계 응용 분야에서 중요합니다.
OPTWVP 의 특징: 기존 OP 와 달리 OPTWVP 는 두 가지 복잡한 요소를 동시에 다룹니다.
1. 시간 창 (Time Windows): 각 노드는 특정 시간 구간 내에서만 방문 가능합니다.
2. 가변 이익 (Variable Profits): 노드에서의 서비스 시간이 길어질수록 수집되는 이익이 선형적으로 증가합니다 (단위 이익 $\times$ 서비스 시간).
핵심 난제: 이 문제는 **이산적 (Discrete)**인 경로 계획 (어떤 노드를 방문할지) 과 **연속적 (Continuous)**인 서비스 시간 할당 (각 노드에서 얼마나 머무를지) 이 서로 긴밀하게 결합되어 있습니다. 경로가 서비스 시간의 가능 영역을 결정하고, 반대로 서비스 시간 할당이 총 보상과 경로 선택에 영향을 미치기 때문에, 두 변수를 독립적으로 최적화하는 것은 불가능하며 검색 공간이 기하급수적으로 커집니다.

2. 제안 방법론: DeCoST (Decoupled Discrete-Continuous Optimization with Service-time-guided Trajectory)

저자들은 이 문제를 해결하기 위해 학습 기반의 2 단계 탈결합 (Decoupled) 최적화 프레임워크인 DeCoST를 제안했습니다.

2.1 전체 구조

DeCoST 는 이산적 경로 결정과 연속적 서비스 시간 할당을 효과적으로 분리하면서도 두 단계 간의 협업을 가능하게 합니다.

1 단계: 병렬 디코딩 (Parallel Decoding)
- 경로 디코더 (Routing Decoder): 다음 방문 노드를 선택합니다.
- 서비스 시간 디코더 (STD, Service Time Decoder): 각 노드에 대한 초기 서비스 시간 비율을 예측합니다.
- 특징: 공간 인코딩 (Spatial Encoding) 을 통해 엣지 (거리) 정보를 주의 메커니즘에 주입하여 그래프 구조를 이해하고, **가능성 마스크 (Feasibility Masking)**를 적용하여 시간 창 위반을 방지합니다. 이를 통해 초기 feasible trajectory 와 서비스 시간 할당 ( $\hat{d}$ ) 을 생성합니다.
2 단계: 서비스 시간 최적화 (Service Time Optimization, STO)
- 1 단계에서 고정된 경로 ( $\tau$ ) 를 기반으로, 서비스 시간 할당 문제는 선형 계획법 (Linear Programming, LP) 문제로 단순화됩니다.
- STO 알고리즘: 병렬 계산을 통해 최적의 서비스 시간 ( $d^*$ ) 을 빠르게 계산합니다. 이 알고리즘은 주어진 경로 내에서 총 보상을 최대화하는 전역 최적해 (Global Optimum) 를 보장합니다 (Theorem 4.1 증명).

2.2 학습 메커니즘: pTAR (Profit-weighted Time Allocation Ratio)

문제: 1 단계의 초기 서비스 시간 예측이 2 단계의 최적 해 ( $d^*$ ) 에 비해 너무 보수적이거나 과감할 경우, 전체 경로 선택이 비효율적으로 이루어질 수 있습니다.
해결책: pTAR라는 새로운 감독 지표 (Supervisory Index) 를 도입했습니다.
- 정의: 경로 내 노드들의 (이익 $\times$ 서비스 시간) / 이동 시간의 합.
- Repulsive Supervisory Loss: 초기 예측값 $\hat{d}$ 와 2 단계 최적값 $d^*$ 사이의 pTAR 차이를 기반으로 한 손실 함수 ( $L_{pTAR}$ ) 를 추가합니다. 이는 모델이 2 단계의 조건부 최적해에过早하게 수렴 (Overfitting) 하는 것을 방지하고, 초기 단계에서 더 넓은 정책 탐색을 유도하여 전체적인 해의 품질을 높입니다.
최종 손실 함수: REINFORCE 손실 (경로 생성) 과 pTAR 감독 손실의 가중 합으로 구성됩니다.

3. 주요 기여 (Key Contributions)

DeCoST 프레임워크 제안: 시간 창과 가변 이익이 있는 OPTWVP 문제를 해결하기 위해 이산/연속 변수를 탈결합하면서도 협력하는 최초의 학습 기반 2 단계 접근법입니다.
전역 최적성 보장 및 효율성: 2 단계의 STO 알고리즘이 고정된 경로 하에서 서비스 시간 할당의 전역 최적해를 수학적으로 증명했습니다. 또한, 병렬 계산을 통해 계산 효율성을 극대화했습니다.
초기 구조 추정을 위한 pTAR: 단순한 경로 예측을 넘어, 서비스 시간 할당의 효율성 (pTAR) 을 1 단계 학습에 피드백함으로써 장기적인 구조 추정이 가능하게 했습니다.
범용성: 제안된 프레임워크는 다양한 구성적 솔버 (Constructive Solvers, 예: POMO, GFACS) 와 호환되어 성능을 향상시킬 수 있음을 입증했습니다.

4. 실험 결과 (Results)

데이터셋: 다양한 노드 수 ( $n=50, 100, 500$ ) 와 시간 창 크기 (TW=100, 500) 를 가진 OPTWVP 벤치마크 및 Solomon 100 데이터셋.
비교 대상:
- 정확한 해법: Gurobi (Branch & Cut).
- 휴리스틱/메타휴리스틱: Greedy-PRS, ILS (Incremental Local Search).
- 학습 기반 (NCO): POMO, GFACS.
성과:
- 해의 품질 (Solution Quality): DeCoST 는 모든 설정에서 기존 NCO 방법 및 최신 메타휴리스틱 (ILS) 을 능가했습니다. 특히 $n=100, TW=100$ 설정에서 Gurobi 대비 최적성 간격 (Gap) 을 **1.97%**까지 줄였습니다 (ILS 는 4.2%, POMO 는 55.7%).
- 계산 효율성 (Efficiency): DeCoST 는 ILS 대비 20~45 배 빠른 추론 속도를 보였습니다. $n=500$ 대규모 문제에서 DeCoST 는 약 1.3 초 만에 고품질 해를 찾은 반면, ILS 는 8.8 초 이상 소요되었습니다.
- 확장성: 노드 수가 500 으로 증가해도 성능 저하가 미미하며, 일관된 안정성을 유지했습니다.
- Ablation Study: STO 모듈이 성능 향상에 가장 결정적인 역할을 했으며, 공간 인코딩 (SE) 과 pTAR 감독 손실 (SL) 이 이를 보완하여 최종 성능을 극대화함을 확인했습니다.

5. 의의 및 결론

이 논문은 이산적 경로 계획과 연속적 자원 할당이 복잡하게 얽힌 조합 최적화 문제를 해결하는 새로운 패러다임을 제시합니다.

학문적 의의: 기존의 NCO 방법들이 주로 경로만 예측하는 한계를 극복하고, 연속 변수 최적화를 2 단계 LP 문제로 전환하여 정확한 해를 구하는 방식을 제안했습니다. 이는 혼합 정수 계획법 (MIP) 과 신경망 학습의 장점을 결합한 사례입니다.
실용적 의의: 로봇 협업, 물류 배송 등 서비스 시간이 이익에 직접적인 영향을 미치는 실세계 문제에서, 기존 휴리스틱보다 훨씬 빠르고 정확한 의사결정을 가능하게 합니다.
한계 및 향후 작업: 비자기회귀 (NAR) 솔버와 결합 시 배치 처리의 한계로 인해 STO 의 병렬화 효율이 떨어질 수 있으나, 향후 더 일반적인 차량 경로 문제 (VRP) 로의 확장과 계산 효율성 개선이 필요하다고 언급했습니다.

요약하자면, DeCoST는 OPTWVP 와 같은 하이브리드 변수 문제를 해결하기 위해 "경로 예측 (1 단계)"과 "정밀한 서비스 시간 최적화 (2 단계)"를 분리하되, pTAR라는 피드백 메커니즘으로 두 단계를 긴밀하게 연결함으로써 최고 수준의 해의 품질과 추론 속도를 동시에 달성한 획기적인 연구입니다.