Métodos de otimização para o problema de roteamento de veículos periódico com frota heterogênea

Abstract

O Problema de Roteamento de Veículos (PRV) é um problema clássico de Otimização Combinatória bastante estudado na literatura devido a sua importância prática. O PRV Periódico (PRVP), abordado neste trabalho, é uma variante do PRV no qual um conjunto de clientes devem ser visitados uma ou mais vezes para atender suas demandas durante um horizonte de tempo composto de vários dias. Os dias de visita/atendimento não são fixados a priori. Uma lista de dias possíveis (agenda de visitas) é associada a cada cliente. O objetivo é determinar os dias de visita de cada cliente e as rotas dos veículos para cada dia do horizonte de tal maneira que a distância total de percurso dos veículos e os custos associados com utilização dos mesmos sejam minimizados. O PRVP é um problema que pertence à classe NP-difícil. Neste trabalho, para resolvê-lo, são desenvolvidos três métodos de otimização: Proximity Search (PS), Ite- rated Local Search (ILS) e Particle Swarm Optimization (PSO). PS é um método genérico que faz uso do modelo de Programação Inteira do problema para melhorar iterativamente uma solução inicial. Em vez de modificar as restrições do modelo com o objetivo de reduzir o espaço de busca, o PS modifica a função objetivo do modelo para tornar a busca mais fácil. Os métodos ILS e PSO são meta-heurísticas de busca em vizinhança e populacional/evolutiva, respectivamente. Os desempenhos dos métodos propostos são analisados em instâncias de pequeno e grande porte geradas neste trabalho, e também em instâncias disponíveis na literatura. O desempenho do PS é comparado com o solver CPLEX, que resolve o modelo original do problema. As meta-heurísticas desenvolvidas são comparadas entre si e também são comparadas com algumas heurísticas da literatura. Os experimentos computacionais mostram que os métodos propostos são eficientes, competitivos e rápidos.

The Vehicle Routing Problem (VRP) is a classic problem of Combinatorial Optimi- zation extensively studied in the literature because of its practical importance. The Periodic VRP (PVRP), discussed in this work, is a variant of VRP in which a group of customers should be visited one or more times to meet their demands over a time horizon composed of several days. The days to visit a customer are not initially fixed. A possible list of days (visits schedule) is associated with each customer. The objective problem is to determine the set of days to visit each customer and determine the routes of the vehicles for each day of the planning horizon such that the total distance of the vehicle route and costs associated with use of them are minimized. The PVRP is a problem that belongs to the NP-hard class. In this work, three optimization methods are developed to solve the problem: Proximity Search (PS), Iterated Local Search (ILS) and Particle Swarm Optimization (PSO). PS is a generic method that makes use of the Integer Programming Problem model to iteratively improve an initial solution. Instead of modifying the model restrictions intended to reduce the search space, the PS changes the objective function to make the search easier. The ILS and PSO methods are meta-heuristic search in the neighborhood and population / evolutionary, respectively. The performances of the proposed methods are analyzed using small and large instances generated in this work, and also for instances available in the literature. The performance of PS is compared with CPLEX solver, which solves the original problem formulation. The developed meta-heuristics are compared to each other and are also compared with some heuristics from the literature. The computational experiments show that the proposed methods are efficient, competitive and fast.