Mathematical programming approaches for NP-Hard constrained shortest path problems

Abstract

In this work, we study two NP-Hard routing problems: the shortest path with negative cycles (SPNC) and the constrained shortest path tour problem (CSPTP). For the SPNC, we propose three exact approaches based on mathematical programming: a compact mixed integer linear programming model, a specialized branch-and-bound algorithm, and a cutting-plane method. We perform numerical experiments comprising both randomly generated and benchmark instances from the literature. The computational tests show that the proposed approaches stand out from state-of-the-art mathematical programming techniques. Moreover, we discuss the linear relaxations of models present it the literature. Concerning the CSPTP, we show two compact models for the problem: a pure integer linear programming model, which we call dummy node-based model; and a mixed integer linear programming one, which we call frontier node-based model. For the latter, we show valid inequalities and propose deterministic and non-deterministic Lagrangian heuristics. Experiments performed on both randomly generated and benchmark instances from the literature validate and attest the effectiveness of our contributions, which achieve the optimal solution in the vast majority of cases. We show that the dummy node and the frontier node-based models alternate better results depending on the characteristics of each instance. The efficiency over specialized branch-and-bound algorithms from the literature is also proven through experiments, as well as the potentialities behind the Lagrangian heuristics, which find the optimal solution for a large number of instances.