楼振凯

(北京理工大学管理与经济学院，北京 100081)

应急物流系统LRP的双层规划模型及算法

楼振凯

(北京理工大学管理与经济学院，北京 100081)

针对洪涝、地震等自然灾害发生后的应急物流配送系统优化问题，考虑到政府和企业共同参与、分散决策的特点，建立了一个设施定位-运输路线问题(LRP)的双层规划模型，以应急物流系统消耗总时间最少为上层目标，以配送成本和时间惩罚成本之和最小为下层目标。根据该模型上下层独立决策而又相互影响的特点，设计了一种带启发式规则的两阶段混合模拟退火算法，一阶段禁忌搜索确定可行应急配送中心集合，贪婪就近原则构建初始解，交换编码搜索邻域可行解，记录并更新过程最优解，累加装卸和行驶时间并随最优解输出作为上层决策的依据。最后给出算例和对比算法，验证了模型的有效性和算法的可行性。

应急物流；设施定位-运输路线；双层规划；禁忌搜索；模拟退火算法

1 引言

我国是世界上受自然灾害最为严重的国家之一，各类重大自然灾害如洪涝、地震等时有发生，受灾规模动辄上万人，给人民生活造成重大影响的同时，也给灾后应急物资的有效配送提出了难题。近年来，应急物流已经形成政府高度重视，企业积极参与的特点，给设施定位-路线安排问题提供了新的解决思路。

应急物流系统的优化问题是近年来研究热点之一，主要的研究内容有集散中心和配送中心选址问题、物资配送问题、系统鲁棒性问题等，每一类问题中又包含若干小问题。Jia Hongzhong等[1]对大规模突发事件医疗用品供应的最大覆盖选址问题进行了研究，考虑到需求的不确定性和医疗用品供应不足等因素，给出了结合拉格朗日松弛和遗传算法的启发式方法。刘波等[3]研究了需求和路网不确定下的应急物流系统优化问题，采用协同配送的方式建立了鲁棒双层规划模型，通过分散决策将不确定性系数转化为确定性，并提出混合遗传算法解决该类模型。Alem等[4]对位置和需求信息模糊的应急物流配送问题进行了研究，构建了基于风险偏好值的两阶段随机规划模型，考虑时效性并结合实际案例给出了有效的解决方案。

不少学者对灾后应急物流系统的设施定位-运输路线问题进行了深入研究，王绍仁等[5]考虑了应急物流的动态性、需求不确定性、道路连通性等因素，将不确定因素表达为一定置信水平模糊约束，建立了以物流总成本为目标函数的LRP模型，在算法设计中用动态规划将多周期转换成单周期模型，运用改进遗传算法求解模型。文中提出的大需求点分割策略很有实际意义，但是以概率方式处理需求长期来看可能效果较好，而应急物流配送往往是短期行为。刘长石等[6]借鉴了王绍红和马祖军[5]的大需求点分割处理方式和模糊需求的概率选择，以总配送时间最短和总配送成本最小为目标构建多目标优化模型，并给出免疫遗传算法。然而文中对多目标的处理不合理，并未对时间和成本之间的重要性进行比较，仅对比了仿真结果中几组非劣解。对带模糊参数的选址-路径问题，张晓楠等[8]给出了另一种建模及求解思路，即预优化-实时调整的两阶段策略，并以配送成本和时间惩罚成本为目标函数建立随机规划模型。王绍仁等[9]在确定性需求下以系统响应总时间为目标对应急物流LRP问题进行了分析，给出“三角”启发式算法，具有一定借鉴意义，但算法的适用范围较小，且收敛性有待证明。

应急物流是由政府和企业多方参与的物流活动，仅仅考虑一方的决策目标显然比较片面。郑斌等[14]考虑在需求不确定的前提下，以应急物资送达时间最短为上层目标，物资分配公平性最大为下层目标对配送系统建立双层规划模型，并给出两阶段遗传算法，即上层给出配送任务的同时下层求出车辆的配送路径。和其他双层规划算法类似，该算法在上下层规模较大的情况下收敛速度慢，且对需求以期望的方式处理，并不能满足特定救援点的需求。Zhang Xiang等[16]、黄正海等[18]分别对双层规划模型分散决策和相互影响的特点，以及不同模型适用的算法进行了较有借鉴意义的研究。

综上所述，研究应急物流系统的文献中，一部分以物流网络成本最低、系统耗时最少等为目标建立单目标模型[5,9]，另一部分虽然考虑多目标，如耗费时间和配送成本、配送时间和分配公平性等[6,14]，但并未从不同决策者的角度出发。在政府和企业共同参与的背景下，政府考虑应急系统耗费总时间最少，企业希望系统总成本最小。为此，本文在考虑应急物流时效性特点的基础上，结合道路连通状况，在满足各救援点需求的前提下，构建以系统总响应时间最短为上层目标、以配送成本和时间惩罚成本最小为下层目标的双层规划模型，分析双层规划模型上层决策受下层执行的影响，考虑需求量和各配送中心容量限制，采用隐枚举法求得可行配送中心集合，并以启发式插值法求得可行初始解，设计带累加记忆的模拟退火算法，以交换编码搜索领域可行解的方式寻找下层最优解，同时累加所得每条配送路线的总时间作为上层规划的目标值。

2 问题描述

自然灾害发生后，为了便于救援，需要从灾区周边选择几个合适的配送中心，救援物资先到达配送中心，然后进行集配，根据各救援点需求量的不同，对其进行配送。对需求量大、体积较大的应急物资如棉被、粮食、饮用水等，常采用直接配送的方式进行；对另一些紧急需求但体积较小的物资如照明设备、食盐、药品等，则采用巡回配送的方式。

本文作如下假设：

(1)考虑某些需求紧急但体积较小物资的巡回配送；

(2)应急物资足够，且车辆数足够；

(3)应急配送中心到救援点以及救援点两两之间均存在可行路径；

(4)各救援点的需求必须得到满足，且只能由一辆车配送；

(5)各救援点都有两个时间点，即期待在此之前被配送的时间点和最晚被配送的时间点；

(6)配送车辆从某配送中心出发，配送完后必须回到该配送中心。

3 模型构建

3.1 符号说明

D= {p|p=1,2,…,P}、DQp表示应急配送中心集合以及配送中心p的容量；

C= {r|r=1,2,…,R}、CQr表示应急物资需求点集合以及需求点r的需求量；

U=D∪C表示所有节点的集合；

V= {k|k=1,2,…,K}、VQk表示配送中心车辆集合以及车辆k的容量；

TDp表示配送中心p投入使用的准备时间；

TVk表示车辆k单位物资装卸花费的时间；

ETr表示需求点r期待物资到达的时间点；

LTr表示需求点r要求物资到达的最晚时间点；

Tr表示需求点r被服务的时间；

vk表示车辆k的平均行驶速度；

dij表示节点i到j的最小行驶距离；

aij表示平面距离与最小行驶距离之间的转换系数，aij=aji，且aij≥1；

SDp表示配送中心p投入使用前的建设成本；

SVk表示车辆k的派遣成本，包括配对的人员成本；

SL表示单位物资到达需求点的装卸成本；

SU表示配送车辆的单位距离运输成本；

SFr表示需求点被配送时超出ETr下的惩罚成本；

h表示单位物资惩罚成本；

g表示时间窗内惩罚成本随时间的变化系数决策变量：

uk：车辆k投入使用则取1，否则取0；

xp：备选配送中心p被选中则取1，否则取0；

yrp：应急需求点r分配给投入使用的配送中心p时取1，否则取0；

zijk：车辆k从节点i驶向j则取1，否则取0。

对符号做一点补充说明。考虑无孤立需求点的应急物流配送问题，总是存在一个非无穷大的常数aij，使得任意点j到某点i的可行路径存在。显然这是符合现实的，任意两地之间不管曲直，总存在可到达路径。

3.2 模型建立

上述应急物流系统设施定位-运输路线问题可以用双层规划模型描述：

上层模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

U=C∪D,xp∈{0,1},yrp∈{0,1},zijk∈{0,1}

(11)

上述模型中，目标函数(1)表示最小化系统响应时间，由配送中心准备时间、物资配送过程中的装卸时间和车辆运输时间三部分组成；式(2)表示配送中心的容量约束；式(3)表示每个需求点只被一个配送中心服务；式(4)表示每个需求点被且仅被服务一次；式(5)表示配送车辆的容量约束；约束式(6)保证配送路线的连续和闭合，进入每个节点的车辆必须从该节点离开；式(7)表示每辆车至多只分配给一个配送中心；式(8)表示每个被选中投入使用的配送中心都有可支配车辆；式(9)表示任意两个配送中心之间无连接；约束(10)表示从某配送中心出发的车辆最后必须回到该配送中心。

下层模型

(12)

zijk≤uk,∀i,j∈U

(13)

(14)

(15)

(16)

除此之外，上层模型的约束同样也是下层模型的约束。模型中，目标函数(12)由五部分组成，分别是配送中心建设成本、车辆人员派遣成本、物资装卸成本、车辆运输成本和时间窗惩罚成本；式(13)表示对配送车辆的约束，车辆k投入使用的情况下才可能存在k的运输服务；式(14)表示对从配送中心出发的车辆的时间窗约束；式(15)表示车辆巡回配送过程中的时间窗约束；式(16)表示车辆到达需求点的时间点。由于上层规划中每确定一个最优方案，总能确定xijk，yrp的取值，因此下层约束中出现两者取1的情形。

其中时间惩罚成本函数表达如下：

(17)

惩罚函数的参数中包含了需求量，这是符合实际意义的，惩罚成本与需求量之间存在线性正相关关系。约束条件中已存在各需求点被服务时间不超过时间窗上限，故时间惩罚成本自变量的范围在期待时间点和可容忍时间点之间。

4 算法设计

上述模型是一个典型的混合整数双层规划模型，属于NP-hard问题，不存在精确求解算法，许多文献对求解双层规划模型的高效算法进行了研究。对非线性双层规划问题，下降方向法是较常用的一种；对线性双层规划问题，求解的方法较多，如极点搜索法、互补旋转法、罚函数法等。然而以上算法在原理上大多要求目标函数在可行域或分块领域内连续，因此对混合整数双层规划问题而言，智能优化算法的应用更为广泛。

上层决策者设施定位的目的是使得应急物流系统总响应时间最短，仅就上层模型而言，在备选配送中心数量不大的情形下，运用优化算法可求得最优应急配送中心集合。考虑到下层决策者在运输路线安排方面有充分的自主权，因此所选择的配送中心集合往往不能达到上层决策者的理想程度，甚至偏差很大，这也是双层规划问题通常不能逐层独立求解的原因。对应急物流系统而言，备选配送中心和选中配送中心的数量并不会太多，否则就失去了集中配送的意义，且当所选中配送中心的容量足以满足所有救援点需求的情况下，其余的配送中心不会被投入使用，否则不但增加上层规划中配送中心投入使用的准备时间，而且增加下层规划中配送中心的建设成本。

基于以上模型的特点和实际问题的意义，设计了一种结合禁忌搜索技术的两阶段混合模拟退火算法进行求解。

阶段一：建立禁忌表，以交换编码方式确定可选配送中心集合。

步骤1对每个备选配送中心进行编号；

步骤2从备选配送中心里按编号依次选择直至被选中配送中心总容量超过救援点总需求量，按实际距离最短原则对救援点进行初始划分，即将救援点依次划分给距离其最近的被选中的配送中心，若超出该配送中心容量则划分给下一个近距离配送中心，以此类推。若有救援点未被分配，则从余下的备选配送中心中选择到这些救援点总距离最小的配送中心放入被选中集合；

步骤3建立禁忌表，将初次选中的配送中心集合放入禁忌表，禁忌规则为不允许出现包含此配送中心集合的集合；

步骤4对已选择的配送中心集合进行换出换入处理，即从中换出一个并且从未被选择的配送中心里换入一个，满足步骤2条件和禁忌要求，并将新的集合放入禁忌表；

步骤5重复步骤4，直至对初始集合里的每个对象都遍历完换入换出步骤。

阶段二：根据阶段一给出的禁忌表，采用启发式规则构造初始解，带记忆累加的模拟退火算法求得每组集合对应的最小成本和总配送时间。

(1)初始解构造。在上一阶段救援点的分配中已经考虑到各救援点到被选中配送中心的距离，类似于聚类法，对救援点的划分较为合理。采用贪婪就近原则构造初始解，对某救援点是否被某辆车配送的判断准则为该救援点需求量不大于配送车辆的剩余容量，且车辆到达时间早于时间窗上限。

(2)模拟退火算法的设定。采用目标函数值评价解的优劣，每条线路上的救援点以两两互换的方式搜索邻域，同时确定降温速度。

(3)路线再调整。对于只服务个别救援点的车辆，判断能否将这些救援点插入别的线路，判断准则为车辆剩余容量、对应配送中心剩余容量、时间窗上限和目标函数。

(4)记忆装置的设计。算法运行中设计一个记忆数组，记录和比较每次邻域转换后目标函数的值，不断更新确保输出的是搜索过程中的最优解。

(5)累加装置的设计。设计一个累加器，对每个救援点的装卸时间和车辆行驶时间进行累加，得到每个配送中心集合最优成本方案下的总配送时间。

(6)终止准则的确定。设定最低温度，当下降到该温度时，算法终止。

图1 算法流程图

5 算例分析

随机给出4个备选应急配送中心，20个灾区救援点，本文研究的问题为一次性应急配送，非多周期多阶段活动，因此车辆数量足够。随机模拟方法生成各救援点坐标及需求量，其中坐标对应单位是公里。定义转换系数aij=1.5，车辆容量800件，派遣费600元/辆，行驶速度90km/h，装卸成本1元/件，卸货时间为0.1min/件，运输成本为1元/km，时间惩罚成本为1元每件每小时。备选配送中心编号、平面坐标、容量等信息如表1所示，各救援点平面坐标、需求、时间窗等信息如表2所示。

表1 备选应急配送中心信息

表2 救援点信息

模拟退火算法的主要参数有初始温度、终止温度、降温函数、邻域选择策略等，许多文献从理论研究、数值分析的角度证明了对不同规模的问题，设定参数的大小对收敛性的影响。鉴于本算例中各条运输路线车辆所服务的救援点不多，取初始温度T0=28，终止温度Tf=1，降温函数定义为Tk+1=Tk-△T，降温步长△T=3，内循环次数设置为n(Tk)=5。一阶段禁忌搜索得应急配送中心可行集合，模拟退火算法求得各可行集的最优配送路线及总配送时间，计算结果及车辆配送路线如表3-7所示。

表3 可行集合{A,B}

表4 可行集合{A,C}

表5 可行集合{A,D}

表6 可行集合{B,C}

表7 可行集合{C,D}

基于上层优先决策并考虑在此基础上下层自由安排路线的原则，选择应急配送中心B和C为最佳LRP方案。

由于混合整数双层规划模型具有递阶决策的结构特性，无法用传统算法求解，本文采用郑斌等[14]设计的混合遗传算法求解，与两阶段模拟退火算法进行对比。对备选配送中心编号，基因位取0或1来表示是否选中该配送中心，当已选配送中心容量小于总需求量时，随机选中未被选择的配送中心，选择下层目标函数作为适应度函数，即系统总成本和时间惩罚成本之和，采用轮盘选择和精英保留结合的选择策略，设置最大迭代次数，每次迭代结束输出总成本和总时间，然后对选中的配送中心换入换出处理，直到遍历完所有可行集合产生重复，算法终止，选择其中总时间最少的解作为最优方案，对应的总成本即为下层模型的目标值。混合遗传算法求解最优结果如下表所示。

表8 选址集合{B,C}

对比可知，所设计的两阶段模拟退火算法效果较好，无论是耗时还是成本都好于混合遗传算法，且由于没有禁忌表来产生可行配送中心集合，混合遗传算法运行中出现多个显然不是最优解的包含三个配送中心的迭代，运行效率较低。

6 结语

本文针对应急物流由政府和企业共同参与的表现形式，研究了灾后设施定位-运输路线安排问题，提出一个上层以应急物流系统总耗时最短、下层以配送成本和时间惩罚成本最小的双层规划模型，以此对物流系统决策分析。根据上下层独立决策又相互影响的特点，设计了带禁忌搜索的混合模拟退火算法，并结合算例和对比算法验证所设计算法的可行性。

本文研究了确定性需求下对救援点进行巡回配送的LRP，未考虑多配送方式以及动态需求下的配送，进一步的研究还要考虑多车型混合配送以及动态需求下的多阶段配送等问题。

[1] Jia Hongzhong, Ordonez F, Dessouky M M. Solution approaches for facility location of medical supplies for large-scale emergencies [J].Department of Industrial and Systems Engineering, 2007, 52(2):257-276.

[2] Doyen A, Aras N, Barbarosoglu G. A two-echelon stochastic facility location model for humanitarian relief logistics [J].Optimization Letters, 2011, 6(6):1123-1145.

[3] 刘波,李波,李砚.不确定条件下应急物流系统鲁棒双层优化模型[J].统计与决策,2014, 9(23):40—43.

[4] Alem D, Clark A, Moreno A. Stochastic network models for logistics planning in disaster relief [J] .European Journal of Operational Research, 2016, 21(28): 1-20.

[5] 王绍仁,马祖军.震后应急物流系统中带时间窗的模糊动态LRP[J].运筹与管理,2011, 20(5):63—72.

[6] 刘长石,彭怡,寇纲.震后应急物资配送的模糊定位-路径问题研究[J].中国管理科学,2016, 24(5):111—118.

[7] Pramanik S, Jana D K, Maiti M. Bi-criteria solid transportation problem with substitutable and damageable items in disaster response operations on fuzzy rough environment [J].Socio-Economic Planning Sciences, 2016(C), 55:1-13.

[8] 张晓楠,范厚明,李剑锋.变动补偿的多模糊选址—路径机会约束模型及算法[J].系统工程理论与实践,2016, 36(2):442—453.

[9] 王绍仁,马祖军.震害紧急响应阶段应急物流系统中的LRP[J].系统工程理论与实践,2011,30(8):1497—1507.

[10] Sheu J B, Pan Cheng. Relief supply collaboration for emergency logistics responses to large-scale disasters [J].Transportmetrica A: Transport Science, 2015, 11(3): 210-242.

[11] 侯玉梅,贾震环,田歆.带软时间窗整车物流配送路径优化研究[J].系统工程学报,2015, 30(2):240—250.

[12] Vincent F. Yu, Parida Jewpanya, Voratas. Particle swarm optimization for the multi-period cross-docking distribution problem with time windows [J] .International Journal of Product Research, 2016, 54(2):509-525.

[13] 丁佩雯,蒋祖华,胡家文.带有交货期时间窗的生产与维护联合调度优化[J].上海交通大学学报,2015, 49(4):524—530.

[14] 郑斌,马祖军,李双琳.基于双层规划的应急物流系统选址—联运问题[J].系统科学与数学,2013, 33(9):1045—1060.

[15] Zhang Jingling, Wang Wanliang, Zhao Yanwei, et al. Multi-objective quantum evolutionary algorithm for the vehicle routing problem with customer satisfaction [J].Mathematical Problems in Engineering, 2012, 10: 1-19.

[16] Zhang Xiang, Wang Hao, Wang Wei. Bi-level programming model and algorithms for stochastic network with elastic demand [J] .Transport, 2015, 30(1):117-128.

[17] 周晓阳,赵璨晖,鲁渤.不确定条件下基于分散式双层规划的绿色协同港口物流系统优化[J].中国管理科学,2015, 23(S1):262—268.

[18] 黄正海,林贵华,修乃华.变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J].运筹学学报,2014, 18(1):113—133.

Bi-level Programming Model and Algorithmof Location-routing Problem in Emergency Logistics

LOUZhen-kai

(School of Management and Economics, Beijing Institute of Technology, Beijing 100081,China)

To optimize emergency logistics distribution system for natural disasters like floods and earthquakes, a bi-level programming model of location allocation-vehicle routing problem is set up by considering the characteristics that government and enterprises participate together but make decision separately. The upper level is to minimize the total time of emergency logistics system, and the lower level is to minimize the sum of distribution costs and time penalty cost. According to the characteristic of independent decision-making and interaction effect in upper and lower level in the model, the problem is broken up into two stages. In the first stage, viable gathers of distribution center are produced. In the second stage, vehicles and transport routes are arranged under viable gathers. A heuristic rule of two stage hybrid simulated annealing algorithm, one-phase tabu search,is designed to determine feasible emergency distribution center collections. The initial solution is construeted by principle of greedy proximity. Code is exchanged to search neighborhood feasible solution. The optimal solution is recorded and updated unloading and driving time is accumulated and output as the basis of the upper decision. Finally a numerical example and the comparing hybrid genetic algorithm are given to verify the validity of the model and the feasibility of the algorithm. A solution for emergency logistics system planning problem of multi-level decision is provided.

emergency logistics system; location allocation-vehicle routing; bi-level programming; tabu search; simulated annealing algorithm

1003-207(2017)11-0151-07

10.16381/j.cnki.issn1003-207x.2017.11.016

F252

A

2016-07-29；

2017-02-27

楼振凯(1989-)，男(汉族)，浙江浦江人，北京理工大学管理与经济学院博士生，研究方向：决策理论优化算法，E-mail：07224014@bjtu.edu.cn.