Ｃ－Ｗ算法在ＪＩＴ采購中的應用

宋志剛　武勝良

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

關鍵詞：JIT；運輸調度；C-W節約算法；3PL

中圖分類號：F224文獻標識碼：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引言

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

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

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

1C-W節約算法研究與改進

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

目前有關C-W算法的研究多用于物流配送，如連鎖超市、煙草配送等，且帶時間窗約束的改進算法研究較多，但卻少有將該算法應用于采購物流領域的。從物流布局來看，采購物流的VRP問題也可以用配送領域的C-W算法來解決。但必須滿足兩個前提條件：（1）整個供應鏈由生產企業主導；（2）采購所需原材料的生產過程平穩有序，采購企業可以使用JIT的生產方式。

1.1基本數學模型

1.1.1假設下列條件已知

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

（2）每次取貨時，向供應商采購產品的數量。令Wi為從供應商i處采購的原材料重量（i=1,2,…,n）。

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

1.1.2數學模型

由于采購取貨的基本目標是總運輸距離最小化，因此目標函數為：

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從點i到點j，其中i≠j；i,j∈N；約束條件（2）表示供應商i處的原材料由車輛k收取，其中i≠0；約束條件（3）表示每一采購路線上采購數量受車輛最大載重量的限制；約束條件（4）表示每個采購商處必須有一輛車去取貨；約束條件（5）表示如果車輛k至采購商j處取貨，則k必從點i到達點j；約束條件（6）表示若車輛k至采購商i處取貨，則k必在該處取完貨后到達采購商j。

1.2修正的數學模型

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

因此在基本C-W算法模型中加入容積約束以及運輸提前或延遲對目標函數的影響。

（1）容積約束

ViYk,i≤Vc,k （7）

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

（2）時間的約束

LEij——連接供應商i與供應商j后，車輛到達供應商j的時間比原線路上車輛到達供應商j時間的提前量（延遲量）

di——為到達供應商i處的規定時間

dij——為從供應商i處到供應商j處的規定時間

Ti——為在供應商i處的裝貨時間

ETi——為供應商i處允許的最早開始時間，車輛早于此時間則會等待

LTi——為供應商i處允許的最遲開始時間，車輛晚于此時間則會延遲

則:

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

設車輛經過供應商j之后所需要經過的供應商為r，當LEij<0，若LEij≤mind-ET，則在經過供應商j之后車輛到過其他供應商時不需要等待，否則，要等待；當LEij>0時，若LEij≤minLT-d，則在經過供應商j之后車輛到過其他供應商時不會出現延遲，否則需要延遲進行。

1.3修正的C-W算法

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

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

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

步驟3：考慮集合M內的第一個元素NSi,j所對應的供應商i，j是否滿足下列條件之一：

①供應商i，j均在初始路線上；

②供應商i，j中有一個在其他組合線路中，并且是線路的起點或終點，另一個在初始線路上；

③供應商分別在兩條不同的線路上，但一個是起點，另一個是終點。

若滿足則轉步驟4，否則轉步驟8。

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

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

步驟6：計算LEij，若LEij=0，轉步驟7；若LEij<0且LEij≤mind-ETr，則轉步驟7，否則轉步驟8；若LEij>0且LEij≤minLT-d，則轉步驟7，否則轉步驟8。

步驟7：連接供應商i和j，構成新組合線路。

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

2實例

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

采用VC++編程求解。按照上述求解步驟，經計算產生三條線路：

P→P1→P0該線路采用10t貨車滿載運輸。

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

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

由此可見，通過該算法，各需求點都能得到較優的運輸方案，供應商P1的供應量最大，可以采用整車運輸的方式，其余各供應商采用5噸貨車收取貨物。

3總結

本文研究了生產企業主導的第三方物流在JIT條件下的車輛調度問題。基本C-W算法可以保證運輸路徑的合理化，有效縮減了運輸距離；加入到達時間約束后，使運輸時間成為一項非常重要的決定因素。因此修正后的C-W算法可以較好地應用于JIT采購。本文建立模型還可以在多個方面進一步拓展，此外對于裝卸貨時間的動態變化等約束條件會使問題變得非常復雜，還有待作進一步的研究。

參考文獻：

[1]李昆鵬, 馬士華. 基于JIT配送的3PL運輸協調調度問題建模與分析[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]祝崇雋, 劉民, 吳澄. 供應鏈中車輛路徑問題的研究進展及前景[J]. 計算機集成制造系統——CIMS, 2001(7):1-6.

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

[7]李靜, 鐘典欽. 基于CW節約算法的ERP系統改進研究[J]. 計算機工程與設計, 2007(11):5214-5217.

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