应急救援物资与伤员协调转运的两阶段调度优化模型研究＊

易宣齐 胡志华

（上海海事大学物流研究中心1） 上海 201306） （同济大学经济与管理学院2） 上海 200331）

灾害事件给人们的生命、财产、安全造成巨大的伤害，为了减少这些灾害事件对人类所产生的影响，越来越多的研究人员对此进行研究［1－3］.应急物流是为了满足应急情形下受灾群体紧急需求，对从供给点到需求点的救援物资、信息及服务进行计划、管理与控制的过程［4］.由于灾害事件发生的时间和地点，以及受灾程度难以预测，因此，应急物流的主要挑战有［5］：运输与需求的不确定性；复杂的沟通和协调；难以实现高效及时的交货；有限资源无法满足大规模的需求.由于应急物流的特殊性，应急物流更强调物流效率与社会效益，而非经济效益.

多供应点多需求点的运输问题可以按需求量大小分为两类：一类是每个点需求量较小，车辆每次要经过多个点，主要考虑怎样安排每辆车对需求点的访问顺序以及由此构成的访问路线，属于车辆路径问题［6］；另一类是由于供需点的供应量和需求量都很大，一般要往返多次才能完成，车辆每次都从供应点直达需求点，主要关注各供应点向各个需求点分配货物的比例问题，成为多点运输问题［7］.

应急物流运输优化的目标主要分2类：配送时间或配送成本的最小化［8－9］；未满足需求最小化，如最小化所有救援物资需求和伤员转运需求的未满足率［10］.为了避免有些灾点在全局优化中被忽略，徐志宇，彭嘉臻等则在总的成本最小、需求未满足率最低的基础上加上了失衡度最小这一目标［11］.

在应急物流管理中，受灾点的需求有2大类：救援物资需求；伤员转运需求.如果按照救援方向来分，则可分为正向救援和逆向救援.正向救援满足受灾点的物资需求，而逆向救援满足伤员的转运需求.本文基于直运的方式，以最小化运输时间为目标，通过对物资伤员的协调转运，可以大大减少救援的时间以及救援成本，达到很好的救援效果.

1 问题定义

受灾点的需求可以划分为救援物资需求和伤员转运需求.它们代表2个方向的资源流动，物资是从救援中心到受灾点，而伤员是从受灾点到受灾点.因为在实际救援中，受灾点对各种物资的需求量以及伤员的转运量是巨大的、不均匀的且具有动态性，本文把受灾点的两种需求单元化，即需求的量以车为单位.车辆的运输方式是直运，因此，节点之间的物流运输情况有图1所示的4种类型.流向1中，车辆从救援中心搭载物资到受灾点，然后载伤员返回；流向2中，车辆从救援中心搭载物资到受灾点，然后空车返回；流向3中，车辆从救援中心空车前往受灾点搭载伤员然后返回救援中心；流向4中，车辆从救援中心搭载物资到受灾点，然后空车赶往最近的受灾点搭载伤员返回救援中心.

图1 物资和伤员转运流向图

应急救援过程中，时间和运输车辆都是稀缺资源.时间成本和运输资源成本是评价调运方案的主要指标.短时间内要在各个节点之间充分利用物流资源，进行应急资源和伤员人员的协调调运，那么协调调运模型和算法的有效性成为应急物流的关键.本文就是基于直运的方式以及上述的4种转运流向，在所有的可行路中选出物资和伤员的转运最优路线，完成车辆的调度优化.

2 模 型

2.1 两阶段方法

应急物流模型主要分成2阶段：在第一阶段，基于物资和伤员转运的4种流向，生成所有的可行路线；在第二阶段，选择部分路线，覆盖所有需求，且最小化总路线的数量和总的运输时间.由此可看出，第二阶段选择的最优路线是第一阶段生成的可行路线的子集，见图2.为了方便和有效研究本文的2阶段问题，问题通过以下条件进一步界定：（1）救援中心的物资供应充足，能够满足所有受灾点的需求；（2）救援中心有足够的车辆，且所有的车辆的出发点和终点都是救援中心；（3）所有救援车辆的速度是相同的，且救援能力也一致；（4）所有的节点之间能够相通；（5）车辆在节点的滞留等待时间不计；（6）通过单元化运输满足需求.

图2 2阶段方法

2.2 可行路线生成算法

路线生成算法主要是根据直运的规则以及物资和伤员转运的4种流向，生成所有的可行路线的一种算法.以下简要说明2阶段方法中各符号所代表的含义.

1）集合

定义C＝｛1，2，…，NC｝为所有节点的集合.其中：NC 为节点数量，包括受灾点和救援中心.CS∈C，表示救援中心.

定义D＝｛1，2，…，ND｝为所有需求的集合，共有ND 个需求.需求的类型有2 种，包括救援物资转运需求和伤员转运需求.其中1为物资转运类需求；2为伤员转运类需求.

CD⊂C，表示受灾节点的集合.物资转运类需求的节点构成集合M，伤员转运类集合的节点构成集合W.

定义R＝｛1，2，…，NR｝为所有可行路线的集合，一共有NR 条.

2）参数 v为车辆的速度；RTk（k∈R）为第k条路线的时间.

3）决策变量

xi∈｛0，1｝ 其中i∈M.当xi＝1表示满足第i个物资转运需求，否则xi＝0.

yi∈｛0，1｝ 其中j∈W.当yj＝1表示满足第j个伤员转运需求，否则yj＝0.

可行路线生成算法见算法1.

算法1 （可行路线生成）

输入 C，CD，CS，D，M，W；v

输出 R；RT

处理

步骤2 由xi＋yj＝1，∀i∈M，j∈W，可得到图1中流向为（2）、（3）的满足一个需求的转运路线ND 条.

步骤3 由xi＋yj＝2，∀i∈M，j∈W，可得到图1中流向为（1）（4）的满足两个需求的转运路线m·（ND－m）条.其中n为物资转运需求的数量.至此，得到了路线集合R，一共有NR 条路线，且NR＝ND＋m·（ND－m）.

步骤4 根据公式t＝d／v，求出车辆在每条路线上的转运时间，于是可得参数RTk，k∈R.

2.3 最优路线组合优化模型

1）决策变量 路线选择的依据是要使所有的转运需求都能够得到满足，且使总的车辆在途时间最短.在第二阶段，新增以下两个决策变量.

（1）RDk，j∈｛0，1｝：当RDk，j＝1 时表示第j∈D个需求安排在路线k∈R 中，否则RDk，j＝0.

（2）zk∈｛0，1｝：当zk＝1 时表示路线k∈R被选择作为最优路线之一，否则zk＝0.

2）目标函数 本文应急救援物资与伤员转运的目标是所有车辆的运输时间最小化.而总的车辆运输时间是每条路线的运输时间之和.这是一个选择路线的过程，从所有的路线中选择部分的路线能够满足所有的需求，且总的运输时间最少.

3）约束条件

式（2）表示每一个需求都必须得到满足.通过最优路线组合优化模型，选择出了最优路线集合，在应急物流救援中，能够以最少的车辆在途时间完成所有的需求.

3 案 例

3.1 参数设置

为了验证模型的正确性和有效性，采用图3所示的网络配置模拟研究.在该受灾区域有50个节点，每个节点的坐标随机生成，取值范围为（0，500），km.其中节点5为救援中心，其他节点为潜在受灾节点.

图3 网络节点图

在这一受灾区域中，总共有100个单位需求，各个节点所对应的需求以及需求的类型见表1.其中节点类型1表示物资转运类需求，2 表示伤员转运类需求.由表1可知，100单位需求中有46单位物资转运类需求，54 单位伤员转运类需求.车速为v＝60km／h.

3.2 结果及分析

通过数学规划软件Gurobi 4.61求解最优路线组合优化模型，可得100个转运需求可通过54条路线的组合予以满足，总的运输时间为373.2 h，路线集合以及表2数据.

由表1和表2可知：路线5只满足了一种类型的需求，车辆从5号救援中心空车到34号节点然后搭载伤员返回5号救援中心；路线9满足了两种类型的需求，车辆从5号救援中心搭载物资到39号节点，然后空车感到9 号节点，最后从9号节点搭载伤员返回5号救援中心；路线11也满足了两种类型的需求，车辆从5号救援中心搭载物资到22号节点，然后从22号节点搭载伤员返回5号救援中心.示意图见图4.

表1 节点的需求

图4 路线示意图

表2 路线及时间

通过对表2数据分析可得以下结论：（1）满足100个目标需求，需要54条路线；（2）所有路线中，满足2种需求且2种需求在同一节点的有28条.满足2种需求但这2种需求不在同一节点的路线有18条.只满足一种需求且需求为伤员的路线有8条，只满足一种需求且需求为物资的路线为0条.由此可知为了满足车辆在途中的总时间最小化，每条路线会尽量满足2种需求；（3）所有路线中，最少的运输时间为1.9h，最大为13.8 h.如果车辆较多，则可派54辆车来完成这100单位需求.如果车辆不足，且两种需求不紧急，则可派少于54辆车来运输，因为车辆返回后可以继续作业来满足其他需求.

通过多次取随机数值实验可得表3数据，其中实验1～4采用原来的节点网络布局，而实验5～8则采用新的节点网络布局.通过表中数据可知，在节点与道路较为均匀分布的物流网络中，转运路线的数量主要取决于两类需求中转运量较大的需求.根据实验3和实验4，可以发现取不同的节点作为救援中心时，总的运输时间会有较大的差异.通过上文的模型，对所有候选节点进行模拟计算，以总时间最短为目标，可以解决救援中心的选址问题或者灾区的救援分区问题.

表3 随机试验结果

4 结束语

本文讨论了应急救援物资与伤员协调转运问题.基于直运的方式，研究了一个救援中心，多个受灾点多单位需求的转运问题，提出了一种2阶段的求解方法.第一阶段根据直运的要求以及4种转运流向生成所有的可行路线；第二阶段在满足所有的需求约束下，通过最小化总车辆运输时间选择最优路线集合.在案例研究部分，对随机生成的50个节点和100个需求，得到54条路线构成的最优运输方案，验证了模型的正确性和有效性.在未来的研究中，可以进一步优化应急救援中各种资源的整合调度.多个救援中心，则涉及分区优化问题；基于直运与带时间窗的VRP 相结合，更能有效地实施救援；物资与伤员的转运与优先级相结合等方面进行拓展研究.

［1］ÖZDAMAR L，EKINCI E，KÜÇÜKYAZICI B.Emergency logistics planning in natural disasters［J］.Annals of Operations Research，2004，129（1－4）：217－245.

［2］ALTAY N，GREEN W G.OR／MS research in dis－aster operations management［J］.European Journal of Operational Research，2006，175（1）：475－493.

［3］CAUNHYE A M，NIE X，POKHAREL S.Optimization models in emergency logistics：A literature review［J］.Socio－Economic Planning Sciences，2011，46（1）：1－10.

［4］SHEU J B.Challenges of emergency logistics management［J］.Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：655－659.

［5］BALCIK B，BEAMON B M.Facility location in humanitarian relief［J］.International Journal of Logistics：Research and Applications，2008，11（2）：101－121.

［6］SHEN Z，DESSOUKY M M，ORDÓEZ F.A twostage vehicle routing model for large－scale bioterrorism emergencies［J］.Networks，2009，54（4）：255－269.

［7］QIANG G，RAJAN B.Allocation and reallocation of ambulances to casualty clusters in a disaster relief operation［J］.IIE Transactions，2007，39（1）：27－39.

［8］CAMPBELL A M，VANDENBUSSCHE D，H W.Routing for relief efforts［J］.Transportation Science，2008，42（2）：127－145.

［9］BALCIK B，BEAMON B，SMILOWITZ K.Last mile distribution in humanitarian relief［J］.Journal of Intelligent Transportation Systems，2008，12（2）：51－63.

［10］YI W，KUMAR A.Ant colony optimization for disaster relief operations［J］.Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：660－672.

［11］徐志宇，彭嘉臻，许维胜.应急物流的分批配送规划及蚁群优化求解［J］.计算机工程与应用，2011，47（24）：1－3.