Será defendida no dia 27 de agosto de 2026, às 16h, por videoconferência, a Proposta de Tese de Doutorado intitulada “Evolução de Regras de Despacho Interpretáveis Informadas por Solver para o Problema de Orientação em Equipe Estocástico”, do candidato ao título de Doutor em Computação – Augusto Magalhães Pinto de Mendonça.

Link para defesa: https://meet.google.com/eyk-dbzg-rbi

Evolução de Regras de Despacho Interpretáveis Informadas por Solver para o Problema de Orientação em Equipe Estocástico

Resumo:

O Problema de Orientação em Equipe com Janelas de Tempo Estocástico (STOPTW, na sigla em inglês) exige que uma equipe de veículos colete prêmios sob incerteza na duração do serviço e janelas de tempo rígidas, escolhendo o próximo cliente durante a execução. Hiper-heurísticas de programação genética (GP, na sigla em inglês) evoluem regras de despacho interpretáveis para esse cenário, mas o conjunto de terminais, os atributos com que as regras são compostas, permaneceu nos onze da linha de base NS-GP (GP com score de vizinhança). Propomos o SI-GP, uma hiper-heurística de programação genética informada por solver, que extrai blocos de construção heurísticos de soluções de referência de alta qualidade e seleciona um subconjunto desses atributos específico por instância. As rotas dos solvers de referência (NVIDIA cuOpt, PyVRP) são lidas movimento a movimento para identificar as operações que as separam das regras da linha de base. Os terminais que implementam essas operações são ancorados na literatura de escalonamento e de orientação, e dois novos terminais compostos são introduzidos. Um algoritmo genético de população estruturada realiza a seleção por instância, avaliando cada cromossomo por meio de uma execução completa da hiper-heurística de GP em GPU. Uma escolha por validação cruzada mantém a linha de base como membro reserva. A regra implantada não precisa de solver nem de simulação, e nunca fica abaixo da linha de base nos cenários reservados. Nas 40 instâncias do benchmark do STOPTW, o SI-GP melhora a linha de base NS-GP em 1,3% nas 30 instâncias em que a linha de base ainda não atende todos os clientes, com 36 vitórias, 4 empates, nenhuma derrota e 10 ganhos que sobrevivem à correção de Holm. As regras evoluídas permanecem legíveis e, na maioria das instâncias, o desvio entre execuções fica abaixo do da linha de base. O padrão é consistente com a hipótese de que o vocabulário informado por solver regulariza a busca do GP.

Abstract:

The stochastic team orienteering problem with time windows (STOPTW) requires a team of vehicles to collect prizes under service-time uncertainty and hard time windows, choosing the next customer online. Genetic programming (GP) hyper-heuristics evolve interpretable dispatching rules for this setting, but the terminal set, the features the rules compose from, has remained the eleven of the neighbourhood-score GP (NS-GP) baseline. We propose SI-GP, a solver-informed genetic programming hyper-heuristic that extracts heuristic building blocks from high-quality reference solutions and selects an instance-specific subset of these features. Routes from the reference solvers (NVIDIA cuOpt, PyVRP) are read move by move to identify the operations that separate them from the baseline rules. The terminals implementing these operations are grounded in the scheduling and orienteering literature, and two novel composite terminals are introduced. A structured-population genetic algorithm performs the per-instance selection, evaluating every chromosome by a full GP hyper-heuristic run on a GPU. A cross-validatory choice keeps the baseline as a backup member. The deployed rule needs no solver and no simulation, and never underperforms the baseline on the held-out set. On the 40 STOPTW benchmark instances, SI-GP improves the NS-GP baseline by 1.3% on the 30 instances where the baseline does not already serve every customer, with 36 wins, 4 draws, no losses, and 10 gains surviving Holm correction. The evolved rules remain readable, and on most instances their run-to-run deviation falls below the baseline’s. The pattern is consistent with the solver-informed vocabulary regularising the GP search.

Banca examinadora:

Prof. Igor Machado Coelho, UFF – Presidente

Prof. Luiz Satoru Ochi, UFF

Profa. Laura Silva de Assis, CEFET-RJ