技术与方法 物流技术２００９年第２８卷第６期（总第２０１期） ｄｏｉ：ｌ０．３９６９／ｊ．ｉｓｓｎ．１００５－１５２Ｘ．２００９．０６．０２６ 应急物流分配模型及算法研究 石玉峰，王金伟，徐军。浦建春 （中国电子科技集团公司 第２８研究所，江苏 南京 ２１０００７） 【摘要】以带有完成任务时限最短和总费用最小为目标的应急物流分配问题为研究对象；构造了基于网络算法，通过消弧和 最小费用路算法求多目标最优解的算法步骤；最后给出了算例，验证了算法的有效性。 【关键词】物流；应急物流；网络优化；分配模式 【中圈分类－￣］Ｆ２５２；Ｆ２２４ 【文献标识码】Ａ ［文章编￣－］１ｏｏ５—１５２ｘ（２０ｏ９）０６—００８０－－０２ Ｒｅｓｅａｒｃｈ ｏｎ Ｅｍｅｒｇｅｎｃｙ Ｌｏｇｉｓｔｉｃｓ Ｄｉｓｔｒｉｂｕｔｉｏｎ Ｍｏｄｅｌ ａｎｄ ｉｔｓ Ａｌｇｏｒｉｔｈｍ ＳＨＩ Ｙｕ－ｆｅｎｇ，ＷＡＮＧ Ｊｉｎ—ｗｅｉ，ＸＵ Ｊｕｎ，ＰＵ Ｊｉａｎ－ｃｈｕｎ （Ｔｈｅ ２８ｔｈ Ｒｅｓｅａｒｃｈ Ｉｎｓｔｉｔｕｔｅ，Ｃｈｉｎａ Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｒｐｏｒａｔｉｏｎ，Ｎａｎｊｉｎｇ ２１０００７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔａｋｉｎｇ ｔｈｅ ｅｍｅｒｇｅｎｃｙ ｌｏｇｉｓｔｉｃｓ ｄｉｓｔｉｒｂｕｔｉｏｎ ｍｏｄｅｌ ｗｉｔｈ ｔｈｅ ｓｈｏｒｔｅｓｔ ｔｉｍｅ ｌｉｍｉｔ ａｎｄ ｍｉｎｉｍｕｍ ｔｏｔａｌ ｃｏｓｔａ ａｓ ｔｈｅ ｏｂｉｅｃｔ，ｔｈｅ ｐａｐｅｒ ｂｕｉｌｄｓ ｕｐ ａｌｌ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｎｅｔｗｏｒｋ，ａｐｐｌｉｅｓ ｄｅｌｅｔｉｏｎ ａｒｅ ａｎｄ ｍｉｎｉｍｕｍ ｃｏｓｔ ｒｏｕｔｅ ａｌｇｏｒｉｈｔｍ ｔｏ ｓｅａｒｃｈ ｔｈｅ ｍｕｈｉ－ｏｂｊｅｃｔ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ ｎｅｔｗｏｒｋ ａｌｇｏｒｉｔｈｍ ａｎｄ ｆｉｎａｌｌｙ ａ ｎｕｍｅｒｉｃａｌ ｅｘａｍｐｌｅ ｉｓ ｐｒｅｓｅｎｔｅｄ． Ｋｅｙｗｏｒｄｓ：ｌｏｇｉｓｔｉｃｓ；ｅｍｅｒｇｅｎｃｙ ｌｏｇｉｓｔｉｃｓ；ｎｅｔｗｏｒｋ ｏｐｔｉｉｍｚａｔｉｏｎ；ｄｉｓｔｉｒｂｕｔｉｏｎ ｍｏｄｅｌ １ 引言 记第ｉ个配送中心到第ｊ个需求点的运输时间为ｔｉｊ，运输单位 物资费用为ｃ ，其实际分配物资数量为ｘ 。根据对应急物流分 在面对地震、雪灾和战争等突发事件时，如何科学的决 配决策目标的分析，运用数学规划方法【‘建立模型： 策，以保障各类物资及时、高效地送达是物流的关键。在应急 第一级目标：ｍｉｌｌＴ＝ｍａｘ｛ｔ Ｉ ＞０｝ （１） 物流过程中，存在这么一类问题，即在后方有多个配送中心， 前方有多个需求点，已知从任一配送中心到任一需求点运输 第二级目标：ｍｉｎＣ：∑Ｅｃ · （２） ｉ＝ｌ ｊ＝ｌ 时间不同、运输费用也不同，考虑到应急需要，要求一是向各 需求点完成配送物资的统一截至时间尽可能短，二是完成整 约束条件：∑ ＝口 ｉ＝ｌ，２，…，ｎｉ，下同 （３） Ｊ＝ｌ 个物流任务的总费用尽可能少。根据目前的研究情况，对该类 问题基本还是空白。下面，本文将以此问题为对象，运用图论 ＥＸｉｊ＝ｂｊ ｉ＝ｌ，２，…，ｎ，下同 （４） 研究该类典型应急物流分配模型和优化算法。 ∑ ＝∑ｂｊ （５） ｉ＝ｌ Ｊ＝ｌ ２问题描述与建模 ｘ 为非负整数 （６） 设有ｉｎ个配送中心（记为Ａ。，Ａ：，…，Ａ ），存有某类物资数 ３算法设计 量分别为ａ。，ａ２，…，ａｔＩＩ，另有ｎ个需求点（记为Ｂ。，Ｂ２，－＂，Ｂ ），各点 的需求量为ｂｌ， …，ｂ ，且供、需物资总量相等（∑ａｌ＝∑ｂｊ）， 上述所列的应急物流分配问题，实质是一类多目标整数 ｉ＝ｌ ｉ＝ｌ 规划问题，考虑到物流具有与传统的网络流量分配问题相似 【收稿日期］２０ｏ８—１２—２５ 【作者简介】石玉峰（１９７３一），男，四川成都人，中国电子科技集团公司第二十八研究所博士后，主要研究方向：物流及信息系统。 ８Ｏ一 石玉峰，等：应急物流分配模型及算法研究 性【１１２１，本文将其转化为多目标网络流量分配优化问题进行求 技术与方法 通过削弧算法所得的新网络ＮＩ． ，Ａ’，Ｔ，Ｃ，Ｕ，ｘ）可能存在多 解。 ３．１ 模型转化 Ａｌ Ｂｌ ｏ Ｄ 图１网络模型 根据对问题的描述，如图１示，用Ｎ＝ ，Ａ，Ｔ，Ｃ，Ｕ，Ｘ）表示应 急物流分配的网络模型。其中：Ｖ代表网络的节点集合（包括虚 拟的源点Ｏ、虚拟的汇点Ｄ、中间节点配送中心Ａ ，Ａ：，…，Ａ 和 需求点Ｂ。，Ｂ ，…，Ｂ ）；Ａ代表网络的弧集合｛（ｉ＇ｊ）Ｉ ｉ，ｊ∈Ｖ，ｉ≠ｊ）；Ｔ、 Ｃ、Ｕ、Ｘ分别代表网络中的各弧上运输时间集合｛ｔｉ ｊＩ（ｉ，ｊ） Ａ｝、 单位运输费用集合ＩｃⅡＪ（ｉ，ｊ）∈Ａ）、容量集合｛ｕ Ｊ（ｉ，ｊ）∈Ａ｝和流量 集合 ｝（ｊ ｉ）ｅ Ａ｝。其网络模型上各参数标定方法： 从虚拟的源点０到配送中心Ａ ，Ａ：，…，Ａ 的弧上参数为： 各弧上的运输时间和单位费用为０，容量分别为ａｈ ａ２＇…，ａｌＴ１。 从配送中心节点Ａ ，Ａ：，…，Ａ 到需求点Ｂ。，Ｂ ，…，Ｂ 的弧上 参数为：各弧上的运输时间和单位费用分别为ｔｉ；和ｃ 而其容 量不受限（可设为很大数，记为Ｍ）。 从需求点Ｂ。，Ｂ ，…，Ｂ 到虚拟的汇点Ｄ的弧上参数为：各 弧上的运输时间和单位费用为０，容量分别为ｂｌ，ｂ ，…，ｂ 。 这样应急物流分配问题就转化为多目标网络流量分配优 化问题：一是求满足给定流量要求的最短时限流，二是在最短 时限流上寻求费用最小的流。最后所求的流量集合Ｉｘ ｌ（ｉ，ｊ）∈ Ａ｝中从配送中心到需求点的流即为应急物流分配方案。 ３－２最短时限分配网络求解 本文参考相关文献［２—３】，构造了削弧算法来求解满足任 务量要求的最短时限分配网络。 第一步：采用标号算法 求网络中的一个最大流分配方 案｛）【ｊ ｊｌ（ｉ，ｊ）∈Ａ）。根据其弧容量约束条件，显然该最大流的流量 定等于总供量 ａｉ或总需求 ｂｊ，记为ｖ 。 ｉ＝ｌ ｊ：ｌ 第二步：在流量分配集合中，求可行流（其弧上的流量ｘ ．＞ ０）的弧上运输时间最长者，即ｔ＝ｍａｘ｛ｔｉｊ ｌ ｘ ｉ＞０，（ｉ，ｊ）∈ＡＩ。 第三步：在原网络中删除所有运输时间不比ｔ小的弧，生 成新的网络Ｎｌ＿ ，Ａ ，Ｔ，Ｃ，ｕ，Ｘ）。 第四步：在新网络Ｎ。中搜索最大流分配方案，如果最大流 的流量仍然等于总供量 ａｉ或总需求 ｂｉ，则转到第二步，否 ｉ＝ｌ ｊ＝ｌ 则搜索结束，此前一步得到所得的网络即为完成应急物流量 要求的最短时限分配网络。 ３．３最小费用最大流求解 种从源点０到汇点Ｄ的流量分配方案，可采用最小费用增广 路算法【ｌＩ 搜索费用最小而流量最大的流量分配方案。最后，得 到网络的最小费用最大流分配方案。此时网络上从配送中心 节点Ａ ，Ａ ，…，Ａ 到需求点Ｂ。，Ｂ２，…，Ｂ 的弧流量即为满足应急 物流分配要求的最优解。 ４算例 设有两个配送中心、三个需求点，参数见表１。表中括号内 第一个参数表示从配送中心至需求点运输时间（单位：天），第 二参数表示运输单位物资的费用（单位：万元）。求满足完成配 送任务量要求截至时间最短，而总费用又最小的物流配送方 案。 表１应急物流基本参数 需求点 需求点 需求点 配送中心存货量 县 且 （单位：件） 配送中心Ａ （２，３） （４，２） （１．３） ５ 配送中心 ， （２，１） （１，３） （３，２） ３ 需求点需求量 ２ ３ ３ （单位：件） 第一步：根据问题描述建立网络模型，并采用最大流算法 求出其最大流分配方案，如图２所示，此时最大流量等于８。网 络图中括号内第一个数字代表通过该段弧的时间，第二个数 字代表单位费用，第三个数字代表弧容量（其Ｍ代表很大数 字），第四个数字代表流量。 Ｂ１ （０ Ｏ Ｄ （０， Ｂ３ 图２算例网络图 第二步：在图２中，求出从配送中心到需求点的可行流中 运输时间最长值为４，然后将网络中所有运输时间不比４小的 弧删除，得到新网络，如图３所示。 Ｂｌ ｆ０ ｏ （０＇ Ｂ３ 图３删除运输时间不比４小的弧得到的新网络 ｌ下转第１１２页） ８１— 供应链管理 立长期稳定合作关系来构建可持续建筑建设项目的供应链。 物流技术２００９年第２８卷第６期（总第２０１期） 虽然上述分析还仅仅是理论上的，但随着供应链管理技 术的成熟，可持续建筑建设项目构建供应链并实施供应链管 理必将是大势所趋。 【参考文献】 【ｌ ｍａ Ａ，Ｉ Ｓｏｌｅｄ．Ａｒｃｈｉｔｅｃｔｕｒｅ ａｓ Ｈｕｍａｎ Ｅｃｏｌｏｇｙ ｔＭＩ．ｂｌｅｗ Ｙｏｒｋ： Ｍｏｎａｃｅｌｌｉ．２００３． ４．３“总承包商主导＋第３方物流辅助”供应链的构 建过程 对于可持续建筑建设项目的承包商来说，构建供应链的 关键是掌握可持续建筑中可持续发展功能的核心技术。只有 掌握了可持续建筑建设的核心技术，可持续建筑建设项目的 总承包商才能对可持续建筑建设项目实施有效的全过程的项 ［２］Ｚｅｎｙ－ｅｎｅｒｇｙ ｂｕｉｌｄｉｎｇ．Ｗｉｋｉｐｅｄｉａ，ｔｈｅ ｆｒｅｅ ｅｎｃｙｃｌｏｐｅｄｉａ［ＥＢ／ＯＬ］．ｈｔｔｐ： 目管理。 ／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｚｅｒｏｅｎｅｒｇｙ＿ｂｕｉｌｄｉｎｇ＃Ｚｅｒｏ－ｅｎｅｒｇｙｂｕｉｌｄｉｎｇｓ在可持续建筑建设项目总承包商掌握了可持续建筑建设 ｗｏｒｌｄｗｉｄｅ． 的核心技术之后，就可以通过与第３方物流机构建立长期稳 ［３］Ｇｌｏｂａｌ Ｇｒｅｅｎ Ｂｕｉｌｄｉｎｇ Ｔｒｅｎｄｓ．ＭｃＧｒａｗ－Ｈｉｌｌ Ｃｏｎｓｔｒｕｃｔｉｏｎ Ｒｅｓｅａｒｃｈ＆ 定的合作关系来构建可持续建筑建设项目的供应链。 Ａｎａｌｙｔｉｃｓ ｔＥＢ／ＯＬＩ．ｈｔｔｐ：／／ ｅｏｍｓ２／ｓｕｍｎｍｒｙ０２４９ ２９４７０２ １ＴＭａｎａｌｙｔｉｅｓ． ５结论 ［４］Ｃｈｆｉｓ￣ｐｈｅｌ＂Ｍ．Ｌｏｇｉｓｔｉｃｓ ａｎｄ Ｓｕｐ￣ｙ Ｃｈｍｎ Ｍａｎａｇｅｍｅｎｔ：Ｓｔｒａｔｅｇｉｅｓ ｆｏｒ Ｒｅｄｕｃｉｎｇ Ｃｏｓｔｓ ａｎｄ Ｉｍｐｒｏｖｉｎｇ Ｓｅｒｖｉｃｅ（Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ） 】．Ｌｏｎｄｏｎ： 对于可持续建筑来说，虽然技术方面仍然需要继续进步， Ｆｉｎａｎｃｉａｌ Ｔｉｍｅｓ／Ｐｒｅｎｔｉｃｅ Ｈａｌｌ，１９９９． 但更需要在管理方面取得应有的突破。构建供应链并实施供 【５】孙大明，苑麟，李菊，．国内绿色建筑的建造成本调查和分析 应链管理作为一种新兴的管理模式，在制造业领域取得的显 ［ＥＢ／ＯＬ］．ｈｕｐ：『／ｗｗｗ．ｅｈｉｎａｇｂ．ｎｅｔ／ｌｕｎｗｅｒｄｚｏｎｇｓｈｕ／２００８０４１８／２２３０３．ｓｈｔｍ１． 著的进步，将其引进到可持续建筑建设领域将有助于可持续 ［６］Ｂｅｎｄｉｎｅｒ Ｊ．Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｓｕｐｐｌｙ Ｃｈｍｎ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ】．ＡＰｌＣＳ－－ 建筑建设项目降低建设成本，有助于可持续建筑形成合作开 ＴｈｅＰｅｒｆｏｒｍａｎｃｅＡｄｖａｎｔｇａｅ，１９９８，（１）． ［７１Ｓｃｏｔｔ Ｃ，Ｗｅｓｔｂｒｏｋ Ｒ．Ｎｅｗ Ｓ ｔｅ百ｃ Ｔｏｏｌｓ ｆｏｒ Ｓｕｐｐｌｙ Ｃｈａｉｎ 发机制。 Ｍａｎａｇｅｍｅｎｔ 【Ｊ】． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｐｈｙｓｉｃａｌ Ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ 可持续建筑建设项目备选的供应链模式有“技术集成机 Ｃｏｎｃｅｐｔｕａｌ Ｍａｎａｇｅｍｅｎｔ，１９９１，２１（１）：１３—２２． 构主导＋第３方物流辅助”、“代建机构主导＋第３方物流辅 【８］Ｓｔｕａｒｔ Ｆ Ｉ，Ｍｕｌｌｅｒ Ｐ Ｊｒ．Ｔｏｔａｌ ＱｕＭｉ￣Ｍａｎａｇｅｍｅｎｔ ａｎｄ Ｓｕｐｐｌｉｅｒ 助”和“总承包商主导＋第３方物流辅助”３种模式。对于第１ Ｐａｒｔｎｅｒｓｈｉｐ：Ａ Ｃａｓｅ Ｓｔｕｄｙ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｐｕｒｃｈａｓｉｎｇ ａｎｄ ＭａｔｅｒｉａＩｓ 种备选模式来说，需要技术集成机构培育全过程的项目能力， Ｍａｎａｇｅｍｅｎｔ．１９９４，３０（１）：１４—２０． 而对于后两种备选模式来说，则需要相应主导机构掌握可持 ［９］刘玉明．大型工程建设项目的供应物流模式选择研究叨．物流技术， 续建筑建设的核心技术或技术管理能力。 ２００７，２６（２）：７６—７８，９１． （上揍第８１页） 第六步：对图３中的网络，利用本文引用描述的最小费用 第三步：在新网络中寻求最大流的分配方案，其结果见图 路算法进行求解。 ３，此时最大流流量等于８，继续下一步。 最后，得到应急物流分配的最优解，从配送中心Ａ１分别 第四步：在图３中，求出从配送中心到需求点的可行流中 向需求点Ｂ１和Ｂ３运送２件和３件物资，配送中心Ａ２向需求 运输时间最长值为２，然后删除该网络中所有运输时间不比２ 点Ｂ２运送３件物资，任务完成的截至时间是２天，总费用为 小的弧，得到新网络，如图４示。 ２４万元。 Ｂ１ ５结束语 （０ Ｏ 本文用网络规划方法研究了应急物流分配问题，构造和 （ｑ 引用了消弧算法、最小费用路算法求解满足配送量要求的最 短时限、最小费用物流分配方案的算法步骤，并给出了算例， 验证了算法的有效性。最后，鉴于应急物流决策本身的复杂 性，笔者还将继续深化这方面的研究。 图４删除运输时间不比２小的弧得到的新网络 【参考文献】 ［１】Ｊ颐颂迪，郭耀皇．运筹学［ＭＩ．北京：清华大学出版社，１９９０． 第五步：在新网络中求最大流分配方案，其结果见图４。显 ［２１ｉ￣金星，刑文训．网络优化［Ｍ】．北京：清华大学出版社，２０００． 然，此时最大流流量等于６，不满足实际运量要求，则前面所求 【３】石玉峰，彭其渊．基于双最短时间的运输分配研究阿．空军工程大学学 的网络（即图３）即为最短时限网络。 报，２００４，５（６）． １１２－
