A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window

作     者：Beheshti, Ali Kourank Hejazi, Seyed Reza 

作者机构：Isfahan Univ Technol Dept Ind & Syst Engn Esfahan 841568311 Iran 

出 版 物：《INFORMATION SCIENCES》 (Inf Sci)

年 卷 期：2015年第316卷

页      面：598-615页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Column generation heuristic Vehicle routing problem with general soft time window Quantum-inspired evolutionary algorithm Electromagnetism algorithm 

摘      要：The vehicle routing problem with general soft time window involves designing a set of routes for a fleet of vehicles based at a central depot that is required to service a number of geographically dispersed customers while minimizing the total travel distance and delivery time costs. Delivery time cost function is a general piecewise linear function. In this study, we propose a mathematical model of this problem. Then an efficient hybrid column generation-metaheuristic approach is developed. In the proposed algorithm, the hybridization of column generation (CG) and the metaheuristic is performed in both integrative and collaborative modes. In the integrative phase, a quantum-inspired evolutionary algorithm is used to solve the sub-problems of column generation. In the collaborative phase, the column generation and electromagnetism algorithms are parallelized, and the information from these two algorithms is exchanged to find better solutions. Finally, the performance of the proposed approach is evaluated using a set of modified classic benchmark instances adopted from the literature. (C) 2014 Elsevier Inc. All rights reserved.