An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints

Bahadır Pamuk, Temel Öncan and İ. Kuban Altınel

European Journal of Operational Research, 2025, vol. 324, issue 2, 398-413

Abstract: In this work we study an extension of the ordinary one-to-many shortest path problem that also considers additional disjunctive conflict relations between the arcs: an optimal shortest path tree is not allowed to include any conflicting arc pair. As is the case with many polynomially solvable combinatorial optimization problems, the addition of conflict relations makes the problem NP-hard. We propose a novel branch-and-bound algorithm, which benefits from the solution of the one-to-many shortest path relaxations, an efficient primal–dual reoptimization scheme and a fast infeasibility detection procedure for pruning the branch-and-bound tree. According to the extensive computational tests it is possible to say that the novel algorithm is very efficient.

Keywords: Combinatorial optimization; Shortest path problem; Conflict constraints; Branch-and-bound (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725000876
Full text for ScienceDirect subscribers only

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:eee:ejores:v:324:y:2025:i:2:p:398-413

DOI: 10.1016/j.ejor.2025.01.044

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().