Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/46642
Title in Portuguese: Mathematical programming approaches for NP-Hard constrained shortest path problems
Title: Mathematical programming approaches for NP-Hard constrained shortest path problems
Author: Saraiva, Rommel Dias
Advisor(s): Andrade, Rafael Castro de
Keywords: Combinatorial optimization
Shortest path with negative cycles
Constrained shortest path tour problem
Integer linear programming
Lagrangian relaxation
Heuristics
Issue Date: 2019
Citation: SARAIVA, Rommel Dias. Mathematical programming approaches for NP-Hard constrained shortest path problems. 2019. 74 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2019.
Abstract in Portuguese: Neste trabalho, estudamos dois problemas de roteamento NP-Difíceis: o problema do caminho mínimo na presença de ciclos negativos (referenciado na literatura estrangeira de shortest path with negative cycles – SPNC) e o problema da trilha mínima com restrição de agrupamento (referenciado na literatura estrangeira como constrained shortest path tour problem – CSPTP). Para o SPNC, propomos três abordagens exatas baseadas em programação matemática: um modelo compacto de programação linear inteira mista, um algoritmo de branch-and-bound especializado e um método de planos de corte. Realizamos uma experimentação englobando tanto instâncias geradas aleatoriamente como também instâncias concebidas por outros autores. Os testes computacionais mostram que as abordagens propostas se sobressaem em relação às técnicas de programação matemática do estado da arte. Além disso, fazemos uma discussão sobre a relaxação linear dos modelos matemáticos presentes na literatura do problema. Com relação ao CSPTP, apresentamos dois modelos compactos para o problema: um de programação linear inteira pura, que chamamos de modelo baseado em vértices artificiais; e outro de programação linear inteira mista, que chamamos de modelo baseado em vértices fronteiras. Para este último, mostramos desigualdades válidas e propomos heurísticas Lagrangeanas determinísticas e não-determinísticas. Experimentos realizados em instâncias da literatura e em outras geradas aleatoriamente validam e atestam a eficácia das nossas contribuições, que alcançam a solução ótima em uma larga quantidade de casos. Mostramos que os modelos baseados em vértices artificais e fronteiras alternam bons resultados dependendo das características de cada instância. A eficiência das metodologias exatas propostas quando comparadas aos algoritmos de branch-and-bound especializados, presentes na literatura para o CSPTP, também é comprovada por meio dos testes computacionais, assim como as potencialidades das heurísticas Lagrangeanas, que alcançam a solução ótima para grande parte das instâncias abordadas.
Abstract: In this work, we study two NP-Hard routing problems: the shortest path with negative cycles (SPNC) and the constrained shortest path tour problem (CSPTP). For the SPNC, we propose three exact approaches based on mathematical programming: a compact mixed integer linear programming model, a specialized branch-and-bound algorithm, and a cutting-plane method. We perform numerical experiments comprising both randomly generated and benchmark instances from the literature. The computational tests show that the proposed approaches stand out from state-of-the-art mathematical programming techniques. Moreover, we discuss the linear relaxations of models present it the literature. Concerning the CSPTP, we show two compact models for the problem: a pure integer linear programming model, which we call dummy node-based model; and a mixed integer linear programming one, which we call frontier node-based model. For the latter, we show valid inequalities and propose deterministic and non-deterministic Lagrangian heuristics. Experiments performed on both randomly generated and benchmark instances from the literature validate and attest the effectiveness of our contributions, which achieve the optimal solution in the vast majority of cases. We show that the dummy node and the frontier node-based models alternate better results depending on the characteristics of each instance. The efficiency over specialized branch-and-bound algorithms from the literature is also proven through experiments, as well as the potentialities behind the Lagrangian heuristics, which find the optimal solution for a large number of instances.
URI: http://www.repositorio.ufc.br/handle/riufc/46642
metadata.dc.type: Tese
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2019_tese_rdsaraiva.pdf989,01 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.