요구량의 지역성에 기반을 둔 섹터링을 통한 마지막 도착 허용 시간을 가지는 차량 라우팅 문제 = A Time - Deadlined Vehicle Routing Problem using Sectoring based on Locality of Customer's Demand

국문 초록 (Abstract)

마지막 도착 허용 시간을 가지는 차량 라우팅 문제는 전통적인 차량 라우팅 문제에 마지막 도착 허용 시간의 시간적 제약 조건을 가진다. 따라서 서비스를 받는 소비자의 지역적인 특성과 시간적인 특성을 고려해야 한다는 어려움이 따른다. 또한 이러한 시간적 제약 조건을 가지는 문제는 N-P hard한 문제로서 최적의 해 또는 그 근사값을 유용한 시간안에 구할 수 있는 효과적인 라우팅을 위한 경험적 방법이 주 연구 대상이 되어 왔다. 본 논문에서는 소비자 요구량의 지역성을 기반으로 하는 섹터링을 통해 라우팅의 범위를 각 섹터당으로 제안하여 계산 복잡도를 줄이고 또한 전체 라우팅 길이와 지연 소비자의 최소화를 위한 알고리즘을 제안한다. TNEWSEN을 통해 생성된 데이터 셋에 대해 기존의 경험적인 알고리즘의 대표적인 갈망 방법에 기반을 둔 DSH와의 성능 평가에 따르면 전체 라우팅 길이가 15% ~ 20% 정도 향상되었음을 알 수 있다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 관련 연구
• 3. 요구량의 지역성을 통한 섹터링 방법
• 4. 성능 평가
• 5. 결론 및 향후 연구
• 6. 참고 문헌