Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows

作     者：Ben Ticha, Hamza Absi, Nabil Feillet, Dominique Quilliot, Alain 

作者机构：Ecole Mines St Etienne F-13541 Gardanne France CMP Georges Charpak UMR CNRS LIMOS 6158 F-13541 Gardanne France Inst Super Informat Modelisat & Leurs Applicat ISIMA LIMOS Campus Cezeaux Aubiere France 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (Comp. Oper. Res.)

年 卷 期：2019年第104卷

页      面：113-126页

核心收录：

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

基　　金：Labex IMobS3 European Fund for Regional Development (FEDER Auvergne region) Auvergne Region 

主　　题：Vehicle routing problem with time windows Multigraph Large neighborhood search Dynamic programming Road-network information 

摘      要：In this paper we propose a multigraph model and a heuristic for the Vehicle Routing Problem with Time Windows (VRPTW). In the classical VRPTW, travel information is commonly represented with a customer-based graph, where an arc is an abstraction of the best road-network path between two nodes. We consider the case when parallel arcs are added to this graph to introduce different compromises between travel time and cost. It has been shown in the literature that this multigraph modeling enables substantial gains in the solution quality, while highly complicating the problem. We develop an Adaptive Large Neighbourhood Search (ALNS) heuristic in which a special data structure and dynamic programming algorithms are used to efficiently address the multigraph setting. Computational experiments on several set of instances demonstrate the effectiveness of our solution method and the impact of alternative paths on the solution quality. (C) 2018 Published by Elsevier Ltd.