Approaches for the Vehicle Routing Problem

Of the approaches mentioned in the introduction to this unit, the first two will be explained, that is the exact and heuristic methods.

Exact solution methods

Exact methods calculate the path lengths of every possible round trip, and in doing so, to choose the smallest path length. The traveling salesman problem and the vehicle routing problem are often a non-deterministic polynomial problem (NP-hard problem). The cost of computing every possible route is too high (Solomon 1987). Particularly in delivery route planning, there are often too many stations (costumers) to be supplied.

Heuristic solution methods

Heuristic solution methods are essential if there is a large amount of data to be processed (e.g. customers to be supplied). These methods can be divided into opening procedure (also called design procedure) and improvement procedure, depending on whether new routes are constructed or existing routes are improved. However, they lack the ability to make a quality assessment of the identified routes.

Opening procedures use the nearest neighbour algorithm that let the salesmen choose the nearest (according to the length of the path) unvisited city as his next move (see Dijkstra). The nearest insertion algorithm additionally tests whether there are stations located near the connecting lines between two stations. If such a station is found it is interposed.

Improvement procedures try shorten existing routes with the help of minor modifications.

Bott und Ballue (1986) identify four different categories of heuristic approaches to solve the vehicle routing problem (Bott et al. 1986):

• Cluster first, route second approaches
• Route first, cluster second approaches
• Savings or insertion approaches
• Exchange or improvement approaches

It is important to note that in practice, often combined methods such as "cluster first, route second" approaches are used. With these appraoches, the routing starts only after customers are assigned to a depot. Other approaches assume that an inadequate assignment leads to poor routing. Therefore, the first arrangement of routes is gradually improved by modification (exchange or improvement procedures) (Foulds 1997).