Ｃ－Ｗ算法在ＪＩＴ采購中的應(yīng)用

宋志剛　武勝良

摘要：文章研究Just in Time（JIT）背景下制造商主導(dǎo)的第三方物流（Third Party Logistics, 3PL）運(yùn)輸調(diào)度問題。制造商根據(jù)其生產(chǎn)計(jì)劃的要求進(jìn)行采購。文章使用C-W路線優(yōu)化算法，在線路規(guī)劃中考慮了車輛載重量、容積以及車輛到達(dá)時(shí)間的影響，實(shí)現(xiàn)以最小的成本達(dá)到JIT采購的目的，并用一個(gè)實(shí)例驗(yàn)證了修正的C-W算法對(duì)解決采購物流中運(yùn)輸調(diào)度問題的適用性。

關(guān)鍵詞：JIT；運(yùn)輸調(diào)度；C-W節(jié)約算法；3PL

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A

Abstract: After analyzed vehicle scheduling problem for manufacture using third party logistics in JIT condition, this paper used C-W algorithm in vehicle scheduling problem. In view of the characteristic of transported products in the manufacture purchasing logistics, vehicle capacity, volume and arriving time as constraint condition was inserted in the route plan, so as to satisfy the purpose of using the least cost for JIT purchase. Then an example was given to confirm the serviceability of the modified C-W algorithm in solving the vehicle scheduling problem.

Key words: JIT; scheduling problem; C-W algorithm; 3PL

0引言

制造業(yè)的激烈競爭，使Just in Time（JIT）的采購方式受到越來越多的企業(yè)的關(guān)注，這種源自于日本豐田汽車公司準(zhǔn)時(shí)制生產(chǎn)的采購方式，要求既要能保證物資的供應(yīng)，又要降低庫存量、縮短訂貨提前期、提高產(chǎn)品質(zhì)量、降低采購成本。在這種采購方式下，車輛的提早或延遲到達(dá)原材料供應(yīng)地均會(huì)產(chǎn)生附加成本。因此制造企業(yè)在制定其生產(chǎn)調(diào)度和運(yùn)輸調(diào)度策略時(shí)，必須從全局出發(fā)，考慮供應(yīng)鏈整體動(dòng)作成本最小化。作為整個(gè)供應(yīng)鏈中的一環(huán)，在進(jìn)行車輛的運(yùn)輸調(diào)度時(shí)，必須考慮與生產(chǎn)之間的有效銜接。

受到外資第三方物流公司大舉進(jìn)入中國的影響，近年來，我國的物流企業(yè)有了較大的發(fā)展，第三方物流（Third Party Logistics，3PL）日益成熟，相當(dāng)數(shù)量的制造商開始有選擇性的將物流業(yè)務(wù)外包給3PL以有效銜接生產(chǎn)、提高JIT采購水平、降低采購成本。研究表明，供應(yīng)鏈中第三方物流運(yùn)輸調(diào)度問題主要分為兩類：生產(chǎn)企業(yè)主導(dǎo)和3PL主導(dǎo)[1]。

目前研究多關(guān)注第一種3PL運(yùn)輸調(diào)度問題。Ruiz Torres和Tyworth（1997）[2]用仿真模型測試了一些簡單的調(diào)度法則，證明在生產(chǎn)和運(yùn)輸中采用恰當(dāng)?shù)恼{(diào)度法則可使整個(gè)系統(tǒng)的效率大大提高。Chang和Lee（2001）[3]的研究目標(biāo)是最小化所有作業(yè)的生產(chǎn)和運(yùn)輸總時(shí)間。Garcia et al.（2004）[4]考慮多生產(chǎn)工廠的系統(tǒng)，目標(biāo)是決定最優(yōu)的訂單至車輛的裝載，使系統(tǒng)利潤最大化。但在最終模型求解的過程中，由于精確算法（包括直接樹搜索算法、動(dòng)態(tài)規(guī)劃法和整數(shù)線性規(guī)劃法三類）只能有效求解中小規(guī)模的確定性問題，當(dāng)求解大規(guī)模問題時(shí)，無法在有限時(shí)間里找到滿意的次優(yōu)解或可行解。因此，在實(shí)際應(yīng)用中，人工智能算法應(yīng)用更廣泛。

1C-W節(jié)約算法研究與改進(jìn)

Clarke和Wright在1964年提出的節(jié)約法（簡稱為C-W算法）是啟發(fā)式算法中的一種，用來解決車輛數(shù)不固定的運(yùn)輸調(diào)度問題[5]。由于算法的簡單實(shí)用，又能很容易的將真實(shí)世界的一些約束條件包含進(jìn)算法模型中，因此在調(diào)度規(guī)劃模型中得到了廣泛應(yīng)用。但國內(nèi)使用該算法解決運(yùn)輸調(diào)度優(yōu)化問題的研究還比較少。

目前有關(guān)C-W算法的研究多用于物流配送，如連鎖超市、煙草配送等，且?guī)r(shí)間窗約束的改進(jìn)算法研究較多，但卻少有將該算法應(yīng)用于采購物流領(lǐng)域的。從物流布局來看，采購物流的VRP問題也可以用配送領(lǐng)域的C-W算法來解決。但必須滿足兩個(gè)前提條件：（1）整個(gè)供應(yīng)鏈由生產(chǎn)企業(yè)主導(dǎo)；（2）采購所需原材料的生產(chǎn)過程平穩(wěn)有序，采購企業(yè)可以使用JIT的生產(chǎn)方式。

1.1基本數(shù)學(xué)模型

1.1.1假設(shè)下列條件已知

（1）生產(chǎn)商的原材料倉庫與供應(yīng)商、供應(yīng)商與供應(yīng)商之間的距離。令Ci,j為i到j(luò)的距離，若i或j等于0，則為收貨倉庫；若i或j不等于0，則為供應(yīng)商。N為供應(yīng)商和生產(chǎn)商的集合。為單位距離的運(yùn)輸成本。

（2）每次取貨時(shí)，向供應(yīng)商采購產(chǎn)品的數(shù)量。令Wi為從供應(yīng)商i處采購的原材料重量（i=1,2,…,n）。

（3）不同車型的載重量。令Qk為車輛k的最大載重量。K為車輛集合，k∈K。

1.1.2數(shù)學(xué)模型

由于采購取貨的基本目標(biāo)是總運(yùn)輸距離最小化，因此目標(biāo)函數(shù)為：

minZ=CX

X=0或1（1）

Yk,i=0或1 （2）

WiYk,i≤Qk （3）

Yk,i=1 （4）

Xk,ij=Yk,j （5）

Xk,ij=Yk,i （6）

其中，約束條件（1）表示車輛k從點(diǎn)i到點(diǎn)j，其中i≠j；i,j∈N；約束條件（2）表示供應(yīng)商i處的原材料由車輛k收取，其中i≠0；約束條件（3）表示每一采購路線上采購數(shù)量受車輛最大載重量的限制；約束條件（4）表示每個(gè)采購商處必須有一輛車去取貨；約束條件（5）表示如果車輛k至采購商j處取貨，則k必從點(diǎn)i到達(dá)點(diǎn)j；約束條件（6）表示若車輛k至采購商i處取貨，則k必在該處取完貨后到達(dá)采購商j。

1.2修正的數(shù)學(xué)模型

上述基本數(shù)學(xué)模型只對(duì)車輛的最大載重量做了限定，朱曉蘭（2007）[6]在其研究中增加了車輛容積和取貨周期內(nèi)車輛最遠(yuǎn)行駛距離兩個(gè)約束條件；李靜（2007）[7]不僅考慮了車輛容積問題，同時(shí)考慮貨物的形狀對(duì)裝載容積的影響，以總?cè)莘e乘以經(jīng)驗(yàn)系數(shù)來考慮容積約束問題。但是關(guān)于時(shí)間對(duì)運(yùn)輸影響的研究則不多見。在眾多企業(yè)努力提高JIT采購水平時(shí)，忽略運(yùn)輸時(shí)間顯然是與實(shí)際不相符的。

因此在基本C-W算法模型中加入容積約束以及運(yùn)輸提前或延遲對(duì)目標(biāo)函數(shù)的影響。

（1）容積約束

ViYk,i≤Vc,k （7）

其中Vi為車輛在供應(yīng)商i處的容積，Vc,k為車輛k的最大容積。

（2）時(shí)間的約束

LEij——連接供應(yīng)商i與供應(yīng)商j后，車輛到達(dá)供應(yīng)商j的時(shí)間比原線路上車輛到達(dá)供應(yīng)商j時(shí)間的提前量（延遲量）

di——為到達(dá)供應(yīng)商i處的規(guī)定時(shí)間

dij——為從供應(yīng)商i處到供應(yīng)商j處的規(guī)定時(shí)間

Ti——為在供應(yīng)商i處的裝貨時(shí)間

ETi——為供應(yīng)商i處允許的最早開始時(shí)間，車輛早于此時(shí)間則會(huì)等待

LTi——為供應(yīng)商i處允許的最遲開始時(shí)間，車輛晚于此時(shí)間則會(huì)延遲

則:

LEij=di+Ti+dij-dj （8）

設(shè)車輛經(jīng)過供應(yīng)商j之后所需要經(jīng)過的供應(yīng)商為r，當(dāng)LEij<0，若LEij≤mind-ET，則在經(jīng)過供應(yīng)商j之后車輛到過其他供應(yīng)商時(shí)不需要等待，否則，要等待；當(dāng)LEij>0時(shí)，若LEij≤minLT-d，則在經(jīng)過供應(yīng)商j之后車輛到過其他供應(yīng)商時(shí)不會(huì)出現(xiàn)延遲，否則需要延遲進(jìn)行。

1.3修正的C-W算法

根據(jù)Clarke和Wright共同提出的C-W算法，本文做如下約定：（1）若只有1個(gè)供應(yīng)商的線路0→i→0稱作初始線路；（2）包含2個(gè)及2個(gè)以上供應(yīng)商的線路稱作組合線路0→…→i→j→…→0稱作組合線路。根據(jù)上述修正后的模型，C-W算法步驟如下：

步驟1：將各供應(yīng)商與工廠倉庫相連，構(gòu)成n條初始化線路。第i條線路的運(yùn)輸距離為DCi=C0,i+Ci,0。

步驟2：計(jì)算將兩個(gè)供應(yīng)商i，j連接在一條線路上的距離節(jié)約值Si,j=C0, j+C0, j-Di, j，令Si,j=Si,j+Pi,j，M=S|S>0；i,j=1,2,…,n，將集合M內(nèi)的元素Si,j按從大到小的順序排列。

步驟3：考慮集合M內(nèi)的第一個(gè)元素NSi,j所對(duì)應(yīng)的供應(yīng)商i，j是否滿足下列條件之一：

①供應(yīng)商i，j均在初始路線上；

②供應(yīng)商i，j中有一個(gè)在其他組合線路中，并且是線路的起點(diǎn)或終點(diǎn)，另一個(gè)在初始線路上；

③供應(yīng)商分別在兩條不同的線路上，但一個(gè)是起點(diǎn)，另一個(gè)是終點(diǎn)。

若滿足則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟8。

步驟4：根據(jù)供應(yīng)商i，j處貨物的重量和體積計(jì)算若將i，j連接，車輛的載重量和容積是否滿足約束條件（1）和（7）。若滿足，轉(zhuǎn)向步驟6，否則轉(zhuǎn)步驟5。

步驟5：從車輛集合K中選擇更大的車型，轉(zhuǎn)步驟4，如果已達(dá)可用車輛容量上限，則轉(zhuǎn)步驟8。

步驟6：計(jì)算LEij，若LEij=0，轉(zhuǎn)步驟7；若LEij<0且LEij≤mind-ETr，則轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟8；若LEij>0且LEij≤minLT-d，則轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟8。

步驟7：連接供應(yīng)商i和j，構(gòu)成新組合線路。

步驟8：在集合M中消去元素Si,j，若M≠，轉(zhuǎn)步驟3，繼續(xù)探索新的組合方案。否則算法終止。

2實(shí)例

案例描述：P0為一家生產(chǎn)手機(jī)的公司，生產(chǎn)過程以流水線裝配為主，產(chǎn)品采用按訂單生產(chǎn)，使用JIT的生產(chǎn)方式，采用3PL公司保障物料供應(yīng)，3PL公司采取主動(dòng)上門收貨的采購模式。各供應(yīng)商的貨物供給量、貨物體積及車輛到達(dá)時(shí)間要求如表1所示，其中3PL的運(yùn)輸車隊(duì)于凌晨2點(diǎn)出發(fā)，假定車輛的時(shí)速為60km/h，固定裝貨時(shí)間為1分鐘。車隊(duì)有10噸貨車1輛、5噸貨車2輛，5噸和10噸貨車的有效容積分別為12m3和20m3，選取9家具有代表性的供應(yīng)商，各個(gè)供應(yīng)商P,P,…,P之間以及它們與P的地理位置如表2所示。

采用VC++編程求解。按照上述求解步驟，經(jīng)計(jì)算產(chǎn)生三條線路：

P→P1→P0該線路采用10t貨車滿載運(yùn)輸。

P→P1→P8→P9→P7→P0該線路采用5噸貨車滿載運(yùn)輸，容積為10.4m3。

P→P3→P2→P4→P6→P5→P0該線路采用5噸貨車，載重量為4.8t，容積為8.7m3。

由此可見，通過該算法，各需求點(diǎn)都能得到較優(yōu)的運(yùn)輸方案，供應(yīng)商P1的供應(yīng)量最大，可以采用整車運(yùn)輸?shù)姆绞?，其余各供?yīng)商采用5噸貨車收取貨物。

3總結(jié)

本文研究了生產(chǎn)企業(yè)主導(dǎo)的第三方物流在JIT條件下的車輛調(diào)度問題?；綜-W算法可以保證運(yùn)輸路徑的合理化，有效縮減了運(yùn)輸距離；加入到達(dá)時(shí)間約束后，使運(yùn)輸時(shí)間成為一項(xiàng)非常重要的決定因素。因此修正后的C-W算法可以較好地應(yīng)用于JIT采購。本文建立模型還可以在多個(gè)方面進(jìn)一步拓展，此外對(duì)于裝卸貨時(shí)間的動(dòng)態(tài)變化等約束條件會(huì)使問題變得非常復(fù)雜，還有待作進(jìn)一步的研究。

參考文獻(xiàn)：

[1]李昆鵬, 馬士華. 基于JIT配送的3PL運(yùn)輸協(xié)調(diào)調(diào)度問題建模與分析[J]. 交通與計(jì)算機(jī), 2008(2):73-79.

[2]Ruiz Torres, A.J., Tyworth, J.E. Simulation based approach to study the interaction of scheduling and routing on a logistic network[C]//Proceeding of the 1997 Winter Simulation Conference, 1997.

[3]Chang, Y.C., Lee, C.Y.. Machine scheduling with job delivery coordination[J]. European Journal of Operational Research,2004,158:470-487.

[4]Garcia, J.M., Lozano, S., Canca, D.. Coordinated scheduling of production and delivery from multiple plants[J]. Robotics and Computer Integrated Manufacturing, 2004,20(3):191-198.

[5]祝崇雋, 劉民, 吳澄. 供應(yīng)鏈中車輛路徑問題的研究進(jìn)展及前景[J]. 計(jì)算機(jī)集成制造系統(tǒng)——CIMS, 2001(7):1-6.

[6]朱曉蘭, 趙一飛. C-W節(jié)約算法在裝配企業(yè)采購物流中的應(yīng)用[J]. 上海交通大學(xué)學(xué)報(bào), 2007(9):1420-1424.

[7]李靜, 鐘典欽. 基于CW節(jié)約算法的ERP系統(tǒng)改進(jìn)研究[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2007(11):5214-5217.

[8]林曉宇, 李金銘, 紀(jì)壽文. 車輛路徑問題Clarke-Wright算法的改進(jìn)與實(shí)現(xiàn)[J]. 交通與計(jì)算機(jī), 2004(6):72-75.