Lifted and Local Reachability Cuts for the Vehicle Routing Problem with Time Windows

作     者：Avella, Pasquale Boccia, Maurizio Vasilyev, Igor 

作者机构：Univ Sannio DING Benevento Italy Russian Acad Sci Siberian Branch Inst Syst Dynam & Control Theory Moscow 117901 Russia 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2013年第40卷第8期

页      面：2004-2010页

核心收录：

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

基　　金：Russian Foundation for Basic Research [12-07-33045-mol_a_ved  12-07-13116-ofi_m_RZD] 

主　　题：Vehicle Routing Problem with Time Windows Mixed Integer Programming Branch and Cut 

摘      要：The Vehicle Routing Problem with Time Windows (VRPTW) requires to design minimum cost routes for a fleet of vehicles with identical capacities to serve a set of customers within given time windows. Each customer must be visited exactly once and the load of a vehicle must not exceed its capacity. In this paper we introduce two new basic families of valid inequalities, called Lifted and Local Reachability Cuts, respectively, which extend the Reachability Cuts introduced by J. Lysgaard. Separation procedures for Lifted and Local Reachability Cuts have been implemented and embedded into a Branch-and-Cut framework to validate their computational effectiveness. They were tested on the Solomon and on the Gehring-Homberger benchmark instances (also known as the Extended Solomon instances) with 200 customers. Computational experiments show that the new cutting plane families can substantially improve the lower bounds returned by Lysgaard s Reachability Cuts. The Branch-and-Cut algorithm could also provide the optimal solution of three previously unsolved instances - C222, 025 and 026 - with large capacities and wide time windows and therefore difficult for exact algorithms. (C) 2013 Elsevier Ltd. All rights reserved.