Modelo de otimização e simulação para o problema de roteamento de veículos com janelas de tempo e incerteza nos tempos de viagem

Abstract

The Vehicle Routing Problem with Time Windows (VRP-TW) is a combinatorial optimization problem with many applications in logistics areas. Its goal is to determine routes for the available vehicles to attend the demands of a set of customers during their available times with minimum cost. Traditional models use fixed service and travel times, which may lead to bad or even impractical solutions in real world-problems, where there is uncertainty. In this work, metaheuristics ILS+VND are initially used to solve the VRP-TW in the traditional way, with the only objective of minimizing cost. Then, the travel and attendance times are replaced by probability density functions and Monte Carlo simulations are used to evaluate the risk of not respecting customers’ availability. Experiments show the level of uncertainty effect depends on instance characteristics. A multiobjective optimization model to minimize cost and risk simultaneously is proposed once the uncertainty effect is identified. An approach combining optimization and simulation is adopted, where the cost is calculated deterministically and Monte Carlo simulations are used to estimate the risk. Three NSGA-II variations are proposed to solve the problem and three performance metrics are applied to the estimated Pareto fronts to measure the solution quality obtained by each algorithm. The results show the solutions found have a nice trade-off between cost and risk.