An ILP Improvement Procedure for the Open Vehicle Routing Problem

Majid Salari, Paolo Toth, and Andrea Tramontani

DEIS, University of Bologna,
Viale Risorgimento 2, 40136 Bologna, Italy
fmajid.salari2,paolo.toth,andrea.tramontanig@unibo.it

Abstract. We address the Open Vehicle Routing Problem (OVRP),
a variant of the \classical" 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
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 ¯nding a new improved 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 ¯nd the new best-known
solution for the considered problem.