Resumo: A ampla categoria de Problemas de Roteamento de Veículos (VRPs) originou-se do VRP Capacitado (CVRP) proposto no fim dos anos 1950, que consiste em encontrar a maneira mais econômica de servir a um conjunto de clientes com uma frota de veículos de uma dada capacidade. Nesta tese, são abordados problemas de otimização combinatória em dois grupos de VRPs: um considerando consumo de energia e outro que considera backhauls. Além de sua relação com custos de transporte, o interesse no consumo de energia em roteamento de veículos está crescendo nas últimas décadas devido ao seu potencial de mitigar impactos ambientais. Enquanto custos no CVRP são mensurados em termos de distância, o VRP Cumulativo (CmVRP) é uma variante que objetiva minimizar uma medida simplificada de consumo de energia dependente de carga. Combinando os conceitos de duas formulações pré-existentes, este trabalho propõe uma nova formulação de programação linear inteira para o CmVRP, cuja relaxação de programação linear (LP) é mais forte que ambas as relaxações de LP das originais. Além disso, visando resolver a versão inteira do problema, é empregado um algoritmo branch-cut-and-price (BCP) baseado em uma formulação da literatura a fim de apresentar resultados em estado-da-arte para o CmVRP. Adicionalmente, um pequeno resultado de aproximação sobre o problema é apresentado. Também lidando com um outro aspecto do consumo de energia, este trabalho propõe variantes do CVRP e CmVRP que consideram limites de energia dependente de carga por veículo, o que pode restringir o alcance de cada veículo sem reabastecer ou recarregar energia. Para estes problemas, este trabalho propõe formulações mestre baseadas em partição de conjunto e subproblemas de pricing correspondentes, onde uma das formulações e os subproblemas fazem uso de cargas discretizadas por arco. Deste modo, esta tese apresenta abordagens BCP baseadas nestes componentes. No melhor do nosso conhecimento, esta é a primeira vez que um consumo de energia dependente de carga dos veículos é limitado por meio do subproblema de pricing. São mostrados vastos resultados computacionais comparando o CVRP, CmVRP e suas variantes com energia limitada. Por fim, este trabalho aborda a variante do CVRP denominada VRP com Backhauls Seletivos, no qual, depois de visitar clientes, cada veículo pode visitar um único backhaul para coletar um valor de receita. Nesta abordagem, considera-se que as receitas são incertas. Para lidar com esta incerteza, um modelo de otimização robusta, para este problema, é elaborado e analisado. São resolvidos os modelos determinístico e robusto por um algoritmo branch-and-cut e são apresentados resultados computacionais comparando-os com uma abordagem heurística Ver menos

Abstract: The large category of Vehicle Routing Problems (VRPs) was originated from the Capacitated VRP (CVRP) proposed in the end of 1950s, which consists in finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. In this thesis, we approach combinatorial optimization problems in two groups of VRPs: one considering energy consumption and other that considers backhauls. Besides its relation to transportation costs, the interest in the energy consumption of vehicle routing is rising in the last decades due to its potential of mitigating environmental impacts. While costs in the CVRP are measured in terms of distance, the Cumulative VRP (CmVRP) is a variant that aims to minimize a simplified measure of a load-dependent energy consumption. Combining the concepts of two previous formulations, we propose a new integer linear programming formulation for the CmVRP, whose linear programming (LP) relaxation is stronger than both LP relaxations of the original ones. Furthermore, aiming at solving the integer version of the problem, we employ a branch-cut-and-price (BCP) algorithm based on a formulation from the literature to present state-of-the-art results for the CmVRP. Additionally, a small approximation result on the problem is presented. Also dealing with another aspect of energy consumption, we propose CVRP and CmVRP variants that consider load-dependent energy limits per vehicle, which might restricts each vehicle range without replenishing. To these problems, we propose master formulations based on set-partitioning and correspondent pricing subproblems, where one of the formulations and the subproblems rely on discretized loads per arc. Thereby we devise BCP approaches based on these components. To the best of our knowledge, this is the first time a load-dependent energy consumption of the vehicles is limited by the means of the pricing subproblem. We show extensive computational results comparing the CVRP, CmVRP, and their variants with limited energy. Finally, we tackle the CVRP variant called VRP with Selective Backhauls, in which, after visiting customers, each vehicle may visit a single backhaul to collect an amount of revenue. In this approach, we consider that the revenues are uncertain. To deal with this uncertainty, a robust optimization model for this problem was devised and analyzed. We solve the deterministic and robust models by a branch-and-cut algorithm and present computational results comparing them with a heuristic approach Ver menos