Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/95406
DC FieldValueLanguage
dc.contributor.advisorPascoal, Marta Margarida Braz-
dc.contributor.authorDehkharghani, Ali Moghanni-
dc.date.accessioned2021-07-14T11:32:21Z-
dc.date.available2021-07-14T11:32:21Z-
dc.date.issued2021-05-17-
dc.date.submitted2020-12-28-
dc.identifier.urihttps://hdl.handle.net/10316/95406-
dc.descriptionTese no âmbito do Programa Interuniversitário de Doutoramento em Matemática, apresentada ao Departamento de Matemática da Faculdade de Ciências e Tecnologia da Universidade de Coimbra.pt
dc.description.abstractIn the present work, the problem of determining sets of K dissimilar paths between a pair of nodes in a given graph is studied. The concept of path dissimilarity, not being uniform, aims to translate some diversity in the solution sought, which generally relates what the paths of this solution have in common and how they differ. The characteristics of the dissimilarity functions make it difficult to use them as objective functions for combinatorial optimization problems, which was the motivation for looking for alternative ways of representing this concept. In the first part of the thesis, integer linear optimization formulations are introduced that model the dissimilarity of a set of paths based on three assumptions: the minimization of the number of overlapping arcs between the pairs of paths in the set; the minimization of the number of overlapping arcs, and the minimization of the number of repetitions of the overlapping arcs. Additionally, the last two types of formulations are combined with capacity constraints, dependent on an upper-bound obtained by means of an auxiliary problem, which have the double role of limiting the number of uses of the solution arcs and promoting diversification in the event of ties. The suitability of each formulation for solving the original problem, as well as its limitations, is assessed. In the second part of the thesis, it is assumed that each arc is associated with a given real value and that it is intended to simultaneously minimize two conflicting objective functions: the dissimilarity of K paths and a linear function of its arc values. The extension of some of the previous formulations to the mono-objective case is investigated and an ϵ-constraint type method for the calculation of the Pareto frontier of the bi-objective problem is presented, following two strategies: one in which the ϵ parameter is updated in a decreasing way and another in which the same parameter increases, and which allows to explore the relationship between the sequence of sub-problems that has to be solved.pt
dc.description.abstractRESUMO: No presente trabalho estuda-se o problema da determinação de conjuntos de K caminhos dissimilares entre um par de nós de um grafo dado. O conceito de dissimilaridade de caminhos, não sendo uniforme, pretende traduzir alguma diversidade na solução procurada, que geralmente relaciona o que os caminhos dessa solução têm de comum e de diferente. As características de funções de dissimilaridade dificultam a sua utilização como funções objetivo de problemas de otimização combinatória, o que serviu de motivação para a procura de formas alternativas de representar este conceito. Na primeira parte da tese introduzem-se formulações de otimização linear inteira que modelam a dissimilaridade de um conjunto de caminhos com base em três pressupostos: a minimização da sobreposição de arcos entre os pares de caminhos do conjunto; a minimização do número de arcos que se sobrepõem e a minimização do número de repetições dos arcos sobrepostos. Os dois últimos tipos de formulações são combinados com restrições de capacidade, dependentes de um majorante obtido através de um problema auxiliar, que têm a dupla função de limitar o número de utilizações dos arcos da solução e promover a diversificação em caso de empates. Para cada formulação é estudada a adequação à resolução do problema original, assim como as suas limitações. Na segunda parte da tese supõe-se que cada arco está associado a um valor real dado e que se pretende minimizar simultaneamente duas funções objetivo conflituosas: a dissimilaridade de K caminhos e uma função linear dos valores dos seus arcos. Investiga-se a extensão de algumas das formulações anteriores para o caso mono-objetivo e apresenta-se um método do tipo ϵ-restrito para o cálculo da fronteira de Pareto do problema bi-objetivo em causa, seguindo duas estratégias: uma em que o parâmetro ϵ é atualizado de forma decrescente e outra em que o mesmo parâmetro aumenta, e que permite explorar a relação entre a sequência de sub-problemas que tem de ser resolvida.pt
dc.language.isoengpt
dc.relationMobiWise: From mobile sensing to mobility advising (P2020 SAICTPAC/0011/2015) projectpt
dc.rightsembargoedAccesspt
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/pt
dc.subjectK alternative pathspt
dc.subjectDissimilaritypt
dc.subjectInteger linear optimization formulationspt
dc.subjectBiobjective optimizationpt
dc.subjectK caminhos alternativospt
dc.subjectFormulações de otimização linearinteirapt
dc.subjectDissimilaridadept
dc.subjectOtimização bi-objetivopt
dc.titleFinding dissimilar paths: formulations and variantspt
dc.typedoctoralThesispt
degois.publication.locationUniversidade de Coimbrapt
dc.peerreviewedyes-
dc.date.embargo2023-05-17*
dc.identifier.tid101654740pt
dc.subject.fosMathematicspt
dc.subject.fosApplied mathematicspt
thesis.degree.disciplineID03003231-
thesis.degree.grantor00500::Universidade de Coimbrapt
thesis.degree.leveldoutor-
thesis.degree.nameDoutoramento em Matemáticapt
thesis.degree.grantorUnit00501::Universidade de Coimbra - Faculdade de Ciências e Tecnologiapor
uc.date.periodoembargo730por
uc.rechabilitacaoestrangeiranopt
uc.date.periodoEmbargo730pt
item.openairetypedoctoralThesis-
item.languageiso639-1en-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.cerifentitytypePublications-
item.grantfulltextopen-
item.fulltextCom Texto completo-
crisitem.advisor.deptFaculty of Sciences and Technology-
crisitem.advisor.parentdeptUniversity of Coimbra-
crisitem.advisor.researchunitCMUC - Centre for Mathematics of the University of Coimbra-
crisitem.advisor.orcid0000-0003-0517-677X-
Appears in Collections:UC - Teses de Doutoramento
FCTUC Matemática - Teses de Doutoramento
Files in This Item:
File Description SizeFormat
Thesis_Revised_Ali_Moghanni.pdf1.51 MBAdobe PDFView/Open
Show simple item record

Page view(s)

122
checked on Mar 26, 2024

Download(s)

21
checked on Mar 26, 2024

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons