Unsplittable Shortest Path Routing: Extended Model and Matheuristic

In this paper, we consider the Unsplittable Shortest Path Routing (USPR) problem which arises in the field of traffic engineering for IP networks. This problem consists, given a bidirected graph and a set of commodities, to compute a set of routing paths and the associated link weights such that each commodity is routed along the unique shortest path between its origin and its destination, according to these weights. In this paper, we propose a novel extended formulation based on routing variables that is solved using a column generation procedure, further enriched by primal heuristics allowing to build of an efficient matheuristic. We show through a set of experiments that our algorithm allows to quickly identify good feasible solutions when compared to the results obtained by the state-of-the-art local search algorithm.