A branch and bound algorithm for the hierarchical transportation network design problem in directed networks

The purpose of this paper is to present a branch and bound algorithm for the hierarchical transportation network design problem in 2-level directed networks. This problem is to find the least cost of hierarchical transportation networks which consist of a primary path and a secondary path. The primary path is a simple path from a prespecified origin node to a prespecified terminal node. All nodes must be either a transsipment node on the primary path or connected to that path via secondary arcs. This problem is formulated to a 0-1 integer programming problem with assignment and illegal subtour elimination equations as constraints. The authors show that the subproblem relaxing subtour elimination constraints is transformed to a linear programming problem by means of the totally unimodularity. Optimal solutions of this subproblem are polynomially obtained by the assignment algorithm and complementary slackness conditions. Therefore, the optimal value of this subproblem is used as a lower bound. When an optimal solution of the subproblem has an illegal subtour, a better disjoint rule is adopted as the branching strategy for reducing the number of branched problems. The computational comparison between the least bound rule and the depth first rule for the search strategy is given. [In Korean.]