Search

Oreintadores: Luiz Manoel Aguilera, Paulo Morelato França Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Resumo: O Problema de Roteamento de Veículos (PRV) procura estabelecer uma eficiente distribuição de bens de forma a atender as demandas existentes. Os atuais avanços em tecnologia de informação como rádio transmissores, telefonia celular, sistemas de localização via satélite, estão alterando o cenário em que um PRV pode ocorrer permitindo, por exemplo, a atualização de dados e localização de veículos em tempo real. Um PRV será considerado dinâmico caso seus dados não sejam conhecidos pelo usuário a priori e atualizados simultaneamente a determinação ou execução do conjunto de rotas. Um Problema de Roteamento Dinâmico de Veículos (PRDV) será estabelecido e um método de resolução, chamado algoritmo MORSS, será adaptado para resolver instâncias deste PRDV. Em seguida, um Problema Dinâmico de Programação (PDP) também será estabelecido e o algoritmo MORSS adaptado para resolver instâncias deste PDP. Um segundo método, baseado em heurísticas de busca em vizinhança e inserção, também será proposto para resolver as instâncias do PDP. O trabalho se propõe a resolver dois diferentes tipos de problemas dinâmicos procurando avaliar a adaptabilidade e desempenho do algoritmo MORSS enquanto método de resolução. No caso do PDP, o desempenho de um segundo método também é analisado e comparado ao desempenho obtido pelo algoritmo MORSS Abstract: The Vehicle Routing Problem (VRP) is the efficient distribution of products in order to attend customer requirement. Recently, the advances in information technology as radio transmission, cellular telephone, localization systems by satellite, are altering the scenarios in that VRP occurs and allowing update of information and vehicle localization occur in real time. The VRP is dynamic if the inputs of the problem are known by the decision-maker and are updated concurrentlY with the deterrnination or execution of the route's set. A Dynamic Vehicle Routing Problem (DVRP) will be established and a solution's method, called MORSS algorithm, will be adapted to solve DVRP instances. Next, a Dynamic Scheduling Problem (DSP) will be established and the MORSS algorithm will be adapted to solve DSP instances. A second method, based in heuristics of neighborhood search and insertion, will be also proposed to solve DSP instances. This work proposes to solve two different dynamic problems searching to evaluate the MORSS algorithm adaptability and performance as resolution method. In the PDP, the performance of the second method proposed also will be analyzed and compared with the performance obtained by MORSS algorithm Mestrado Mestre em Engenharia Elétrica