A Routing/Assignment Problem in Garden Maintenance Services

We address a routing/assignment problem posed by Neoturf, which is a Portuguese company working in the area of project, building and garden’s maintenance. The aim is to define a procedure for scheduling and routing efficiently its clients of garden maintenance services. The company has two teams available throughout the year to handle all the maintenance jobs. Each team consists of two or three employees with a fully-equipped vehicle capable of carrying out every kind of maintenance service. At the beginning of each year, the number and frequency of maintenance interventions to conduct during the year, for each client, are agreed. Time windows are established so that visits to the client should occur only within these periods. There are clients that are supposed to be always served by the same team, but other clients can be served indifferently by any of the two teams. Since clients are geographically spread over a wide region, the total distance traveled while visiting clients is a factor that weighs heavily on the company costs. Neoturf is concerned with reducing these costs, while satisfying agreements with its clients. We give a mixed integer linear programming formulation for the problem, discuss limitations on the size of instances that can be solved to guarantee optimality, present a modification of the Clarke and Wright heuristic for the vehicle routing with time windows, and report preliminary computational results obtained with Neoturf data.