韦晓 WEI Xiao；常相全 CHANG Xiang-quan
（School of Management，University of Ji´nan，Ji´nan 250022，China）
摘要： 在静态路径优化问题的基础上，本文引入了动态规划思想，将道路阻塞情况与受灾点需求信息不断更新等因素考虑进来，构建了动态需求条件下的应急物流路径优化模型。结合相关研究成果探讨了模型的求解思路，并利用改进的蚁群算法进行算例分析，得出了动态更新的优化路径，验证了模型的有效性。
Abstract: Based on the static path optimization, this paper brings in the idea of dynamic planning. It considers the factors such as the road congestion and the constantly updated demand information of disaster-affected area to build the emergency logistics path optimization model under the condition of dynamic demand. Combined with the related research results, this paper discusses the thinking of solving the model and analyzes the examples by the advanced ant colony algorithm to obtain the dynamic update of optimized path and verify the validity of the model.
教育期刊网 http://www.jyqkw.com
关键词 ： 应急物流；动态路径优化；蚁群算法
Key words: emergency logistics；dynamic path optimization；ant colony algorithm
中图分类号：TP18 文献标识码：A
文章编号：1006-4311（2015）06-0024-03
0 引言
基于现实条件的限制，当大规模自然灾害突发以后，相关部门第一时间得到的信息往往是模糊的、不确定的。随着道路情况、受灾点需求等信息的不断更新，应急物流路径优化的决策也应随时进行调整，这就是本文要研究的动态需求条件下的路径优化问题，也可称为“实时”问题或“在线”问题，但国内外相关文献研究中使用“动态”问题的描述更为广泛。1977年，Wilson和Colvin研究了顾客如何搭载车辆到达目的地的问题，这是首次将动态特性与VRP问题结合的文献[1]；Potvin（2006）[2]、Xiang（2008）[3]等通过考虑不同的动态因素，提出了相应的调配策略；Guner[4]（2012）、饶卫振[5]（2013）等针对不同起讫点的路径优化问题，建立了具有模糊需求的动态多目标约束规划模型。本文在分析国内外相关研究成果的基础上综合考虑了四种动态事件，建立了动态路径优化模型，为动态规划理论在该领域的应用提供了相关理论依据；通过算例分析验证了模型的有效性，可以更加适用于实际灾情发生后信息不断更新的情况，为动态事件发生后如何优化配送方案提供了有效参考。
1 问题描述
静态需求条件下的路径优化问题是应急物流领域的热点问题，也是本文研究的动态路径优化问题的基础，可以简单描述为：大规模自然灾害发生后，假设受灾地区的需求信息是确定的并可以一次性得到的，相关救援部门根据第一时间获取的灾情信息制定救援方案，从临时中转站调配车辆完成配送任务。静态需求条件下的路径优化模型有时间和成本两个目标：
1.1 时间最小化目标
目标函数（1）为模型第一目标，即保证运载过程中的物资运输时间总和与未满足时间窗限制的惩罚最小。对于突发自然灾害来说，各灾区对于救援物资响应时间的要求是较高的，随着时间的推移，需求的重点转化为对物资数量的要求。
1.2 成本最小化目标
目标函数（2）的目标是追求运载过程的总成本最小，包括车辆固定成本与变动成本两方面。
在实际突发自然灾害中，信息总是不断更新的，本文在此基础上考虑了四种情况下的动态信息：①出现新的受灾点；②原有受灾点改变需求信息；③原有受灾点撤销应急需求；④道路阻塞。静态和动态应急物流路径优化问题的区别在于，前者假设灾害发生后的需求信息是确定的，其物资配送方案是配送前一次性求解得到的；而动态需求条件下的应急物流路径优化问题需要基于灾害初始时刻的已知信息求解得到初始配送方案，进而在执行的过程中将不断更新的信息考虑进来，产生新的配送方案。假设在配送的过程中共有M次新信息的出现，则求解的过程就是M+1次。因此，动态需求条件下的应急物流路径优化问题可以看成是在出现新信息的时刻点分别将新的因素考虑进来，得出新的优化配送方案。静态与动态应急物流车辆路径问题的对比分析如图1所示。
从图1可以看出，动态问题的初始求解是基于静态问题的，而当新信息出现后，运载物资的车辆正在执行初始的配送方案，如何调整配送方案使之达到全局最优就是本文需要解决的问题。
2 动态需求条件下的路径优化模型
由上述分析可知，建立动态需求条件下的路径优化模型，就等价于建立能够表示M+1个静态车辆路径问题的模型，具体来说就是在M个动态事件发生的时刻点{EventTime1，EventTime2…EventTimem}下，动态路径优化模型的求解会分别对应M个静态路径优化问题。
因此，本文的动态路径优化模型的最终解是M+1个静态路径优化问题在时刻点{EventTime1，EventTime2…EventTimem}下的组合。
2.1 模型假设 为了更好地描述和理解灾后需求不断更新的路径优化模型，模型的构建应满足如下假设：
①只考虑一个受灾分组内的需求点物资配送信息，即所有配送车辆从同一个中转站出发，中转站坐标已定。
②每个受灾点的物资需求都只由同一辆车供应，且需求点的需求量小于车辆的载重。
③只考虑局部道路阻塞问题，即不考虑大面积交通瘫痪致配送方案无法执行的问题。
④整个救援任务以所有需求点的需求量得到满足为止。
⑤运载车辆的平均速度是已知的。
2.2 模型构建 动态需求条件下的路径优化问题在时刻点t下的模型是一个多目标优化模型，根据上述分析，结合动态规划的原理和已构建的静态路径优化模型，现构建动态路径优化模型如下：
Obj fd=ft0-tE+optftE-te（3）
式（3）为本文建立的动态路径优化模型，其中t0为配送方案开始的时刻点，tE为配送过程中新的动态信息Eventm出现的时刻点，ft0-tE表示从配送方案开始到动态信息出现的过程中，配送车辆按静态路径优化模型得出的优化方案所执行得到的最优解；te为整体配送方案结束的时刻点，ftE-te表示动态信息出现后根据静态路径优化模型所得到的新的配送方案，新的动态事件可能有M种，其中用d（t）表示t时刻点的动态信息，是一个离散函数。
d（t）=dt t=0，1，2…end（4）
在物资配送过程中，原有信息不断更新，本文考虑的动态信息包括四类：①出现新的受灾点；②原有受灾点改变需求信息；③原有受灾点撤销应急需求；④道路阻塞。
3 模型求解思路
针对以上分析，形成了适用于本文构建动态路径优化模型的求解思路：将动态路径优化问题看成M+1个静态问题，即接收动态事件后，将新信息替换原有信息得到一个新的静态路径优化问题，在每次动态事件发生后整合接收的新信息，从全局角度出发重新优化配送方案。
通过引用关于静态需求条件下路径优化问题设计的改进蚁群算法，结合动态路径优化模型的特点，本文设计的算法步骤如图2。
4 算例分析
4.1 问题的初始条件 在静态需求条件下的应急物流路径优化问题中，通过考虑临时中转站与受灾点坐标、灾情等级、受灾点需求信息等数据，将15个受灾点分成两个受灾分组，利用设计的改进蚁群算法进行了相关分析，最终的总目标函数值是由5条子路径的目标函数值分别相加并赋予权重获得：f1=3004，f2=8035；0.7f1+0.3f2=4513.3。并将改进蚁群算法的改进之处分别限制从而构造了另外两种蚁群算法进行比较，证实了改进蚁群算法的优越性。
图3为静态路径优化问题其中一个受灾分组得到的最优解，即本文动态路径优化问题的初始配送方案。初始最优解的车辆数目为3，临时中转站为Ⅰ。子路径1：Ⅰ→8→3→9→1→Ⅰ；子路径2：Ⅰ→4→7→6→Ⅰ；子路径3：Ⅰ→2→5→Ⅰ。
现对配送过程中发生的动态事件进行假设如下：
①在EventTime1（3）时刻，受灾点3和4改变应急需求，其中受灾点3对物资1和物资2的需求量更新为（3；5），受灾点4对物资1和物资2的需求时间窗更新为（7；9）；
②在EventTime2（6）时刻，受灾点9撤销应急物资需求；
③在EventTime3（9）时刻，受灾点1和5之间的道路阻塞，经过5个时间段后修复完好，这一过程中车辆选择继续等待或者寻找新的路径；
④在EventTime4（10）时刻，新的受灾点10和11提出应急需求，其中受灾点10的坐标为（14，8），对物资1和物资2的需求量为（5；4），时间窗为（9；6），受灾点11的坐标为（18，22），对物资1和物资2的需求量为（14；10），时间窗为（8；9）。
4.2 实验结果分析 本算例中设定车辆的平均行驶速度为1，车辆的载重负荷为65吨，车辆行驶的固定成本为500元/辆，车辆行驶的变动成本为50元/小时，时间窗限制的惩罚系数假定为100元/小时。本算例中设定改进蚁群算法的参数如下：迭代次数为200，种群大小为20，α=2，β=2，ρ=0.5，Q=1，τmin=3，τmax=10。
将上述设定的实际问题的初始条件代入本文建立的动态路径优化模型中，并根据上述模型求解思路的分析求解算例，结果如下：
①t0时刻的配送方案已知，在EventTime1（3）时刻，子路径1中受灾点8已完成配送，下一配送点为3；子路径2中受灾点4即将接受配送；子路径3中受灾点2即将接受配送。
根据更新的信息，当前时刻最优解的车辆数目为3，子路径1：Ⅰ→8→3→9→1→Ⅰ；子路径2：Ⅰ→4→7→6→Ⅰ；子路径3：Ⅰ→2→5→Ⅰ。
②在EventTime2（6）时刻，子路径1中受灾点8、3已完成配送，下一配送点为9；子路径2中受灾点4已完成配送，下一配送点为7；子路径3中受灾点2即将接受配送。
根据更新的信息，当前时刻最优解的车辆数目为3，子路径1：Ⅰ→8→3→1→5→Ⅰ；子路径2：Ⅰ→4→7→6→Ⅰ；子路径3：Ⅰ→2→Ⅰ。
③EventTime3在（9）时刻，子路径1中受灾点8、3已完成配送，下一配送点为1；子路径2中受灾点4、7已完成配送，下一配送点为6；子路径3中受灾点2即将接受配送。
根据更新的信息，当前时刻最优解的车辆数目为3，子路径1：Ⅰ→8→3→1→Ⅰ；子路径2：Ⅰ→4→7→6→Ⅰ；子路径3：Ⅰ→2→5→Ⅰ。
④在EventTime4（10）时刻，子路径1中受灾点8、3已完成配送，下一配送点为1；子路径2中受灾点4、7已完成配送，下一配送点为6；子路径3中受灾点2已完成配送，下一配送点为5。
根据更新的信息，当前时刻最优解的车辆数目为4，子路径1：Ⅰ→8→3→1→11→Ⅰ；子路径2：Ⅰ→4→7→6→Ⅰ；子路径3：Ⅰ→2→5→Ⅰ；子路径4：Ⅰ→10→Ⅰ。
由上述假设可知，在时刻点EventTime4（10）后不再有动态事件出现，配送方案执行至结束。最终解的最优路径如图4所示。
最终的总目标函数值是由4条子路径的目标函数值分别相加并赋予权重获得：
f1=4631.5，f2=6510
0.7f1+0.3f2=5195.1
从上述实验结果可以看出，动态需求条件下的应急物流路径优化问题比较复杂，最终解的值要大于相同数据下静态路径优化问题的值，这是因为在动态需求条件下，配送方案是不断修正并更新的，车辆可能会在两个受灾点之间时接受新的配送方案，从而修正原路径，因而会增加时间和成本。
5 结论
本文在静态需求条件下路径优化问题的基础上，根据实际应急物资配送过程中会不断有信息更新的情况，构建了动态路径优化模型。结合改进蚁群算法解决静态路径优化问题的特点，本文分析了动态路径优化模型的思路，并通过相应的算例分析了四种动态事件发生后配送方案的更新过程，以此证实了本文构建动态路径优化模型的有效性，为实际灾情发生时相关部门的决策提供了参考。
教育期刊网 http://www.jyqkw.com
参考文献：
[1] WiIson N，Colvin N. Computer control of the rochester dial-a-ride system[Z].Cambridge，Massachusetts，1977.
[2]Potvin J Y，Ying X B，Benyahia H. Vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research，2006，33(4): 1129-1137.
[3]Xiang Z H，Chu C B，Chen H X. The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments[J]. European Journal of Operational Research，2008，185(2): 534-551.
[4]Guner A R，Murat A，Chinnam R B. Dynamic routing under recurrent and non-recurrent congestion using real-time its information[J]. Computers & Operations Research，2012，39（2）：358-373.
[5]饶卫振. 大规模动态车辆路径问题优化方法研究[D].大连理工大学，2012.
[6]王旭，葛显龙，代应.基于两阶段求解算法的动态车辆调度问题研究[J].控制与决策，2012， 27(2); 175-181.
[7]A.D. López-Sánchez, A.G. Hernández-Díaz, D. Vigo, et al. A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem[J]. European Journal of Operational Research, 2014,238(1):104-113.