地理学报 ›› 2014, Vol. 69 ›› Issue (12): 1847-1857.doi: 10.11821/dlxb201412010

• • 上一篇    下一篇

基于最多叶子生成树的中国航空网络轴辐结构构建

徐敏政1,2, 许珺1(), 陈娱1   

  1. 1. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室, 北京 100101
    2. 中国科学院大学资源与环境学院, 北京 100049
  • 收稿日期:2013-09-06 修回日期:2014-07-28 出版日期:2014-12-25 发布日期:2015-01-24
  • 作者简介:

    作者简介:徐敏政 (1990-), 男, 江西抚州, 硕士研究生, 主要研究方向为空间网络数据挖掘、地理信息检索。E-mail: xumz@lreis.ac.cn

  • 基金资助:
    国家863计划项目 (2012AA12A211, 2012AA12A403);国家自然科学基金项目(41371380,41171296)

Construction of Chinese aviation hub-spoke structure based on maximum leaf spanning tree

Minzheng XU1,2, Jun XU1(), Yu CHEN1   

  1. 1. Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
    2. College of Resources and Environment, University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2013-09-06 Revised:2014-07-28 Online:2014-12-25 Published:2015-01-24
  • Supported by:
    National High Technology Research and Development Program of China, No.2012AA12A211, No.2012AA12A403;National Natural Science Foundation of China, No.41371380, No.41171296

摘要:

航空网络的轴辐 (Hub-Spoke) 结构是实现规模经济发展的重要交通运输网络结构,本文为此提出了一种全新的航空网络轴辐结构构建方法。该方法从图论和地理学的角度出发,引入地理距离约束,改进了传统的最多叶子生成树 (Maximum Leaf Spanning Tree) 算法,直接从现有的中国航空网络中抽取树形轴辐结构形成航空支线网络,然后选取支线网络中度前10的节点作为航空枢纽点,并将枢纽点之间在原图中的航线抽取为航空干线网络,最后将支线网络和干线网络合并形成中国航空网络的轴辐结构。在与相关研究的对比分析中,本文方法虽是从图论角度出发,但构建的中国航空轴辐结构符合实际地理环境,划分支线网络距离阈值的选择更加客观合理,所选的航空枢纽点地理意义更为明显,干支线网络的覆盖度更为全面。

关键词: 轴辐结构, 中国航空网络, 最多叶子生成树, 距离约束, 图论

Abstract:

Aviation hub-spoke structure is an important transportation network to achieve economies of scale development. As regards to its construction, most of methods are proposed by human geography scientists, whose efficiencies are affected by the authors' experience. In this paper, we present a novel graph method to extract hub-spoke structure from aviation network directly, which is more objective and efficient. Taking Chinese aviation network as a case study, we integrate a constraint distance into the conventional maximum leaf spanning tree algorithm to extract tree-shaped hub-spoke structure. The tree-shaped hub-spoke structure forms the branch airlines, and the top 10 degree nodes selected as aviation hubs are Beijing, Shanghai, Guangzhou, Chengdu, Urumqi, Kunming, Xi'an, Changsha, Harbin and Guiyang. The ten hubs dominate other non-hubs in different regions of China. For example, Urumqi dominates Northwest China and Shanghai dominates eastern China. The airlines among the hubs form the trunk airline network, which covers most of China's territory except the southwestern part because of lacking of a powerful hub. The aviation hub-spoke structure is generated by merging the branch airlines and the trunk airline network. Compared with the result of previous research, the hub selection of our method is more reasonable in some cases, such as selecting Harbin instead of Shenyang in Northeast China; the branch airlines and trunk airlines generated by our method have broader coverage; the division of branch and trunk airlines is more objective due to the use of constraint distance. In addition, our hub-spoke structure fits the real geographical situation better than the previous results. To sum up, the contributions of this paper are: (1) developing a novel maximum leaf spanning tree algorithm with distance constraint; (2) proposing a novel aviation hub-spoke structure construction method based on the algorithm; (3) applying the method to extract the hub-spoke structure of Chinese aviation in 2012, and it performs quite well.

Key words: Key works: hub-spoke, Chinese aviation network, maximum leaf spanning tree, distance constraint, graph theory