Problemas de roteamento com custos de carga

O Problema do Caixeiro Viajante (PCV) e o Problema de Roteamento de Veículos (PRV), apesar da enorme gama de aplicações e do grande número de algoritmos desenvolvidos para resolvê-los, não possuem uma estrutura de custo que permita diferenciar produtos e/ou clientes mais importantes. Eles também não se preocupam com o tempo de espera dos consumidores que recebem as mercadorias e não asseguram um dado nível de qualidade de serviço para esses consumidores. Tanto o PCV quanto o PRV se preocupam apenas com o custo egoísta do operador logístico, que deseja retornar ao ponto de partida o mais cedo possível. Nesta tese são apresentados e resolvidos, de forma exata, quatro problemas, em que o custo da carga é relevante para o cálculo do custo total. Esse custo da carga está relacionado com a quantidade e com a qualidade dos produtos transportados, podendo também priorizar clientes mais importantes e/ou produtos perecíveis.Os problemas estudados neste trabalho são: Problema de Mínima Latência (PML); Problema de Um Veículo de Entrega (PUVE); Problema do Caixeiro Viajante Multiproduto (PCVM); e, Problema do Caixeiro Viajante Multiproduto Congestionado (PCVMC). Esses problemas têm como objetivo principal aliar os interesses, muitas vezes conflitantes, dos operadores logísticos que tendem a minimizar o seu próprio custo operacional, mas também precisam maximizar a satisfação dos seus clientes. Para todos os quatro problemas são apresentadas novas formulações matemáticas. Para o PML e para o PUVE, problemas existentes na literatura, são apresentados resultados exatos e resultados heurísticos melhores que os presentes na literatura. Para o PCVM são apresentados três versões de um algoritmo Cut-and-Branch baseado no método de Decomposição de Benders. Esse método se mostrou mais eficiente, em termos de tempo computacional, que o resolvedor CPLEX. Além disso, foi desenvolvido um algoritmo Lagrangeano que conseguiu resolver instâncias para as quais o CPLEX não consegue. Para o PCVMC, o problema mais geral, que engloba todos os anteriores e que usa uma função de custo não-linear, também foi desenvolvido um algoritmo baseado no Método de Particionamento de Benders que conseguiu resultados exatos de maneira eficiente.There are a lot of applications and a lot of algorithms for the Traveling Salesman Problem (TSP) and for the Vehicle Routing Problem (VRP). Despite of that, both problems do not have a cost structure that enables differ more important products and clients. Besides, the TSP and the VRP do not care about the waiting times of all the costumers that want to receive their products as soon as possible. Both, the TSP and the VRP, just care about the single selfish driver that wants to return as soon as possible to the depot. The objective of this work is to present, to model and to solve problems where a load cost is incurred, besides the time or distance. This load cost can represent the weight, the price of the load or even the priority of some clients. In this work four problems are presented where the load cost is important. The problems are The Minimum Latency Problem (MLP); The Single Vehicle Delivery Problem (SVDP); The Multicommodity Traveling Salesman Problem (MTSP) and The Congested Multicommodity Traveling Salesman Problem (CMTSP). All these problems deal with the logistic operator conflict between minimize its own operational costs and maximize the client satisfaction. For all these problems it is presented a new mathematical formulation. For the MLP and the SVDP, the exact and heuristics results are better than found in literature. For the MTSP, it is developed a Cut-and-Branch algorithm that is able to find optimal solutions faster than stand alone CPLEX codes. For instances that CPLEX cannot deal with (very large ones), a Lagrangean Relaxation was deployed to compute lower bounds. A version of the well known GRASP procedure is also provided to ensure the calculation of optimality gaps not attainable by CPLEX. For the CMTSP, the more general problem of this work, that uses a non-linear objective function, it is also developed a Generalized Benders Decomposition algorithm