基于网络优化的交通网络设计研究  

Research on Transportation Network Design Based on Network Optimization

作　　者：张江华[1] 

机构地区：[1]山东大学管理学院

出　　处：《复旦学报（自然科学版）》2008年第2期260-265,共6页Journal of Fudan University：Natural Science

基　　金：教育部人文社会科学项目(06JA630018)

摘　　要：针对交通网络设计问题,首先定义了赋权二分图的单边控制集问题,给出了相应的算法;然后将上述算法和割集遍历算法相结合,构建了基于网络优化思想的两个启发式算法,并对两个算法进行了比较分析,证明了算法Ⅱ可在有限步终止.最后通过算例验证了两个算法的有效性.The problem of transportation network design is studied. Firstly, a single-side domination set problem of weighted bipartite graph is defined, along with the corresponding algorithm. Then two heuristic algorithms based on network optimization are put forward by combining the algorithm mentioned above with the algorithm enumerating all cut sets. Furthermore, these two heuristic algorithms are analyzed. It is proved that the algorithm Ⅱ could end in finite step. Finally, a numerical example is presented to show the efficiency of these two algorithms.

关 键 词：交通网络设计 网络优化 单边控制集 赋权二分图 启发式算法 

分 类 号：O157[理学—数学] U491[理学—基础数学]