应急物资供应区域的物资调度模型与算法研究

季开青，李大卫

(辽宁科技大学理学院，辽宁 鞍山1140511)

摘  要:    对跨区域的大规模应急物资调度来说，应急物资供应区域的物资调度是保障应急后续物资的关键。本文将轴辐式网络应用在应急物资供应区域的物资调度中，建立以外运开始时间最早、成本最少为目标的连续消耗型物资调度的双层优化数学模型，基于该问题的特点，给出了相应的求解算法，并对具体算例进行了求解。

关键词:    轴辐式网络；应急物资调度；区域系统；模型；算法

中图法分类号:    C935；TP391.9         文献标识码: A

On material dispatch model and algorithm in the emergency supplies region

JI Kai-qing, LI Da-wei

(School of Science, University of Science and Technology Liaoning, Anshan Liaoning 114051, China)

Abstract: To large-scale emergency distribution of materials across regions, the material dispatches in emergency supplies regions is the key ensuring follow-up materials of emergency. In this paper, hub-and-spoke network is applied to the dispatch of emergency supplies in the region, and, for continuous consumption problem, a bi-level optimization mathematical model based on both the earliest start time for materials outside-transports and the lowest cost is established. Finally, we give the algorithm and an example for this model.

Key words: hub-and-spoke network; emergency materials dispatch; region system; mathematical model; algorithm

发生大规模自然灾害和突发性公共事件后，对应急物资的需求量一般很大，对应急时间具有强烈要求，有时这样的要求还具有刚性特征，因此对应急物资的调度往往会跨地区进行。被调度的区域称为应急物资供应区域，该区域应急物资的调度是整个应急物资调度系统的重要组成部分，其最显著的特点与应急物资需求点的应急问题一样，同样表现为应急时间的紧迫性。如何快速有效的调度该区域的物资对整个应急过程将起到十分重要的意义。

O’KELLY于1987年首先提出了轴辐式网络枢纽设施选址和网络设计模型[1]。作为一个和实际应用密切关联的术语，轴辐式网络根据应用背景不同，有不同的定义。“轴—辐”结构要求交通运输在时空上集中，建设区域性多功能的枢纽，通过枢纽的拆箱、分拣、转运和配送，实现全程物流管理，要求各种交通方式在整个物流网络系统中特别是在节点上协调分工，实现无缝衔接[2]。“轴—辐”结构的最大特征是交通流量在支柱链路上高度集聚，有利于整个网络成本的降低[3]。目前轴辐式网络在应急物资调度中的应用很少，施晓岚在文献[4]中建立了基于轴辐式结构的应急物资动态调度网络，并将轴辐式应急物资调度动态网络构成分为三个阶段，其中的第三个阶段指的就是应急物资供应区域的物资调度。但文献[4]中没有给出具体的研究模型。

对于轴辐式网络在应急物资供应区域的应用，其实质还是多出救点、单应急点的应急问题。目前对多出救点、单应急点的应急问题的研究已经取得了较大的成果：文献[5]—[9]对单资源应急时间最短、出救点数最少的连续消耗系统进行了研究；文献[10]—[11]对多资源应急时间最短、出救点数最少的连续消耗系统进行了研究；文献[12]—[13]对单资源应急时间最短、成本最低的应急物资调度系统从不同角度进行了研究。

本文将在基于轴辐式网络的应急物资供应区域系统中，建立以外运开始时间最早、成本最少为目标的连续消耗问题的双层优化数学模型，并给出相应的算法和算例。

1  系统描述

图1为一个基于轴辐式网络的应急物资供应区域系统。

图1 基于轴辐式网络的应急物资供应区域系统结构图

Fig. 1 system diagram

设点为某地区应急物资储备中心，称之为轴点；为该地区除了轴点外的个应急物资储备点，称之为辐点。由于轴点本身也储备了大量应急物资，因此轴点也可以作为辐点，为了表示方便，记为辐点。当外地发生大规模突发性事件，需要调用该地区的应急储备物资时，辐点的物资集中到轴点处，由轴点统一运往应急地区。设该地区需要调用的总物资量为，辐点的物资可用量为，；物资从辐点到轴点的运输时间为，不妨设；辐点的物资单位成本为，其中包括从辐点到轴点得运输成本和将来其本身物资的补给成本等。要求在保证应急物资连续外运的条件下，给出一个满足外运开始时间最早、物资成本最少的调度方案（即确定参与调度的辐点及相应的物资数量）。

该问题属于连续消耗问题。连续消耗问题首先要保证在任何时刻已到达物资量满足应急所需的物资消耗，即不能出现因物资供应不足引起的应急活动的停止[5][6]。

由于本文讨论的问题不仅涉及物资需求而且还考虑了多个辐点物资的调度情况，因而调度方案应该体现参与调度的辐点及相应的应急物资数量。通过集合的形式，任一方案可以表示为：

其中，， 

上面定义的方案确定了参与调度的辐点，从这些辐点调度的资源数量分别为。

设为应急物资外运开始时间，为应急物资外运结束时间，为物资消耗速率，则有。

定义1 方案关于应急物资外运开始时间是连续可行的，如果对，有

其中：表示时刻已抵达轴点的应急物资量，表示时刻从轴点外运的应急物资量。

按照上述方案，在任何时刻，轴点的应急物资到达量不小于以为外运开始时间至时刻的应急物资连续外运量，那么称方案是关于起始时间是连续可行的。

2  系统建模

假设应急物资外运开始的最早时间为，基于以上假设，建立以外运开始时间最早、成本最少为目标的双层目标连续消耗问题的数学模型如下：

                          （1）

                        （2）

              （3）

                     （4）

其中（1）式表示所有外运物资的成本和最小，为上层目标函数；（2）式表示物资开始外运的最早时间，为下层目标函数，同时也是上层目标的约束函数；（3）式表示每个辐点的调用物资量不大于本身所有的物资量；（4）式表示所有调用物资两等于需求总量。根据以上模型最后可以求出最优可行的调度方案：

。

3  模型分析及求解算法

3.1  模型分析

求解的主要过程如下[5]：首先给出一种重要方案

其中。

该方案的的特点是：选取离轴点最近的辐点进行调运，如果它的全部物资量小于需求量，则再让第二近的辐点参与调运，如果和的全部物资量之和还小于需求量，则让第三近的出救点参与调运，如此等等，直至满足应急物资的需求。

定理3.1 可行方案对应的应急物资最早开始外运时间：

3.2  求解算法

设计求解算法时，需要考虑一下两个因素：第一，必须保证应急物资供应的连续性，外运一旦开始，不能出现供应中断现象；第二，在保证应急物资供应连续的基础上，在外运开始的每一时刻，选取单位成本最低的辐点的物资。考虑到以上因素，设计如下算法：

1)，，，，，；

2) 求：令，转3)；

3) 令。若，则，，转4)；否则求：，再令，，转4)；

4) 若，则，，，转2)；否则：，转5)；

5)。

4  算例

应用上节提出的求解算法，对表4.1中的仿真数据进行详细求解。

由定理3.1知：

可求出最早外运时间：

表4.1 仿真数据(其中，)

Tab. 4.1 simulation data

该方案应急物资总成本为：

若按照文献[6]或[8]的方法求得解为：

此时的成本费用则为：。

由此可以看出可以节约成本2540-2430=110。

5  结论

本文对单资源应急物资连续消耗供应区域系统进行了研究，建立了基于轴辐式网络的以“外运时间开始最早、成本最小”为目标的双层优化模型，给出了求解算法和算例。但在实际问题中，常常会涉及多资源问题和非连续消耗的问题，对多资源和非连续消耗系统的“开始最早、成本最小”问题，将是下一步研究的重点。

参考文献：

[1]O’Kelly, Morton E., A Quadratic Integer Program for the Location of Interacting Hub Facilities[J], European Joural of Operational Research 32, 1987,pp.393-404.

[2]张世翔．基于轴辐式网络模型的城市群物流配送系统规划研究[D]．上海：同济大学博士学位论文，2006．

[3]李阳．轴辐式网络理论及应用研究[D]．上海：复旦大学博士论文，2006．

[4]施晓岚，许宗桢，郭晓汾．基于轴辐式结构的应急物资动态调度网络研究[J]．物流技术，2008，27(9)：87~90．

[5]刘春林，盛昭瀚，何建敏．基于连续消耗应急系统的多出救点选择问题[J]．管理工程学报，1999，13(3)：13~16．

[6]刘春林，何建敏，施建军．一类应急物资调度的优化模型研究[J]．中国管理科学，2001，9(3)：299~306．

[7]刘春林，何建敏，盛昭瀚．应急系统调度问题的模糊规划方法[J]．系统工程学报．1999，14(4)：351~355．

[8]高淑萍，刘三阳．应急系统调度问题的最优决策[J]．系统工程与电子技术，2003，25(10)：1222~1224．

[9]刘春林，沈厚才．一类离散应急供应系统的两目标优化模型[J]．中国管理科学，2003，11(4)：27~31．

[10]戴更新，达庆利．多资源组合应急调度问题的研究[J]．系统工程理论与实践，2000(9)：52~55．

[11]高淑萍，刘三阳．基于联系数的多资源应急系统调度问题[J]．系统工程理论与实践，2003，23(6)：113~116．

[12]韩强．一类应急物资调度的双层规划模型及其算法[J]．中国管理科学，2007，z1：716~718．

[13]刘北林，马婷．应急救灾物资紧急调度问题研究[J]．哈尔滨商业大学学报(社会科学版)，2007(3)：3~5．