An adaptive large neighborhood search heuristic for dynamic vehicle routing problems. (April 2018)

• Record Type: Journal Article
• Authors: Chen, Shifeng; Chen, Rong; Wang, Gai-Ge; Gao, Jian; Sangaiah, Arun Kumar
• Is Part Of: Computers & electrical engineering. Volume 67(2018)
• Page Start: 596
• Page End: 607
• Publication Date: 2018-04
• Subjects: Dynamic vehicle routing -- Time windows -- Adaptive large neighborhood search -- Limited vehicles; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2018.02.049
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: The vehicle routing in real-life transportation, distribution and logistics may change with time, especially when there is existing technology that can produce real-time routing data. In this paper, a metaheuristic procedure based on an Adaptive Large Neighborhood Search (ALNS) algorithm is proposed to solve the Dynamic Vehicle Routing Problem (DVRP) with limited vehicles and hard-time windows. The ALNS involves ad hoc destroy/repair heuristics and a periodic perturbation procedure. In addition, an efficient feasibility check has been designed for inserting customer. By conducting several computational experiments with Lackner's benchmark, we show that the present approach can solve real-time problems within a very short time while improving the quality of the solution. The average number of vehicles is smaller than that of existing algorithms, the maximum average error of the vehicle traveling distance is reduced, and the average computation time remains the same.