摘要
针对交通网络设计问题,首先定义了赋权二分图的单边控制集问题,给出了相应的算法;然后将上述算法和割集遍历算法相结合,构建了基于网络优化思想的两个启发式算法,并对两个算法进行了比较分析,证明了算法Ⅱ可在有限步终止.最后通过算例验证了两个算法的有效性.
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.
出处
《复旦学报（自然科学版）》
CAS
CSCD
北大核心
2008年第2期260-265,共6页
Journal of Fudan University：Natural Science
基金
教育部人文社会科学项目(06JA630018)
关键词
交通网络设计
网络优化
单边控制集
赋权二分图
启发式算法
transportation network design
network optimization
single-side domination set
weighted bipartite graph
heuristic algorithm
