HIPER-HEURÍSTICAS APLICADAS AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS DE GRANDE ESCALA

Abstract

This work presents the modeling and implementation of hyper-heuristic-based algorithms applied to the Large-Scale Vehicle Routing Problem (LSVRP). The research implemented a hybrid two-phase sequential approach based on Costa, Mei and Zhang (2020, 2021) methodologies: a Perturbative Selection Hyper-Heuristic with chromosomes composed of (heuristic_id, search_limit) pairs and an Evolutionary Hyper-Heuristic with KnowledgeGuided Local Search (KGLS). The system was implemented in C++ with five perturbative heuristics (Two-Opt, Or-Opt, Cross-Exchange, Two-Opt and Relocate) and optimized parameters: maximum limit of 300 seconds, maximum of 1000 main iterations, and improvement tolerance of 0.001. Experiments were conducted on VRPLib instances ranging from 199 to 448 customers. For statistical consolidation of the results, each algorithm was executed 30 times. Results demonstrated an average gap of 4.96% relative to best-known solutions (BKS), average processing of 94.2 customers per second, and computational time ranging from 1 to 8 seconds. Analysis identified a very strong correlation (0.986) between number of customers and computational time, indicating linear scalability. All 8 tested instances produced valid solutions, with decreasing efficiency from 199 customers/second for small instances to 56 customers/second for larger ones. Although the practical gap shows a difference of 3.95 percentage points compared to the theoretical EHH method (1.01%), results validate the feasibility of the approach for large-scale problems.