2. Problem characteristics.
The vehicle routing problem, for which the algorithm has been designed, is characterized
as follows. From a depot goods must be delivered in given quantities to given customers.
For the transportation of the goods a number of vehicles are available, each with a certain
capacity with regard to the quantities. Every vehicle that is applied in the solution must
cover a route, starting and ending at the depot, on which goods are delivered to one or
more customers.
The problem is to determine the allocation of the customers among routes, the sequence in
which the customers shall be visited on a route, and which vehicle that shall cover a route.
The objective is to find a solution which minimizes the total transportation costs.
Furthermore, the solution must satisfy the restrictions that every customer is visited
exactly once, where the demanded quantities are delivered, and the total demand on
every route must be within the vehicle’s capacity.
The transportation costs are specified as the cost of driving from any point to any other
point. The costs are not necessarily identical in the two directions between two given
points.