救援物资运输问题的多模式分层网络规划模型

救援物资运输问题的多模式分层网络规划模型

1应急救援物资运输的主要理论模型近年来，自然灾害、各种事故和公共安全灾害的发生频率和规模都明显超过了正常情况。九八洪水、SARS危机等都对我国社会整体生产生活程序造成了巨大冲击。随着我国经济的快速发展与政府行政体制改革的深化,政府部门逐渐认识到在经济建立中,加强自身对大规模自然灾害与公共事件的管理,建立有效地应急反应机制的重要性。如何利用先进的技术手段,增强政府与社会团体、组织应对大规模自然灾害与突发公共事件的应急反应能力已成为一个重要课题。应急救援物资的运输是应急管理领域中的一个中心问题。它是在大规模自然灾害与突发性公共事件发生以后,研究如何调度不同运输方式下的运输工具(为了简便,以下所有运输方式中的运输工具都简称为车辆)将数量与种类可能随时间变化的救援物资尽快从多个供应点运输到事件发生地,以追求时间效益最大化和灾害损失最小化为目标的特种物流活动。应急物资运输与商业运输相比主要差别是:①应急救援物资运输具有弱经济性,它的目标是在尽快将救援物资运输到目的地的前提下实现运输费用最小化,属于同时追求货物运输时间最小化与费用最小化的多目标规划问题。②由于自然灾害与公共突发事件的突发性与规模、种类的不确定。所需救援物资种类较多,每种物资的供应点与需求点可能都不一致。而且物资的需求量、供应量可能会随着时间而变化的。③救援物资运输行动是由政府组织的非常规性活动,货物配送中需要的车辆,一般是由政府按照应急预案临时征用社会团体或个人的,它可以出现在网络中的任何点,完成一项运输任务后也无需返回出发点,所以需要同时研究货物流及配套车辆配送问题。④应急救援物资运输需要使用公路、铁路、航空等多种运输方式,而且会在不同的运输方式中进行转换。因此应急物资运输问题是一个复杂的集成了多货物多起止点网络流问题与多运输方式满载车辆无固定起止点运输工具调度问题的多目标规划。由于应急物资运输问题的复杂性,国内外相关文献较少。这其中Kemball-Cook和Stephenson首先提出在救援物资运输时对物流管理的需要,以提高运输效率。接着Ray、Rathi、Wael、Eqi、宋明安在不同的约束条件下研究了以最小化运输费用为目标的应急救援物资运输的问题;Linet提出了最小化运输时间为目标函数的救援物资运输模型。计雷提出了应急管理中的救援物资运输问题是最小化运输费用与运输时间的多目标组合优化问题,但是该文献并没有涉及到问题模型的建立与实现。2应急材料运输模式的结构2.1多模式分层网络模型应急运输的每种物资都可能包括多个供应点与需求点,并且经常会用到多种运输方式。据此设计了多模式分层网络,将每种运输方式分成一个网络层,称为一个模式层。在多模式分层网络中有四类顶点,分别是中转点:代表运输枢纽或可进行运输方式转换的地点,不能贮存物资;映像点:代表供应点或需求点在某种运输方式下发送或接收物资,货物流入量与流出量相等;供应点:通过映像点向各模式层上发送物资;需求点:产生物资需求的点,它通过映像点在各模式层上接收物资。同时多模式分层网络中的弧分为三类。分别是载重弧:代表运输通路,与载重弧关联的费用为货物运输费,同一模式层所有中转点、映像点彼此连接的弧为载重弧;转换弧:沟通不同运输方式之间的通路,货物通过转换弧在不同运输方式间转运,在其上关联了货物转运费;映像弧:连接映像点与供应点或需求点,没有相关联的费用与容量,也不消耗时间。图1是一个多模式分层网络示例图,其中a、b是需求点;c、d是供应点;e、f是中转点,整个运输网络有三种运输方式,所以示例图中三个模式层,c点可以通过运输方式一、二向外运输货物,所以它在模式层一、二上有映像点c′、c″,代理它发送货物。运输方式二与运输方式三可以在中转点f进行转运,在模式层二、三上分别有f″、f‴两个点代表在运输方式二、三上的f点,并在它们之间有转换弧连接,表示货物可在此点进行运输方式二、三的转运。车辆作为运输工具需要循环使用,可以被看为模式层上的循环流,称为车辆流。在应急物资运输这个特定场景下车辆流有一些特殊的约束条件。首先是应急救援车辆可以在网络上的任意点被动员征用,所以车辆可在对应模式层上的任意点出发执行运输任务。其次是车辆没有固定的车场,完成计划任务后,也不知道是否还有下一项运输任务,所以完成运输任务后车辆不需要返回出发地而是在原地待命。再次是车辆流只能在载重弧上流转,而不能通过其他类型的弧。同时车辆流的流量上限就是载重弧的容量,而货物流的流量上限是分配运输该种货物的车辆容量。救援物资运输问题的目标之一是缩短货物运输时间,属于包括时间在内的四维空间优化问题。为了将对时间的考量集成到救援物资运输模型中,将整个救援物资运输的计划周期划分成多个等长时段,模型中与时间有关的变量都以时段数来表示时间维度的值。同时货物供应量、需求量、可用车辆数等参数发生变化时,也可以按照时段重新调整计划,从而解决了模型参数随时间变化的问题。在模型中时段的长度设置必需适中,以尽量减少车辆在完成任务后的闲置时间。但是它也不能太短,这将会使车辆路径变量以指数方式增加。加入时间维度后,多模式分层网络可以转换成一个时空网络,图2就是从图1示例中的模式二层产生的时空网络,在连接不同点对间的虚线是行驶线路,同一相邻点之间的点横线是车辆停靠线路,设车辆的起点在c与d点,虚线与点横线是车辆的可选路线。从图2可以看出,车辆流是在在时空网络中单向可行路线中选择一条满足目标要求的行-停路线,以此为基础就可以制定详细车辆配送计划。救援物资运输问题的目标是减少运输时间、降低运输费用的多目标规划,其中运输费用是包括车辆在载重弧上行驶的费用(包括空驶与重载)和运输方式转换的费用。而对于最小化物资运输时间的目标,我们采用了罚函数方法,根据每种救援物资在需求点的需求紧迫性制定一个延期罚函数系数,它定义为单位未满足货物需求量延续一个时段对目标函数的增加量。这个方法的优点是使用灵活,比如灾害发生后情况紧急,这时应急物资运输的主要目标是减少运输时间,我们可以将运输费用值设置为0。而如果救援行动持续了一段时间,救援物资运输已经成为日常例行事务,这时货物运输的目标是最小化费用,我们就可以将延期罚函数系数设为0。2.2模型的构建(1)计算重负荷弧的运输时间①由于大规模突发性事件情况下救援物资运输量都较大,因此只考虑车辆满载情况。②每一载重弧的运输时间都以时段数量来衡量,不足1时段的以1时段计算。③转运弧消耗的时间都是1时段。④所有的费用函数都假定为线性的。⑤货物的供应量与需求量已知。⑥每一种运输方式下车辆规格一致。(2)车辆载重量cdgi-运输方式单位段i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,j及车辆参数决策变量cgi分析E-映像点点集FE-中转点与映像点的集合T-计划期的总时段数CA-载重弧集SNgit-g种类物在i点t时段新增供应量RNgit-g种货物在i点t时段新增需求量M-运输方式集合VAmit-第m种运输方式下在i点t时段新增车辆数VCapm-m种运输方式下车辆的载重量G-货物的种类集tmij-在第m种运输方式从i点到直接相邻j点所需时段数ACapmij-第m种运输方式载重弧(i,j)的道路容量CTm-第m种运输方式单位时段内单位车辆的运输费用CFgmm′i-单位g货物在i点从m到m′运输方式的模式转换费用CDgi-在需求点i点单位g货物需求延期单位时段满足的罚函数系数Pg-g种类货物的比重决策变量:Xgmitjt′-t时段从i点经过t′-t时段到达j点的g货物流量Xgmm′it(t+1)-货物g在t时段、i点通过从m到m′模式的流量RDgit-需求点i在t时段g货物未满足的需求SDgit-供应点i在t时段g货物还未运输的供应量Ymitjt′-m层车辆在t时段从i点经过tmij时段到j点的车辆流量VDmit-模式m层在i点、t时段未使用的车辆数(3)货物流模型的形成根据以上的符号定义,可以将应急救援物资运输与车辆调度模型构建如下:目标函数:min∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1CΤm⋅Ymitj(t+tmij)⋅tmij(1)min∑m∈M∑i∈FE∑j∈FE∑t=1TCTm⋅Ymitj(t+tmij)⋅tmij(1)+∑g∈G∑i∈FEΤ∑t=1∑m∈Μ∑m′∈ΜCFgmm′i⋅Xgmm′it(t+1)(2)+∑g∈G∑i∈RΤ∑t=1CDgi⋅RDgit(3)约束条件:∑m∈Μi′∈EXmgiti′t=SDgi(t-1)+SΝgit-SDgit,i∈S,g∈G,t∈T(4)-∑m∈Μi′∈EXmgi′tit=-RDgi(t-1)-RΝgit+RDgit,i∈R,g∈G,t∈T(5)∑j∈FEXmgj(t-tmji)it+∑m′∈ΜXgm′mi(t-1)t+Xmgi′tit=∑j∈FEXgmitj(t+tmij)+∑m′∈ΜXgmm′it(t+1)+Xmgiti′t,i∈FE,t∈Τ,g∈G,m∈Μ,i′∈R∪S(6)SDgit,SNgit,RDgit,RNgit,Xgmitj(t+tmij),Xgmm′it(t+1)≥0(7)VAmit+∑j∈FEYmj(t-tmji)it+VDmi(t-1)=∑j∈FEYgmitj(t+tmij)+VDmit,i∈FE,t∈T,m∈M(8)Ymitj(t+tmij)≤ACapmij,t∈T,m∈M,(i,j)∈CA(9)Ymitj(t+tmij)≥0且为整数;VDmit≥0且为整数(10)∑g∈GXgmitj(t+tmij)⋅Ρg≤VCapm⋅Ymitj(t+tmij),t∈Τ,m∈Μ,(i,j)∈CA(11)以上模型的开始时刻可以定为货物的最早起运时间,它的目标函数分为三部分,分别是:①车辆的行驶费用;②改变货物运输方式所引起的模式转换费用;③表示需求延期满足所引起的目标函数增加值,其中CDgi就是需求货物的延期罚函数系数。它的约束条件可以分为三类,分别是:①货物流约束;②车辆流约束;③货物流与车辆流关联约束式。货物流约束包括模型中(4)~(7)式,其中约束式(4)是供应点货物流引出约束,它表示供应点向网络发送救援物资的量与库存量的关系,等式左边是g货物在i点向其映像点流出的货物流,等式右边是i点上一时段延期到本时段未起运货物量加上新增供应量再减去延期到下一时段以后起运的货物量。约束式(5)是需求点货物流引出约束,它表示需求点从网络中接收救援物资的量与未满足及新增货物需求的关系,它与(4)式分别定义了供应点与需求点的货物流平衡。约束式(6)是中转点或映像点货物流平衡约束,等式左边表示货物流入量,等式右边表示货物流出量,它表示进入中转点或映像点的货物量等于离开该点的货物量。其中Xmgi′tit表示如果对于g货物i点是供应映像点,从供应点向供应映像点发送的货物量;Xmgiti′t表示如果对于g货物i点是需求映像点,则需求映像点向需求点发送的货物量;约束式(7)是非负约束。车辆流约束包括模型中的(8)~(10)式,其中约束式(8)是车辆流平衡约束,这个式子约束进入中转点或映像点的车辆数等于完成任务,停在该点的车辆数与离开该点的车辆数之和。(9)式是车辆流上界约束,它表示通过(i,j)弧的车辆数不能超过道路的容量。(10)约束式是表示车辆流决策变量不为负并且都为整数。货物流与车辆流关联约束式(11)表示的是货物流与车辆流之间的关系。上述约束中货物流约束表示货物流从供应点流向需求点应该满足的条件,车辆流约束是限制车辆的流转关系,它们从约束式上看是独立的,它们之间就是通过关联约束式集成为一个整体,共同表示为应急救援物资运输与车辆调度问题的数学模型。救援物资运输问题是研究如何高效地调度车辆将救援物资从供应点运输到需求点,这里车辆通过“运载”与货物发生关系,关联约束式表示通过载重弧(i,j)的货物重量不能大于通过车辆的载重量来约束货物流与车辆流的流量关系,从而将货物运输与车辆配送统一起来,形成了完整的描述应急救援物资运输与车辆调度问题的约束集。2.3分时段计划方式由于在大规模自然灾害发生时,信息处于不对称状态,这时向灾害发生地调运救援物资往往带有一定的盲目性。随着应急反应部门相互沟通与信息反馈,这时上一级的应急管理部门才能够比较准确地估计灾害发生地需要物资的种类、数量等参数。在此过程中物资供应量、需求量以及车辆数都会经常发生变化,应急物资运输与车辆调度计划也需随之调整。对此在构建应急物资运输模型时考虑到上述因素,采用分时段计划方式,加入参数调整量,从而可以比较方便地根据参数变化重新调整计划。对于应急物资运输计划按照以下方式调整:(1)SNgit、RNgit、VAmit按照变化量进行调整,因为在灾害应急场景下,货物供应量与车辆数都会随着动员范围逐渐扩大而增加,不需要考虑负值情况。如果RNgit<0,则取RDgit=max(RNgit+RDgit,0),其中t是上一个计划期的最后一个时段。(2)对于上一阶段已分配运输任务但还没有到达目的地的车辆不再调整其运输任务。对货物需求量与供应量调整如下:本时段的延期满足货物需求量等于上一个计划期最后一个时段的未满足货物需求量。本时段的延期运输货物供应量等于上一个计划期最后一个时段的货物供应量。(3)调整计划中的可用车辆数是以下几部分组成:①本时段新加入救援物资运输任务的车辆;②以前时段征集准备承担救援物资运输任务,但一直没有使用的车辆;③当前时段停留在当地等待新任务的车辆,因为这一部分车辆可能在上一个计划中就计划在以后某时段离开停靠点,因此车辆数在后面时段可能会减少。因此我们需要根据前一个计划判断出该点等待车辆数不再减少的时段t′,将t′时段后在该点原地待命的车辆作为新计划该点的可用车辆,将其作为新增车辆加入到新计划中。3解决算法的设计3.1拉式子问题的求解应急物资运输与车辆调度模型是一个混合整形规划,仅车辆流部分就包括CA·T·Ym个整形决策变量,如果简单地采用单纯形法与分支定界法解决此问题,车辆数、运输方式、计划周期等变量数的增加将会使计算复杂性以指数方式递增,满足不了应急反应过程中快速、高效的需要。从应急物资运输与车辆调度模型分析,整个模型约束分成可以分成货物流约束与完成货物运输任务而产生的车辆流约束两部分,而且目标函数也可以分为与货物流相关的运输模式转换费和需求延期惩罚费,以及与车辆流相关的车辆行驶费用两部分。它们通过货物流与车辆流关联约束式联系。如果能够使用方法松弛该关联约束,就可以将应急物资运输与车辆调度模型分为货物运输模型与车辆调度模型两个子问题,这将会大大降低该模型求解的计算复杂度。根据以上分析,以LargangianRelaxation为基础求解该模型,将关联约束乘上拉氏乘子后加入目标函数中,这个方法类似在问题的目标函数中对每一条货物重量超过车辆容量的弧施以罚数,迭代计算出合适的拉氏乘子向量组,再求出原问题的最优解。应用拉式松弛后,目标函数成为min(1)+(2)+(3)+∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1Wmijt(∑g∈GXgm′itj(t+tmij)⋅Ρg)(12)-∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1Wmijt(VCapm⋅Ymitj(t+tmij))(13)其中,Wmijt是拉氏乘子向量组。通过以上变化后,应急物资运输与车辆调度模型的拉式子问题由以上目标函数与(4)~(10)约束组成,以下简称为Lag(OP)。将关联约束松弛以后可以将Lag(OP)分为Lag1(X)货物流和Lag2(Y)车辆流两个子问题分别计算,其中Lag1(X)是目标函数为(2)式、(3)式、(12)式组成,约束集由(4)~(7)组成,由于在拉式子问题去掉了关联约束,这就可能会出现载重弧上的货物流重量超过弧容量,为了避免这个问题,在Lag1(X)加入货物流上界约束(14):∑g∈GXgmitj(t+tmij)⋅Ρg≤ACapmij⋅VCapm,m∈M,t∈T,i∈FE,j∈FE(14)Lag2(Y)问题的目标函数由(1)式与(13)式组成,约束集由式(8)~(10)组成。求解Lag(OP)最优解的计算步骤如下:步骤1:求解Lag(OP)整形松弛问题的解,如果没有得到解,则终止运算,原问题没有可行解。如果得到Lag(OP)整形松弛问题的解S*,则设置迭代计数k=1,问题低界解LB=S*,最初的拉氏乘子W0mijt=0。求任意一个原问题的可行解S′.设置Lag(OP)最优解OP*=S′.执行步骤2。步骤2:通过子梯度法来计算拉氏乘子问题,首先分别计算Lag1(X)和Lag2(Y),得到最优解Xk与Yk,利用这两个解计算出Lag(OP)的目标函数值Sk.如果Sk>LB,则LB=Sk.判断Xk和Yk是否满足关联约束,如果满足且Sk<OP*,则OP*=Sk,执行步骤3;如果不满足则执行步骤3。步骤3:判断以下循环退出条件:(a)判断Xk与Yk是否满足条件关联约束式左值等于右值;(b)(OP*-LB)/OP*<α;(c)k=TK.其中满足条件(a),当前Sk就是问题的最优解,输出Sk.α为收敛率,如果当前OP*距离低界解LB的比率小于α,认为OP*是可接受解,且输出OP*.TK是循环次数限制,满足条件(c)直接退出,将当前的最优解输出。如果以上退出条件都不满足,则执行步骤4。步骤4:计算拉氏乘子的步长θk,设λ为比例因子,初始值为2,将Xk和Yk计代入下式计算步长θk=λ⋅(ΟΡ*-LB)/∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1(∑g∈GXgmitj(t+tmij)⋅Ρg-Ymitj(t+tmij)⋅VCapm)2,为保证目标函数的值收敛,如果在三次循环中LB值不增加,则减少λ=λ/2。执行步骤5。步骤5:计算拉氏乘子,计算Wk+1mijt=Wkmijt+θk⋅(∑g∈GXgmitj(t+tmij)⋅Ρg-Ymitj(t+tmij)⋅VCapm),因为Wkmijt必须满足非负条件,所以Wk+1mijt=max(0,Wk+1mijt),设k=k+1,转步骤2。3.2多模式分层网络模型①货物流问题Lag1(X)的目标函数是(2)式、(3)式与(12)式的和,约束集由(4)~(7)和(14)式组成,在多模式分层网络中Lag1(X)可以分析为多种救援物资的多货物最小费用流问题,通过应用列生成法等算法可以计算最小费用流。其中(2)与(12)式可以直接表示为弧的费用,对于(3)式需要转换为弧形式,如计算g货物到l需求点最短路时,网络上弧(i,j)的需求延期满足费率=tmij·CDgi.如果救援物资运输的目标是时间最短而不考虑费用(这会在救援物资需求与生命损失密切相关的情况下出现),则将(2)式移除后求解就得到运输时间最短的路线。②车辆流问题Lag2(Y)的目标函数是(1)式与(13)式的和,约束集由(8)~(10)式组成的整数规划。解决该问题可以将多模式分层网络中每个模式层单独求解。在每个模式层的时空网络中,增加一个中转点,该点通过入弧与时空网络期末各FE点相连,入弧的关联费用为零,上界约束为无穷。通过出弧与时空网络上每一个VAmit大于零的FE点相连,出弧的关联费用为零,上下界约束都为VAmit,这就将Lag2(Y)问题转换为最小费用循环流问题,可