基于重力p-median模型的支线机场物资供应中心选址

雷继超，种小雷，张世迪，于庆坤,龙小勇

(空军工程大学 航空工程学院，陕西 西安 710038)

支线机场一般地处偏远，存在物资供应不便、保障困难等方面的问题。一个地区中一般存在多个支线机场，因其担负的任务不同，对物资的需求量也不尽相同，因此根据支线机场需求物资的种类和数量，建立区域机场物资供应中心是十分必要的。文献[1-5]针对多层级设施选址问题进行了建模分析，构建了不同的算法并给出了求解方案，结果表明多层级选址模型明显优于单层的模型。在分阶段解决多层级选址问题的研究方面，文献[6-9]通过建立多层级选址模型，运用遗传算法对选址进行了优化，结果表明以运输总成本为最小目标函数建立的多层级选址模型是可行的。文献[10-13]将重力p-median模型应用到布局设施设计中，结果表明该模型的改进具有实际意义。Wang等[14]建立配送中心的选址模型，并运用改进的免疫优化算法解决配送中心选址问题。

配送中心的选址涉及到很多错综复杂的因素，相关研究往往只能解决小区域范围的选址，具有局限性；并且选址往往只是选择一个物流中心，考虑的因素相对较少，并不能解决多个机场物资供应的问题。本文从区域的角度出发，考虑了多个物流配送中心的情况，建立重力p-median模型，并采用改进的免疫优化算法对相应模型进行求解，从而确定出机场物资供应中心的最优位置。

1 问题描述

针对建立区域机场物资供应中心现阶段存在的问题，解决方案的具体设想及建模目标约束要求如下。

1.1 问题方案设想

本文设想的区域层级机场物资运输运行模式见图1。依托区域物流运输体系，由地区物流中心向机场物资供应中心运输货物，物资供应中心将不同区域的机场根据就近原则划分为几个物资分散区。每个供应中心保障对应区域的物资供应，通过设计三级运输体系可以提高物资运输效率，因此机场物资供应中心的选址在经济发展中具有重要的意义。

图1 机场物资保障模式Fig.1 Airport material security model

1.2 建模目标约束

机场物资供应中心选址模型的建立围绕目标约束展开。

(1)费用约束

在选择机场物资供应中心时，使其到地区物流中心与到机场的运输总成本最小。

(2)距离约束

选择各机场物资供应中心到机场运输货物的总距离在满足条件时,同时需要满足距离最短原则。

(3)容量约束

考虑选择供应中心的物资供应量应大于机场的物资需求量，保证机场物资使用时不受供应量的限制。

(4)需求分配

要求每个机场对应一个供应中心，一个供应中心可对应多个机场。

2 选址模型建立与求解

建模的思路采用阶段选址的方法，首先采用Voronoi图确定备选点初始位置，然后重心法确定备选点的位置时，需要满足每个组的机场与机场物资供应中心可变成本最小。为了进一步减少重心法带来的误差，基于重力p-median模型从备选点中选取合适的机场位置，采用改进的免疫优化算法进行求解，确定符合目标约束的选址位置。

2.1 选址备选点位置确定

由于重心法求解时精度不够，因此首先采用Voronoi确定备选点初始位置。采用Voronoi图对机场群进行不同区域划分，并求出不同区域的备选位置。Voronoi图由一组连接两相邻点直线的垂直平分线组成的连续多边形组成，具有以下特点：在构网时，总是选择最邻近的点形成三角形且不与约束线段相交；在一个Voronoi区域内的所有点到此区域内控制点的距离比到其他任何一控制点的距离都近。因此，选择Voronoi图作为机场物资供应中心选址的理论基础。Voronoi图原理见图2。

图2 Voronoi 图Fig.2 Voronoi diagram

假设二维空间上存在q(q≥2)个互异的点，其几何表示为G={g1,g2,…,gq}∈R2,二维空间上任意一点r到点gf的欧式距离记为d(r,gf),则Voronoi图的数学表达式为：

V(gf)={r∈R2|d(r,gf)≤d(r,gh)}

(1)

式中h=1,2,3,…,f-1,f+1,…,q。

选择对偶生成法生成Voronoi图，步骤为：

步骤1：在图上利用机场位置点构建Delaunay三角网，对各三角形进行编号，并记录其构成的三个机场点；步骤2：利用三点画圆找到各三角形的外接圆圆心，计算坐标；步骤3：遍历三角形链表，将相邻三角形外心连接，遍历结束后生成以每个三角形顶点为生成元的多边形网，即所需Voronoi图。

根据Voronoi图性质可将Voronoi图内所有区域控制点选为该区域的备选点，记录备选点坐标。以其中一个三角形机场组为例，Voronoi图控制点求法如下：以控制点为对应三角形外接圆圆心，该点到圆心各顶点距离相等的性质求解。公式如下：

(2)

(3)

式中，(x1,y1)，(x2,y2)，(x3,y3)为机场坐标，待求坐标(x,y)为重心法求解初始坐标。

2.2 基于重力p-median模型的选址优化

2.2.1 重心法确定备选点

重心法选址是利用物理学中求解一个二维封闭图形重心的原理来解决选址问题的方法。在平面选址问题中，将Voronoi图三角形顶点各机场的物资需求量视为物体的重量，考虑运输过程中的运费，求得区域重心点，即重心备选点。

重心法求解过程如下：

(4)

(5)

式中，U为运输总距离，wl为各机场物资需求量，dl为重心备选点到第l个机场的距离。

通过求二元函数极值点得出重心备选点坐标，即令∂U/∂x=0,∂U/∂y=0求得相应解。

(6)

(7)

通过迭代得到公式(8)～(9)：

(8)

(9)

求解时需要用迭代重心法求出最优解。迭代重心法计算步骤如下：

步骤1：将式(6)～(7)联立求得的备选点坐标代入式(8)～(9)得到需要求的坐标(x′,y′),代入公式(4)中求得费用值；步骤2：为保证得到的解是全局最优初始解，将步骤1中坐标(x′,y′)代入式(8)～(9)中，求得(x″,y″)，再次代入式(4)中，以此方法迭代求解，直到所求费用值为最小的(x*,y*)；步骤3：记录所求坐标(x*,y*)，以待进一步求解。

2.2.2 重力p-median模型的选址建模

假设采用重心法求出物资供应中心备选点集合为P={pi|pi=(λi,φi),i=1,2,…,n)，pi为各备选点，i为数目，n为备选点总数，λi、φi为优化求解得到的坐标，本文通过建立重力p-median模型对备选点进行优化。

重力p-median模型的基本理论可以抽象描述为在n个可能的地点中选取p个地点建立机场物资供应中心，使得机场集合与备选点集合之间的相对距离之和最小，并对其进行分配。其核心问题是p-median算法。该算法的基本原理为假设一个图的所有结点为潜在可用结点，模型优化的目标为找出一个结点的集合，使未选中的节点与已选中最近的结点的目标值达到最小。为了使得运输总成本最小，需要考虑货物在运输过程中的成本，货物运输主要采用公路运输方式，汽车运输成本的主要项目有：(i)车辆直接费用：外购燃料费用、轮胎费用、公司职工工资、职工福利费用、固定资产折旧费用、固定资产修理费用、养路费用、公路运输管理费用、车辆保险费用、事故费用、应交税金、其他费用。(ii)运营间接费用：固定成本费用、每车每公里变动成本费用、每吨每公里变动成本。根据一般运价成本规则，运输总成本可以表示为如下的形式:

(10)

式中，c表示物资运输总成本，sij表示每年进行物资运输所产生的不变成本，gij表示按照运输每公里每吨进行折算所需要的成本，wi表示第i个机场物资需求量，tij为机场j和备选点i之间的相对距离。

建模求解的目标是使每年的物资运输总成本达到最小，运输总成本由可变运输总成本和固定运输总成本组成，由于每年的固定运输总成本是不变的，为了简便计算，只需要计算可变运输总成本即可。属于可变成本的是外购燃料费用、应交税金、其他费用，物资运量，运输距离；属于不变成本的是公司职工工资、职工福利费用、固定资产折旧费用、固定资产修理费用、养路费用、公路运输管理费用、车辆保险费用。

确定约束条件：

(i)总目标：三级运输总成本最小；

(ii)供应约束：从区域物流中心向各机场物资中心的供应总量总和小于其总供应能力；

(iii)需求约束：从各机场物资中心供应地向各机场供应量应满足其需求量；

(iv)映射约束：一个机场只能与一个机场物资中心对应；

(v)分配约束：需求节点可以被指派到相应的候选节点；

(vi)个数约束：允许建立机场物资中心为r个；

(vii)0-1约束：指定相应变为为0-1变量。

重力p-median模型如公式(11)所示：

(11)

(12)

(13)

(14)

约束条件:

(15)

(16)

fij≤qj,i=1,2,…,n;j=1,2,…,m

(17)

(18)

fij,qj∈{0,1}

(19)

式中：rij表示机场i选址机场物资供应点j的概率；β表示重力模型中的距离衰减参数；m表示机场总数；Di表示机场的需求规模；Sj表示机场物资供应中心的吸引力，吸引力根据该机场的客货吞吐量来确定；U(p)表示机场物资供应中心到机场的总距离；hij表示机场i选址机场物资供应中心j的物资需求量；Z表示机场供应中心到机场的可变运输总成本；wj表示第j个机场物资供应中心供应量；qj表示决策变量。

目标函数(14)表示机场供应中心到机场的可变运输总成本最小；式(15)保证一个机场只能接收最近的一个机场物资备选点的供应；式(16)保证机场物资供应中心的供应量满足机场的需求量；式(17)保证机场可以被指派到相应的备选点；式(18)表示备选点为p个；式(19)保证控制变量fij、qj取值范围为0或1。

2.2.3 模型求解

本文利用免疫优化算法求解重力p-median模型，该算法经过“初始种群产生—评价标准计算—种群间个体信息交换—新种群产生”的循环过程能获得较大概率的问题最优解。

步骤如下：

步骤1：初始抗体群产生由记忆单元和保留种群组成。保留种群随机生成，记忆单元生成方式举例如下：设有10个备选点，用数字1～10标号表示。以0-1代码表示是否选择该备选点，代码所在位置为该机场位置，图3表示选择备选点3、7、9为所需备选点。

图3 单个抗体表示举例 Fig.3 Examples of individual antibodies

步骤 2: 计算抗体与抗原间亲和力，设计亲和力函数 A v 如式( 20) 所示;

(20)

(21)

步骤3:选择亲和力较高的抗体形成新的抗体群，计算新抗体群中抗体浓度Cv。即计算群体中相似抗体所占比例；Sv,s为抗体间亲和度，kv,s为抗体v与抗体xj中相同的位数；L为抗体长度。

(22)

(23)

(24)

步骤4：利用亲和力浓度和抗体浓度组成期望繁殖概率Pv，采用轮盘赌机制的方法，对新抗体群进行选择。

(25)

步骤5：对个体利用式(20)期望繁殖概率Pv进行选择。

步骤6：随机选择变异位进行变异。

步骤7：选择已变异的抗体中亲和度高的个体组成记忆库，将父代个体中亲和度低的个体淘汰，重新生成下一代种群。

步骤8 以进化代数作为终止条件，判断是否终止。若满足终止条件，则终止程序，输出结果；否则转步骤2。

2.2.4 免疫优化算法的改进

本文提出以可变运输总成本作为目标函数，在改进的免疫优化算法中，对亲和力函数进行改进，并在程序编程过程中，考虑了各机场与机场物资供应中心的重力的因素。免疫优化算法对机场与机场物资供应中心的可变运输总成本，和机场物资供应中心与地区物资供应中心的可变运输成本进行优化，从备选的机场物资供应中心点中选取总的可变运输成本最小的位置点。

3 算例分析

3.1 问题描述

为解决某地区机场物资运输的问题，提高机场物资保障能力，需要在某地区依托地区物流中心新建机场物资供应中心。在资金允许的情况下，经过财务预算，建造机场物资供应中心所需费用，最多能够修建3个机场。同时经过论证以后，需要3个机场能够保证本地区的机场物资的供应。因此新建3个机场物资供应中心以满足某地区内所有支线机场的物资供应，需要找出3个最优位置，保证可变运输总成本达到最小。已知某地区区域物流中心和机场物资供应中心的相对位置坐标，如图4所示。

图4 区域机场及物流中心位置图 Fig.4 Location map of regional airports and logistics centers

假设某地区不同机场所需年均物资量数据及机场相对坐标如表1所示。

表1 重心坐标计算表Table1 Table of center of gravity coordinate calculation

3.2 基于Voronoi图确定备选方案

利用Voronoi图对该区域机场群进行划分，得到不同机场组。在图上作出对偶元Delaunay三角网及每个三角形对应中垂线，形成以每一三角形顶点为生成元的多边形网，生成Voronoi图见图5。

图5 机场区域Voronoi图Fig.5 Voronoi diagram of airport area

采用式(2)～(3)计算各重三角形内切圆圆心点坐标，为重心法初始坐标，将初始坐标记录于表2备选点坐标。

表2 备选点坐标表Table 2 Alternate point coordinate

将所求的备选点坐标作为重心法求解的初始坐标，代入式(8～9)，进行多次迭代求解，直到所求得坐标使得式(14)取得最小值，将所求得坐标记录于表3。

表3 重心备选点坐标Table 3 Barycenter alternate point coordinate

3.3 建立重力p-median模型求解分配方案

3.2中求出的备选点个数为9个，则本节问题变为从9个备选点中选择3个，并分配给机场。从区域物流中心向机场物资供应中心发送货物，由3个机场物资供应中心向9个机场运输货物。

本文依据2.2中p-median模型进行选址建模处理，对1.2中建模目标约束进行求解。具体约束条件如下：

(26)

(27)

(28)

(29)

fji≤qj,(i=1,2,…,9;j=1,2,…,10)

(30)

(31)

fji,qj∈{0,1},(i=1,2,…,9;j=1,2,…,10)

(32)

式中，T表示地区物流中心总运输量，d0i表示地区物流中心到物资中心i的距离，wi表示第i个物资中心接收物资量；dij表示第j个物资中心到第i个机场的距离。

3.4 算法求解重力p-median模型

针对本文运用的改进的免疫优化算法，采用Matlab编程。在计算中取种群规模为50，记忆库容量为10，迭代次数为100，交叉概率为0.5，变异概率为0.4，多样性评价参数为0.95，将相关数据代入后得到最优选址结果及相应分配方案，见图6。图7为免疫算法收敛曲线。

注：0点代表地区物流中心;1～9 代表机场; f、g、h 代表机场物资供应中心。图6 物资供应中心位置点及分配方案Fig.6 Location and distribution plan of material supply center

图7 免疫算法收敛曲线Fig.7 Immune algorithm convergence curve

改进的免疫优化算法得出的结果能够避免出现局部最优的情况，可以有效地避免算法早熟的现象，保证了机场与机场物资供应中心的可变运输成本和机场物资供应中心与地区物流中心的可变运输总成本达到最小。由图7可知，在40代以后种群的最优适应度和平均适应度接近平稳。由图6可知，最优选址方案为f(562.39，414.96),g(424, 478)，h(169.56, 301.02)。机场物资供应中心f负责机场 1,2,8,9 物资的供应，机场g负责机场3、4 的供应，机场物资供应中心h负责机场 5、6、7 的供应。机场物资供应中心位置及对应机场如表4所示。

表4 重力p-median模型计算结果Table 4 Calculation result of the gravity p-median model

4 结论

本文采用重力p-median模型在某地区选出最优的3个配送点，得出以下结论：

(1)考虑了机场物资供应中心的吸引力，地区物流中心-支线机场物资供应中心-机场三者的运输费率等实际因素，保证了优化结果与实际相符合。

(2)运用了改进的免疫优化算法，优化了目标函数，从地区物流中心-支线机场物流中心-机场三者之间的对应关系出发，进行优化。与以往单纯只考虑配送中心与需求点的关系相比，保证了可变运输总成本最小，也使得运输总成本最小。

(3)从优化后的结果可以看出，从3个点选出的其中1个点实际上是其中1个机场的位置，说明了此机场吸引力较大，物资需求量较大，因此机场物流中心选在此位置，既减少了运输距离，降低了成本，又提高了运输效率。