Uma nova formulação e um algoritmo branch-and-cut para o problema da cobertura máxima P-Hub com alocação simples e critérios de cobertura binária e parcial

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorRoboredo, Marcos Costa-
Autor(es): dc.contributorPessoa, Artur Alves-
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorVelasco, André Soares-
Autor(es): dc.creatorÁvila, Patrick Douglas Doglio Nunes de-
Data de aceite: dc.date.accessioned2024-07-11T18:46:03Z-
Data de disponibilização: dc.date.available2024-07-11T18:46:03Z-
Data de envio: dc.date.issued2024-07-08-
Data de envio: dc.date.issued2024-07-08-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/33083-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/777143-
Descrição: dc.descriptionNo Problema da Cobertura Máxima p-Hub com Alocação Simples (AS-PCMpH), duas decisões são tomadas: a localização de p hubs e a atribuição de cada ponto não hub a exatamente um hub localizado. Essas decisões geram um custo de serviço para cada par origem-destino (O/D) da rede. O problema considera uma função não-decrescente que associa cada par O/D com um grau de cobertura l 2 L de acordo com o seu custo de serviço, onde L é o conjunto discreto com valores entre 0 e 1. Quando L = f0; 1g, o critério de cobertura adotado é binário. Caso contrário, o critério de cobertura adotado é parcial. O AS-PCMpH visa maximizar a soma dos fluxos de cada par O/D ponderado pelo seu grau de cobertura. Neste trabalho são apresentadas uma nova formulação e um conjunto de desigualdades válidas para o AS-PCMpH que são válidas para os dois critérios de cobertura. É proposto que as desigualdades sejam geradas sob demanda, seguindo a clássica abordagem de branch-and-cut. De modo a provar a robustez do método proposto, são apresentados diversos experimentos computacionais, e eles mostram que o método proposto supera a melhor formulação exata da literatura, sendo capaz de obter a solução ótima de instâncias grandes pela primeira vez-
Descrição: dc.descriptionIn the Single Allocation p-Hub Maximal Covering Problem (SApHMCP), two decisions are taken: the location of p hubs and the assignment of each non-hub point to exactly one placed hub. Those decisions generate a service cost for each origin-destination (O/D) pair from the network. The problem considers a non-increasing function that associates each O/D pair with a degree of coverage l 2 L according to its service cost, where L is a discrete set with values between 0 and 1. When L = f0; 1g, the coverage criterion adopted is binary. Otherwise, the coverage criterion adopted is partial. The SApHMCP aims to maximize the sum of each O/D pair flow weighted by its degree of coverage. In this work, a new formulation and a set of valid inequalities for the SApHMCP that are valid to both coverage criteria are presented. It is proposed that the inequalities are generated on demand, following a classical branch-andcut approach. In order to prove the robustness of the proposed method, several computational experiments are presented, and they show that the proposed method outperforms the best exact formulation found in the literature, being able to optimally solve several large instances for the first time-
Descrição: dc.description75 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectLocalização de hubs-
Palavras-chave: dc.subjectCobertura máxima-
Palavras-chave: dc.subjectPesquisa operacional-
Palavras-chave: dc.subjectLogística-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectInteger programming-
Palavras-chave: dc.subjectHub location-
Palavras-chave: dc.subjectMaximal covering-
Título: dc.titleUma nova formulação e um algoritmo branch-and-cut para o problema da cobertura máxima P-Hub com alocação simples e critérios de cobertura binária e parcial-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.