Formulations and valid inequalities for the Hamiltonian p-median problem

Autor: Rodrigues, Davi, 1992
Přispěvatelé: Usberti, Fábio Luiz, 1982, Cavellucci, Celso, 1951, Hokama, Pedro Henrique Del Bianco, Xavier, Eduardo Candido, Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação, UNIVERSIDADE ESTADUAL DE CAMPINAS
Jazyk: portugalština
Rok vydání: 2022
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da Universidade Estadual de Campinas (UNICAMP)
Universidade Estadual de Campinas (UNICAMP)
instacron:UNICAMP
Popis: Orientadores: Fábio Luiz Usberti, Celso Cavellucci Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O problema do caixeiro viajante (travelling salesman problem - TSP) tem por objetivo encontrar um ciclo Hamiltoniano de custo mínimo em um grafo não direcionado completo G = (V,E). Uma generalização do TSP é o problema das p-medianas Hamiltonianas, cujo objetivo é encontrar p ciclos disjuntos de custo mínimo que visitam todos os vértices em G. Este trabalho propõe novas formulações, desigualdades válidas e metodologias de so- lução exata para o problema das p-medianas Hamiltonianas. Métodos heurísticos e meta- heurísticos também são explorados em alternativa aos métodos exatos. Experimentos computacionais avaliam o desempenho dos métodos propostos para um conjunto de ins- tâncias da literatura. Uma variação do TSP, o problema do caixeiro viajante com cobertura (Covering Sa- lesman Problem - CSP), visa obter um ciclo de custo mínimo que cobre todos os nós do grafo G, onde a cada vértice v é associado um conjunto de vértices que cobrem v. Este trabalho também apresenta uma generalização do CSP, o problema das p-medianas Ha- miltonianas com cobertura (Covering Hamiltonian p-Medians Problem - CHpMP), cujo objetivo é encontrar em G um subgrafo de custo mínimo composto por p ciclos Hamiltoni- anos disjuntos que cubram todos os nós de G. Uma formulação para este novo problema é apresentada, assim como ensaios computacionais para avaliar a solução exata do CHpMP Abstract: The travelling salesman problem (TSP) has the objective to find a minimum cost Hamil- tonian cycle in a complete undirected graph G = (V, E). A generalization of the TSP is the Hamiltonian p-median problem, whose objective is to find p minimum cost disjoint cycles that visit all vertices in G. This work proposes new formulations, valid inequalities and exact solution method- ologies for the Hamiltonian p-median problem. Heuristic and meta-heuristic methods are also explored as an alternative to exact methods. Computational experiments evaluate the performance of the proposed methods on a benchmark of instances from literature. A variation of the TSP, the Covering Salesman Problem (CSP), searches for the min- imum cost cycle that covers all nodes of the graph G, where each vertex v is associated with a set of nodes that cover v. This work also presents a generalization of the CSP, the Covering Hamiltonian p-Medians Problem (CHpMP), whose objective is to find in G a subgraph of minimum cost composed of disjoint p Hamilton cycles that cover all the G nodes. A formulation for this new problem is presented, as well as computational tests to evaluate the exact solution of CHpMP Mestrado Ciência da Computação Mestre em Ciência da Computação
Databáze: OpenAIRE
Externí odkaz: