轴辐式网络变扣轴选址问题研究

轴辐式网络变扣轴选址问题研究

0轴辐式网络设计轴向网络是指将od（或局部网络）流程集中在一些路段进行集中运输，然后分布到目的地形成的运输网络。它的特点是，专注于运输的路段根据规模和经济效益大大降低了成本。它也适用于第三方物流、邮政、航空和其他领域。轴线选址问题(HubArcLocationProblem,HALP)是轴辐式网络设计中新的研究热点,由Campbell等人于2015年提出以解决枢纽选址问题(HubLocationProblem,HLP)目前,轴辐式网络设计研究主要集中于HLP中的枢纽中位问题(HubMedianProblem,HMP)。HMP最初由O’Kelly本文针对HALP的不足,提出变折扣轴线选址问题(HubArcLocationProblemwithUnfixedDiscounts,HALPUD)。HALPUD的假设条件除了包括HALP改进的两点,还有包括:1)轴线上的运输必须汇集一定的OD流量,且需支付额外附加成本;2)轴线运输折扣依赖于其上的总OD流量。本文建立HALPUD的数学模型,探讨问题的最优解特性,并设计拉格朗日松弛求解算法。1问题建模1.1halpud的模型给定一个连通网络G(N,A),N为节点集合,A为边集合。假设G中任一节点都有货物要运送到其他节点,任一条边都有一定权值代表单件货物运送代价。一条边若被选为轴线,则该边运送代价将会有一个依赖于其上总OD流量的运输折扣。HALPUD研究的是:如何选择轴线和OD流路线,使得整个输运网络的运行成本最小。为简化问题,为HALPUD再增加一个假设条件:所有OD流均按最小成本原则选择在每个路段上的流动方式:轴线方式或非轴线方式。这可使得所有OD流在选择运输路径时相互独立,从而能对每个OD流进行单独考虑。下面是模型中用到的符号变量:WCFHXYα(fD:表示OD流以非轴线方式通过路段(k,m)时的单位流量成本,1.2节点流量平衡变折扣轴线选址问题模型M在模型中,目标式(1)表示总运输网络运行成本最小。约束式(2)表示OD流i→j被全部运送。约束式(3)和式(4)保证一个节点出入流量平衡;约束式(5)表示若(k,m)不是轴线,则X依据文献[14],运输折扣α(f在图1中,相邻的空心点和实心点为同一个点,表示前一段函数不包含该点,而后一段函数包含该点;a将分段线性成本流量函数应用到模型M目标函数式(10)满足约束条件式(2)~式(9)以及约束条件式(11)~式(14):在模型中,R1.3路段k,m为轴线分析变折扣轴线选址问题的最优解,可得到以下性质:性质1若路段(k,m)为轴线,则其上汇集的OD流量必定不少于F证明:令f性质2任一轴线(k,m)上汇集的总OD流量f证明:若存在一个轴线(k,m)上总OD流量f2算法的设计本文为M2.1、、式通过松弛M目标函数式(15)满足约束条件式(2)~式(4)、式(6)~式(9)、式(11)~式(14)。其中,λ算法1求解拉格朗日松弛问题计算固定成本:2)对其中,S4)对于路段:2.2第一个问题的可执行解的计算M算法2计算原问题可行解其中,S5)对于轴线2.3拉格朗日乘数更新本文利用次梯度法其中,t表示迭代次数;s其中,θ2.4步长和拉格朗日乘子更新令算法3拉格朗日松弛算法2)根据算法1求解拉格朗日松弛问题得到H3)根据算法2得到原问题的可行解4)更新步长参数θ5)根据式(16)更新拉格朗日乘子λ7)判断程序是否达到终止条件:(1)UB3拉格朗日松弛算法计算本文采用CAB标准数据集对变折扣轴线选址模型及其拉格朗日松弛求解算法进行计算实验。该数据集是轴辐式网络设计问题的经典测试数据集,包含美国25个城市的流量矩阵和单位流量成本矩阵,即提供了参数W在所有实验参数确定后,在VS2013上用C++编程,具体实验环境为:Intel(R)Core(TM)i5-2400CPU@3.10GHz,4.00GBRAM。实验结果如表2~表4所示,第1列n表示节点规模,第2列表示该节点规模中具有的总OD流数;拉格朗日松弛算法计算结果包括两部分:1)R变折扣轴线选址问题考虑了轴线的额外附加成本,因此,每个OD流的运输路径在根据最小成本原则选择是直达运输还是中转运输时,需要比较中转运输获取的折扣与分摊的附加成本加绕道成本的大小,只有当前者大于后者时,该OD流才会选择中转运输。但由于每个OD流在轴线上分摊的附加成本与该轴线上总的OD流量有关,因此在不知道轴线上的总OD流量时,不能预先确定OD流在该轴线上分摊的附加成本。本文在求原问题下界的过程中,直接取分段线性函数中每个片段对应的最大流量值作为该轴线上总的OD流量值,因此实际原问题的下界要高于此下界。而在求原问题上界的过程中,由于轴线上的总OD流量必然在分段线性函数中每个片段对应的最小流量值与最大流量值之间,本文分别从这2个边界值来考虑,因此实际原问题的上界便在所求得的2个上界之间。从表2~表4可以看出,对于不同的问题规模以及不同的分段线性函数,拉格朗日松弛求解算法均具有较好的求解质量和效率:原问题的上下界差距(Gap4算法整体仿真本文针对现有轴线选址问题(HALP)研究大多数采用固定折扣轴线的情形,提出一种利用分段线性函数进行变折扣模拟的变折扣轴线选址问题(HALPUD)。本文建立HALPUD的数学模型,分析该问题的最优解特性并进行证明。对于模型的求解,本文设计一种拉格朗日松弛算法。首先构造并求解拉格朗日松弛问题得到原问题的下界;其次以拉格朗日松弛问题的解为基础构造原问题的可行解,得到原问题的上界;最后通过次梯度法迭代更新拉格朗日乘子,逐步缩小原问题的上下界差距,得到原问题的近优解。从CAB标准数据集上的实验结果可以看出,对于不同的问题规模以及不同的分段线性函数,拉格朗日松弛算法