Exact Solution of the Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is a hard and well-known combinatorial optimization problem which calls for the determination of the optimal routes used by a fleet of vehicles, based at one or more depots, to serve a set of customers. In practical applications of the VRP arising in the design and management of distribution systems, several operational constraints are imposed on the route construction. For example, the service may involve both deliveries and collections, the load along each route must not exceed the given capacity of the vehicles, the total length of each route must not be greater than a prescribed limit, the service of the customers must occur within given time windows, the fleet may contain heterogeneous vehicles, precedence relations may exist between the customers, the customer demands may not be completely known in advance, the service of a customer may be split among different vehicles, and some problem characteristics, as the demands or the travel times, may vary dynamically.