An Application of Network Design with Orientation Constraints

We address the problem of orienting the edges of an undirected graph so as to minimize the sum of the distances between a given set of origin-destination pairs in the resulting directed graph. The problem originates from the design of Personal Rapid Transit (PRT) networks. We consider an Integer Linear Programming (ILP) formulation with variables associated with the orientation of the arcs, and variables associated with the arcs in the paths in the directed graph between origin-destination pairs. Given that the direct solution of this natural formulation is impractical even for small instances, we propose a branch-and-cut approach based on Benders decomposition, reporting preliminary experimental results on arising from PRT networks.