Two Phases Algorithm of Transport Network Design Problem

The transport network design problem deals with how to add or improve some edges on an existing transport network using quantitative analysis method. This paper put forward two phases algorithm of transport network design based on network optimization, which concludes enumerating all cut sets and resolving single-side domination set problem of weighted bipartite graph. Firstly, a single-side domination set problem of weighted bipartite graph is defined, along with the corresponding algorithm. Then two phases algorithm of transport network design is constructed by combining the algorithm mentioned above with the algorithm enumerating all cut sets. Further, the complexity of algorithm is analyzed, and it is proved that the algorithm could end in finite step. Finally, a numerical example is presented to show the efficiency of algorithm.