物资紧急调运问题的优化模型
摘要
本文就物资的紧急调运问题，运用图论和线性规划的理论和方法建立数学模型，针对防洪救灾物资的调运问题设计了合理的调运方案。
在问题（1）中，将工作量（运输路程?调运量）作为衡量调运方案的标准。利用Floyd算法（Matlab程序代码见附录二）得到各重要节点（企业、仓库、国家级储备库）之间的最短路线（详见表1）。由于要求重点保证国家级储备库的库存量，我们将调运过程分为两个阶段：（1）企业和现有库存量超过预测需求量的仓库向国家级储备库调运；（2）企业向现有库存量小于预测需求量的仓库调运。据此建立线性规划模型，用LINGO进行求解，得到最佳的紧急调运方案。（详见表3、表4）。
在问题（2）中，在问题（1）所确定的调运方案的基础上，建立以时间最省为目标的线性规划模型。利用LINGO软件求解得到18辆车的最佳调度方案（见表7），所用的时间为68.2天。
在问题（3）中，因为时间充裕，我们认为各仓库及国家级储备库均要达到其最大库存量才能应对灾害，为降低运输成本，在建立Floyd算法的邻接矩阵时，应以运费为权重，找到费用最省的路线后，调运救灾物资时必定沿费用最省的路径调运，据此建立线性规划模型求出使运输费用最省的调运方案（见表10）。确定调运量后即可确定使车辆数最小的车辆调度方案（见表11），共需要32辆车。最终得到最低运输成本为724253元。
在问题（4）中，由于16号地区灾情紧急，急需10万件救灾物资。此时应在保证在5天内完成调运任务的前提下，使所需车辆尽量少。首先在路段○16—21,○16—○23,○11—○25 ,○25—○26和○32—○34中断的情况下求出各企业、仓库、○
国家级储备库向16号地区调运救灾物资的时间最省路径；其次建立以所需车辆最少为目标，5天内完成调运任务等为约束条件的线性规划模型。通过LINGO求解得到最少需要60辆车（详见表13）。
关键词：救灾物资调运；Floyd算法；线性规划； LINGO
1.问题的重述
我国地域辽阔，气候多变，洪水、泥石流等各种自然灾害频频发生，给国家和人民财产带来重大损失，防洪救灾成为各级政府的一项重要工作。某地区为做好今年的防洪救灾工作，根据气象预报及历史经验，决定提前做好某种防洪救灾物资的储备工作。
该地区现有3家该物资的生产企业，8个不同规模的物资储存仓库，2个国家级物资储备库，相关数据如表14(见附录一)所示，其位置分布和道路情况如图2（见附录一）所示。经测算该物资的运输费用为高等级公路2元/公里?百件，普通公路1.2元/公里?百件。各企业、物资仓库及国家级储备库的物资需要时可以通过公路运输相互调运。请你们研究下列问题：
（1）根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的情况下，还要重点保证国家级储备库的储存量，试设计给出该物资合理的紧急调运方案，包括调运线路及调运量。
（2）如果用于调运这批防洪救灾物资车辆共有18辆，每辆车每次能装载100件，平均在高等级公路上时速为80公里/小时，在普通公路上时速为50公里/小时。平均装与卸一车救灾物资各需要1小时，一天按24小时计算。按照问题（1）的调运方案，如何来调度车辆，大约需要多少天能完成调运任务？
（3）若时间容许，希望尽量地减少运输成本，请给出最佳的调运方案，最少需要多少车辆？大约需要多少天能够完成调运任务？
（4）若在调运中，正好遇到灾害使下列路段意外中断： ○16—○21,○16—○23,○11—○25 ,○25—○26和○32—○34
而且16号地区严重受灾，急需向16号地区调运 10 万件救灾物资，请给出相应的紧急调运方案。必要时可动用国家级储备库的物资，也可以不考虑库存量的最低限制。如果要求必须在 5 天内完成这次调运任务，那么最少需要多少辆车，并给出车辆的调度方案。 16 ○
2.问题的分析
2.1问题（1）的分析
该问题要求根据未来预测需求，在保证最低库存量和不超过最大库存量的情况下，还要重点保证国家级储备库的储存量，设计合理的紧急调运方案，包括调运线路及调运量。在紧急情况下，应保证调运的路径最短，所需调运的救灾物资最少。故可先利用Floyd算法求出各节点（企业、仓库、储备库）间的最短线路。调运时救灾物资沿两个节点间的最短路径调运。
根据重点保证国家级储备库的库存量的要求和各仓库现有库存量及预测需求情况，在调运时分两个阶段进行。第一阶段从企业1、2、3和仓库3、4调运救灾物资满足国家级储备库的预测需求量，第二阶段从企业1、2、3调运救灾物资以满足仓库1、2、5、6、7、8的预测需求量，如图1所示：
企业1企业2企业3仓库3仓库4国家储备库1第一阶段企业1企业2国家储备库2企业3仓库1仓库2仓库5仓库6仓库7仓库8第二阶段
图1 调运时的两个阶段
由于现有库存量总和无法满足各个仓库的预测需求量之和，故3个企业还要
)为目标函数,库存量为约束条件建再进行生产。由此以min(路程?调运物资数量立线性规划模型，利用Lingo软件求出最佳的调运方案。 2.2问题（2）的分析
该问题要求在问题（1）所确定的紧急调运方案的基础上，确定车辆的调度
方案，给定用于调运救灾物资的车辆为18辆，并给出车辆在高等级公路和普通公路上的时速分别为80公里/小时、50公里/小时。在紧急调运方案中，应考虑尽量减少完成调运任务的时间，故应计算出问题（1）紧急调运方案中所用到的调运线路对应消耗的时间，以完成调运任务的时间最短为目标函数，用于调运任务的车辆数、各货源地向目的地的调运量等为约束条件建立线性规划模型并用Lingo进行求解。 2.3问题（3）的分析
该问题在给出时间充裕的条件下，要求设计最佳的调运方案使运输成本最低，并确定完成调运任务所需的最少车辆和大概时间，已知救灾物资在高等级公路和普通公路上的运输费用分别为2元/公里?百件、1.2元/公里?百件。由于时间充裕，即可认为灾害在较短的时间内不会发生，因此不再重点保证国家级储备库的库存量。同时，我们认为每个仓库、国家级储备库要达到其最大库存量才能应对灾情。对问题的研究分三个步骤进行，首先利用Floyd算法确定三个企业到
仓库和国家储备库运输费用最省的路径；其次以总运输费用最省为目标建立线性规划模型求解3个企业往仓库和国家级储备库的调运量，得到最佳调运方案；最后根据已确定的路径和调运量分配车辆，使得所需车辆尽量少。 2.4问题（4）的分析
该问题要求向受灾的16号地区紧急调运10万件救灾物资，已知因为灾害路段16—○21,○16—○23,○11—○25 ,○25—○26和○32—○34意外中断。要求设计使所需○
车辆最少的车辆调度方案和调运方案，保证能够在5天内完成调运任务，必要时可动用国家级储备库的物资，也可以不考虑库存量的最低限制。首先运用Floyd算法确定由各企业、仓库、国家级储备库分别向16号地区调运救灾物资的时间最省路径，在此基础上综合考虑上述要求建立线性规划模型求出最佳的车辆调度方案。
3.问题的假设与符号说明
3.1问题的假设
1.假设在确定车辆的调度方案时每条调运路线上派发的车辆数是不变的； 2.任意一条调运路线上派发的所有车辆都是同时发车；
3.除装、卸车所消耗的时间外，车辆一直在调运路线上往返； 4.不考虑行车过程中因加油、故障等原因所浪费的时间； 5.企业每天生产救灾物资的行为是不间断的。 3.2符号说明
xij：第i个货源地到第j个目的地的运货量，单位“百件”
bi：第i个节点（企业、仓库或国家级储备库）的预测需求量，单位“百件” ci：第i个节点（企业、仓库或国家级储备库）的现有库存量，单位“百件” Bi：第i个节点（企业、仓库或国家级储备库）的最大库存量，单位“百件” ai：第i个节点（企业、仓库或国家级储备库）的最低库存量，单位“百件”
mi：第i个企业救灾物资的日产量，单位“天/百件”
dij：任意两相邻的节点i、j之间的运费 Dij：第i个货源地到第j个目的地的总运费 sij：任意两相邻的节点i、j之间的路程
Sij：第i个货源地到第j个目的地的总路程
A：以任意两相邻节点i、j之间的路程为权重建立的邻接矩阵 B：以任意两相邻节点i、j之间的运费为权重建立的邻接矩阵
C：以任意两相邻节点i、j之间的单程运输时间为权重建立的邻接矩阵
其它符号将在文中另作说明。
4．模型的建立与求解
4.1问题（1）的模型建立与求解
4.1.1求节点（企业、仓库、国家级储备库）间的最短路线
根据企业、仓库及国家级储备库的分布图，以任意两相邻节点i、j之间的路程为权重，建立各节点的邻接矩阵：
?040inf?40035??inf350A???infinfinf???????infinfinfinf?inf?inf?inf??inf?inf??，
0?inf??????inf?0??这是个对称矩阵，数字代表相邻两节点的距离，inf代表两节点不相邻。利用Floyd算法，求出部分重要节点（企业、仓库、储备库）间的最短路线如下表：
表1 各货源地到目的地的最短线路 企业1 企业2 41-9-28 企业3 34-32-39-30-29-28 34-32-31-42-27-11-25-18-23 34-32-31-42-27-仓库3 35-39-30-29-28 35-39-5-6-11-25-18-23 35-39-5-6-11-仓库4 31-42-40-6-41-9-28 31-42-27-11-25-18-23 31-42-27-26仓24-26-25-1库5-9-28 1 仓24-26-25-1库8-23 2 仓24-20-22 41-9-15-18-23 41-9-15-18-
物资紧急调运问题的优化模型
