Implementation of an OVRP heuristic. Based on The open vehicle routing problem: Algorithms, large-scale test problems, and computational results by Feiyue Li, Bruce Golden, Edward Wasil.
In the open vehicle routing problem (OVRP), a vehicle does not return to the depot after servicing the last customer on a route.
The description of this variant of the standard vehicle routing problem appeared in the literature over 20 years ago, but has just
recently attracted the attention of practitioners and researchers. Today, the OVRP is encountered in practice in the home delivery of
packages and newspapers. Contractors who are not employees of the delivery company use their own vehicles and do not return to
the depot. In the last five years, tabu search, deterministic annealing, and large neighborhood search have been applied to the OVRP
with some success.
In this paper, we review OVRP algorithms, develop a variant of our record-to-record travel algorithm for the standard vehicle
routing problem to handle open routes, and report computational results on test problems taken from the literature. Finally,we develop
a set of eight large-scale problems that range in size from 200 to 480 nodes and report solutions generated by our record-to-record
travel algorithm on this test set.
© 2005 Elsevier Ltd. All rights reserved.