Abordagens determinística e estocástica para o problema de roteirização de veículos na entrega de refeições

Abstract

Resumo: O problema de roteamento de veículos (PRV) é um dos mais estudados nas áreas de logística e otimização combinatória e consiste em determinar rotas de custo mínimo para uma frota de veículos, atendendo à demanda de um conjunto de clientes. Devido à complexidade computacional dos problemas de roteamento, torna-se inviável resolvê-los de forma exata, e em virtude disso, na maioria das vezes, a solução é obtida através de heurísticas. Mesmo sendo amplamente estudado o PRV carece de implementações práticas e nem sempre as soluções disponíveis resolvem satisfatoriamente os problemas das empresas, daí a necessidade de buscar soluções customizadas para cada problema. Dessa forma, o objetivo desse trabalho é desenvolver uma ferramenta que auxilie no processo de elaboração de roteiros de entrega de refeições feitas pela ASSEMCO - Associação dos Servidores Municipais de Colombo, localizada na região metropolitana de Curitiba, Paraná. A configuração atual dos roteiros de entrega não contempla todas as particularidades do problema, pois os clientes atendidos pela ASSEMCO possuem demanda variável e alguns destes precisam ser atendidos em horário fixo. Para resolução desse problema este trabalho apresenta duas abordagens: um programa computacional para o planejamento de rotasde entrega e um modelo estocástico que descreve o problema. Na abordagem determinística foi desenvolvido um programa em Visual Basic 6.0 que gera os roteiros de entrega através de métodos heurísticos de agrupamento e roteirização. Na odelagem estocástica do problema foram considerados a probabilidade de presença dos clientes, a probabilidade do veículo fazer o trajeto e o tempo de viagem entre os clientes, baseado na probabilidade de presença destes. Este modelo foi resolvido através do software Lingo 9.0 e através da meta-heurística Ant Colony System. Em relação à abordagem determinística, observou-se que os roteiros obtidos com a utilização do programa mostraram-se melhores em comparação com os roteiros normalmente praticados pela empresa. Em relação à abordagem estocástica, observou-seque o modelo proposto se adequou ao problema. Além disso, a meta-heurística Ant Colony System implementada para a resolução do modelo mostrou-se eficiente, visto que apresentou soluções de boa qualidade em tempo computacional viável.

Abstract: The vehicle routing problem (VRP) is one of the most studied in logistics and combinatorial optimization and it consists in determining minimum cost routes for a fleet of vehicles, in order to serve the demand of a set of customers. Due to the computational complexity of routing problems, it becomes impossible to solve them optimally, so in most cases, th solution is achieved by heuristics implementation. Even widely studied, PRV lacks practical implementation and not always available solutions solve satisfactorily companies problems, hence the necessity of seeking customized solutions for each problem. Thus, the purpose of this research is to assist in the meal delivery routes process made by ASSEMCO - Colombo Municipal Servers Association, great Curitiba, in Paraná. The current configuration of delivery routes does not include all the details of the problem because the customers served by ASSEMCO have variable demand and some of them need to be attendend at fixed times. To solve this problem this research presents two approaches: a software for planning delivery routes and a stochastic model that describes the problem. In a deterministic approach, it was developed a program in Visual Basic 6.0 that generates the delivery route through heuristic methods for clustering and routing. In the stochastic modeling, based on customers presence probability, vehicle probability traversing the path, and the travel time between customers were considered. This model was solved by Lingo 9.0 software and through the meta-heuristic Ant Colony System. Concerning deterministic approach, it was observed that obtained routes by the program proved to be better compared to the route normally adopted by the company. Concerning stochastic approach, it was observed that the proposed model is suitable to the problem. n addition, the metaheuristic Ant Colony System implemented for solving the model proved to be useful, because it produced good quality solutions in reasonable computational time.