动态规划和整数规划

1、3应急物流物资配送方案3.1理论模型本文中将动态规划的最短路问题以及整数规划中的指派 问题应用于配送方案的制定。最短路问题解决车辆在两个城 市间运动如何使时间最短并可以得到最短路径，指派问题可 以实现在一个人只做一份工作、一份工作只由一个人做的情 况下，如何分配工作可以使N个人完成N项工作所需的总时 间最短。3.2灾害区域分类灾害发生后，乡级、县级、地级、省级人民政府和相关部门 要根据灾情，按照分级管理、各司其职的原则，启动相关层级 和相关部门应急预案，做好灾民紧急转移安置和生活安排工 作，做好抗灾救灾工作，做好灾害监测、灾情调查、评估和报告 工作，最大程度地减少人民群众生命和财产损失。根据突

2、发性 自然灾害的危害程度等因素，对受灾区域进行评定，若受灾区 域较小，便将受灾区域视为一个整体处理；若受灾区域宽广， 则将受灾区域分为四个等级：特别重大灾害区（I级）、重大灾 害区（II级）、较大灾害区（III级）、一般灾害区（IV级）。在向灾 区配送应急物资时，要本着优先原则，优先向I级区配送，最 后向IV级区配送。3.3应急物资分类灾害发生后，按照应急物资适用的紧急情况将其分为一般级（A类）、严重级（B类）和紧急级（C类）三类。在向灾区配 送应急物资时，若应急物资需求量不大，则三类物资集体配 送；若各类物资需求都很大，则要本着优先原则，优先配送C 类物资，最后配送A类物资。3.4非受灾区分

3、类灾害发生后，按照应急物资的需求状况以及非受灾区各 地的应急物资库存状况，若受灾区附近地区能够满足应急物 资的需求，则应急物资完全由附近地区提供；若应急物资需求 量较大，则根据实际情况将非受灾区按照由近及远的顺序分 为一个甚至多个供应域，所选供应域独立、同时向受灾区配送 物资，可以保证物资连续、分阶段到达受灾区，这样可以保证 应急物资的充足供应同时减少因应急物资过度供应而引起的 浪费。3.5配送方案前期分析在方案制定前，需要根据灾害的实际程度做出以下决定：（1）当受灾区波及范困过广时，则需要对受灾区根据受灾程度进行分类，保证物资优先送达到最需要的地方。（2）当各类应急物资需求过大时，则需要对应

4、急物资按照 急需程度，保证紧急级物资优先送达到灾区。（3）当应急物资需求过大时，则需要对非受灾区进行区域 划分，从而保证应急物资的及时供应。（4）灾害发生后，将受灾区划分为X小区域，每个区域选 择一个应急物资接收点。然后根据对应急物资的需求大小，对 非受灾区进行区域划分，将非受灾区以受灾区为中心按照由 近及远的顺序分为一个甚至多个供应域，每个供应域再划分为X个小区域，每个小区域设立一个应急物资集中点，并依据 指派问题模型建立每个供应域内部应急物资集中点与受灾应急物资接收点之间的配送网络, 各个供应域的配送网络同时运行，向灾区配送物资，这样可以实现应急物资的分区配 送、分阶段到达。然后根据灾害是

5、否影响到受灾区内部交通状 况，若不影响则利用指派问题模型直接实现供应域内部各应 急物资集中点与受灾区内部各应急物资接收点间的一对一配 送；反之则可以在受灾区边缘设立X个应急物流分部，应急物 资从应急物资集中点途经应急物流中心分部运到应急物资接 收点。理论上讲，在非受灾区的应急物资集中点与受灾区的应 急物资接收点之间直接运用整数规划中的指派问题模型求解 可以得到理论上最优方案，此方案所用的总时间最短，但是当 非受灾区以及受灾区内部的交通状况并不相同时，在受灾区 边缘增设应急物流中心分部可有效缓解二者之间的矛盾，达 到相对最优。4配送方案分析4.1情景介绍本文所讨论的突发事件以某地区发生地震为代表

6、，此次 地震波及范闱较小，故受灾区对应急物资需求较小，所有应急 物资不需分类，只需从附近地区运送应急物资到达受灾区。以 受灾区为本文的研究系统，将其划分为M个待服务的小区域， 然后选取区域中心或者偏近区域中心的城市或乡镇作为应急 物资接收点。由于地震的发生导致受灾区内交通状况发生重 大改变，故需从临近受灾区的非受灾区选取M个城市或乡镇 作为应急分流中心分部。依据指派问题模型建立应急物流中 心分部与应急物资接收点之间的配送网络。应急物资接收点 在接收到应急物资后再向自己所管辖的区域配送。对于附近 的非受灾区，除去己经被指定为应急物流中心分部的城市或 乡镇，将剩余地区以受灾区为中心，划分为M个物资

7、供应地区 （或者根据实际情况从中选择M个物资供应地区），然后选取区 域中心或者偏近区域中心的城市或乡镇作为应急物资集中 点。应急物资集中点负责接收所辖区域内应急物资，并且依据 指派问题模型建立应急物资集中点与应急物流中心分部之间的配送网络。资源调度方案包括两个步骤。首先各应急物资集中点在集中完物资后将其送达应急物流中心分部，应急物流中心分部接收到应急物资后将其送达到应急物资接收点，具体步骤如下：（1）采用动态规划方法，将最短路问题用于运输方案制定，计算各应急物资集中点到各应急物流中心分部的最短路所需时间以及应急物流中心分部到各应急物资接收点的最短路时间。（2）采用整数规划方法，将指派问题应用于

8、应急物资从各应急物资集中点运送到各应急物流中心分部过程，完成物资的运输过程，并使总时间最小。（3）采用整数规划方法，将指派问题应用于应急物资从各应急物流中心分部运送到各应急物资接收点过程，完成物的配送过程，并使总时间最小 4.2物资配送模型4.2.1模型假设（1）假设该应急物流配送系统具有先进的信息系统，应急物流中心能够及时得知各受灾点应急物资的库存量或缺货量，以便能够根据受灾区物资需求进行配送。（2）对于整个系统而言，将系统分为受灾区以及非受灾区，灾区内部缺少的应急物资完全由非受灾区供应。（3）在整个系统内部，城市与城市之间的运输时间是可以量化的。（4）在配送方案制定中，本文只考虑陆路运输，

9、由于水运或者空运在运输条件、路径等与陆路运输存在较大差异，本文 暂不涉及。4.2.2模型建立（1）求最短时间（最短路问题）。在求最短时间的过程中，假设始点与终点间中间要经过N个城市（包括始点和终点），其分别为k （k=l,，n）, k=l表示始点，k=n表示终点，sk表示应急物资运输车辆位于k市这种状态，其集合为Sk,uk表示第k阶段从状态出发的允许决策（即从k市向哪个城市出发），其集合为Uko （skk）表示从k市到（k+1）市所需的时间。V k,n（Sk,uk k+1,uk+1 yn+1）表示从k到n市所需要的最短时间。sk+1=Tk（sk）_表示在sk状态下做出决策uk后得到新状态sk+

10、1。用多阶段决策过程的数学模型（具有无后效性）：为国Sz）=饥（&,蜘）+ 右（Sf /z,Sf ）= 4（%,七）SJ.阵1,2,通过上述模型利用动态规划求解方法可以得出从始点到终点的最优轨线，从始点到终点的最短时间O（2）配送策略（指派问题）。由于无论在应急物资的运输过程中还是物资的配送过程中，都是实现M个供应点向M个接收点的一对一配送，故以应急物资从各应急物流中心分部运 送到各应急物资接收点为例，介绍我们的配送方案。（11=1,，m）表示应急物流中心分部，（JJ=1，m）表示应 急物资接收点，c1J表示第1应急物流中心分部向第J应急物资接收点配送应急物资花费的时间。1与j间存在一一对应关

11、系。X1J表示第1应急物流中心分部是否向第J应急物资接收点配送 应急物资，是则为1，反之则为0。“ li丫产1U = Ln)孔=0 或 1（i = lr-sn;j = l,.,n）式（1）表示第j应急物资接收点只接受一个应急物流中心分部的物资，式（2）表示第1应急物流中心分部只向一个应 急物资接收点配送物资。通过上述模型利用整数规划的求解 方法可以得到最佳的配送方案。4.3配送方案优势分析本方案旨在灾害发生初期为应急物流中心提供一个快速 响应的配送方案。根据最短路问题模型可以使应急物资在物 资发送点与接收点之间按最短路径进行配送，保证应急物资 配送的及时性。根据指派问题模型制定的配送方案将物资发 送点与物资接收点一一对应起来，物资发送点可以根据物资 接收点的需求配送物资，实现了对应急物资有目的性的配送， 避免了局部地区物资过剩而其他地区不足的局面，同时使物 资的配送井然有序，避免物资配送混乱局面的出现。5结论及时合理的资源配送是应急管理的根本保证，对建立完 善的突发时间应急管理保障体系具有重要意义。本文针对突 发事件的突发性、不确定性和应急物资紧缺性等特