Formulações e abordagens lagrangeanas para problemas de subrotas : aplicações ao caixeiro viajante com coleta de prêmios e ao dimensionamento e seqüenciamento de lotes

Abstract

This paper deals with the Traveling Salesman Problem with Prize Collection – PCTSP, asymmetric version. It consists of finding a minimum cost route that starts at the root node r, visits each node i at most once, and collects a prize associated with each node. The goal of this work is to propose new formulations and a hybrid algorithm for solving PCTSP and related problems. Among the related problems, the Lot Sizing with Sequencing Problem – LSSP – was chosen. This problem, like PCTSP, belongs to a group of Combinatorial Optimization problems known as Subroutine Problems – StP. Problems in this group are characterized by two types of decisions: in the selection of which items will be active in the solution (scheduling); and their respective sequencing (routing). Like StP, LSSP consists in determining the production lot size for each product (scheduling), as well as the sequence in which the products will be produced (routing), subject to demand and capacity constraints. Notice that for each period t of the planning horizon a PCTSP arises, that is, fixed t, the LSSP consists in selecting the subset of items that will be produced, as well as, the production order. Note that the items that will be produced can be interpreted as the vertices that will be visited. Therefore, the PCTSP arises within the LSSP from the division of the planning horizon into a finite set of periods. In this way, the LSSP can be seen as a PCTSP with complicants. Because a PCTSP arises for each period, and, due to the machine state conservation constraint (carryover), the solution of period t depends on the previous period t − 1. To solve the problems, initially, the main formulations for each problem are taken from the literature. Next, new formulations for the problems are presented. A new formulation proposed in this paper proves to be the strongest by dominating the others considered. However, its use to solve the problems up to optimality is restricted due to its dimensions. In this case, a hybrid algorithm based on the Lagrangean relaxation resulting from this tight formulation is proposed. This algorithm combines heuristic techniques, such as a local search procedure, with cutting plans implemented according to a relax-and-cut scheme. These procedures are embedded within the Volume Algorithm. Which is used to solve the dual Lagrangean problem. It was able to bound the optimal solution value of these large instances in small optimality intervals with moderate computational time. Also, the algorithm is efficient in obtaining feasible solutions in a reasonable amount of time. It especially stands out for the most difficult instances where the exact method was not even able to find feasible solutions.