布草租賃洗滌物流網絡優化

劉 琛，王 東

（1.上海交通大學中美物流研究院，上海 200030；2.上海交通大學 軟件學院，上海 200040）

1 引言

隨著我國城市化進程的加快，城市內出現了大量的賓館飯店、醫療單位、餐館酒店、工廠、學校、機關團體等大型服務企業和單位。由于城市內土地、水資源的稀缺，大型服務性企業和單位沒有條件對日常使用的布草進行就地洗滌作業，而是將自有布草的洗滌作業外包給專業的洗滌公司。然而，對于洗滌企業來說，客戶自有布草的品種、材質、大小、洗滌要求、耐性程度等屬性千差萬別，無法進行統一流程的洗滌和管理，難以產生規模經濟。于是新的布草租賃、洗滌一體化模式被提了出來。

租賃洗滌是洗滌企業將床單、被罩、毛巾、浴巾等布草出租給有需要的客戶，同時提供日常的洗滌服務。在這種租賃、洗滌一體化的模式下，企業或單位不僅可以免去洗滌作業所需的人力、物力、財力和空間，還能減少布草占用的資金以及淡季的布草庫存成本；洗滌企業則可以將大量相同的布草匯集到中央洗滌工廠，進行大規模洗滌作業，從而提高設備使用率，并降低能耗，產生規模效益。

服務型企業或單位的布草屬于高頻使用物品，這要求洗滌企業不但要高效、快速地完成洗滌作業，還要保證布草能夠準時配送和回收。目前，洗滌企業多采用一級配送的方式，即在整個布草配送回收過程中，將洗滌廠作為唯一物流據點，通過自有車輛或者租賃車輛進行物流作業。隨著客戶數量的增多、分布范圍的擴大，洗滌企業的物流作業難度和成本相應增加，再加上城市對大型車輛的通行有諸多限制，一級配送方式逐漸難以保證對客戶的響應速度和配送效率。物流成本高企，嚴重阻礙了租賃洗滌業的發展。

多級配送模型具有整合物流資源、提高物流資源利用效率、降低物流成本的作用，并且應用于郵政業務、航空運輸、企業物流諸多領域。本文試圖借鑒其他領域經驗，探究多級配送模型在布草租賃洗滌物流領域的應用。

多級配送模式的物流環節中包含了若干級中轉點或者配送中心，工廠到中轉站點可以采用大型運輸工具進行直達運輸，然后使用小型車輛進行配送。中轉站點的選址決定了物流系統運行的優劣，當客戶需求普遍小于整車的容量時，則在進行中轉站選址的過程中，還需要考慮車輛配送的路徑，即定位-路徑問題（Location-Routing problem，LRP）。在LRP問題中，中轉站點的位置選取會影響到配送車輛的配送路徑；配送車輛路徑的安排也會影響應急中轉站點布局的合理性。在布草洗滌物流中，也需要同時考慮上述兩個重要問題，從系統整體優化的角度出發，對物流系統進行集成優化和管理。

2 文獻綜述

關于LRP的文獻主要集中在LRP模型的研究和LRP求解算法的研究。

有關LRP模型的文獻可以追溯到1961年Von Boventer[1]關于運輸問題中的運輸成本和定位成本的相互關系。隨后國內外研究人員根據不同知識背景修改和拓展LRP模型，使得模型更接近現實物流配送系統。Laporte et al.(1989)[2]考慮客戶的需求滿足某概率分布，若規劃路線中客戶需求超過車輛容量，則需要額外配送，這一部分費用也計入總成本中。Wu et al.(2002)[3]在約束條件里對諸如車型、車輛運輸能力等進行了限制。Albareda-Sambola et al.(2005)[4]增加了LRP模型的層次，并且考慮了庫存成本。隨后，逆向物流越來越受到人們的重視，Ceiner(2010)[5]，Karaogaln(2011)[6]等學者將回收和配送過程同時考慮，改進了LRP模型。

對于LRP的解法，目前有兩種思路：一是精確解法，通常使用數學規劃的方法，將LRP問題中的約束松弛或者重新引入約束，進而能夠求解[7]。精確解法可以得到最優解，但是由于LRP自身問題的復雜性，只適用小規模問題。另一種思路是啟發式方法，用來求解較大規模的問題。目前利用啟發式算法求解LRP的文獻可以分為四類：（1）順序解法。首先通過最小化客戶到中轉點的距離和來解決定位問題，然后依上一步的選址結果進行車輛路徑規劃[8]。（2）聚類解法。首先將需求點劃分為不同的簇，然后在每個簇中選擇中轉站并解決路徑規劃問題[9]。（3）迭代解法。首先將問題分成選址和路徑規劃兩個組合的子問題，其中一個子問題的結果會提供反饋信息，從而影響另一個子問題的求解，先求解問題結果的優劣會讓后續子問題的結果產生較大的偏離，于是提出了兩階段解法[10]。（4）兩階段解法將選址問題作為主要算法，在每一步迭代中嵌套車輛路徑問題的求解，這種解法更接近實際情況也更可能得到滿意解[11]。

盡管國內外學者對商業、公共物流系統中的LRP已經進行了不少的研究，但是對于布草洗滌的物流系統研究幾乎沒有。借鑒其他行業的物流系統，結合布草租賃洗滌的實際情況，本文建立了以下規劃模型。

3 數學建模

3.1 問題描述

多級配送模式下的洗滌布草物流過程是：洗滌廠將干凈布草由大型租賃車輛運送到各個中轉站點，然后由從中轉站點出發的自有小型車輛將干凈布草配送至中心站點服務的需求點，配送的過程中，同時將臟布草回收。配送車輛返回中轉站，租賃車輛將臟布草統一運回至洗滌廠洗滌。

酒店需要洗滌的布草是每天變化的，為了簡化模型取一年內需要洗滌布草的均值為每天的需求量，每個需求點需要回收的臟布草數量與配送的干凈布草數量相同，且不會超過配送車輛的容量。一個需求點每天僅被服務一次，出于安全考慮配送車輛每天的運行時間不超過12h。

需要解決的問題是，在滿足自有配送車輛的容積限制下，確定中轉站點的選址，以及各個中轉站點到各需求點的運輸路徑。使得中轉站設立成本、車輛持有成本、配送成本、干線運輸成本之和最小。

3.2 變量與參數

3.2.1 變量

本文涉及的變量包括：

變量間的關系為：

3.2.2 參數

本文涉及的參數包括：

G中轉站候選點集合

D客戶酒店集合

V自有車輛集合

L自有車輛車次集合

l表示第l車次

S=G?D中轉站候選點和客戶酒店的集合

qi客戶i日均需求

Qi候選點i的容量

Q自有配送車輛容量

T車輛工作時間限制

tij自有車輛從點i到點j所需要的時間

Fi候選點i的日均租金

Cij自有車輛從點i到點j進行配送的日均費用

C車輛的日均費用（維護費用、司機工資）

Kj租賃車從洗滌廠到候選點j的費用（與載重量成正比）

3.3 模型構建

根據上述假設、變量和參數，建立布草租賃洗滌的物流網絡，模型如下：

目標函數：使得日均中轉站點和運輸費用最小化。

其中第一項表示自營車輛每天的配送成本；第二項表示租賃車輛每天干線運輸的費用；第三項表示車輛的日均費用；第四項表示中轉站的日均費用。

其中，公式（2）表示支線配送車輛容量約束；公式（3）表示支線配送車輛行駛約束；公式（4）保證每個酒店僅有一輛車的某一車次訪問；公式（5）表示每個酒店僅分配到一個中轉站點；公式（6）、（7）保證中轉站開設了才能分配客戶，沒開設則不分配客戶；公式（8）是連續性約束，保證某車輛的某車次從某點進需要從某點出；公司（9）表示每車次只經過一個中轉站點；公式（10）-（11）表示當中轉站開設了才分配車輛，沒有開設則不分配車輛；公式（12）-（13）表示當車輛可用了，才有相應的車次；公式（14）表示被分配給某個中轉站的客戶，由屬于中轉站的車輛配送；公式（15）表示一輛車只服務一個中轉站，即任意中轉站間沒有連接；公式（16）確保規劃路線沒有子回路。

3.4 模型求解

上述模型可以歸結為LRP問題，LRP問題屬于NP-hard問題，加上上述模型變量、約束眾多，傳統的精確解法難以在有效時間和有限計算資源上求解，因此本文采取以遺傳算法[12-13]為總框架，嵌套改進的插入法的兩階段算法來求解此模型。

3.4.1 算法流程。算法詳細流程如圖1所示：

圖1 算法流程

3.4.2 遺傳算法。遺傳算法是由美國J.H.Holland于1975年提出的一種基于生物體進化機制的智能算法，它模擬了自然界中生物體的生存和繁殖過程。根據問題的目標函數構造一個適應度函數，對一個由多個解（每個解對應一個染色體）構成的種群進行評估、遺傳運算、選擇，經多代繁殖，獲得適應度最好的個體作為問題的最優解。

（1）編碼。編碼采用二進制編碼，基因第i位表示候選點i的候選情況。1表示該候選點設立中轉站點，0表示不設立。

（2）選擇。選擇操作是為了選擇高性能的個體得以更大的概率生存，從而提高全局收斂性和計算效率，本文選擇操作采用輪盤賭選擇，并運用精英保留策略加快收斂速度。

（3）變異。變異操作可以避免遺傳算法陷入局部最優解，本文采用單點變異的方法。

（4）交叉。交叉操作用于組合新的個體，在解空間中進行有效的搜索，同時降低有效解的破壞概率。本文采取單點交叉的方法。

（5）適應值。適應值函數用于對個體進行評價，是優化選擇的依據。由于模型中所求的目標函數是最最小值，因此將本文中個體X的適應值函數選擇為：

其中指數部分可以使原有適應度較高的個體的新適應度與其他個體的新適應度相差較大，增加了選擇的強制性。f(x)為第二階段的路徑規劃的結果包含支線配送成本和車輛持有成本，a、b為正值參數。

3.4.3 改進的插入法。插入法是Mole和Jameson于1976年所提出，結合了最鄰近法與節省法的觀念，依序將顧客點插入路徑中以構建配送路線。

插入法包含二個步驟[14]：

（1）選取距離配送中心最遠的顧客點為起點，從其它剩余的顧客點中，根據最鄰近法決定下一個被插入的顧客點。

（2）以節省法決定該顧客點應被插入的位置，在車輛容量限制下，重復進行選取與插入的步驟，當無法再擴大充路徑時，則再建立另一路線，直至所有顧客都被排入路徑中。

該方法只適合單一車次的路徑構建，本文提出以下改進方案：在（2）中已有路線插入顧客點時，可以再插入中轉站，此時形成新的車次。一條路線由多條車次構成，一輛車只行駛一條路徑，增加新的路線需要增加額外的車輛，造成成本的增加。在進行插入步驟時候，要保證每一車次貨物量不超過車輛限制，整個行駛路線的時間不超過車輛行駛時間限制。

4 案例驗證

以某布草洗滌廠為例，該洗滌廠計劃在10個候選點中設立若干個中轉站點，服務150個客戶點，位置和日均布草需求已知，如圖2所示。

圖2 某洗滌廠案例各點分布圖

設置車輛容量限制為每車次300套布草，車輛日行駛時間不超過10h，平均時速為30km/h，車輛日均持有成本為350元/d；中轉站設立之后日均費用為2 000元/d；干線運輸費用為0.005元/套·km；支線配送費用為2.5元/km；交叉比率為0.25，變異比率為0.01；a取0.000 1，b取1。迭代100次的結果如圖3所示：

已經設立的中轉站點的計算匯總表見表1：

圖4、圖5分別為3號和9號中轉站點的路徑規劃結果。

圖3 遺傳算法計算結果

表1 成本一覽表

圖4 3號中轉站點的路徑規劃結果

在優化之前，洗滌廠作為唯一物流據點，采用案例中的參數和上文提出的改進型插入法進行路徑規劃，則需要15輛自有小型車輛，共計46車次，自有車輛成本和配送成本共計13 742元/d。采用兩級物流網絡之后，進行配送則只需要6輛自有小型車輛，共計31車次，各類成本需11 619元/d，成本減少了15.45%。調整布草租賃洗滌物流網絡結構之后，物流成本得到了有效減少，但是兩層物流結構也多了中轉的環節，對租賃洗滌企業的管理水平提出了更高的要求。

圖5 9號中轉站點的路徑規劃結果

5 總結

針對布草租賃洗滌的物流網絡優化是租賃洗滌模式良好運行的重中之重，而研究其配送回收物流網絡可以為洗滌公司節省物流成本提供有益的指導，進而為推廣租賃洗滌模式提供物流基礎。本文針對布草租賃洗滌的物流配送需求，建立了中轉站選址與車輛路徑安排問題的集成優化模型，考慮了車輛容量限制、行駛時間限制、多車次等約束條件，以車輛持有成本、支線配送成本、干線運輸成本和中轉站設立成本之和最低為目標，比較符合現實情況。此外，本文利用遺傳算法為求解框架，集成適合求解多車次路徑規劃問題的改進后的插入法，案例分析表明，該算法運行效果較好。

在今后進一步的研究中，應該優化多車次車輛路徑規劃以及考慮時間窗約束、中轉站庫存等問題。

[參考文獻]

[1]Boventer EV.The Relationship Between Transportation Costs And Location Rent In Transportation Problems[J].Journal of Regional Science,1961,3(2):27-40.

[2]Laporte G,Louveaux F,Mercure H.Models and exact solutions for a class of stochastic location-routing problems[J].European Journal of Operational Research,1989,39(1):71-78.

[3]Wu T H,Low C,Bai J W.Heuristic solutions to multi-depot location-routing problems[J].Computers&Operations Research,2002,29(10):1 393-1 415.

[4]Albareda-Sambola M,D Az J A,Fernández E.A compact model and tight bounds for a combined location-routing problem[J].Computers&Operations Research,2005,32(3):407-428.

[5]Cetiner S,Sepil C,Süral H.Hubbing and routing in postal delivery systems[J].Annals of Operations Research,2010,181(1):109-124.

[6]Karaoglan I,Altiparmak F,Kara I,et al.The location-routing problem with simultaneous pickup and delivery:Formulations and a heuristic approach[J].Omega,2012,40(4):465-477.

[7]Laporte G,Nobert Y,Taillefer S.Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems[J].Transportation Science,1988,22(3):161-172.

[8]Daganzo C F.Logistics Systems Analysis(second edition)[J].Journal of the Operational Research Society,1997,48(4).

[9]Min H.Consolidation terminal location-allocation and consolidated routing problems[J].Journal of Business Logistics,1996,17(2):235-263.

[10]Hansen P H,Hegedahl B,Hjortkj?r S,et al.A heuristic solution to the warehouse location-routing problem[J].European Journal of Operational Research,1994,76(1):111-127.

[11]Nagy G,Salhi S.Nested Heuristic Methods for the Location-Routing Problem[J].Location Science,1996,47(9):1 166-1 174.

[12]汪定偉.智能優化方法[M].北京:高等教育出版社,2007.

[13]王迎春.配送中心動態選址-路線安排問題研究[D].哈爾濱:哈爾濱工業大學,2007.

[14]夏新海.物流配送車輛調度優化研究[D].武漢:武漢理工大學,2004.