布草租賃洗滌物流網(wǎng)絡(luò)優(yōu)化

劉 琛，王 東

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

1 引言

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

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

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

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

多級(jí)配送模式的物流環(huán)節(jié)中包含了若干級(jí)中轉(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)客戶需求普遍小于整車的容量時(shí)，則在進(jìn)行中轉(zhuǎn)站選址的過(guò)程中，還需要考慮車輛配送的路徑，即定位-路徑問(wèn)題（Location-Routing problem，LRP）。在LRP問(wèn)題中，中轉(zhuǎn)站點(diǎn)的位置選取會(huì)影響到配送車輛的配送路徑；配送車輛路徑的安排也會(huì)影響應(yīng)急中轉(zhuǎn)站點(diǎn)布局的合理性。在布草洗滌物流中，也需要同時(shí)考慮上述兩個(gè)重要問(wèn)題，從系統(tǒng)整體優(yōu)化的角度出發(fā)，對(duì)物流系統(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)輸問(wèn)題中的運(yùn)輸成本和定位成本的相互關(guān)系。隨后國(guó)內(nèi)外研究人員根據(jù)不同知識(shí)背景修改和拓展LRP模型，使得模型更接近現(xiàn)實(shí)物流配送系統(tǒng)。Laporte et al.(1989)[2]考慮客戶的需求滿足某概率分布，若規(guī)劃路線中客戶需求超過(guò)車輛容量，則需要額外配送，這一部分費(fèi)用也計(jì)入總成本中。Wu et al.(2002)[3]在約束條件里對(duì)諸如車型、車輛運(yùn)輸能力等進(jìn)行了限制。Albareda-Sambola et al.(2005)[4]增加了LRP模型的層次，并且考慮了庫(kù)存成本。隨后，逆向物流越來(lái)越受到人們的重視，Ceiner(2010)[5]，Karaogaln(2011)[6]等學(xué)者將回收和配送過(guò)程同時(shí)考慮，改進(jìn)了LRP模型。

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

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

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

3.1 問(wèn)題描述

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

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

需要解決的問(wèn)題是，在滿足自有配送車輛的容積限制下，確定中轉(zhuǎn)站點(diǎn)的選址，以及各個(gè)中轉(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車輛工作時(shí)間限制

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

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

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

3.4 模型求解

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

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

圖1 算法流程

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

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

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

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

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

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

其中指數(shù)部分可以使原有適應(yīng)度較高的個(gè)體的新適應(yīng)度與其他個(gè)體的新適應(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)建配送路線。

插入法包含二個(gè)步驟[14]：

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

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

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

4 案例驗(yàn)證

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

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

設(shè)置車輛容量限制為每車次300套布草，車輛日行駛時(shí)間不超過(guò)10h，平均時(shí)速為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)的計(jì)算匯總表見(jiàn)表1：

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

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

表1 成本一覽表

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

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

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

5 總結(jié)

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

在今后進(jìn)一步的研究中，應(yīng)該優(yōu)化多車次車輛路徑規(guī)劃以及考慮時(shí)間窗約束、中轉(zhuǎn)站庫(kù)存等問(wè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]王迎春.配送中心動(dòng)態(tài)選址-路線安排問(wèn)題研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2007.

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