Formulações e algoritmos em programação inteira para o problema do caixeiro viajante com coleta e entrega sobre carregamento lifo

Abstract

This dissertation addresses the Pickup and Delivery Travelling Salesman Problem withMultiple Stacks and algorithmic approaches to obtain its exact solution. In this problem,a single vehicle must serve a set of customer requests defined by a pair of pickup anddelivery destinations of an item. The vehicle contains a fixed number of stacks whereeach request is loaded at a pickup location and unloaded at the corresponding deliverylocation. Each stack has finite capacity, and its loading/unloading sequence must followthe last-in-first-out policy, i.e. for each stack, just the last item loaded can be unloaded atits corresponding delivery location.We propose a new integer programming formulation for this problem with a polyhedralrepresentation described by exponentially-many inequalities. In particular, we introducea new set of variables used to model the last-in-first-out policy for loading andunloading items. With the inclusion of these new variables, finding violations concerningthe capacity of each stack or the LIFO policy for a given tour can be done by solvingpolynomial problems. These ideas are used within a branch-and-cut algorithm to solvethe proposed formulation.Computational results show that our approach is competitive with the best algorithmin the literature, outperforming it for some benchmark instances. Also, two newcertificates of optimality are provided.