Optimal Solution of a Vehicle-routeing Problem: Transporting Mentally Handicapped Adults to an Adult Training Centre

Many organizations must devise tours for vehicles to collect from or deliver to a given set of destinations—the vehicle-routeing problem. This paper presents the optimal solution to a real-world problem with 38 destinations and four vehicles, and is thought to be the largest such problem that has been solved optimally. The organization concerned is a local authority (Berkshire County Council) which has aims other than profit maximization. Therefore explicit consideration is given to the multi-objective nature of the problem. Attempts to solve the problem using a commercial mathematical-programming package failed, but a specially written computer program was run on a mini-computer. In the optimal solution, total travel time is reduced by 15.7% and total distance by 11.5%, while the number of empty seats in each vehicle is more equally distributed.