An Analysis of the Similarity Constrained K-shortest Paths Problem
Author | : Joseph Jay Kennedy |
Publisher | : |
Total Pages | : 178 |
Release | : 2018 |
ISBN-10 | : OCLC:1084975218 |
ISBN-13 | : |
Rating | : 4/5 (18 Downloads) |
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.