《时间限制算法.doc》由会员分享，可在线阅读，更多相关《时间限制算法.doc（5页珍藏版）》请在金锄头文库上搜索。
1、 对于食品企业物资的配送，与其它普通货物配送有相似之处，但是也有独特的性质。食品作为一类特殊的物资，时间限制是配送的主要约束条件，本文对基于时间限制的食品配送进行优化，然后得到最优方案。在配送作业中，我们将食品物资的保质期成为预警时间。配送作业的必须在预警时间内完成，否则将给企业带来很高的惩罚成本。 带有时间约束的配送问题是一个含有离散目标约束的目标规划问题，所以不能直接用传统求解目标规划的方法求解。但可以先不考虑预警时间，只求在最短时间内将物资如数运到，且使总运费最小的调度方案。将此方案中的最短时间与预警时间相比较，若小于等于预警时间，则此方案为该问题的解；若大于预警时间，则表明不能在预警时
2、间内如数运到，即最好的结果也只能是所求方案中的最短时间。故求基于时间约束的物资配送问题可化为先求在最短时间内将物资如数运到，且总运费最小的运输问题，此配送问题的数学模型描述如下：目标函数： ,为一个基可行解 中非零分量 在目标函数中的系数为从第 i地运往第j地1个单位物资的运输费用 (时间)；为从第 i 地运往第j地的运输量 ,为第i地的供量 ； 为第j地的需求量 ； minT 为 所有物资如数运抵 目的地的最短时间。 求出 minT 后与原问题的预警时间相比较，即可知物资是否能在预警时间内如数运抵目的地，且运输总代价最低 。应用引例： 有3个食品物资供应点(供地)1、2、3和4个客户点（需求
3、地）A、B、C、D。一批生鲜食品必须4小时内运送到位，否则会超过食品保值期，所以装载后必须马上运抵客户要求地点进行补给。现已知各供应点的供量ai(T)、各作战地域的需量bj(T)和从装载到运抵目的地补给整个过程所需的时间(h)如下图所示。应如何制定配送方案，使食品在规定时限内如数运抵各客户点，而又使总运费最少。 供地需地ABCD供量ai（T）137645224322343853需量bj（T）3322对于该 问题， 首先不考虑时限 4 小时， 只求在 最快的时间内如数地运抵各作战地， 且总运费最小 的方案 。具体计算按前面所述流程进行 ， 过程如下 ： 第一步： 此例为平衡 的运输 问题。首先，
4、将表1中的时间(距离)按由小到大的顺序列出序号t， 如 表2：供地需地ABCD供量ai（T）126535213212332743需量bj（T）3322 第二步：写出效能矩阵。其中=2t，t为该处在表2中的序号，如表3和表4所示。 表3 运算过程表供地需地ABCD供量ai（T）122262523252212322212232322272423需量bj（T）3322 表4 运算过程表供地需地ABCD供量ai（T）14643285228422384128163需量bj（T）3322 第三步：确定每行或每列的减数。第i行的减数，表示该行第k小的元素,k应满足，其中表示从该行最小元素到第n小元素对应的需
5、求量之和，且k2.在本列中，对第1行，当k=2时有，故；同理，对第2行；对第三行，。如表5。同理，若计算每列的减数，则有，第j列的减数Dkj表示该列第k小元素cij，k应满足，其中代表从第j列最小元素到第n小元素对应的供应量ai，且。表5 运算过程表供地需地ABCD供量ai（T）减数14643285822842223841281638需量bj（T）3322第四步：每行各元素分别减去该行对应的减数，并找出各列最小元素，结果如表6所示。然后每列各元素减去该列的最小元素，结果如表7所示。 供地需地ABCD供量ai（T）减数1-45624058206202230-4120838列中最小元素-4-420
6、需量bj(T)3322表7 运算过程表供地需地ABCD供量ai（T）减数10602205824100022340118838需量bj（T）3322 第五步 ： 检验每行每列零元素对应 的 ai和 bj， 是否满足约束条件 ， 即第 i行零元素对应需量bj之和是否大于等于ai ； 第 j列零元素对应供量 ai 之和 是否大于等于 bj 。满足则进行下一步 ，否则跳到第 3 步开始计算， 重复直至满足条件为止。如计算表 7 第 1 行，该行零元素对应 bj之和为 b1+b4=5大于等于 a1 =5， 同理可计算其它行和列 ， 知本例 已经满足上 述约束条件 ， 故可得最优解， 即对零元素对应方格安
7、 排 运输 为最 优运输 方案 。 第六步：安排最优方案。从零元素个数最少的行或列开始对零元素格安排运输方案，每安排完一格，则除开此零元素格，再从零元素最少的行或列开始安排，重复至安排完为止。设xij为第i地运往第j地的运输量，如表8所示。表8中元素即为xij，其上标为安排的步骤，其下标为该格的运费(时间)。故例中的最优解为即总运费(时间)为33+24+23+3332，其中最后一个运抵目的地的为c14对应方格，即最短需要4h才能将弹药如数运抵目的地。 表8 运算过程表供地需地ABCD供量ai（T）1145232323需量bj（T）3322 可见 货物刚好在4小时内从配送点运抵客户点，这批货物不仅在规定的时间之内运到，而且总运费最低。 在食品物资配送作业中，运用此方法对食品物资调度进行优化。保证食品物资在预警时间内按照客户要求送达指定地点。
