A multi-depot period vehicle routing problem arising in the utilities sector

This paper considers the resource planning problem of a utility company tha t provides preventive maintenance services to a set of customers using a fl eet of depot-based mobile gangs. The problem is to determine the boundaries of the geographic areas served by each depot, the list of customers visite d each day and the routes followed by the gangs. The objective is to provid e improved customer service at minimum operating cost subject to constraint s on frequency of visits, service time requirements, customer preferences f or visiting on particular days and other routing constraints. The problem i s solved as a Multi-Depot Period Vehicle Routing Problem (MDPVRP). The comp utational implementation of the complete planning model is described with r eference to a pilot study and results are presented. The solution algorithm is used to construct cost-service trade-off curves for all depots so that management can evaluate the impact of different customer service levels on total routing costs.