宋志剛　武勝良

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

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

中圖分類號：F224文獻標(biāo)識碼：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)時制生產(chǎn)的采購方式，要求既要能保證物資的供應(yīng)，又要降低庫存量、縮短訂貨提前期、提高產(chǎn)品質(zhì)量、降低采購成本。在這種采購方式下，車輛的提早或延遲到達原材料供應(yīng)地均會產(chǎn)生附加成本。因此制造企業(yè)在制定其生產(chǎn)調(diào)度和運輸調(diào)度策略時，必須從全局出發(fā)，考慮供應(yīng)鏈整體動作成本最小化。作為整個供應(yīng)鏈中的一環(huán)，在進行車輛的運輸調(diào)度時，必須考慮與生產(chǎn)之間的有效銜接。

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

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

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

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

目前有關(guān)C-W算法的研究多用于物流配送，如連鎖超市、煙草配送等，且?guī)r間窗約束的改進算法研究較多，但卻少有將該算法應(yīng)用于采購物流領(lǐng)域的。從物流布局來看，采購物流的VRP問題也可以用配送領(lǐng)域的C-W算法來解決。但必須滿足兩個前提條件：（1）整個供應(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)商的集合。為單位距離的運輸成本。

（2）每次取貨時，向供應(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)是總運輸距離最小化，因此目標(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從點i到點j，其中i≠j；i,j∈N；約束條件（2）表示供應(yīng)商i處的原材料由車輛k收取，其中i≠0；約束條件（3）表示每一采購路線上采購數(shù)量受車輛最大載重量的限制；約束條件（4）表示每個采購商處必須有一輛車去取貨；約束條件（5）表示如果車輛k至采購商j處取貨，則k必從點i到達點j；約束條件（6）表示若車輛k至采購商i處取貨，則k必在該處取完貨后到達采購商j。

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

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

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

（1）容積約束

ViYk,i≤Vc,k （7）

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

（2）時間的約束

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

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

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

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

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

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

則:

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)商時不需要等待，否則，要等待；當(dāng)LEij>0時，若LEij≤minLT-d，則在經(jīng)過供應(yīng)商j之后車輛到過其他供應(yīng)商時不會出現(xiàn)延遲，否則需要延遲進行。

1.3修正的C-W算法

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

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

步驟2：計算將兩個供應(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)的第一個元素NSi,j所對應(yīng)的供應(yīng)商i，j是否滿足下列條件之一：

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

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

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

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

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

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

步驟6：計算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實例

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

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

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。

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

3總結(jié)

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

參考文獻：

[1]李昆鵬, 馬士華. 基于JIT配送的3PL運輸協(xié)調(diào)調(diào)度問題建模與分析[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]. 計算機集成制造系統(tǒng)——CIMS, 2001(7):1-6.

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

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

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