Vehicle Routing

The feeding problem involves determining in what order each trolley should visit its workstations. There is one route per vehicle which starts and ends at the warehouse. Then the routing problem becomes an extension of the Vehicle Routing Problem (VRP) with additional constraints. There are many extensions of the basic VRP to account for the large number of practical applications. They are usually in the form of extra constraints or combinations of constraints. Examples can be found in Dror et al. (1994). Further constraints that can be included are the following: durations of the route, start and end locations for the route/driver, route starting time, weight and volume restrictions on vehicle load, loading constraints, rules for split deliveries if any, and multi-routes per vehicle (Kozan, 2000).

There are many exact and heuristic methods proposed to solve different extensions of the VRP. Exact methods are only used to solve small problems and can be put into three broad categories: tree searches, dynamic programming and integer programming. Details of these techniques can be found in Christofides et al. (1989), Laporte (1992) and Foster et al. (1976).

Heuristic methods can be grouped into the following classifications: constructive methods, twostep methods, exact but incomplete tree search methods and improvement methods (Osman, 1993).