Despacho online para o problema dinâmico de roteamento de veículos

Abstract

The allocation of vehicles for a specific customers demand is subject to a combinatorial explosion of possibilities by the exponential increase of alternatives according to growth of the problem size. When environmental changes are considered, such as the advent of new customers, the Vehicle Routing Problem becomes dynamic and even more complex and unpredictable. It is common to find, in the literature of the Dynamic VRP (DVRP), works that use a periodic approach to the vehicles dispatch. This treatment way divides the day at well-defined intervals and handles many static problems over time. As its main contribution, this work proposes the use of online dispatches to treat DVRPs. In this approach, the customers are quickly informed when they will be attended. This work shows that the online dispatch may have a greater impact on costs compared to the periodic dispatch. In addition of online dispatch contribution, this work presents two hybrid heuristics to solve the static Vehicle Routing Problem with Time Windows (VRPTW). Both heuristics explore the set partitioning formulation for the VRPTW. The first hybrid algorithm is specially proposed to attend dynamic contexts of the VRPTW, where new solutions must be quickly found. The second hybrid algorithm is more robust, it achieves best results and it is indicated for static contexts. Computational results show that the proposed heuristics are competitive in comparison with other algorithms of literature considering the well-known Solomons database. This work has found eight new best solutions considering the total distance minimization for VRPTW. Moreover, the second algorithm has obtained results better or equal to 82.1% of the best-known results from Solomons instances.