Paper Info
Title
An ILP improvement procedure for the Open Vehicle Routing Problem
Abstract
We address the Open Vehicle Routing Problem (OVRP), a variant of the ''classical'' (capacitated and distance constrained) Vehicle Routing Problem (VRP) in which the vehicles are not required to return to the depot after completing their service. We present a heuristic improvement procedure for OVRP based on Integer Linear Programming (ILP) techniques. Given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in the attempt of finding a new improved feasible solution. The overall procedure can be considered as a general framework which could be extended to cover other variants of Vehicle Routing Problems. We report computational results on benchmark instances from the literature. In several cases, the proposed algorithm is able to find the new best known solution for the considered instances.
Year
DOI
Venue
2010
10.1016/j.cor.2010.02.010
Computers & OR
Keywords
Field
DocType
vehicle routing problem,heuristics,integer linear programming,local search
Mathematical optimization,Vehicle routing problem,Link-state routing protocol,Destination-Sequenced Distance Vector routing,Heuristics,Integer programming,Cutting stock problem,Local search (optimization),Mathematics
Journal
Volume
Issue
ISSN
37
12
Computers and Operations Research
Citations 
PageRank 
References 
24
0.74
19
Authors
3
Name
Order
Citations
PageRank
Majid Salari115210.08
Paolo Toth22336252.94
Andrea Tramontani3966.05