时间限制算法.docx

对于食品企业物资的配送，与其它普通货物配送有相似之处，但是也有独特 的性质食品作为一类特殊的物资，时间限制是配送的主要约束条件，本文对基 于时间限制的食品配送进行优化，然后得到最优方案在配送作业中，我们将食 品物资的保质期成为预警时间配送作业的必须在预警时间内完成，否则将给企 业带来很高的惩罚成本带有时间约束的配送问题是一个含有离散目标约束的目标规划问题，所以不 能直接用传统求解目标规划的方法求解但可以先不考虑预警时间，只求在最短 时间内将物资如数运到，且使总运费最小的调度方案将此方案中的最短时间与 预警时间相比较，若小于等于预警时间，则此方案为该问题的解；若大于预警时 间，则表明不能在预警时间内如数运到，即最好的结果也只能是所求方案中的最 短时间故求基于时间约束的物资配送问题可化为先求在最短时间内将物资如数 运到，且总运费最小的运输问题，此配送问题的数学模型描述如下：目标函数:minnc.. x..1J jj=1i=1Z x.. = ai = 1,2,3...mj ij=1iJ > 0minT = maxcij , cij为一个基可行解中非零分量在目标函数中的系数c ij为从第i地运往第j地1个单位物资的运输费用（时间）；X力•为从第i地运往第j地的运输量，ijai为第i地的供量；bj为第j地的需求量；minT为所有物资如数运抵目的地的最短时间。

求出minT后与原问题的预警时间相比较，即可知物资是否能在预警时间内 如数运抵目的地，且运输总代价最低应用引例：有3个食品物资供应点（供地）1、2、3和4个客户点（需求地）A、B、C、D 一批生鲜食品必须4小时内运送到位，否则会超过食品保值期，所以装载后必须 马上运抵客户要求地点进行补给现已知各供应点的供量ai（T）、各作战地域的 需量bj（T）和从装载到运抵目的地补给整个过程所需的时间（h）如下图所示应 如何制定配送方案，使食品在规定时限内如数运抵各客户点，而又使总运费最少供地需地ABCD供量ai （T）137645224322343853需量bj (T)3322对于该问题，首先不考虑时限4小时，只求在 最快的时间内如数地运抵各 作战地，且总运费最小的方案具体计算按前面所述流程进行，过程如下：第一步：此例为平衡的运输问题首先，将表1中的时间（距离）按由小到 大的顺序列出序号t，如表2：供地需地ABCD供量ai （T）126535213212332743需量bj（T）3322第二步：写出效能矩阵其中Cij=2t, t为该处在表2中的序号，如表3和表4 所示表3运算过程表供地需地ABCD供量ai (T)122262523252212322212232322272423需量bj (T)3322表4运算过程表供地需地ABCD供量ai (T)14643285228422384128163需量bj (T)3322第三步：确定每行或每列的减数。

第i行的减数D.k，表示该行第k小的元素 ikC.. ,k应满足匸b. < a.. 2.在本列中，对第1行，当k=2时有艺b.二 b2 二 3 < a1 = 5 <工b.二 b2 + b4 二 5，故 D1k = D12 = c14 = 8 ；同理，对第 2 行1 1D2k = D22 = c21 = 2 ；对第三行，D3k = D32 = c31 = 8同理，若计算每歹U的减数，则有，第j列的减数Dkj表示该列第k小元素cij, k应满足艺a. < b. <工a.，. J .1 1其中工a.代表从第j列最小元素到第n小元素对应的供应量ai，且k > 2表5运算过程表供地需地ABCD供量ai (T)减数14643285822842223841281638需量bj(T)3322第四步：每行各元素分别减去该行对应的减数，并找出各列最小元素，结果如表6所示然后每列各元素减去该列的最小元素，结果如表7所示供地需地ABCD供量ai (T)减数1-45624058206202230-4120838列中最小兀素-4-420需量bj(T)3322表7运算过程表供地需地ABCD供量ai (T)减数10602205824100022340118838需量bj(T)3322第五步：检验每行每列零元素对应的ai和bj， 是否满足约束条件， 即第i行零元素对应需量bj之和是否大于等于ai ；第j列零元素对应供量 ai之和是否大于等于bj。

满足则进行下一步，否则跳到第3步开始计算， 重复直至满足条件为止如计算表 7第1行，该行零元素对应bj之和为 bl+b4=5大于等于al =5，同理可计算其它行和列，知本例已经满足上述 约束条件，故可得最优解，即对零元素对应方格安排运输为最优运输 方案第六步：安排最优方案从零元素个数最少的行或列开始对零元素格安排运 输方案，每安排完一格，则除开此零元素格，再从零元素最少的行或列开始安排, 重复至安排完为止设xij为第i地运往第j地的运输量，如表8所示表8 中元素即为xij，其上标为安排的步骤，其下标为该格的运费（时间）故例中的 最优解为即总运费（时间）为3 X 3+2 X 4+2 X 3+3 X 3—32,其中最后一个运抵目的 地的为c14对应方格，即最短需要4h才能将弹药如数运抵目的地表8运算过程表供地需地ABCD供量ai (T)13 3 12 4 4522 3 3233 3 23需量bj (T)3322可见货物刚好在4小时内从配送点运抵客户点，这批货物不仅在规定的时间 之内运到，而且总运费最低在食品物资配送作业中，运用此方法对食品物资调度进行优化保证食品物 资在预警时间内按照客户要求送达指定地点。