Tabu search and memetic algorithms for a real scheduling and routing problem

The Scheduling and Routing Problem (SRP) is a special case of the well-known vehicle routing problem, where a set of employees should perform an ensemble of services, at the clients’ locations. In this work, we present a real SRP faced by a company of water and electricity distribution. Under some particular constraints, the company seeks to minimize the total distance traveled by its technicians. The services required by the clients consist of installation, maintenance and control operations. The problem is modeled as a mixed integer linear program. Three meta-heuristic algorithms based on tabu search methodology and memetic algorithm are proposed to solve it. These algorithms are tested on a set of real instances and others generated randomly. To measure the quality of the solutions obtained by our algorithms their results are compared to those given by CPLEX.