批量运输与及时配送的对抗

李 岩，赵文卓

(1.吉林化工学院理学院，吉林 吉林132022;2.吉林化工学院工会，吉林吉林132022)

及时配送的概念在近几年中越来越流行［1-2］.但是，及时配送的执行要依赖于交易力和供求关系.例如汽车或电脑装配厂，大多数的提供者不得不把原料运送至第三方的仓库，然后再从第三方的仓库以及时配送的方式运送至生产商进行装配.另一方面，由于购买者缺乏议价能力而使及时配送不能够进行.例如购买者要从汽车厂购买引擎，购买者想要寻找一个及时配送的提供商，这意味着按需送货.然而，生产商规定了一个最小的配送数量，记为R.另一方面，当地的零售商承诺以按需配送的形式提供购买者引擎，但是需要较高的价格.目前的问题购买者是继续从生产商那里购买引擎还是转向当地的零售商.

Wagner和Whitin［3-7］利用动态规划算法对整批运送问题做了大量的工作.本文寻找了一个解析的方法［9］帮助购买者以最小的成本选择提供者.如果购买者从零售商手中购买产品，由于是及时配送，所以成本很容易计算［11-13］.如果购买者从生产商手中购买产品，成本就为存储费用和运输费用之和，我们设计了动态批量模型来计算逐步增加到最小数量约束的货物费用.针对问题的几种最优性，我们设计了多项式最优算法.

1 符号和公式

定义T为一个计划周期的长度.定义t为一个计划周期长度，t=1，…，T，定义符号如下:

dt:周期t的需求

xt:周期t的补充数量

R:每一次定单的最小补给数量

It:周期t结束后已有的存储量，It≥0.

ht:周期t放置一个单元的费用

P(xt):周期t补给xt个单元的费用

其中n为确定的整数，S为每次运输的固定费用，W是一次货物的容量，A是运输货物的费用.Min∑(P(xt)+htIt)

2 最优性质

定义:如果It=0，则称周期t为新生点，如果xt＞0，则称t为补给周期.补给周期称为整车货(FTL)周期，如果xt=nW，t称为最小需求周期，如果xt=R，t称为不规则补给周期，如果xt＞R且t不是FTL周期.

性质1 存在一个最优解，如果l-1和m是两个连续的再生点，并且在l和m之间至多存在一个不规则的补给周期.

性质2 存在一个最优解，如果l-1和m是两个连续的再生点，并且在l和m之间存在一个不规则的补给周期t，则在t之前必存在一个最小补给周期，并且这个补给周期是整车货的周期.

性质3 存在一个最优解，如果l-1和m是两个连续的再生点，并且在l-1和m之间没有不规则的补给周期，则对任意两个连续的补给周期s，t，其中l-1＜s＜t≤m，若s是FTL，则t必为FTL周期.

3 多项式算法

令C(i，j)为从周期i到周期j中间没有新生点的费用，F(j)为从周期1到周期j的总的费用.得到以下动态规划算法:

F(0)=0 对于 j=1，…，T，

F(j)=min{F(i-1)+C(i，j):1 ≤i≤j}

问题归结为寻找最小的 C(i，j)，1 ≤i≤j≤T .由于当 d(i，j)＜ R，C(i，j)= ∞，则只需考虑 d(i，j)≥ R的情况.根据性质1-3，只需考虑MR和FTL周期的情况.另外，我们可以得到以下性质.

性质4对于(i，j)问题的最优解问题，对于任意一个补给周期u，必满足Iu-1＜du.

性质5对于FTL周期的(i，j)问题的最优算法，必满足Iv-1＜min{dv，mW}，其中m=「R/W.

在周期MR和FTL这间可能有一个不规则的周期，对于i=1，2，…，T;j=T，T-1，…，1，定义

I(i，u-1)= 「d(i，u-1)/RR-d(i，u-1)其中 1 ≤i≤u ，

I′(v-1，j)=d(v，j)-d(v，j)/W?W 其中 1 ≤v≤j.

根据性质 4，5，我们可以在 o(T2)时间内计算 I(i，j)，I′(i，j)，其中1 ≤i≤j≤T .

寻找R(i，T)的算法:

Step0:设 R(i，T)={i}，v=i+1 .

Step1:若 I(i，u-1)=0 或 I(i，u-1)+R ＞ d(u，T)，则停止.否则，转到 Step2.

Step2:若 I(i，u-1)＜ du，则令R(i，T)=R(i，T)∪{u}，并转到Step3.否则，令u=u+1 并转到Step1.

Step3:若 I(i，u-1)+R ≤du，则停止.否则，令 u=u+1 并转到 Step1.

定义S(i，u)是从周期i到周期u-1，存货从0到I(i，u-1)时应用MR供给的最小的费用，有S(i，i)=0，同理定义T(v，j)′是从周期v到周期j，存货从I′(v-1，j)到0时应用FTL供给的最小的费用.对于固定的 i和 j，定义 q(i，u)→(v，j)′是从周期 u 到周期 v-1，存货从 I(i，u-1)到 I′(v-1，j)时的最小的费用.则有

T(v，j)′的计算复杂性为O(T3).

因此，C(i，j)的计算复杂性为O(T4+T3+T2)=O(T4).

4 问题举例

5 结 论

成本、速度和一致性是影响运输合理化的至关重要的因素.具体的运输作业涉及到运输方式的选择和运输路线的选择及计划运输设备的使用时间(本文主要指仓库).本文以这三个因素为标准，设计动态规划算法帮助购买者合理选择提供者和运输方式使总成本达到最小.例如上面问题举例中所指，如果购买者一次购买产品的数量是15，批量运输的总费用130，则购买者可以根据零售商提供的报价合理选择提供商而使自己的利益最大化.

［1］ R.W.Hall，Zero Inventories，Homewood，IL，Dow Jones Irwin.1983.

［2］ R.G.Moras，M.R.Jalali，R.A.Durek，A categorized survey of the JIT literature［J］.Prod.Planning Control，1992(2):322-334.

［3］ H.M.Wagner，T.M.Whitin.Dynamic version of the economic lot-size model［J］.Management Science 5，1958:89-96.

［4］ Z.M.Cheng，D.H.Xu.Parallel Machine Scheduling Problem With Preemptions and Release Times to Minimize Total Completion Time［J］.2007(16):77-84.

［5］ N.G.Hall，M.A.Lesaoana，C.N.Potts.Scheduling with fixed delivery dates［J］.Operations Research，2001(49):134-144.

［6］ H.Matsuo.The weighted total tardiness problem with fixed shipping times and overtime utilization［J］.Operations Research，1988，36:293-307.

［7］ C.L.Li，G.Vairaktarakis，C.Y.Lee，Machine scheduling with deliveries to multiple customer locations，European Journal of Operational Research，2005，164:39-51.

［8］ K.R.Baker..AComparetivesurv，y of Flowshop Algorithm［J］.Operations Research，1975，23:62-73.

［9］ B.Chen，C.N.potts，G.J.Woegiger.1998.A Review of Machine Scheduling:Complexity，Algorithms，and Approximability［J］.Operations Research Letters，1997，21:69-76.

［10］ J.Bruno，E.G.Coffman，JR.and R.Sethi.Scheduling Independent Tasks to Reduce Mean Finishing Time［J］.Commun.ACM，1974，17:382-387.

［11］ Rawls C.G.，Turnquist M.A.pre-positioning of Emergency Supplies for Disaster Response［J］.transportation Research，2010，44(4):521-534.

［12］ Widener M.J.，Horner M.A hierarchical Approach to Modeling hurricane Disaster Relief Goods Distribution［J］.Journal of Transport Geography，2011，19(4):821-828.

［13］ Afshar A.，Haghani A.Modeling Integrated Supply Chain Logistics in Real-time Large-scale Disaster Relief Operations［J］.Socio-Economic Planning Sciences，2012，46(4):327-338.

［14］ Rath S.，Gutjahr W.J.A Math-heuristic for the Warehouse Location-routing Problem in Disaster Relief［J］.Computers ＆Operations Research，InPress，Corrected Proof，Available online，2011(7).