Metrics
123 File views/ downloads
52 Record Views
Thesis
AN ANALYSIS OF THE SIMILARITY CONSTRAINED K-SHORTEST PATHS PROBLEM
University of West Florida
Master of Science (MS), University of West Florida
2018
Abstract
In the world of optimization, network optimization problems are considered fundamental to the practice. The work presented here focuses on the similarity constrained k shortest paths problem (SCKSPP) its formulation, and subsequent analysis. The formulation addresses several deficiencies which are present in prior works, and the analysis focuses on addressing major topics of feasibility and optimality which are not present in prior works. SCKSPP focuses around finding k simple paths from source to sink nodes while maintaining a pairwise dissimilarity. The purpose of this paper is to develop an underlying theory behind the SCKSPP to guide the development of an efficient solution method. The work itself is entirely theoretical; we give properties which use graph connectivity to describe the existence of feasible solutions, we demonstrate how objective function behavior affects uniqueness of the optimal solution, as well as other properties regarding feasibility and optimality. Furthermore, we show how specific graph structures allow smaller less computationally intensive problems to be solved, and then extrapolated to form optimal solutions of the larger problems. We also give several examples of similarity measures that incorporate context-specific constraints into already existing similarity constraints.
Details
- Title
- AN ANALYSIS OF THE SIMILARITY CONSTRAINED K-SHORTEST PATHS PROBLEM
- Resource Type
- Thesis
- Publisher
- University of West Florida
- Format
- text
- Copyright
- http://rightsstatements.org/vocab/InC-EDU/1.0/
- Identifiers
- 99380090837306600
- Academic Unit
- Mathematics and Statistics
- Language
- English
- Awarding Institution
- University of West Florida; Master of Science (MS)
- Theses and Dissertations
- Master of Science (MS), University of West Florida