A clustering and insertion heuristic applied to a large routeing problem in food distribution

This article investigates a large food distributor and describes a heuristic approach to provide satisfactory solutions to large, realistic, complicated routeing problems of food distribution. The approach includes routeing (clustering and insertion) procedures and the allocation of drivers and vehicles. These procedures were heuristically developed, on the basis of the delivery data of three days of four large geographic regions. The approach was used to develop an integrated, interactive, computer-based system for routeing of food-service delivery vehicles after being tested on the problems of four to five days of seven geographic regions which cover the Western, Midwest and Southern United States. The sizes of the problems ranged from 5 to 24 routes per region and 69 to 308 customers per schedule. The revised approach improved the solutions of the previous system by an average of 5.6% of delivery costs. The cost savings were caused mainly by a reduction in the number of routes.