User:OR Scholar/sandbox

A schematic solution of a vehicle routing problem. The square represents the central depot, and the circles are the customers. Straight lines depict vehicle tours; each colour corresponds to a different vehicle. In this figure, three vehicles are required (blue, red, and black tours).

The Vehicle Routing Problem (VRP) is a generic term used to indicate a family of combinatorial optimisation problems arising from applications in logistics. Generally speaking, a solution to a vehicle routing problem is a set of routes, one for each vehicle of a given fleet, that fulfil transportation requests. It can be considered a generalisation of the Travelling Salesman Problem using multiple vehicles rather than just one.

In the most frequent variants, the size of the fleet is fixed, and its vehicles (often assumed to be identical) start and end their routes at a central depot. Customers place transportation requests. All requests are known in advance and must be fulfilled exactly once. The routes comprising a solution to the problem must satisfy feasibility requirements. For example, they might be required to visit customer locations during predetermined time windows. Finally, operating the vehicles incurs travel costs, which the problem aims to minimise.

Each of the above aspects might be forgone in particular variants of the problem. For example, in the Heterogeneous VRP, there can be different types of vehicles; in the sub-class of VRP with Profits, it is not mandatory to fulfil all requests; in Dynamic VRPs, the requests are not known in advance and keep coming during a time horizon.