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

Pamuk B., ÖNCAN T., Altınel İ. K.

European Journal of Operational Research, 2025 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2025
  • Doi Numarası: 10.1016/j.ejor.2025.01.044
  • Dergi Adı: European Journal of Operational Research
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, International Bibliography of Social Sciences, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Compendex, Computer & Applied Sciences, EconLit, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
  • Anahtar Kelimeler: Branch-and-bound, Combinatorial optimization, Conflict constraints, Shortest path problem
  • Galatasaray Üniversitesi Adresli: Evet

Özet

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.