摘要： 现有轴线选址问题(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

中图分类号: 

• TP301.6