Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

이 논문은 실시간 수요 대응 교통 서비스에서 사전 예약 요청에 대한 즉각적인 승인 확인과 동시에 수락된 요청의 지속적인 경로 최적화를 보장하기 위해, 강화 학습 기반의 비단시적 목적 함수를 통합한 새로운 동적 차량 경로 문제 해결 방안을 제시하고 실증 데이터를 통해 그 유효성을 입증했습니다.

핵심

🚕 핵심 이야기: "지금 당장 대답해 줄 수 있을까?"

상상해 보세요. 여러분이 마법 같은 택시 회사를 운영한다고 칩시다. 손님이 "내일 오전 10 시에 A 에서 B 로 가주세요"라고 미리 예약을 넣습니다.

기존의 시스템들은 두 가지 큰 고민이 있었습니다:

1. 빠른 답변을 원하면: "네, 가능해요!"라고 바로 말해주지만, 나중에 다른 손님이 몰려오면 약속을 지키지 못해 낭패를 봅니다. (약속은 지키지만, 효율이 낮음)
2. 최고의 효율을 원하면: "잠시만요, 모든 상황을 계산해 볼게요"라고 기다리게 합니다. 계산이 끝나면 가장 효율적인 배정이 가능하지만, 손님은 "내 예약이 될지 안 될지 10 분이나 기다려야 해?"라며 화를 냅니다. (효율은 좋지만, 답장이 늦음)

이 논문은 "빠른 답변도 주고, 동시에 최고의 효율도 달성하는" 두 마리 토끼를 잡는 방법을 제안합니다.

---

🧩 이 시스템의 비밀: "즉석 계산기"와 "밤새 고민하는 전략가"

이 시스템은 두 명의 직원이 협력해서 일합니다.

1. 첫 번째 직원: "즉석 계산기" (Prompt Confirmation)

• 역할: 손님이 전화를 걸면 0.2 초 만에 "네, 가능해요!" 또는 "죄송합니다, 불가능해요"라고 답합니다.
• 방법: 손님의 요청을 현재 차량들의 경로에 가장 간단하게 끼워 넣을 수 있는지만 봅니다. 복잡한 계산을 하지 않고, "아, 이 차 빈자리가 있네? 여기 끼워보자"라고 빠르게 결정합니다.
• 효과: 손님은 기다림 없이 즉시 확정 여부를 알 수 있어 안심합니다.

2. 두 번째 직원: "밤새 고민하는 전략가" (Continual Optimization)

• 역할: 두 번째 손님이 전화를 걸 때까지의 여유 시간을 활용합니다.
• 방법: "즉석 계산기"가 끼워 넣은 경로가 정말 최선일까? 다른 차와 손님을 바꿔보거나, 순서를 바꾼다면 더 많은 손님을 태울 수 있지 않을까? **시뮬레이션 안테나 (Simulated Annealing)**를 돌려가며 밤새도록 경로를 다듬습니다.
• 효과: 다음 손님이 전화하기 직전에, 이미 모든 경로가 최적화되어 있습니다. 그래서 더 많은 손님을 태울 수 있게 됩니다.

---

🧠 두 직원의 뇌: "미래를 보는 AI (강화 학습)"

이 두 직원이 어떻게 그렇게 현명한 결정을 내릴까요? 바로 **AI(인공지능)**가 가르쳐 주기 때문입니다.

• 단순한 생각 (Myopic): "지금 손님을 태우면 당장 1 명을 태울 수 있으니 OK!" (이건 나중에 다른 손님을 태울 기회를 잃을 수 있음)
• 미래를 보는 생각 (Non-myopic): "지금 이 손님을 태우면, 1 시간 뒤에 더 중요한 손님을 태울 수 있는 차량이 부족해질 거야. 차라리 거절하는 게 전체적으로는 더 많은 손님을 태우는 길이야."

이 논문의 핵심은 **강화 학습 (Reinforcement Learning)**을 통해 AI 에게 **"지금 당장의 이익보다, 장기적으로 더 많은 손님을 태우는 방법"**을 가르쳤다는 점입니다. 마치 체스 선수처럼, 지금 당장 말 한 수를 두는 게 아니라, 10 수 뒤의 승리를 보고 움직이는 것입니다.

---

📊 실제 결과: "거절당하는 손님이 1% 로 줄었다!"

미국 중규모 도시의 실제 택시 데이터를 가지고 실험해 보았습니다.

• 기존 방법들 (구글의 도구, 다른 알고리즘 등):
  • 답장은 빠르지만, 손님을 거절하는 비율이 높았습니다. (약 5~15% 거절)
  • 혹은 답장이 느려서 손님이 짜증을 냈습니다.
• 이 논문의 방법:
  • 답장 속도: 0.2 초 (순식간!)
  • 거절 비율: **약 1%**로 압도적으로 낮아졌습니다.
  • 결론: 손님은 기다림 없이 "네"라는 답을 받고, 회사는 더 많은 손님을 태워 수익을 극대화했습니다.

---

💡 한 줄 요약

"손님에게는 0.2 초 만에 '가능합니다'라고 확답을 주고, 그 사이에는 AI 가 밤새도록 경로를 다듬어 더 많은 손님을 태울 수 있게 만든, 두 마리 토끼를 잡은 똑똑한 택시 배정 시스템입니다."

이 기술은 앞으로 우리가 미리 예약한 택시나 배송 서비스를 이용할 때, "내 요청이 받아들여질까?"라는 불안감 없이, 그리고 기다림 없이 서비스를 이용할 수 있게 해줄 것입니다.

기술 요약

논문 요약: 선제적 요청에 대한 신속한 확인이 포함된 동적 차량 라우팅 문제

1. 문제 정의 (Problem Definition)

이 논문은 온디맨드 교통 서비스 (마이크로트랜짓, 패러트랜짓 등) 를 운영하는 교통 기관이 직면한 새로운 현실적 문제를 다룹니다. 기존 연구들은 주로 실시간으로 도착하는 요청을 처리하는 데 집중했으나, 실제 서비스에서는 **선제적 예약 (Advance Requests)**이 중요한 요소입니다.

• 핵심 문제: 선제적으로 예약된 요청 (예: 몇 시간 후 출발) 이 들어왔을 때, 기관은 신속하게 (Promptly) 승낙 여부를 확정해야 합니다. 승낙된 요청은 약속대로 반드시 서비스되어야 합니다.
• 기존 접근법의 한계:
  1. 신속한 확인만 제공: 요청 도착 시 즉시 승낙/거부를 결정하지만, 이후 경로 최적화를 지속적으로 수행하지 못해 서비스 효율성이 낮음.
  2. 지속적 최적화만 제공: 경로를 계속 최적화하지만, 승낙 여부를 즉시 확정하지 못하거나 승낙된 모든 요청을 보장하지 못함.
• 목표: 모든 요청에 대해 **신속한 확인 (Prompt Confirmation)**을 제공하면서도, 승낙된 요청들을 지속적으로 최적화하여 서비스율 (Service Rate, 승인된 요청 중 성공적으로 수행된 비율) 을 극대화하는 알고리즘 개발.

2. 제안된 방법론 (Methodology)

저자들은 이 문제를 해결하기 위해 **신속한 삽입 탐색 (Quick Insertion Search)**과 **Anytime 알고리즘 (Continual Optimization)**을 결합한 새로운 계산적 접근법을 제시합니다.

A. 문제 모델링 (MDP)

• 문제를 불확실성 하의 순차적 의사결정 문제로 모델링하여 **마르코프 의사결정 과정 (MDP)**으로 정의합니다.
• 상태 (State): 차량 위치, 탑승자, 승인된 요청 집합, 현재 경로 계획, 최신 도착 요청 등.
• 행동 (Action): 요청의 승인/거부 결정 및 새로운 경로 계획 (Manifest) 생성.
• 보상 (Reward): 요청을 승인할 경우 1, 거절할 경우 0. 장기적으로 보상을 극대화하는 것이 곧 서비스율 극대화입니다.

B. 핵심 알고리즘 구성

1. 신속한 확인 (Prompt Confirmation):

   • 요청 도착 시 수십 분의 1 초 이내에 승낙/거부 결정을 내립니다.
   • Quick Insertion Search: 기존 경로 계획에 새로운 요청을 단순히 삽입 (Insertion) 할 수 있는지 탐색합니다. 복잡한 재배열 없이 현재 경로에 삽입 가능한지 확인하여 계산 시간을 단축합니다.
   • 비단시적 (Non-myopic) 목적 함수: 단순히 현재 요청을 수용하는 것이 아니라, 미래 요청을 수용할 가능성을 고려한 최적의 결정을 내리기 위해 강화학습으로 학습된 **행동 가치 함수 (Action-Value Function, Q)**를 사용합니다.

2. 지속적 최적화 (Continual Optimization):

   • 두 요청 사이의 공백 시간을 활용하여 경로 계획을 지속적으로 개선합니다.
   • Anytime 알고리즘 (Simulated Annealing): 다음 요청이 도착하기 전까지 알고리즘을 실행하며, 언제든지 중단할 수 있도록 설계되었습니다.
   • 연산자: Swap(두 차량 간 요청 교환), Move(요청 이동), Shift(정류장 순서 변경), Reverse(순서 반전) 등을 통해 해를 개선합니다.
   • 다음 요청이 도착하면 그 시점까지 찾은 최선의 해를 새로운 경로 계획으로 채택합니다.

C. 강화학습 (Reinforcement Learning)

• 목적: 장기적인 서비스율을 극대화하는 비단시적 (Non-myopic) 목적 함수 $Q(s, a)$를 학습합니다.
• 학습 방식:
  • 지도 학습 사전 학습 (Supervised Pre-training): 간단한 휴리스틱 정책 (모든 요청 수용, 유휴 시간 최대화) 으로 대량의 경험을 생성하여 신경망을 초기화합니다.
  • 강화학습 미세 조정 (Fine-tuning): Bellman 방정식을 사용하여 Q-learning 을 수행하며, 신경망 (MLP, KAN, CNN) 을 통해 상태 - 행동 쌍을 입력받아 Q 값을 예측합니다.
• 특징 벡터: 복잡한 상태 정보를 신경망에 입력하기 위해 '총 유휴 시간', '시간별 차량 가용성', '시공간적 가용성 (그리드 기반)' 등의 특징 벡터를 설계했습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 문제 형식화: 선제적 예약 요청에 대해 '신속한 확인'과 '지속적 최적화'를 동시에 만족해야 하는 동적 차량 라우팅 문제 (DVRP) 를 최초로 체계적으로 정의했습니다.
2. 하이브리드 계산 프레임워크: 빠른 삽입 탐색과 Anytime 메타휴리스틱을 결합하여, 실시간 응답성과 장기적 최적화 효율성을 동시에 달성하는 알고리즘을 제안했습니다.
3. 비단시적 목적 함수 학습: 강화학습을 통해 단순한 현재 상태 최적화가 아닌, 미래 요청 수용 가능성을 고려한 최적의 의사결정 기준 (Q 함수) 을 학습했습니다.
4. 실제 데이터 검증: 미국 내 실제 마이크로트랜짓 데이터와 NYC 택시 데이터를 사용하여 제안된 접근법의 우수성을 입증했습니다.

4. 실험 결과 (Results)

• 데이터셋: 미국 중규모 도시의 실제 마이크로트랜짓 데이터 (2022-2023) 와 NYC 택시 데이터.
• 비교 대상: Google OR-Tools, Rolling Horizon (RH), Monte Carlo VRP (MC VRP).
• 성능 지표:
  • 확인 시간 (Confirmation Time): 제안된 방법은 평균 0.2 초 (마이크로트랜짓) 및 1 초 (NYC) 내에 결정을 내렸습니다. 이는 실시간 서비스에 충분히 빠른 속도입니다. (OR-Tools 는 0.1~0.5 초로 비슷했으나, 서비스율에서 뒤처짐).
  • 거절율 (Rejection Rate): 제안된 방법은 기존 모든 베이스라인보다 거절율을 획기적으로 낮췄습니다. (마이크로트랜짓 데이터에서 약 1% 수준으로 감소).
  • 지속적 최적화의 효과: 요청 간격에서 Anytime 알고리즘을 실행할수록 거절율이 감소함을 확인했습니다.
  • 학습된 Q 함수의 효과: 단순 휴리스틱 대신 강화학습으로 학습된 Q 함수를 사용할 때 서비스율이 크게 향상되었습니다.

5. 의의 및 결론 (Significance)

이 연구는 온디맨드 마이크로트랜짓 서비스의 실용적 장벽을 해결합니다.

• 사용자 경험 향상: 승객은 예약 시 즉시 확정을 받을 수 있어 여행 계획을 세울 수 있으며, 승인된 요청은 약속대로 수행된다는 보장을 가집니다.
• 운영 효율성 극대화: 교통 기관은 실시간으로 경로를 최적화하여 차량 가용성을 높이고, 더 많은 요청을 수용할 수 있게 됩니다.
• 실제 적용 가능성: 제안된 알고리즘은 계산 복잡도를 줄이면서도 강화학습의 지능적 의사결정을 결합하여, 실제 교통 시스템에 배포 가능한 수준의 성능을 입증했습니다.

결론적으로, 이 논문은 신속한 응답과 지속적인 최적화라는 상충되는 두 요구사항을 동시에 충족시키는 새로운 패러다임을 제시하며, 미래의 지능형 교통 시스템 (ITS) 개발에 중요한 기여를 합니다.