We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The Cost-Balanced Path Problem: A Mathematical Formulation and Complexity Analysis.
- Authors
Ambrosino, Daniela; Cerrone, Carmine
- Abstract
This paper introduces a new variant of the Shortest Path Problem ( S P P ) called the Cost-Balanced Path Problem ( C B P P ). Various real problems can either be modeled as B C P P or include B C P P as a sub-problem. We prove several properties related to the complexity of the C B P P problem. In particular, we demonstrate that the problem is NP-hard in its general version, but it becomes solvable in polynomial time in a specific family of instances. Moreover, a mathematical formulation of the C B P P , as a mixed-integer programming model, is proposed, and some additional constraints for modeling real requirements are given. This paper validates the proposed model and its extensions with experimental tests based on random instances. The analysis of the results of the computational experiments shows that the proposed model and its extension can be used to model many real applications. Obviously, due to the problem complexity, the main limitation of the proposed approach is related to the size of the instances. A heuristic solution approach should be required for larger-sized and more complex instances.
- Subjects
NP-hard problems; LINEAR programming
- Publication
Mathematics (2227-7390), 2022, Vol 10, Issue 5, p804
- ISSN
2227-7390
- Publication type
Article
- DOI
10.3390/math10050804