A Vehicle Routing Problem for Human-Centered Electric Mobility

[기술 요약] 인간 중심의 전기 모빌리티를 위한 차량 경로 문제 (EM-DARP)

1. 연구 배경 및 문제 정의 (Problem Definition)

기존의 전기차 다이얼어라이드 문제(EV-DARP)는 전기차의 배터리 제한 사항을 고려하여 수요 응답형 서비스를 최적화하는 데 집중해 왔습니다. 그러나 현대의 모빌리티 서비스(예: 교통 약자를 위한 셔틀)는 승객의 특성에 따라 차량 내부 공간을 유연하게 조정해야 하는 **'가변적 용량(Configurable Capacity)'**의 필요성이 있습니다.

본 논문은 이를 해결하기 위해 **EM-DARP (Electric Mobility Dial-a-Ride Problem)**를 제안합니다. 이 문제는 다음과 같은 복합적인 요소를 포함합니다:

• 다양한 승객 요구사항: 승객 수뿐만 아니라 휠체어와 같은 이동 보조 기구의 탑재 여부 고려.
• 가변적 용량 (Configurable Capacity): 차량 내부 설정을 변경하여 승객 수 또는 보조 기구 탑재 수를 조절.
• 전기차 특성: 비선형 충전 모델(Nonlinear Charging) 및 적재량에 따른 방전율 변화(Load-Dependent Discharging) 반영.
• 유연한 운영: 시간 창(Time Window) 제약, 요청 거부(Selective variant), 오픈 VRP(Open VRP, 종점 제한 없음) 지원.

2. 연구 방법론 (Methodology)

연구진은 EM-DARP를 혼합 정수 선형 계획법(Mixed-Integer Linear Programming, MILP) 모델로 정식화하였습니다.

• 수학적 모델링 핵심 요소:

  • 목적 함수 (Objective Function): 전체 미션 시간(Mission Duration) 최소화, 도착 시간 및 시간 창(TW) 위반 최소화, 요청 거부 최소화를 동시에 목표로 하며, 요청의 중요도($\lambda_r$)에 따라 가중치를 부여합니다.
  • 배터리 모델:
    • 방전: 기본 방전율에 승객 및 보조 기구의 무게에 따른 추가 방전율을 더한 선형 모델을 사용합니다.
    • 충전: 배터리 잔량(SoC)에 따라 충전 속도가 달라지는 비선형 특성을 **구간별 선형 근사(Piecewise Linear Approximation, PLW)**를 통해 모델링하였습니다.
  • 가변 용량 제약: 보조 기구 1개가 승객 몇 명의 공간을 차지하는지를 나타내는 변환 계수($\gamma_k$)를 도입하여, 차량의 물리적 공간을 승객과 기구 사이에서 최적으로 배분하도록 설계했습니다.
  • 충전소 방문: 동일한 충전소에 여러 번 방문할 수 있도록 가상의 중복 노드(Duplicate nodes)를 생성하여 순차적 방문을 보장합니다.

• 구현 도구: Pyomo 라이브러리를 사용하여 모델을 구현하고, Gurobi 최적화 솔버를 통해 해를 도출했습니다.

3. 주요 기여 (Key Contributions)

1. 새로운 문제 모델 제안: 기존 EV-DARP에 '가변적 용량'과 '이동 보조 기구' 개념을 통합하여 실제 교통 약자 서비스에 훨씬 근접한 EM-DARP 모델을 최초로 제시했습니다.
2. 현실적인 배터리 모델링: 단순히 충전 여부만 따지는 것이 아니라, 적재량에 따른 방전 변화와 SoC 구간별 비선형 충전 특성을 MILP 프레임워크 내에 정교하게 통합했습니다.
3. 모델의 유연성: 다중 거점(Multi-depot), 요청 선택/거부, 오픈 VRP 등 실제 운영 환경에서 발생할 수 있는 다양한 시나리오를 수용할 수 있는 범용적인 수식을 구축했습니다.

4. 실험 결과 (Results)

논문은 두 가지 시나리오를 통해 모델의 유효성을 검증했습니다.

• 시나리오 1 (Selective Closed VRP): 2대의 차량과 6개의 요청을 대상으로 수행되었습니다. 배터리 소모를 높게 설정하여 강제로 충전소 방문을 유도했을 때, 모델이 우선순위($\lambda_r$)에 따라 특정 요청을 거부하고 최적의 경로와 충전 타이밍을 찾아내는 것을 확인했습니다. (해 도출 시간: 4.22초)
• 시나리오 2 (Non-selective Open VRP): 3대의 차량과 8개의 요청을 대상으로 수행되었습니다. 승객을 태운 상태에서 다른 승객을 먼저 태우는 'Pickup-Pickup' 경로가 생성되는 등, 복잡한 경로 최적화 능력을 보여주었습니다.

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

본 연구는 **인간 중심의 지속 가능한 모빌리티(Human-Centered Green Mobility)**를 위한 수학적 기반을 마련했다는 점에서 큰 의의가 있습니다. 특히, 단순히 탄소 배출을 줄이는 것을 넘어, 장애인이나 노약자와 같은 교통 약자의 특수한 요구사항을 차량 경로 최적화 과정에 직접적으로 통합할 수 있음을 증명했습니다.

향후 연구로는 대규모 실제 데이터를 처리하기 위해 MILP 외에도 휴리스틱(Heuristics)이나 메타휴리스틱(Metaheuristics)과 같은 더 효율적인 알고리즘 개발이 계획되어 있습니다.