전기 용량 차량 경로 문제 (ECVRP) 에서 계층적 후기 수용 힐 클리밍의 인스턴스 인식 파라미터 설정

요약

본 논문은 전기 용량 차량 경로 문제(ECVRP)와 같은 조합 최적화 문제에서 발생하는 인스턴스 이질성 문제를 해결하기 위해, 계층적 후기 수용 힐 클리밍(Bilevel Late Acceptance Hill Climbing) 알고리즘의 인스턴스 인식 파라미터 설정 방법을 제안합니다. 오프라인 튜닝을 통해 얻은 인스턴스별 파라미터를 회귀 모델로 학습시켜, 실행 전에 미확인 인스턴스의 최적 파라미터를 예측할 수 있습니다. 실험 결과에 따르면, 이 접근법은 기존의 전역 튜닝 방식보다 평균 목표 함수 값 감소를 달성하여 실제 운송 운영에서 상당한 비용 절감 효과를 가져올 수 있음을 입증했습니다.

핵심 포인트

• 조합 최적화 알고리즘의 성능은 파라미터 설정에 매우 민감하며, 인스턴스별 이질성을 고려해야 한다.
• ECVRP와 같은 문제에서는 구조 및 에너지 제약이 다르므로 전역 튜닝 방식만으로는 한계가 있다.
• 제안된 방법은 오프라인 튜닝과 회귀 모델을 결합하여 미확인 인스턴스의 최적 파라미터를 예측한다.
• 실험적으로, 이 접근법은 기존의 전역 튜닝 구성 대비 우수한 성능 향상(평균 목표 함수 값 감소)을 보였다.