The Vehicle Routing Problem

Many methods have been developed to solve the vehicle routing problem. A very successful algorithm for solving this problem, which is still the focus of much research, is called column generation.

Column generation considers each possible route that a vehicle can take as a variable (or possible option) in the problem. However, even with only a small number of deliveries the number of routes can be prohibitively large to solve this problem using todays computers. So the column generation algorithm works as follows: 1. only some of the total possible routes are initial considered in the optimisation problem, 2. once this smaller problem is solved, if the best possible vehicle routing solution is not given, then new routes are added to the problem, 3. with these new routes, and the original set of routes, the optimisation problem is then resolved. Steps 2 and 3 repeated until no more routes are added to the optimisation problem.

The beauty of this algorithm is that the best possible vehicle routing solution can be found by considering only a small fraction of all possible routes. This approach significantly reduces the computing time and power that is required to solve this problem.

The vehicle routing problem arises in may practical applications. In addition to grocery deliveries, there are many applications for delivery and courier companies. Also, the vehicle routing problem can be used by carpooling services and the packing and collection of goods from warehouses. The vehicle routing problem is a classical problem that receives much attention from researchers. The reason for this attention is that transportation is a significant cost for many companies. The development of better techniques for solving the vehicle routing problem can produce large savings for manufacturing and transportation companies that can drive lower costs for the consumer.