文章图片
戳上面的蓝字关注我们哦！
基于双层规划的应急物资邮政运输模型优化方法研究周海霞1,2, 梅育荣1,2, 吕福如1,2, 孙知信1,2
1 南京邮电大学国家邮政局邮政行业技术研发中心(物联网技术)，江苏 南京 210003
2 南京邮电大学江苏省邮政大数据技术与应用工程研究中心，江苏 南京 210003
摘要:
应急物流是在发生重大突发事件时保障人员、物资和资金需求的一项特殊物流活动。在应急物资邮政运输模型中，如何快速准确地将应急物资运送至需求点是应急物流面临的巨大挑战。双层规划方法可以在满足需求点对应急物资需求的情况下，使整个物流过程中的物流成本最低，物流时间也最短。构建了一个以上层物流成本最低、下层物流时间最短为目标的双层规划模型，并设计了一种混合禁忌搜索遗传算法(HTSGA,hybrid tabu search genetic algorithm)求解模型，解决了灾后应急物流的运输路径优化问题。最后，实验结果对比验证了所提模型和算法的有效性。 关键词：双层规划方法 ;
应急物资邮政运输 ;
混合禁忌搜索算法
引用格式：
周海霞,梅育荣,吕福如,等. 基于双层规划的应急物资邮政运输模型优化方法研究[J]. 物联网学报, 2020, 4(3): 86-95. ZHOU H X, MEI Y R, LV F R, et al .Research on the optimization method of emergency material post transportation model based on bi-level programming[J]. Chinese Journal on Internet of Things, 2020, 4(3): 86-95.
1 引言 自然灾害的频繁发生使得人们的生命和财产安全遭受到巨大的威胁，因此，为了减少人员伤亡和经济损失，在发生突发灾害时，如何把大量的救援物资快速精准地送到需求地是应急物流面临的巨大挑战。应急物流是在发生严重自然灾害及其他突发性事件时，能够及时地保障人员、物资和资金需求的一项特殊物流活动。在应急响应中，经常会出现一系列问题，如救援物资供应点与需求点相距太远、交通拥堵等导致救援物资不能及时送达等。因此，及时合理地分配和运输救援物资具有至关重要的作用。 随着应急物流优化问题的不断演变，应急物资的分配以及运输路线的选择已成为近年来的研究热点，如应急选址、应急物资分配、应急物资运输、应急车辆配送路径以及应急车辆调度等。本文主要考虑在发生重大突发事件后，如何在有限时间内满足需求点需求的情况下进行物资分配，使得物流时间最短、成本最低。通过构建双层规划模型，设计求解算法，进行算例实验，对比本文HTSGA和文献的双层遗传算法的实验结果，验证了HTSGA的有效性与可行性。
2 相关技术研究 为了优化应急物流系统，一些学者对应急物资分配和运输路线的选择进行了研究，文献提出了一种用于应急资源分配的改进位置分配模型，定义了应急服务级别(ESL,emergency service level)的新概念，然后将该问题表述为混合整数非线性规划(MINLP,mixed-integer nonlinear programming)模型，提出了一种混合枚举搜索规则的遗传算法求解MINLP模型，这种模型确定了应急物资配送中心的数量、选址和规模，但是在预测疾病和后勤管理方面还存在局限性。文献对车辆路径问题(VRP,vehicle routing problem)进行了研究，为了使车辆的调度和操作工作更合理，在满足应急物流及时性的前提下降低了物流成本，对应急物流中 VRP 的特征进行分析。针对 VRP 的实际情况，提出了一种改进的遗传算法并将其应用于应急物流中由VRP 建立的通用数学模型，但该方法需要大量计算，并且计算量与人口规模有关，计算时间较长。文献提出了一种由地震灾害引起的应急物流运输调度问题，该问题分两个阶段进行研究：1) 选择合适的运输方式；2) 确定运送到灾区的救援物资的分配。对粒子群算法进行二进制和自然数编码改进，利用改进后的算法求解模型。由于该算法缺乏对灾区救援物资需求动态变化的考虑，所以存在应急物资后勤计划不准确的问题。文献针对应急物流问题，提出了一种多目标动态遗传算法，该算法通过使用最少数量的救援车辆生成最优路径，使整个救援过程更有效，但是无法解决异构车辆的应急物流运输问题。文献对应急物流配送过程中的位置和需求信息等进行了研究，通过分析风险偏好值设计了一种两阶段的随机规划模型，并提出了一种在合理计算时间内解决问题的简单两阶段启发式方法。 1973年，Bracken等首次提出双层规划数学模型，而双层规划和多层规划名词的正式出现是在1977年Candler等的科学报告中。双层规划利用上、下层决策者之间既相互独立又相互影响的特点求解问题，首先上层决策者做出决策，其次下层决策者根据上层决策信息优化自身的目标并做出决策，最后上层决策者利用下层决策者优化后的决策做出最终决策。如何将双层规划方法应用于应急物流，目前已有部分学者对此进行了研究。 文献研究了在模糊环境中具有固定费用的双目标应急物流运输问题，构建了模糊环境下的运输模型，其中有3个特殊模型：一些可替代物品模型、一些易损物品模型以及具有安全系数的灾害运输问题(DTP,disaster transportation problem)模型。文献利用双层规划方法构建了应急物流设施选址—车辆路径问题稳健双层优化模型，该模型主要研究了应急物流设施的选址和车辆运输路线的选择，针对需求点在突发事件发生时对救援物资的需求量存在不确定性的情况，利用分散式决策中的转换定理将模型中不确定系数确定化进行求解，开发了一种混合的遗传算法求解转换后的模型。文献建立了一个应急物流设施选址—车辆路径问题的双层规划模型，模型的上层目标为物流系统消耗的时间最短，下层目标为配送成本与时间惩罚成本之和最小，设计了一种混合模拟退火算法，该算法在传统的模拟退火算法的基础上进行改进，引入了带有启发式规则的两阶段式方法。对于存在多种配送方式混合配送的问题，该模型并没有进行考虑，因此，无法解决多车混合配送的问题。文献构建的数学模型以物资运送时间最短、物资分配公平性最大为上、下层目标，是一个动态的双层规划模型。该模型考虑了一系列约束条件，如需求点的时间窗、物资最低满足率等，并设计了一种符合双层规划动态模型特点的混合遗传算法。但随着震后救援工作的不断推进，该算法无法动态优化应急物资的配送问题。在文献中，现有的双层规划应急物资运输模型主要研究了应急物资分配的公平性与满足率、物资运输时间长短以及物流成本高低等方面。由于应急物流需要很强的时效性，因此，最小化物流时间和物流成本是现有采用双层规划方法构建应急物流运输模型的主要目标，但文献的模型对物流成本和物流时间的优化缺少对库存成本和应急物资集散点准备时间的考虑。因此，本文在满足各个需求点需求的情况下，考虑时间对模型产生的影响，采用双层规划方法构建数学模型。本文所提模型主要以整个物流过程中的总成本最低为上层目标、耗费总时间最短为下层目标，结合禁忌搜索算法和遗传算法设计了一种HTSGA求解模型，达到应急物流消耗的成本最低和物流时间最短的效果。对比本文所提算法与文献所提算法的实验结果，验证了HTSGA的有效性与可行性。
3 应急物资邮政运输模型
3.1 问题描述
邮政物流业务不断发展壮大，为了应对愈发激烈的市场竞争，依靠强大的运输网络优势，邮政企业积极整合物流运输资源。邮政车辆运输问题的关键是如何进行车辆运输调度，使得运输效率得到提高。在发生自然灾害时，为了使救援工作更便利，面对不断变化的救灾环境，应急物资邮政运输需要在灾区附近选择一些合适的应急物资配送中心，通过运输车辆将灾区外围应急物资集散点的物资运送到灾区附近的应急物资配送中心，然后根据灾区需求点对物资需求量的大小，对应急物资进行分配。 根据应急物资邮政运输的特征，作出如下假设。 1) 应急物资运输车辆和应急物资足够多。 2) 应急物资配送中心与需求点、需求点与需求点之间都存在可行路径。 3) 存在多个应急物资配送中心，并且每个应急物资配送中心满足多个应急物资需求点的需求。 4) 应急物资需求点的物资需求为单一品种的商品，并且商品的规格和单价相同。 5) 每个应急物资需求点仅由一个应急物资配送中心的一辆运输车辆配送物资，应急物资需求点的物资需求必须得到满足。 6) 每个应急物资需求点都有两个时间点，期待最早被配送的时间点和能接受最晚被配送的时间点。 7) 应急物资运输车辆为同一类型，并且每辆运输车辆在运输任务完成后必须返回出发点。 8) 应急物资运输车辆早到或晚到应急物资需求点，都会产生相应的时间惩罚成本。
3.2 模型参数
模型中的参数说明如表1所示，模型中的决策变量说明如表2所示。 
文章图片
文章图片
3.3 模型建立
根据自然灾害发生后对初期救援情况的分析，可将应急物流系统分为上、下两级。根据上、下两级不同的决策目标，使用双层规划方法构建模型，其中，上层以整个物流活动的总成本最低为目标，下层以整个物流过程所耗费的时间最短为目标，上、下层模型之间相互关联又相互制约。 本文基于文献的研究成果，在上层模型的总成本中加入应急物资配送中心的库存成本，确保整个应急物流过程的总成本最低，并且将运输成本分为两个部分，其中，时间惩罚成本对文献的时间惩罚函数加以改进。在下层模型中，加入了应急物资集散点接到应急物资配送中心的供货需求后投入准备的时间。因此，根据不同的决策目标，对应急物资邮政运输问题采用双层规划方法构建模型进行描述。 3.3.1 上层模型 
文章图片
在上述模型中，目标函数式(1)表示整个模型的物流总成本最低，物流总成本包含6部分：应急物资集散点和应急物资配送中心的固定成本、应急物资配送中心的库存存储成本、运输车辆派遣成本(包含车辆配对人员)、应急物资的装卸成本、车辆两阶段的运输成本和时间惩罚成本。其中，车辆两阶段的运输成本分为：应急物资集散点到应急物资配送中心的运输成本、应急物资配送中心到需求点的运输成本，R = P ∪ Q表示所有应急物资配送中心和需求点的集合。式(2)表示车辆k只有在投入使用时才有运输服务；式(3)表示每个应急物资需求点仅被一个应急物资配送中心的一辆运输车辆服务；式(4)表示运输车辆的载物量不超过车辆的容量；式(5)表示应急物资配送中心只有在开放时才能给应急物资需求点分配物资；式(6)表示车辆的时间窗约束，车辆从应急物资配送中心出发后到达需求点的时间不能晚于需求点所接受的最晚到达时间点；式(7)表示运输车辆到达应急物资需求点的时间点。 由于运输车辆早到或晚到都会产生相应的时间惩罚成本，因此，在式(8)时间惩罚成本的函数表达式中，α表示车辆晚到应急物资需求点的惩罚成本系数，β表示车辆早到应急物资需求点的惩罚成本系数。由于每个需求点都有自身接收应急物资的时间窗[ ET q ,LT q ]，因此，应急物资配送中心安排配送车辆时需要尽可能满足每一个需求点的时间窗，即 ET q ≤ T q ≤ LT q ，从而减少车辆提前到达或延迟到达产生的成本损失。 
文章图片
3.3.2 下层模型 
文章图片
在双层规划模型中，上层模型的约束同样适用于下层模型。在上述模型中，目标函数式(9)表示整个应急物流所耗费时间之和最短，总时间主要分为4 部分：应急物资集散点接到应急物资配送中心供货需求后的准备时间、应急物资配送中心的准备时间、物资配送途中的装卸时间以及车辆的运输时间。其中，车辆的运输时间又分为应急物资集散点到应急物资配送中心、应急物资配送中心到需求点两部分。式(10)表示需求点的需求量不能超过应急物资配送中心的容量；式(11)表示每辆运输车辆最多服务于一个应急物资配送中心；式(12)表示每个应急物资配送中心都有可以支配的运输车辆；式(13)表示运输车辆的起点和终点必须为同一个应急物资配送中心；式(14)表示运输车辆的配送路线是连续且闭合的，进入该节点的车辆必须从该节点离开。
4 算法设计 根据上述模型的特点，本文基于设计了一种混合禁忌搜索算法和遗传算法的 HTSGA， HTSGA流程和HTSGA伪代码分别如图1和算法1所示。其中，HTSGA的步骤如下。 步骤1 对算法中的参数进行初始化设置。 步骤2 对种群进行初始化设置。 步骤3 根据双层规划模型中的下层目标式(9)计算种群的适应度值，并使用轮盘赌算法保留优秀个体。 步骤 4 判断算法是否满足终止条件，即迭代数K是否达到预设值，若满足终止条件，则结束算法并输出优化结果；否则，继续执行下一步操作。 步骤 5 从优秀的个体中随机选择两个染色体xi和xj，以初始交叉概率Pc对其进行交叉操作，产生两个新的染色体xi′和xj′，根据玻尔兹曼选择机制，新的染色体选择概率为 
文章图片
自适应交叉概率Pc为 
文章图片
其中，fmax(x)、favg(x)分别表示种群的最大适应度值和平均适应度值，L表示禁忌表的长度。 步骤 6 在种群库中随机选择一个染色体xi，以变异概率Pm对其进行变异操作，生成新的染色体x i′。根据玻尔兹曼选择机制，判断是否选择该新染色体。自适应变异概率Pm为 
文章图片
步骤 7 更新禁忌表，为了避免重复选择，将已选择的最佳选项放到禁忌表中。 步骤 8 对算法进行收敛性判断，判断其是否满足收敛条件。若满足收敛条件，则执行步骤 9；否则，更新禁忌表，返回步骤 3，重新计算染色体适应度，并保留优秀个体。 步骤 9 确定候选解，利用当前解产生其邻域解 x 1 ，以当前邻域解为依据产生遗传算法新的初始种群N( x 1 )，并代入上层目标函数式(1)中，确定候选解。 步骤10 对候选解进行特赦条件的判断，若满足特赦条件，则该候选解为当前最优解 xbest，更新禁忌表与当前解的状态，返回步骤 3；否则，继续执行下一步操作。 步骤11 选择最佳解作为当前解，然后返回步骤3。 算法1 HTSGA伪代码 初始化 for all 种群中的个体 do 
文章图片
end for if K =预设值 then 输出最小物流总成本 f1(x) else 执行下一步 end if for 当前种群 do 从优秀的个体中随机选择两个染色体xi和xj，并以概率Pc进行交叉操作产生两个新的染色xi′和x′j 随机选择一个染色体xi并以概率Pm对其进行变异操作从而产生新的染色体xi′ if 满足玻尔兹曼机制 then 接受该新染色体 end if 更新禁忌表：将已选择的最佳选项放到禁忌表中，避免重复选择 if 满足收敛条件 then 执行步骤9 else 更新禁忌表，返回步骤 3，重新计算染色体适应度，并保留优秀个体 end if 利用当前解产生其邻域解x1，以当前邻域解为依据产生遗传算法的初始种群N(x1)，并代入目标函数式(1)中，从而确定候选解 if 满足特赦条件 then 将该候选解作为当前最优解 xbest，同时更新禁忌表和当前状态，并返回步骤3 else 执行下一步操作 end if 选择最佳解决方案作为当前解决方案， 然后返回步骤3 end for
5 实验分析 为了能够更好地理解上述模型，本文设计了一个简单的算例。假设随机给出4个应急物资配送中心，编号分别为A、B、C、D，应急物资需求点20个，运输车辆数量足够。假设应急物资集散点j的固定使用成本为16 000元，规格相同的运输车辆的容量为800件，平均行驶速度为90 km/h，车辆包含配对人员的派遣成本为800元/辆，应急物资的装卸成本和装卸时间分别为1元/件、0.1 min/件，车辆的运输成本为 1 元/km，每件物资的时间惩罚成本为1元/h，应急物资配送中心接到需求点的需求后投入准备的时间均为1.5 h，应急物资集散点接到应急物资配送中心的需求后投入准备的时间均为1.5 h，固定的应急物资订购成本为100元。20个应急物资需求点信息如表3所示，4个应急物资配送中心的固定成本如表4所示。表3、表4展示了部分实验数据，分别表示实验涉及的 20 个应急物资需求点信息和4个应急物资配送中心的固定成本。 
文章图片
文章图片
根据本文设计的 HTSGA，算法中的主要参数包括初始种群N、迭代数K、初始交叉概率 P c 、变异概率 P m 、禁忌表以及禁忌长度L等。 对于不同规模的运输问题，算法的收敛性与所设置的参数大小有关。 由于本文设计的算例较简单，参数初始化时令 N=100，K=100， P c =0.95， P m =0.005，L=round ((cityNum×(cityNum-1)/2)×0.5)，其中cityNum表示需求点的数量。 使用R2017a版本的Matlab进行仿真计算，HTSGA求解 最优分配车辆运输路径如表5所示，表5中车辆运输路线一列数据表示运输车辆从应急物资配送中心出发，经过各个需求点，最终返回该应急物资配送中心，其中A、C表示应急物资配送中心，各个数字表示需求点。 在求解具有递阶决策结构特性的混合双层规划模型时，传统的启发式算法无法进行求解，利用设计的双层遗传算法求解本文算例，双层遗传算法求解最优分配车辆运输路径如表6所示，表6中车辆运输路线一列数据表示运输车辆从应急物资配送中心出发，经过各个需求点，最终返回该应急物资配送中心。其中，A、B 表示应急物资配送中心，各个数字表示需求点。从初始种群中随机选择应急物资配送中心，选择下层目标函数式(9)作为适应度函数，即应急物流所耗费时间作为适应度函数，采用轮盘赌选择方法保留优秀个体，设置最大迭代数，当迭代结束后输出总成本。 对比表5和表6的实验结果可知，本文设计的HTSGA 在求解算例时，无论是物流总成本、消耗的总时间还是车辆运输路线都优于双层遗传算法。HTSGA 求解路径、双层遗传算法求解路径分别如图2、图3所示。图2表示HTSGA求解的最佳配送路线，图2中A、C表示应急物资配送中心，车辆运输路线分别为 A-12-2-1-13-3-A、A-6-18-15-16-8-A以及C-5-4-11-20-C、C-17-7-10-19-9-14-C。图3表示双层遗传算法求解的最佳配送路线，图3中A、B表示应急物资配送中心，车辆运输路线分别为 A-3-13-1-2-12-A、A-8-16-7-15-18-6-A 以及B-4-11-20-B、B-5-17-B和B-10-19-9-14-B。 
文章图片
文章图片
文章图片
图2HTSGA求解路径 
文章图片
图3双层遗传算法求解路径 利用双层遗传算法和HTSGA仿真得出迭代次数与总成本的关系曲线，算法收敛对比如图4所示，从图4可以看出，虚线比实线率先趋于稳定，可见HTSGA 的收敛速度明显比双层遗传算法快，当迭代次数达 52 次时，总成本较先趋于稳定。综上所述，本文设计的HTSGA在求解有双层规划的应急物流运输模型时，算法的收敛性较好。 
文章图片
图4算法收敛对比 当平面上存在 100 个需求点时，利用 HTSGA进行求解。为了降低计算量，假设每个需求点的需求量为0～50件，需求点分布较密集，其中，每辆运输车辆的容量为1 000件，在平面上选择一个应急物资配送中心，对周边100个需求点进行配送， 100个需求点的配送路径如图5所示。由图5可见， 6条路线表示应急物资配送中心派出6辆运输车辆进行配送，100 个需求点的最优分配车辆运输路径如表7所示，表7中车辆运输路线一列中数字0表示应急物资配送中心，其他数字表示100个需求点的编号，即配送车辆由应急物资配送中心出发，经过各个需求点最终回到应急物资配送中心。 
文章图片
图5100个需求点的配送路径 
文章图片
6 结束语 本文针对应急物流的时效性和物流成本研究了灾后应急物资邮政运输问题，通过使用双层规划方法构建了一个上层以整个应急物流过程的总成本最低、下层以配送过程所耗费时间最短为目标的数学模型。针对双层规划模型中上、下层目标决策者既相互独立又相互影响的特点，设计了一种带禁忌搜索的遗传算法HTSGA求解模型，最后通过一个简单的算例和对比算法验证了本文所提算法和模型的有效性与可行性。本文仅利用单一的车辆进行运输，未来可以对多种车型混合配送的多联式车辆运输问题以及车辆返回时是否出现空载现象等方面进行研究，提高车辆使用效率。本文暂未考虑道路交通信息，下一步可以利用车载网络技术获取车辆运输过程中的道路交通信息，通过信息实时共享进行车辆的动态规划。 作者简介 About authors
周海霞(1995-)，女，江苏南通人，南京邮电大学现代邮政学院硕士生，主要研究方向为路径优化算法等 。 梅育荣(1996-)，女，安徽宣城人，南京邮电大学现代邮政学院硕士生，主要研究方向为区块链技术、物联网关键技术等 。 吕福如(1996-)，女，江苏连云港人，南京邮电大学现代邮政学院硕士生，主要研究方向为区块链技术、物流信息安全与隐私保护等 。 孙知信(1964-)，男，安徽宣城人，博士，南京邮电大学教授、博士生导师，主要研究方向为计算机网络及安全、物联网应用、多媒体通信、计算机软件等。 联系我们:
Tel:010-81055683
010-81055483
010-81055691
E-mail:wlwxb@bjxintong.com.cn
http://www.infocomm-journal.com/wlw
http://www.wlwxb.com.cn
往期文章回顾
【论文】工业物联网中基于边缘计算的跨域计算资源分配与任务卸载
【论文】基于毫米波感知的小型无源物体定位追踪
【论文】基于顾问引导搜索的虚拟网络映射算法
【论文】基于OLAP技术的物联网客户数据平台构建
【论文】空天地一体化网络技术：探索与展望
【论文】基于无源反向散射技术的智能标签：应用与挑战
【论文】基于SDN的铁路系统空天地融合网络架构
【论文】基于深度强化学习的无人机数据采集和路径规划研究
【论文】无线能量收集驱动的铁路物联网中断性能分析
【论文】多源异构航班航迹数据流实时融合方法研究
【论文】面向自动驾驶应用的车联多智能体信息融合协同决策机制研究
【论文】基于多特征时空图卷积网络的水运通航密度预测
文章图片
『物联网学报』办刊方针和业务范围为：刊载物联网及相关交叉学科研究领域具有创新性的基础理论、关键技术、研究热点及基础与应用研究成果的学术论文，充分展示我国研究成果，反映我国的前沿研究水平，为我国正在迅速发展的物联网科技创新与产业服务提供学术支持，促进我国物联网技术与应用领域的发展。 
文章图片
【wps|wps 模拟分析 规划求解_【论文】基于双层规划的应急物资邮政运输模型优化方法研究...】扫码关注物联网学报官方微信获取更多！
