Um algoritmo híbrido para os problemas de roteamento de veículos estático e dinâmico com janela de tempo

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. The objective of the problem is to plan routes for vehicles, with no violated constraints, minimizing costs. The costs normally are related to the total travel distance, the number of vehicle or routes utilized, the total wait time in the customers or combination of theses. The DVRPTW is the dynamic generalization of the VRPTW, where part of the informationis only known after the initial of the optimization process. Exact methods have normally proposed for the static version of the VRPTW. Results from this type of approach have been improved exploring parallel implementations and modern branch-and-cut techniques. However, 23 out of the 56 high order instances from Solomons test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many efficient heuristic methods have been developed to make possible a good solution in a reasonable amount of time. Using travel distance as themain objective, in this thesis, a robust heuristic approach for the VRPTW using an efficient genetic algorithm and a set partitioning formulation is proposed. The tests were run using both, real numbers and truncated data type, making it possible to compare the results with previous heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previous known heuristic methods in the literature, in terms of the minimal travel distance. However, a great number of heuristics has used the number of vehicles as the first objective and travel distance as the second, subject to the first. An additional phase is proposed to minimize the number of vehicles. Initially, a hierarchical tournament selection genetic algorithm is applied. It can reach all best results in number of vehicles of the 56 Solomons problems explored in the literature. After then, the two phase approach, the genetic and the set partitioning, is applied to minimize the travel distance as the second objective. Finally, the proposed framework is applied a dynamic version of the problem. Using part of customers being inserted or canceled after the initial of the optimization process, the instances of Solomon are modified, making it possible to consider many degrees of dynamism. The fact of the desired results of the dynamic version of the proposed instances are the same of the static version, has make possible to evaluate the quality of the results from the proposed heurist for the DVRPTW.