You are here

Open Vehicle Routing Problem

Defintion

The Open Vehicle Routing Problem (OVRP) is a version of the well known Capacitated Vehicle Routing Problem (CVRP), in which each route ends at the last served customer. More precisely, a vehicle does not return to the depot  after servicing the last customer  as is the case of the classic CVRP.
 
This problem can be modeled on a directed graph G(V,A), where each node in V represents a customer, 0 means the depot location and arcs in A represent connections between them. Each arc (i, j)  has an associated nonnegative cost cij  and each customers i has a demand di  and a related service time s. Furthermore, each vehicle has load capacity limit Q and operation time limit L
 
Each route performed by a vehicle is a Hamiltonian path. Thus each vehicle processes the service demands of its customers using a sequence of adjacent arcs and nodes of the directed graph.

The objective is  considering the vehicles' constraints finding a set of valid routes with minimal overall costs.

 

Example

The figure below shows the sturcture of the routes in the solution of a OVRP instance 

Instances

A set of OVRP instances is available for testing algorithms.

File format and instances files are available in the file IntancesOVRP_WebOR.zip