Problemas de roteamento com custos de carga

Abstract

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.