劉 琛，王 東

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

1 引言

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

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

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

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

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

2 文獻(xiàn)綜述

關(guān)于LRP的文獻(xiàn)主要集中在LRP模型的研究和LRP求解算法的研究。

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

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

盡管國內(nèi)外學(xué)者對商業(yè)、公共物流系統(tǒng)中的LRP已經(jīng)進(jìn)行了不少的研究，但是對于布草洗滌的物流系統(tǒng)研究幾乎沒有。借鑒其他行業(yè)的物流系統(tǒng)，結(jié)合布草租賃洗滌的實(shí)際情況，本文建立了以下規(guī)劃模型。

3 數(shù)學(xué)建模

3.1 問題描述

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

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

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

3.2 變量與參數(shù)

3.2.1 變量

本文涉及的變量包括：

變量間的關(guān)系為：

3.2.2 參數(shù)

本文涉及的參數(shù)包括：

G中轉(zhuǎn)站候選點(diǎn)集合

D客戶酒店集合

V自有車輛集合

L自有車輛車次集合

l表示第l車次

S=G?D中轉(zhuǎn)站候選點(diǎn)和客戶酒店的集合

qi客戶i日均需求

Qi候選點(diǎn)i的容量

Q自有配送車輛容量

T車輛工作時間限制

tij自有車輛從點(diǎn)i到點(diǎn)j所需要的時間

Fi候選點(diǎn)i的日均租金

Cij自有車輛從點(diǎn)i到點(diǎn)j進(jìn)行配送的日均費(fèi)用

C車輛的日均費(fèi)用（維護(hù)費(fèi)用、司機(jī)工資）

Kj租賃車從洗滌廠到候選點(diǎn)j的費(fèi)用（與載重量成正比）

3.3 模型構(gòu)建

根據(jù)上述假設(shè)、變量和參數(shù)，建立布草租賃洗滌的物流網(wǎng)絡(luò)，模型如下：

目標(biāo)函數(shù)：使得日均中轉(zhuǎn)站點(diǎn)和運(yùn)輸費(fèi)用最小化。

其中第一項(xiàng)表示自營車輛每天的配送成本；第二項(xiàng)表示租賃車輛每天干線運(yùn)輸?shù)馁M(fèi)用；第三項(xiàng)表示車輛的日均費(fèi)用；第四項(xiàng)表示中轉(zhuǎn)站的日均費(fèi)用。

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

3.4 模型求解

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

3.4.1 算法流程。算法詳細(xì)流程如圖1所示：

圖1 算法流程

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

（1）編碼。編碼采用二進(jìn)制編碼，基因第i位表示候選點(diǎn)i的候選情況。1表示該候選點(diǎn)設(shè)立中轉(zhuǎn)站點(diǎn)，0表示不設(shè)立。

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

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

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

（5）適應(yīng)值。適應(yīng)值函數(shù)用于對個體進(jìn)行評價，是優(yōu)化選擇的依據(jù)。由于模型中所求的目標(biāo)函數(shù)是最最小值，因此將本文中個體X的適應(yīng)值函數(shù)選擇為：

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

3.4.3 改進(jìn)的插入法。插入法是Mole和Jameson于1976年所提出，結(jié)合了最鄰近法與節(jié)省法的觀念，依序?qū)㈩櫩忘c(diǎn)插入路徑中以構(gòu)建配送路線。

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

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

（2）以節(jié)省法決定該顧客點(diǎn)應(yīng)被插入的位置，在車輛容量限制下，重復(fù)進(jìn)行選取與插入的步驟，當(dāng)無法再擴(kuò)大充路徑時，則再建立另一路線，直至所有顧客都被排入路徑中。

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

4 案例驗(yàn)證

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

圖2 某洗滌廠案例各點(diǎn)分布圖

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

已經(jīng)設(shè)立的中轉(zhuǎn)站點(diǎn)的計算匯總表見表1：

圖4、圖5分別為3號和9號中轉(zhuǎn)站點(diǎn)的路徑規(guī)劃結(jié)果。

圖3 遺傳算法計算結(jié)果

表1 成本一覽表

圖4 3號中轉(zhuǎn)站點(diǎn)的路徑規(guī)劃結(jié)果

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

圖5 9號中轉(zhuǎn)站點(diǎn)的路徑規(guī)劃結(jié)果

5 總結(jié)

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

在今后進(jìn)一步的研究中，應(yīng)該優(yōu)化多車次車輛路徑規(guī)劃以及考慮時間窗約束、中轉(zhuǎn)站庫存等問題。

[參考文獻(xiàn)]

[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]汪定偉.智能優(yōu)化方法[M].北京:高等教育出版社,2007.

[13]王迎春.配送中心動態(tài)選址-路線安排問題研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2007.

[14]夏新海.物流配送車輛調(diào)度優(yōu)化研究[D].武漢:武漢理工大學(xué),2004.