Proposta para otimização de rotas de entrega de merenda escolar na rede pública da cidade de Manaus

Abstract

The vehicle routing problem is critical when it comes to company logistics and the administration of public resources. This work proposes a hybrid approach to solve the Vehicle Routing Problem with Time Window (VRPTW). In order to evaluate this new approach, a case study was proposed with the goal to establish the school meal delivery routes in the public school system of Manaus city, Brazil. Particularly, the optimized solution (route) should minimize the distance traveled by the delivery vehicle, taking into account both capacity and time window constraints. In addition, the proposed approach is the global-local kind and it was named global-local-g method. In the global search, the metaheuristic simulated annealing (SA) is combined with a new technique to generate neighbors, named neighbors‟ generation per quadrant. In contrast, the main purpose of the local search is the refinement of all solutions found by the global search. For this reason, the A* algorithm is combined with a new heuristic, called as heuristic of the next step. It is worth noticed that the main difference between the approach presented here to others in the literature is the local optimization. In this new approach, all solutions from the global method are optimized through local searches. In similar works, the distances between the nodes of interest (i.e., schools) are already pre-calculated in terms of the Euclidean distance between these nodes. However, in this work, the distance between the nodes is calculated at run time and it takes into account the distance from the actual streets, i.e., it considers the route distance between streets in a map. In the global search, the SA method combined with the neighbors‟ generation per quadrant produces all solutions, which are formed by a sequence of the nodes of interest. Then, using the street distances, window time restrictions, and the vehicle capacity, all node clusters are defined. Thus, within each cluster, the path traveled through local searches is optimized by the A* algorithm combined with the heuristic of the next step. Experimental results with the proposed approach presented prominent results in comparison to the other existing ones regarding run time and distance traveled.