Computers and Operations Research, ( ISI ), Volume (37), No (12), Year (2010-12) , Pages (2106-2120)

Title : ( An ILP improvement procedure for the Open Vehicle Routing Problem )

Authors: Majid Salari , Andrea Tramontani , Paolo Toth ,

Citation: BibTeX | EndNote


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.


, integer linear programming, local search, heuristics, open vehicle routing problem
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

author = {Salari, Majid and Andrea Tramontani and Paolo Toth},
title = {An ILP improvement procedure for the Open Vehicle Routing Problem},
journal = {Computers and Operations Research},
year = {2010},
volume = {37},
number = {12},
month = {December},
issn = {0305-0548},
pages = {2106--2120},
numpages = {14},
keywords = {integer linear programming; local search; heuristics; open vehicle routing problem},


%0 Journal Article
%T An ILP improvement procedure for the Open Vehicle Routing Problem
%A Salari, Majid
%A Andrea Tramontani
%A Paolo Toth
%J Computers and Operations Research
%@ 0305-0548
%D 2010