Modelo de otimização para o problema de roteirização de viaturas na Marinha do Brasil

Abstract

A necessidade de deslocamentos eficientes, impulsionada pelo crescimento urbano e pela busca por redução de custos, torna o planejamento de rotas uma tarefa desafiadora quando se consideram múltiplos locais, veículos e restrições operacionais. O Problema de Roteamento de Veículos (VRP), uma generalização do Problema do Caixeiro Viajante (TSP), aborda essa complexidade ao buscar soluções otimizadas para o transporte de pessoas ou bens. Neste contexto, este trabalho apresenta um estudo de caso aplicado a um Centro de Análises de Sistemas Navais (CASNAV), da Marinha do Brasil, responsável pelo planejamento de rotas de viaturas administrativas. Como principal contribuição, foi proposto um modelo matemático adaptado às características do problema real, denominado HFDARPTW (Heterogeneous Fleet Dial-a-Ride Problem with Time Windows) Multi-Trip, que incorpora variantes como coleta e entrega, janelas de tempo, frota heterogênea, múltiplas viagens por veículo e limitação do tempo de permanência dos passageiros. A formulação foi implementada em AMPL e resolvida com o Solver Gurobi, sendo possível obter soluções exatas para casos de até dez pares coleta-entrega. A metodologia adotada envolveu uma revisão sistemática com base na recomendação PRISMA 2020, coleta e tratamento de dados reais, construção do modelo matemático e análise comparativa entre os resultados otimizados e a operação empírica. Os resultados indicam que o modelo proposto respeita todas as restrições do problema e pode oferecer ganhos operacionais, especialmente em cenários mais complexos, nos quais a definição empírica de rotas se torna limitada. Além disso, a modelagem proposta pode servir de base para o desenvolvimento de métodos aproximados voltados à resolução de instâncias maiores.

The need for efficient transportation, driven by urban growth and the pursuit of cost reduction, makes route planning a challenging task when multiple locations, vehicles, and operational constraints are considered. The Vehicle Routing Problem (VRP), a generalization of the Traveling Salesman Problem (TSP), addresses this complexity by seeking optimized solutions for the transportation of people or goods. In this context, this study presents a case study applied to the Naval Systems Analysis Center (CASNAV) of the Brazilian Navy, responsible for planning administrative vehicle routes. As its main contribution, a mathematical model adapted to the characteristics of the real-world problem is proposed, named HFDARPTW (Heterogeneous Fleet Diala-Ride Problem with Time Windows) Multi-Trip. This model incorporates variants such as pickup and delivery, time windows, heterogeneous fleet, multiple trips per vehicle, and passenger ride time limitations. The formulation was implemented in AMPL and solved using the Gurobi Solver, with exact solutions obtained for cases of up to ten pickup-delivery pairs. The adopted methodology involved a systematic review based on the PRISMA 2020 guideline, collection and processing of real data, construction of the mathematical model, and comparative analysis between the optimized results and the empirical operation. The results indicate that the proposed model respects all problem constraints and can offer operational gains, especially in more complex scenarios where empirical route definition becomes limited. Furthermore, the proposed model may serve as a foundation for the development of approximation methods aimed at solving larger instances.