Otimização robusta e programação estocástica para o problema de roteamento de veículos com múltiplos entregadores: formulações e métodos exatos

Abstract

In this thesis, we study the vehicle routing problem with time windows and multiple deliverymen with uncertainty. In addition to routing and scheduling decisions, this problem involves deliverymen allocation decisions on each route to reduce costs and service times. Parameters such as customer demands, travel and service times are considered uncertain. Thus, we propose new models of static robust optimization, which incorporate measures to effectively deal with the cost-risk trade-off, and new models of two stage stochastic programming with recourse to address this problem. Usually, when applying the concepts of robust optimization and stochastic programming, the number of decision variables and constraints grow significantly in terms of instance size. Consequently, the larger the instances, the greater is the computational effort required to solve the resulting models with general purpose solvers. However, computational effort can be significantly reduced if appropriate exact methods are developed that take advantage of the resulting robust and stochastic models’ structure. For this reason, we propose exact methods based on branch-and-cut and branch-price-and-cut, which are effective to solve literature instances. Numerical experiments based on these instances and risk analysis based on Monte Carlo simulation indicate the potential of static robust optimization to address the trade-off between cost and risk. These experiments also reveal that this approach provides good results, even without complete knowledge of some probabilistic measure of the uncertain parameters. Regarding stochastic programming, the numerical experiments show that it is possible to save important resources by solving the two stage stochastic programming model with recourse rather than adopting simpler strategies based on the expected value. To the best of our knowledge, there is no studies in the literature that have addressed the problem under study in this thesis, with uncertainty in demands, as well as in travel and service times. We believe that developing models and effective solution methods to address the vehicle routing problem with time windows and multiple deliverymen are original and relevant contributions to the state-of-the-art literature, opening up new fields for future research not only for the problem under study, but also for other variants of vehicle routing problem.