권역이 있는 실제 차량 경로 문제 해결을 위한 시스템 설계

Abstract

This study deals with a real world vehicle routing problem with time windows in Korea. The problem has the following characteristics that existing researches have not considered: (1) heterogeneous vehicles are considered, (2) delivery locations belong to different levels of districts, (3) there is eligibility between vehicles and delivery locations, (4) there is eligibility between vehicles and districts, (5) each vehicle has the maximum trip numbers and each vehicle-trip has the maximum number of delivery locations that can be included. A Large Neighborhood Search (LNS) based algorithm has been developed and successfully implemented as a software system. The system is being used for daily delivery planning at six distribution centers for a major logistics company of Korea. The delivery planning time has been reduced by 26 percent (50 minutes) because of the system. However, the system is specialized for the real company. In order to develop a more general and extendible system, this study proposes a hierarchical class design, which consists of a common library, a scheduling problem library, a vehicle routing problem library, and various application systems. The system design has been successfully implemented and tested. Using the libraries, the development time of a delivery planning system could be reduced from eight weeks to two weeks. Furthermore, some embedded algorithms have been parallelized to reduce the computation time. The parallelism could reduce the computation time by 26%. The proposed system architecture and parallelism can be used for various vehicle routing problems and scheduling problems.