SynthCharge: An Electric Vehicle Routing Instance Generator with Feasibility Screening to Enable Learning-Based Optimization and Benchmarking

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

이 논문은 **"SynthCharge"**라는 새로운 도구를 소개합니다. 이 도구의 역할을 이해하기 위해 먼저 배경 이야기를 해보겠습니다.

🚗 배경: 전기 트럭 배달의 난제

옛날에는 배달 트럭이 기름만 가득 채우면 끝났습니다. 하지만 요즘은 전기 트럭을 쓰죠. 문제는 전기 트럭은 배터리가 방전되면 멈춰버린다는 점입니다. 그래서 "어디서, 언제, 얼마나 충전할지"를 계산하면서 동시에 "어떤 순서로 고객을 방문할지"를 정해야 합니다. 이를 **'전기차 경로 최적화 문제 (EVRPTW)'**라고 합니다.

지금까지 연구자들은 이 문제를 해결하는 AI(머신러닝) 를 개발하려 했지만, 시험 문제 (데이터) 가 너무 단순하거나 고정되어 있었다는 문제가 있었습니다. 마치 수학 시험을 볼 때, 항상 같은 문제만 풀게 해서 실력을 측정하는 것과 비슷합니다. AI 가 특정 문제만 잘 풀고, 조금만 상황이 바뀌면 엉망이 되는 것입니다.

💡 해결책: SynthCharge (가상의 배달 시뮬레이터)

이 논문은 **"SynthCharge"**라는 도구를 만들어 이 문제를 해결했습니다. 이 도구를 **마치 '배달 게임의 맵 생성기'**라고 생각해보시면 쉽습니다.

1. 무한한 맵을 만들어주는 '랜덤 맵 생성기'

기존의 시험 문제는 고정된 100 개의 맵만 있었습니다. 하지만 SynthCharge 는 연구자가 원하는 대로 맵을 수없이 많이, 그리고 다양하게 만들어줍니다.

고객 분포: 고객이 도시 전체에 고르게 퍼져있을 수도 있고 (랜덤), 특정 구역에 뭉쳐있을 수도 있고 (클러스터), 둘 다 섞여 있을 수도 있습니다.
시간 제한: "1 시간 안에 도착해!"라고 엄격하게 할 수도 있고, "오후 5 시까지면 돼"라고 넉넉하게 줄 수도 있습니다.
배터리: 배터리를 많이 넣을 수도, 적게 넣을 수도 있습니다.

2. '불가능한 미션'을 미리 걸러내는 '현실성 검사관'

가장 중요한 특징은 현실성 검사입니다.

상황: 만약 AI 가 "고객 A 에게 가려면 배터리가 부족해서 갈 수 없는데, 충전소가 너무 멀어서 아예 갈 수 없는 상황"을 만들면, AI 가 아무리 똑똑해도 해결책을 찾을 수 없습니다.
SynthCharge 의 역할: 이 도구는 맵을 만든 직후, **"이 미션이 물리적으로 가능한가?"**를 빠르게 검사합니다.
- 충전소가 너무 멀어서 갈 수 없는가?
- 시간이 너무 짧아서 도착할 수 없는가?
- 이런 불가능한 시나리오는 미리 걸러내고, 실제로 해결 가능한 시나리오만 연구자들에게 줍니다.

3. '난이도 조절' 기능

이 도구는 연구자들이 AI 의 실력을 정확히 측정할 수 있도록 난이도를 조절해줍니다.

쉬운 단계: 배터리가 넉넉하고, 시간이 충분하고, 고객이 가까이 모여 있는 경우.
어려운 단계: 배터리는 부족하고, 시간은 바쁘고, 고객은 도시 끝까지 흩어져 있는 경우.
이렇게 단계별로 난이도를 높여가며 AI 를 훈련시키면, AI 는 어떤 상황에서도 잘 대처하는 강력한 배달 로봇이 될 수 있습니다.

🏆 왜 이것이 중요한가요?

이전까지 연구자들은 "내 AI 가 이 고정된 문제집을 풀었으니 1 등이다!"라고 주장했습니다. 하지만 SynthCharge 는 **"내 AI 는 이 천 가지의 다양한 상황에서도 모두 해결책을 찾았으니, 진짜로 똑똑하다!"**라고 증명할 수 있게 해줍니다.

한 줄 요약:

SynthCharge는 전기 트럭 배달 AI 를 훈련시키기 위해, **현실적이고 다양한 배달 시나리오를 자동으로 만들어주고, 불가능한 시나리오는 미리 걸러내는 '최고급 시뮬레이션 키트'**입니다. 이를 통해 AI 가 실제 도로에서 어떤 상황에도 잘 대처할 수 있도록 검증할 수 있게 됩니다.

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

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

전기차 라우팅 문제 (EVRPTW): 전기차 라우팅 문제는 기존 VRPTW(시간제약 차량 라우팅 문제) 에 배터리 용량 제약과 충전소 방문 결정이라는 새로운 차원을 추가한 문제입니다. 이는 경로 구성과 실현 가능성 (feasibility) 을 근본적으로 변화시킵니다.
기존 벤치마크의 한계:
- 기존 데이터셋은 정적 (static) 이며, 검증 가능한 실현 가능성 정보가 부족합니다.
- 학습 기반 최적화 모델 (신경망, 강화학습 등) 의 평가 시, 고정된 분포의 인스턴스만 사용함으로써 분포 이동 (distribution shift) 에 대한 민감성을 제대로 평가하기 어렵습니다.
- 공간 구조, 문제 크기, 제약 조건 (시간 창, 에너지) 의 체계적인 변화에 따른 모델 성능을 평가할 수 있는 인프라가 부재합니다.
연구 목표: 학습 기반 라우팅 모델의 견고성 (robustness) 을 체계적으로 평가할 수 있도록, 다양한 공간 - 시간 구성과 확장 가능한 고객 수를 가진 실현 가능성 (feasibility) 이 선별된 EVRPTW 인스턴스를 생성하는 도구인 SynthCharge를 개발하는 것입니다.

2. 방법론 (Methodology)

SynthCharge 는 파라미터 기반의 인스턴스 생성기이며, 다음과 같은 핵심 메커니즘을 가집니다.

가. 공간 토폴로지 및 충전 인프라 생성

공간 구조: 솔로몬 (Solomon) VRPTW 구조에서 영감을 받아 세 가지 공간 패밀리 (Random, Clustered, Mixed) 를 지원합니다.
충전소 배치: 고정된 템플릿이 아닌 범위 인지 (range-aware) 규칙을 따릅니다.
- 차량의 주행 가능 거리 ( $R$ ) 를 기반으로 충전소가 필요한 지점 (고객 간 거리가 $0.8R$ 이상인 경우, 또는 창고와 고객 간 거리가 $0.7R$ 이상인 경우) 에 충전소를 배치합니다.
- 이는 에너지 제약과 공간 구조를 연결하여 인스턴스의 실현 가능성을 높입니다.

나. 에너지 및 파라미터 스케일링

적응형 배터리 용량: 인스턴스의 기하학적 특성 (평균 고객 간 거리, 창고 분산 등) 에 따라 배터리 용량 ( $B$ $B$ ) 을 동적으로 조정합니다.
- 목표 주행 거리 ( $R^*$ ) 를 공간적 확산에 비례하도록 설정하고, 이를 정규화된 밴드 $[R_{min}, R_{max}]$ 내에서 제한하여 인스턴스가 에너지 제약이 있되 지나치게 비현실적이지 않게 만듭니다.
시간 창 (Time Windows): 고객별 시간 창 폭 ( $W$ ) 을 전체 계획 기간 ( $H$ ) 의 비율 ( $\phi$ ) 로 정의하며, '넓음', '중간', '좁음' 세 가지 레짐을 지원합니다.

다. 실현 가능성 선별 (Feasibility Screening)

생성된 인스턴스가 실제로 해결 가능한지 확인하기 위해 2 단계 검증 프로세스를 적용합니다:

1 단계: 구조적 선별 (Structural Screening, $O(N)$ ):
- 결정론적 검사를 통해 명백한 위반 사항을 제거합니다.
- 조건: 모든 고객이 충전소 또는 창고로부터 주행 거리 $R$ 이내에 있어야 함, 계획 기간 내에 창고로 복귀 가능해야 함 등.
- 이 단계는 계산 비용이 매우 낮아 대규모 인스턴스 ( $N > 10$ ) 에 적용됩니다.
2 단계: 정밀 검증 (Exact MILP Verification, $N \le 10$ ):
- 소규모 인스턴스에 대해 정확한 혼합 정수 선형 계획법 (MILP) 솔버를 사용하여 경로 존재 여부를 엄격하게 검증합니다.
- 이 과정을 통과한 인스턴스만 최종 벤치마크 데이터로 사용됩니다.

라. 출력 및 재현성

생성된 인스턴스는 .txt 파일 형식으로 내보내지며, 생성 파라미터와 실현 가능성 상태를 기록한 JSON 메타데이터 로그가 함께 제공됩니다.
모든 무작위 시드는 고정되어 결과의 재현성을 보장합니다.

3. 주요 기여 (Key Contributions)

SynthCharge 생성기 개발: 공간적 구조, 고객 규모, 시간 창 제약, 에너지 용량 레짐을 체계적으로 변화시킬 수 있는 파라미터 기반 EVRPTW 생성기입니다.
실현 가능성 선별 메커니즘: 생성된 인스턴스의 구조적 무결성을 보장하기 위해 빠르고 효율적인 선별 프로세스를 통합하여, 학습 모델 평가 시 '해결 불가능한' 인스턴스로 인한 편향을 제거합니다.
학습 기반 최적화를 위한 벤치마크 인프라: 고정된 데이터셋이 아닌, 분포 이동 (distribution shift) 하에서의 모델 일반화 능력을 평가할 수 있는 동적인 벤치마크 환경을 제공합니다.
개방형 도구: GUI 를 통한 실시간 시각화와 오픈소스 코드 공개를 통해 연구 커뮤니티의 재현성 있는 평가를 지원합니다.

4. 실험 결과 (Experimental Results)

실험 설정: 고객 수 5~100 명, 다양한 공간/시간 레짐 조합에서 총 2,475 개의 인스턴스를 생성하여 평가했습니다.
수용률 (Acceptance Rate, $\gamma$ ):
- 시간 창이 좁아질수록 (Tight regime), 특히 클러스터형 (Clustered) 공간 구조에서 수용률이 감소하는 경향을 보였습니다.
- 전체적으로 수용률은 공간 구조와 제약 조건에 따라 유의미하게 변동하여, 단순한 인스턴스 생성이 아님을 입증했습니다.
생성 효율성:
- $N \le 10$ 인 경우 MILP 검증으로 인해 약 0.1 초 소요되나, $N > 10$ 인 경우 구조적 선별만 적용되어 0.01 초 미만으로 매우 빠르게 생성됩니다.
- 이는 대규모 학습 데이터셋 생성에 적합함을 보여줍니다.
실제 해결 가능성 검증:
- 생성된 인스턴스 (모든 크기) 에 대해 변이 Neighborhood Search/Tabu Search 메타휴리스틱을 적용한 결과, 100% 의 인스턴스에서 실현 가능한 경로를 성공적으로 도출했습니다.
- 이는 1 단계 구조적 선별이 실제 라우팅 실현 가능성과 높은 상관관계를 가짐을 의미합니다.
자원 활용도: 시간 창이 좁아지고 공간이 분산될수록 평균 이동 거리와 필요 차량 대수가 증가하는 경향을 확인했습니다.

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

학습 기반 모델 평가의 표준화: 기존 고정된 벤치마크의 한계를 넘어, 다양한 제약 조건과 공간 구조 하에서 신경망 기반 라우팅 모델의 일반화 성능을 체계적으로 평가할 수 있는 기반을 마련했습니다.
재현성 및 투명성: 인스턴스 생성의 모든 파라미터와 실현 가능성 검증 과정을 명확히 문서화하여, 연구 결과의 재현성과 신뢰성을 높였습니다.
한계 및 향후 과제: 현재는 유클리드 거리, 단일 창고, 선형 충전 모델 등에 국한되어 있습니다. 향후 다중 창고, 비선형 충전 곡선, 시간 의존적 이동 시간, 실제 도로 네트워크 통합 등을 통해 확장할 계획입니다.

요약하자면, SynthCharge 는 전기차 라우팅 문제 연구, 특히 학습 기반 최적화 알고리즘의 성능을 엄격하고 재현 가능하게 평가하기 위해 필수적인 '동적이고 검증된' 벤치마크 인프라를 제공하는 도구입니다.