A composite very-large-scale neighborhood search algorithm for the vehicle routing problem

Abstract

The classical vehicle routing problem (VRP) is defined on an undirected graph G = (N, E), where N = {0, 1,…, n} is a node set and E = {(i, j): i, j ∈ N} is an edge set. For simplicity (i, j) and (j, i) represent the same edge. Node 0 corresponds to a depot at which are based m identical vehicles of capacity C, while the remaining nodes are customers. Each customer i has a nonnegative demand qi. With each edge (i, j) is associated a cost ci j corresponding to a distance or to a travel time. The VRP consists of determining vehicle routes of minimum total cost satisfying the following constraints: 1. Each route starts and ends at the depot. 2. Each customer belongs to exactly one route. 3. The total customer demand of any route does not exceed C. 4. The total cost of any route does not exceed a preset limit D.