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.
Referências
Dantzig, G. B. and Ramser, J. H. (1959), “The Truck Dispatching Problem”, Management Science, v. 6, n. 1, p. 80-91.
Fanggeng, Z., Dong, M., Jiangsheng, S. and Weimin, L. (2009) “A hybrid genetic algorithm for the vehicle routing problem with simultaneous pickup and delivery”, Chinese Control and Decision Conference, p.3928-3933.
Guan, C. H., Cao, Y. and Shi, J. (2010) “Tabu Search Algorithm for Solving the Vehicle Routing Problem”, Third International Symposium on Information Processing, p.74-77.
Hai, S., Yunlong, Z., Li, J. and Wenping, Z. (2010) “Two-phase heuristic for Capacitated Vehicle Routing Problem”, Second World Congress on Nature and Biologically Inspired Computing (NaBIC), p.534-539.
He, Y., Miao, W., Xie, R. and Shi, Y. (2014) “A tabu search algorithm with variable cluster grouping for multi-depot vehicle routing problem”, Proceedings of the 2014 IEEE 18th International Conference on Computer Supported Cooperative Work in Design (CSCWD), p.12-17.
Brazilian Institute of Geography and Statistics – IBGE (2015) “Arranjos Populacionais e Concentrações Urbanas do Brasil”, Geociências, D. D. e Geografia, C. D., Rio de Janeiro.
Lin, S. W., Ying, K. C., Lee, Z. J. and Chen, H. S. (2006) “Vehicle Routing Problems with Time Windows Using Simulated Annealing”, IEEE International Conference on Systems, Man and Cybernetics, p.645-650.
Lin, S. W., Ying, K. C., Lee, Z. J. and Hsi, F. H. (2006) “Applying Simulated Annealing Approach for Capacitated Vehicle Routing Problems”, IEEE International Conference on Systems, Man and Cybernetics, p.639-644.
Marques, D. D. S., Araújo, C. S. D. and Rodrigues, H. F. (2013) “Roteirização do transporte da merenda escolar das escolas municipais urbanas de Manaus usando SIG”, XX Simpósio de Engenharia de Produção - SIMPEP, Bauru, SP.
Mine, M. T., Silva, M. S. A., Ochi, L. S., Souza, M. J. F. and Silva, T. C. B. (2010) “O problema de roteamento de veículos com coleta e entrega simultânea: uma abordagem via Iterated Local Search e GENIUS”, Transportes, v. XVIII, n. 3, p. 60-71.
Pop, P. and Chira, C. (2014) “A hybrid approach based on genetic algorithms for solving the Clustered Vehicle Routing Problem”, IEEE Congress on Evolutionary Computation (CEC), p.1421-1426.
Russell, S. J. and Norving, P. (2003) “Artificial intelligence: a modern approach”, 2th edition.
Sakakibara, K., Tsuda, T. and Nishikawa, I. (2010) “Simulated annealing method based on recursive problem decomposition for vehicle routing problems”, SICE Annual Conference, p.1016-1020.
