Hybrid Metaheuristic Vehicle Routing Problem for Security Dispatch Operations
Created by
- Haebom
Category
Empty
저자
Nguyen Gia Hien Vu, Yifan Tang, Rey Lim, G. Gary Wang
개요
본 논문은 보안 및 순찰 애플리케이션에 초점을 맞춘 차량 경로 문제(VRPSD)의 최적화를 연구합니다. VRPSD는 정확한 시간 및 엄격한 시간 창과 같은 어려운 제약 조건을 포함합니다. 본 논문에서는 적응형 대규모 이웃 탐색(ALNS), 금기 탐색(TS), 임계값 수용(TA)을 기반으로 하는 세 가지 알고리즘을 제안합니다. 첫 번째 알고리즘은 단일 단계 ALNS와 TA를 결합하고, 두 번째 알고리즘은 다단계 ALNS와 TA를 사용하며, 세 번째 알고리즘은 다단계 ALNS, TS, TA를 통합합니다. 251개 고객 요청으로 구성된 인스턴스에 대한 실험을 수행한 결과, 세 번째 알고리즘인 하이브리드 다단계 ALNS-TS-TA 알고리즘이 최고의 성능을 제공하는 것으로 나타났습니다. 이 방법은 ALNS의 광범위한 탐색 기능을 활용하여 탐색하고 다단계 ALNS가 TS 및 TA와 결합될 때 지역적 최적점을 효과적으로 벗어납니다. 또한, 실험에서 하이브리드 다단계 ALNS-TS-TA 알고리즘은 모든 시도에서 계산 시간 증가에 따라 결과를 개선할 가능성을 보여주는 유일한 알고리즘입니다.
시사점, 한계점
•
시사점: 하이브리드 다단계 ALNS-TS-TA 알고리즘이 VRPSD 문제에 효과적임을 실험적으로 증명. 계산 시간 증가에 따라 성능 개선 가능성 제시. ALNS, TS, TA의 장점을 결합하여 효율적인 탐색 및 지역 최적점 탈출 가능.
•
한계점: 실험이 251개 고객 요청의 단일 인스턴스에 대해서만 수행됨. 다양한 규모 및 특성의 인스턴스에 대한 추가 실험 필요. 알고리즘의 일반화 가능성에 대한 추가 연구 필요.
