An adaptive large neighborhood search heuristic for dynamic vehicle routing problems

被引：84

作者：

Chen, Shifeng ^{[1
]}

Chen, Rong ^{[1
]}

Wang, Gai-Ge ^{[2
]}

Gao, Jian ^{[1
]}

Sangaiah, Arun Kumar ^{[3
]}

机构：

[1] Dalian Maritime Univ, Dept Informat Sci & Technol, Dalian 116026, Peoples R China

[2] Ocean Univ China, Coll Informat Sci & Engn, Qingdao 266100, Shandong, Peoples R China

[3] VIT Univ, Sch Comp Sci & Engn, Vellore 632014, Tamil Nadu, India

来源：

COMPUTERS & ELECTRICAL ENGINEERING | 2018年 / 67卷

基金：

中国国家自然科学基金;

关键词：

Dynamic vehicle routing; Time windows; Adaptive large neighborhood search; Limited vehicles; ALGORITHM;

D O I：

10.1016/j.compeleceng.2018.02.049

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2018 Elsevier Ltd. All rights reserved.

引用

页码：596 / 607

页数：12