Iterated local search adapted to clustering and routing problems

Physical distribution is a critical activity for companies because it defines successful customer service. This article discusses a case study of a liquefied gas distributor with respect to improving customer service and reducing delivery costs. The proposed method for the delivery process consists of two steps: First, the customers for each day are distributed to the delivery trucks by using the metaheuristic Iterated Local Search (ILS) in order to solve the Capacitated P-median Problem. This metaheuristic is also applied to some published instances in order to assess their efficiency in problems of different sizes. The second stage consists of determining the route of each truck by using the ILS metaheuristic for the traveling salesman problem. The results show a reduction of 11% in the distances in the clusters, in addition to an improvement in the routing, which previously did not use mathematical methods. These results generate improvement in terms of both the level of service offered to customers and the scale economy. The metaheuristic ILS performs well for the two subjects tackled, with a very low error compared to the exact methods and almost instantaneous computational times.