Ayırıcı çatışma kısıtlı en kısa yol problemi

An extension of the ordinary one-to-many shortest path problem that also considers additional disjunctive conflict relations between the arcs is considered in this study. In this problem called SPC, 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 three novel algorithms for SPC. One such algorithm is a novel branch-and-bound algorithm, which benefits from the solution of the one-to-many shortest path relaxation, an efficient primal-dual re-optimization scheme and a fast infeasibility detection procedure for pruning the branch-and-bound tree. The second solution method is a greedy depth first search algorithm, which benefits from the sufficient conditions of infeasibility special to shortest path problem. The third one is also a branch-and-bound algorithm; but it searches through the solution space using the stable sets of the conflict graph, benefiting from an efficient circuit prevention and a fast infeasibility detection procedure for pruning the branch-and-bound tree. Several MILP formulations are tested in order to find the best one. At last, new algorithms are extensively tested on both randomly generated and realistic test instances, comparing them with the best MILP formulation implemented with a state-of-the-art commercially available MILP solver. According to the obtained results, it is possible to say that the best of the novel algorithms outperforms the solver, while the other two's performances are comparable.