Algoritmo para o problema de roteamento dinâmico de veículos com janelas de tempo e tempos de viagem variáveis

Abstract

It is well-know that the final cost of commercial products is mostly due to expenses with their transport. In this context, appears the vehicle routing problem that aims to optimize the routes of a fleet which is responsible of providing pick-up and delivery services. In face of the necessity in attending requests that come during the fleet's operation time, appears the dynamic vehicle routing problem. This dissertation brings an approach to obtain good quality solutions to the time-dependent dynamic time-window vehicle routing problem. A framework was proposed based on column generation heuristic that uses a evolutionary algorithm aiming to generate a solution set to the problem. Moreover, the evolutionary algorithm generates a set of columns, or a set of routes that attends the problem's constraints, for a set partitioning problem formulation. The optimal solution for the set partitioning problem is a good solution for the vehicle routing problem. Three dynamic policies were presented to determinate the moment at which the new requests are sent to the dynamic evolutionary algorithm.The Online policy sends the request as soon as they are generated. The Size Demand policy stores the new requests in a buffer and sends them forward to the dynamic evolutionary algorithm only when the buffer is full. While the Periodic policy waits a fixed period of time before forwarding a new requests to the dynamic evolutionary algorithm. The framework was tested with the classic instances proposed by Solomon(1987). It was reported tests using the three policies presented and the results were analyzed by statistics.