A New Global-Local Approach to Optimize School Meals Delivery
Resumo
This paper proposes a hybrid approach to solve the capacitated vehicle routing problem with time window constraints (CVRPTW). In order to evaluate such approach, we propose a case study with the primary goal of defining the delivery routes of school meals in the public school system of Manaus city (Amazonas - Brazil). The optimized solution minimizes the traveled distance of the delivery vehicle and takes into account the capacity and time window time constrains. The approach present in this paper is classified as global-local. On one hand, the metaheuristic simulated annealing, usingthe swap operator, is applied in the global search. On the other hand, A* search algorithm is applied in the local search, in order to refine all solutions presented by the global search. Importantly, the main difference between such approach and the remaining ones present in the literature is that all solutions from the global search are optimized in the local search. The experimental evaluation compares the results with another approach, which will be presented throughout the paper, by means of computation time and total traveled distance.
