The Cost-Balanced Path Problem: A Mathematical Formulation and Complexity Analysis

Daniela Ambrosino and Carmine Cerrone
Additional contact information
Daniela Ambrosino: Department of Economics and Business Studies, University of Genoa, 16126 Genoa, Italy
Carmine Cerrone: Department of Economics and Business Studies, University of Genoa, 16126 Genoa, Italy

Mathematics, 2022, vol. 10, issue 5, 1-13

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.

Keywords: shortest path problem; mixed-integer linear programming; cost-balanced paths (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/5/804/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/5/804/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:5:p:804-:d:763262

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().