基于双层规划的应急物资邮政运输模型优化方法研究

　　摘要：应急物流是在发生重大突发事件时保障人员、物资和资金需求的一项特殊物流活动。在应急物资邮政运输模型中，如何快速准确地将应急物资运送至需求点是应急物流面临的巨大挑战。双层规划方法可以在满足需求点对应急物资需求的情况下，使整个物流过程中的物流成本最低，物流时间也最短。构建了一个以上层物流成本最低、下层物流时间最短为目标的双层规划模型，并设计了一种混合禁忌搜索遗传算法(HTSGA,hybridtabusearchgeneticalgorithm)求解模型，解决了灾后应急物流的运输路径优化问题。最后，实验结果对比验证了所提模型和算法的有效性。

　　关键词：双层规划方法;应急物资邮政运输;混合禁忌搜索算法

　　1引言

　　自然灾害的频繁发生使得人们的生命和财产安全遭受到巨大的威胁，因此，为了减少人员伤亡和经济损失，在发生突发灾害时，如何把大量的救援物资快速精准地送到需求地是应急物流面临的巨大挑战。应急物流是在发生严重自然灾害及其他突发性事件时，能够及时地保障人员、物资和资金需求的一项特殊物流活动。在应急响应中，经常会出现一系列问题，如救援物资供应点与需求点相距太远、交通拥堵等导致救援物资不能及时送达等。

　　因此，及时合理地分配和运输救援物资具有至关重要的作用。随着应急物流优化问题的不断演变，应急物资的分配以及运输路线的选择已成为近年来的研究热点，如应急选址[1-3]、应急物资分配[4]、应急物资运输[5]、应急车辆配送路径[6]以及应急车辆调度[7]等。本文主要考虑在发生重大突发事件后，如何在有限时间内满足需求点需求的情况下进行物资分配，使得物流时间最短、成本最低。通过构建双层规划模型，设计求解算法，进行算例实验，对比本文HTSGA和文献[8]的双层遗传算法的实验结果，验证了HTSGA的有效性与可行性。

　　2相关技术研究

　　为了优化应急物流系统，一些学者对应急物资分配和运输路线的选择进行了研究，文献[9]提出了一种用于应急资源分配的改进位置分配模型，定义了应急服务级别(ESL,emergencyservicelevel)的新概念，然后将该问题表述为混合整数非线性规划(MINLP,mixed-integernonlinearprogramming)模型，提出了一种混合枚举搜索规则的遗传算法求解MINLP模型，这种模型确定了应急物资配送中心的数量、选址和规模，但是在预测疾病和后勤管理方面还存在局限性。文献[10]对车辆路径问题(VRP,vehicleroutingproblem)进行了研究，为了使车辆的调度和操作工作更合理，在满足应急物流及时性的前提下降低了物流成本，对应急物流中VRP的特征进行分析。

　　针对VRP的实际情况，提出了一种改进的遗传算法并将其应用于应急物流中由VRP建立的通用数学模型，但该方法需要大量计算，并且计算量与人口规模有关，计算时间较长。文献[11]提出了一种由地震灾害引起的应急物流运输调度问题，该问题分两个阶段进行研究：1)选择合适的运输方式;2)确定运送到灾区的救援物资的分配。对粒子群算法进行二进制和自然数编码改进，利用改进后的算法求解模型。由于该算法缺乏对灾区救援物资需求动态变化的考虑，所以存在应急物资后勤计划不准确的问题。文献[12]针对应急物流问题，提出了一种多目标动态遗传算法，该算法通过使用最少数量的救援车辆生成最优路径，使整个救援过程更有效，但是无法解决异构车辆的应急物流运输问题。

　　文献[13]对应急物流配送过程中的位置和需求信息等进行了研究，通过分析风险偏好值设计了一种两阶段的随机规划模型，并提出了一种在合理计算时间内解决问题的简单两阶段启发式方法。1973年，Bracken等[14]首次提出双层规划数学模型，而双层规划和多层规划名词的正式出现是在1977年Candler等[15]的科学报告中。双层规划利用上、下层决策者之间既相互独立又相互影响的特点求解问题，首先上层决策者做出决策，其次下层决策者根据上层决策信息优化自身的目标并做出决策，最后上层决策者利用下层决策者优化后的决策做出最终决策。

　　如何将双层规划方法应用于应急物流，目前已有部分学者对此进行了研究。文献[16]研究了在模糊环境中具有固定费用的双目标应急物流运输问题，构建了模糊环境下的运输模型，其中有3个特殊模型：一些可替代物品模型、一些易损物品模型以及具有安全系数的灾害运输问题(DTP,disastertransportationproblem)模型。文献[17]利用双层规划方法构建了应急物流设施选址—车辆路径问题稳健双层优化模型，该模型主要研究了应急物流设施的选址和车辆运输路线的选择，针对需求点在突发事件发生时对救援物资的需求量存在不确定性的情况，利用分散式决策中的转换定理将模型中不确定系数确定化进行求解，开发了一种混合的遗传算法求解转换后的模型。

　　文献[18]建立了一个应急物流设施选址—车辆路径问题的双层规划模型，模型的上层目标为物流系统消耗的时间最短，下层目标为配送成本与时间惩罚成本之和最小，设计了一种混合模拟退火算法，该算法在传统的模拟退火算法的基础上进行改进，引入了带有启发式规则的两阶段式方法。对于存在多种配送方式混合配送的问题，该模型并没有进行考虑，因此，无法解决多车混合配送的问题。文献[19-20]构建的数学模型以物资运送时间最短、物资分配公平性最大为上、下层目标，是一个动态的双层规划模型。该模型考虑了一系列约束条件，如需求点的时间窗、物资最低满足率等，并设计了一种符合双层规划动态模型特点的混合遗传算法。

　　但随着震后救援工作的不断推进，该算法无法动态优化应急物资的配送问题。在文献[16-20]中，现有的双层规划应急物资运输模型主要研究了应急物资分配的公平性与满足率、物资运输时间长短以及物流成本高低等方面。由于应急物流需要很强的时效性，因此，最小化物流时间和物流成本是现有采用双层规划方法构建应急物流运输模型的主要目标，但文献[18-20]的模型对物流成本和物流时间的优化缺少对库存成本和应急物资集散点准备时间的考虑。

　　因此，本文在满足各个需求点需求的情况下，考虑时间对模型产生的影响，采用双层规划方法构建数学模型。本文所提模型主要以整个物流过程中的总成本最低为上层目标、耗费总时间最短为下层目标，结合禁忌搜索算法和遗传算法设计了一种HTSGA求解模型，达到应急物流消耗的成本最低和物流时间最短的效果。对比本文所提算法与文献[8]所提算法的实验结果，验证了HTSGA的有效性与可行性。

　　3应急物资邮政运输模型

　　3.1问题描述

　　邮政物流业务不断发展壮大，为了应对愈发激烈的市场竞争，依靠强大的运输网络优势，邮政企业积极整合物流运输资源。邮政车辆运输[21-22]问题的关键是如何进行车辆运输调度，使得运输效率得到提高。在发生自然灾害时，为了使救援工作更便利，面对不断变化的救灾环境，应急物资邮政运输需要在灾区附近选择一些合适的应急物资配送中心，通过运输车辆将灾区外围应急物资集散点的物资运送到灾区附近的应急物资配送中心，然后根据灾区需求点对物资需求量的大小，对应急物资进行分配。根据应急物资邮政运输的特征，作出如下假设。

　　1)应急物资运输车辆和应急物资足够多。2)应急物资配送中心与需求点、需求点与需求点之间都存在可行路径。3)存在多个应急物资配送中心，并且每个应急物资配送中心满足多个应急物资需求点的需求。

　　4)应急物资需求点的物资需求为单一品种的商品，并且商品的规格和单价相同。5)每个应急物资需求点仅由一个应急物资配送中心的一辆运输车辆配送物资，应急物资需求点的物资需求必须得到满足。6)每个应急物资需求点都有两个时间点，期待最早被配送的时间点和能接受最晚被配送的时间点。7)应急物资运输车辆为同一类型，并且每辆运输车辆在运输任务完成后必须返回出发点。8)应急物资运输车辆早到或晚到应急物资需求点，都会产生相应的时间惩罚成本。

　　3.2模型参数模型中的参数说明。

　　3.3模型建立根据自然灾害发生后对初期救援情况的分析，可将应急物流系统分为上、下两级。根据上、下两级不同的决策目标，使用双层规划方法构建模型，其中，上层以整个物流活动的总成本最低为目标，下层以整个物流过程所耗费的时间最短为目标，上、下层模型之间相互关联又相互制约。本文基于文献[8-9,18]的研究成果，在上层模型的总成本中加入应急物资配送中心的库存成本，确保整个应急物流过程的总成本最低，并且将运输成本分为两个部分，其中，时间惩罚成本对文献[23]的时间惩罚函数加以改进。在下层模型中，加入了应急物资集散点接到应急物资配送中心的供货需求后投入准备的时间。因此，根据不同的决策目标，对应急物资邮政运输问题采用双层规划方法构建模型进行描述。

　　4算法设计

　　根据上述模型的特点，本文基于文献[24]设计了一种混合禁忌搜索算法和遗传算法的HTSGA，其中，HTSGA的步骤如下。步骤1对算法中的参数进行初始化设置。步骤2对种群进行初始化设置。

　　步骤3根据双层规划模型中的下层目标式(9)计算种群的适应度值，并使用轮盘赌算法保留优秀个体。步骤4判断算法是否满足终止条件，即迭代数K是否达到预设值，若满足终止条件，则结束算法并输出优化结果;否则，继续执行下一步操作。步骤5从优秀的个体中随机选择两个染色体ix和jx，以初始交叉概率Pc对其进行交叉操作，产生两个新的染色体ix和jx，根据玻尔兹曼选择机制，新的染色体选择概率为()()1,()()e,()()iiiifxfxiLiifxfxPfxfx≥(16)自适应交叉概率Pc为00avgmaxavgmaxavg,()()(()()),()()()()cicciiPfxfxPPfxfxfxfxfxfx≤(17)其中，maxf()x、f()xavg分别表示种群的最大适应度值和平均适应度值，L表示禁忌表的长度。

　　5实验分析

　　为了能够更好地理解上述模型，本文设计了一个简单的算例。假设随机给出4个应急物资配送中心，编号分别为A、B、C、D，应急物资需求点20个，运输车辆数量足够。假设应急物资集散点j的固定使用成本为16000元，规格相同的运输车辆的容量为800件，平均行驶速度为90km/h，车辆包含配对人员的派遣成本为800元/辆，应急物资的装卸成本和装卸时间分别为1元/件、0.1min/件，车辆的运输成本为1元/km，每件物资的时间惩罚成本为1元/h，应急物资配送中心接到需求点的需求后投入准备的时间均为1.5h，应急物资集散点接到应急物资配送中心的需求后投入准备的时间均为1.5h，固定的应急物资订购成本为100元。

　　邮政运输论文投稿刊物：《中国邮政》(月刊)创刊于1976年，是由中华人民共和国国家邮政局主管、主办。邮政综合性刊物。集中反映我国邮政通信建设、业务技术发展状况、经营管理、服务水平、职工生活、教育训练、古代邮驿和集邮等内容。

　　6结束语

　　本文针对应急物流的时效性和物流成本研究了灾后应急物资邮政运输问题，通过使用双层规划方法构建了一个上层以整个应急物流过程的总成本最低、下层以配送过程所耗费时间最短为目标的数学模型。针对双层规划模型中上、下层目标决策者既相互独立又相互影响的特点，设计了一种带禁忌搜索的遗传算法HTSGA求解模型，最后通过一个简单的算例和对比算法验证了本文所提算法和模型的有效性与可行性。本文仅利用单一的车辆进行运输，未来可以对多种车型混合配送的多联式车辆运输问题以及车辆返回时是否出现空载现象等方面进行研究，提高车辆使用效率。本文暂未考虑道路交通信息，下一步可以利用车载网络技术获取车辆运输过程中的道路交通信息，通过信息实时共享进行车辆的动态规划。

　　参考文献：

　　[1]RAWLSCG,TURNQUISTMA.Pre-positioningofemergencysuppliesfordisasterresponse[J].TransportationResearchPartB:Methodological,2010,44(4):521-534.

　　[2]GENGSQ,HOUHP,ZHANGSG.Multi-criterialocationmodelofemergencysheltersinhumanitarianlogistics[J].Sustainability,2020,12(5):1759.

　　[3]FENGJR,GAIWM,LIJY.Multi-objectiveoptimizationofrescuestationselectionforemergencylogisticsmanagement[J].SafetyScience,2019,120:276-282.

　　[4]WANGYY,BIERVM,SUNBQ.Measuringandachievingequityinmultiperiodemergencymaterialallocation[J].RiskAnalysis,2019,39(11):2408-2426.

　　[5]GARZA-REYESJA,VILLARREALB,KUMARV,etal.Alean-TOCapproachforimprovingemergencymedicalservices(EMS)transportandlogisticsoperations[J].InternationalJournalofLogisticsResearchandApplications,2019,22(3):253-272.

　　作者：周海霞1,2，梅育荣1,2，吕福如1,2，孙知信1,2

转载请注明来自发表学术论文网：http://www.fbxslw.com/jjlw/24923.html