计算机工程

• 开发研究与工程应用 • 上一篇    

轴辐式网络设计中的变折扣轴线选址问题研究

陈晓欣a,b,徐云a,b,刘向彬a,b   

  1. (a.中国科学技术大学 计算机科学与技术学院; b.安徽省高性能计算重点实验室,合肥 230027)
  • 收稿日期:2015-12-14 出版日期:2017-01-15 发布日期:2017-01-13
  • 作者简介:陈晓欣(1991—),女,硕士研究生,主研方向为轴辐式网络优化;徐云(通信作者),教授、博士生导师;刘向彬,硕士研究生。
  • 基金项目:
    国家自然科学基金(61033009);高等学校学科创新引智计划项目(B07033)。

Research on Hub Arc Location Problem with Unfixed Discounts in Hub-and-spoke Network Design

CHEN Xiaoxin  a,b,XU Yun  a,b,LIU Xiangbin  a,b   

  1. (a.School of Computer Science and Technology; b.Key Laboratory of High Performance Computing of Anhui Province,University of Science and Technology of China,Hefei 230027,China)
  • Received:2015-12-14 Online:2017-01-15 Published:2017-01-13

摘要: 现有轴线选址问题(HALP)研究多数采用固定折扣的轴线,不能有效地针对轴辐式网络中轴线流量差别较大的情形。为此,在改进HALP假设条件的基础上,提出采用分段线性函数进行变折扣模拟的变折扣轴线选址问题(HALPUD),建立HALPUD数学模型,分析问题的最优解特性并设计拉格朗日松弛算法对HALPUD进行求解。在CAB标准数据集上的实验结果表明,对于不同的问题规模及分段线性函数,拉格朗日松弛算法均能在较短的时间内得到求解结果,具有较高的求解效率和质量。

关键词: 轴辐式网络, 轴线选址问题, 变折扣, 拉格朗日松弛算法, 分段线性函数

Abstract: Previous researches on Hub Arc Location Problem(HALP) mostly adopt hub arcs with fixed discounts which cannot effectively deal with the situation that flows on hub arcs in the hub-and-spoke network have large differences.Therefore,this paper proposes a Hub Arc Location Problem with Unfixed Discounts(HALPUD) based on improved assumptions amd uses a piece-wise linear function to simulate the unfixed discounts.It establishes a mathematical model of the HALPUD,discusses the optimal solution features,and designes an algorithm based on Lagrangian relaxation.Experiments on the standard Civil Aeronautics Board(CAB) datasets show that,for different scale of the problem and different piece-wise linear functions,the Lagrangian relaxation algorithm can always get results quickly.The algorithm has good solution efficiency and quality.

Key words: hub-and-spoke network, Hub Arc Location Problem(HALP), unfixed discount, Lagrangian relaxation algorithm, piece-wise linear function

中图分类号: