基于动态规划模型的救灾物资路线规划问题

(西南石油大学 四川 成都 610500)

引言

我国是自然灾害频发国之一，自然灾害给我国带来的损失巨大。由此，国家特别重视自然灾害救助问题，在各地相继建立救灾物资储备库，救灾物资储备库的物资由分布在全国各地的生产厂家提供。除了生产厂家捐赠的救灾物资以外，另外的物资由国家救灾指挥部统一购买，各个地区的民政部门负责本地区的物资集中和运送，并需要付出物资的购买费用以及运输费用。

问题提出

10家产品生产厂家用Si(i=1,2,…,10)表示，能够提供的物资有5种，分别是：M1,M2,M3,M4,M5，需要物资供应的18地区用Dj(j=1,2,...,18)表示。根据物资实际生产状况要求，部分供应物资生产量有最低要求：如果订单量低于此线，则不开工生产。由于部分物资的使用可以相互替代，对于需求地区Dj，如果要订购的话，M1和M2仅需订购一种，M3和M5仅需订购一种，其它需求没有特别的要求。根据各种物资的实际作用，对每个需求地区而言，有最低需求量和额外需求量。

节点之间(包括生产厂家、需求地区，以及道路的连接点)的道路里程如图1所示，标注在图中道路一侧，每种物资单位里程平均运输费用已知，产品的订购价格按照一定的数量实施分段定价原则。通过建立数学模型，来确定生产订单以及物资运送路线，希望以最小的费用代价，完成救灾物资的订购和运输要求。

图1 地区分布图

问题分析

为了得到以最小费用为代价的生产订单与物资运送路线组合[1]，需要知道各个地区的所需物资组合。但由于各种约束条件，该组合是动态变化的，可以分两个阶段来考虑。

阶段一：最简单的模型是找到生产厂家到地区之间单位数量物资所花费用最低的路径。

阶段二：在阶段一的前提下，继续满足各厂家Si供给各地区Dj物资Mk的数量的各项约束条件，即为各个厂家供应能力、厂家物资生产的最低数量要求、各个地区的额外物资需求、最低需求量和部分物资的使用可以相互替代等约束条件，那么一定会在阶段一中的路径中找到一簇符合最优总费用的最优路径，即可确定生产订单。

动态规划模型的建立

第一阶段 最短路模型[2]的建立

由问题分析可知，物资的总费用P包括购买费用Pmj以及运输费用Ptj，让总费用达到最小化，核心的问题是厂家Si(i=1,2,…,10)到需要物资供应的地区Dj(j=1,2,...,18)的路程最优。

对于题中的距离问题，将18个需要物资供应的地区Dj、10家生产厂家Si以及道路的连接点Ru看做由35个点连接成的网络图(其中，生产厂家Si为1～18，道路的连接点Ru为11～17，地区Dj为18～35)，构造赋权图[3]G(V,E,W)，如图2所示。其中，顶点集V={v1,…,vn},其中v1,…,vn表示35个顶点，E为边的集合；邻接矩阵W=(wxy)n×n,wxy表示顶点vx和vy之间的距离，若两点之间无道路相通，则wxy=∞，问题便是求赋权图G中两顶点所具有最小权的路。

图2 物资运输问题的无向赋权图

取点i到点j的路程dij作为边(vi,vj)的权wij，即

假设先不考虑厂家的供应能力、厂家物资生产的最低数量要求以及各个地区的额外物资需求等约束条件，使得地区Dj到距自己最短路程的生产厂家处就能满足自己所需物资的最低需求，通过赋权图计算两点之间的最短距离。

目标函数 若设决策变量xij=1表示边所选择的路线均为各单位之间的最短距离，此时的权重为dij。则地区Dj到厂家Si的距离dij的最短路模型为：

若设单位物资所花费用为pij，此时的最优路径距离为sij。我们将定义目标函数每段路线上的权重wij=pijsij，则目标函数变为：

求得的结果为生产厂家到地区之间单位数量物资所花费用最低的路径。

第二阶段 在第一阶段的基础上，继续满足各个厂家供应能力、厂家物资生产的最低数量要求以及各个地区的额外物资需求等约束条件，此时将在阶段一的结果——生产厂家到地区之间所花费用最低的路径中找到满足约束条件的总费用的最优路径。

约束条件

xijk为厂家Si供给地区Dj物资Mk的数量，xijk≥0。则：

(6)

最后，由于部分物资的使用可以相互替代，M1和M2仅需订购一种，M3和M5仅需订购一种。因此：

目标函数 设任意生产厂家到任意地区之间所花费用最低的最优路径的每单位物资Mk共花费用为Wijk元。则可得到生产厂家到地区之间所花费用最低的路径中找到满足约束条件的总费用的目标函数为：

生产订单数Xik目标函数为：

综上，整合为：

模型求解 此模型的求解采用Floyd(弗洛伊德)算法[4]，它是一种矩阵(表格)迭代方法，该算法是通过对表示有向图的邻接矩阵作迭代计算，来解决有向图任意一对顶点之间的最短路径问题。

Step1:整合所有数据，求得任意两点的距离矩阵。

Step2:结合Floyd算法，求出关于单位物资所花费用为pij的任意两点的邻接矩阵，该邻接矩阵即为任意两点的最优路径。

Step3:在Step2所得路径下，带入厂家Si供给地区Dj物资Mk的数量xijk，使用目标费用函数求得总费用。

Step4:将上步中得到的总费用进行比较，得到最小总费用。

Step5:根据厂家Si供给地区Dj物资Mk的数量xijk确定生产订单。

模型总结

本文采用的动态规划模型能够得到题中所需的一簇最优解，动态规划方法反映了动态过程演变的联系和特征，在计算时可以利用实际知识和经验提高求解效率。本文的最短路模型采用Floyd算法，其算法可以求解任意两点之间的距离，应用范围比Dijkstra算法要广。模型的劣势表现在文中的动态规划模型没有统一的标准模型，在数值方法求解时存在维数灾，采用最短路模型的Floyd算法，其时间复杂度比较高，并且在对数据的整合分析过程中，不考虑额外需求量对最低费用的影响，会对结果产生相应的误差。在第二阶段中，将各个影响总费用的因素采取先分后合的方法，对于因素的影响具有一定的主观因素。