Formulations and lagrangean approaches for subtour problems : applications to the prize collecting traveling salesman and to lot sizing and sequencing

Autor: Guido Pantuza Júnior
Přispěvatelé: Maurício Cardoso de Souza, Franklina Maria Bragion de Toledo, Reinaldo Morabito Neto, Alexandre Salles da Cunha
Jazyk: portugalština
Rok vydání: 2022
Předmět:
Zdroj: Repositório Institucional da UFMG
Universidade Federal de Minas Gerais (UFMG)
instacron:UFMG
Popis: Este trabalho trata do Problema do Caixeiro Viajante com Coleta de Prêmios – PCTSP, versão assimétrica. Ele consiste em encontrar uma rota de custo mínimo, que inicie no vértice raiz r, e visite cada vértice i, no máximo, uma única vez e colete um prêmio associado a cada vértice. O objetivo deste trabalho é propor novas formulações e um algoritmo híbrido para a resolução do PCTSP e problemas correlatos. Entre os problemas correlatos, escolheu-se o Problema de Dimensionamento de Lotes com Sequenciamento – LSSP. Este problema, assim como o PCTSP, pertence a um grupo de problemas de Otimização Combinatória conhecido como Problemas de Sub-Rotas – StP. Os problemas deste grupo são caracterizados por dois tipos de decisão: na seleção de quais itens estarão ativos na solução (programação); e seu respectivo sequenciamento (roteamento). Assim como os StP, o LSSP consiste em determinar o tamanho do lote de produção de cada produto (programação), bem como a sequência na qual os produtos serão produzidos (roteamento), sujeito às restrições de demanda e capacidade produtiva. Repare que para cada período t do horizonte de planejamento surge um PCTSP, ou seja, fixado t, o LSSP consiste em selecionar o subconjunto de itens que será produzido, bem como, a ordem de produção. Note que os itens que serão produzidos podem ser interpretados como os vértices que serão visitados. Logo, o PCTSP surge dentro do LSSP a partir da divisão do horizonte de planejamento em um conjunto finito de períodos. Dessa forma, o LSSP pode ser visto como um PCTSP com complicantes. Pois surge um PCTSP para cada período, e, devido à restrição de conservação do estado da máquina (carryover), a solução do período t depende do período anterior t − 1. Para resolver os problemas, inicialmente, são retiradas da literatura as principais formulações para cada problema. Em seguida, são apresentadas novas formulações para os problemas. Uma nova formulação proposta neste trabalho mostra-se a mais forte ao dominar as demais consideradas. Entretanto, seu uso para resolver os problemas até a otimalidade é restrito devido às suas dimensões. Neste caso, propõe-se um algoritmo híbrido baseado na relaxação Lagrangeana resultante desta formulção forte. Este algoritmo combina técnicas heurísticas, como um procedimento de busca local, com planos de corte implementados de acordo com um esquema relax-and-cut. Estes procedimentos são embutidos dentro do Algoritmo Volume. O qual é utilizado para resolver o problema dual Lagrangeano. Os resultados demonstram que a abordagem proposta é eficiente para o PCTSP e o LSSP. Ele foi capaz de limitar o valor da solução ótima dessas grandes instâncias em pequenos intervalos de otimalidade, com um tempo computacional moderado. Ainda, o algoritmo é eficiente para obter soluções viáveis em um tempo razoável. Ele destaca-se, especialmente, para as instâncias mais difíceis nas quais o método exato não foi sequer capaz de encontrar soluções viáveis. 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.
Databáze: OpenAIRE
Externí odkaz: