基于遺傳算法的協(xié)同配送路徑優(yōu)化研究

曹慶奎，李言幫，陸 楠 CAO Qing-kui,LI Yan-bang,LU Nan

（河北工程大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北 邯鄲 056038）

(School of Economics&Management,Hebei University of Engineering,Handan 056038,China)

對(duì)于現(xiàn)代物流企業(yè)，如何降低營(yíng)運(yùn)成本、提高獲利能力、優(yōu)化運(yùn)輸路線成為物流管理的核心問題，直接影響和決定物流企業(yè)的核心競(jìng)爭(zhēng)力。經(jīng)濟(jì)區(qū)域內(nèi)，多物流中心各自根據(jù)客戶要求選擇配送路線的現(xiàn)象對(duì)于資源的利用率低、成本高，協(xié)同配送作為一種新的配送方式應(yīng)運(yùn)而生。協(xié)同配送就是把過去按不同貨主、不同商品分別進(jìn)行的配送，改為不區(qū)分貨主和商品集中運(yùn)貨的“貨物及配送的集約化”。也就是把貨物都裝入在同一條路線運(yùn)行的車上，用同一臺(tái)卡車為更多的顧客運(yùn)貨，有效地降低了營(yíng)運(yùn)的成本，提高了資源利用率和物流企業(yè)競(jìng)爭(zhēng)力。

路徑優(yōu)化問題一直是學(xué)者們研究的熱點(diǎn)，協(xié)同配送的配送方式的研究正處于初級(jí)階段，Zhang等采用一種框架式的中央?yún)f(xié)調(diào)系統(tǒng)，同時(shí)配備一個(gè)多目標(biāo)遺傳優(yōu)化的功能解決了在協(xié)同配送中訂單分布的問題[1]。溫惠英等用了模糊規(guī)劃模型和算法，考慮車輛行駛時(shí)間和顧客服務(wù)時(shí)間的不確定性，建立車輛配送總費(fèi)用最小的協(xié)同車輛路徑問題模糊規(guī)劃模型，使用了自適應(yīng)離散粒子群算法求解了該問題[2]。李丁等基于虛擬企業(yè)與資源集成理論，提出在虛擬環(huán)境下第三方物流企業(yè)實(shí)施協(xié)同配送的模型，并用Automod仿真軟件對(duì)該模型進(jìn)行了仿真研究[3]。劉明等構(gòu)建了一種混合協(xié)同配送模式兼顧了傳統(tǒng)點(diǎn)對(duì)點(diǎn)配送模式和樞紐輻射模式的長(zhǎng)處，給出了具體求解的啟發(fā)式搜索算法，采用該模式能形成更加高效的應(yīng)急救援網(wǎng)絡(luò)[4]。楊韜等提出協(xié)同配送通過企業(yè)間資源共享、優(yōu)勢(shì)互補(bǔ)，能有效降低配送成本，增加收益。協(xié)同配送能否健康發(fā)展關(guān)鍵在于合作企業(yè)間的成本分?jǐn)偱c利益分配是否合理，綜合考慮收益與成本提出了收益分配的新思路[5]。王新平等采用縱向配送和橫向轉(zhuǎn)運(yùn)相結(jié)合的協(xié)同配送模式，構(gòu)建了一類應(yīng)急物流網(wǎng)絡(luò)優(yōu)化多目標(biāo)隨機(jī)規(guī)劃模型[6]。綜上所述，普通配送方式的路徑優(yōu)化的研究已經(jīng)比較成熟，但是協(xié)同配送的物流配送方式的研究現(xiàn)在主要是對(duì)于利益分配機(jī)制的研究。對(duì)于協(xié)同配送的物流配送路徑優(yōu)化的研究很少，而且對(duì)協(xié)同配送的研究也主要是針對(duì)配送的成本降低展開的，對(duì)影響配送的其他方面的研究很少。

1 協(xié)同配送路徑優(yōu)化數(shù)學(xué)模型的描述及建立

本文結(jié)合普通物流配送路徑優(yōu)化的模型建立，以物流中心與客戶為研究對(duì)象，遵從費(fèi)用最小化原則，考慮雙方在物流過程中所涉及的配送距離、車輛載重等問題，構(gòu)建協(xié)同配送路徑模型：

假設(shè)聯(lián)盟中有M個(gè)物流中心 （m=1,2,…,M）向N個(gè)站點(diǎn) （n=1,2,…,N ）配送貨物，且每個(gè)物流中心只有一輛可用的車輛，每輛車的最大載重量為G，第n個(gè)站點(diǎn)的貨運(yùn)量為g（n），允許車輛進(jìn)入站點(diǎn)的最早時(shí)間為St（n ），最遲時(shí)間為Et（n ），St（n）≤Et（n），卸貨消耗時(shí)間為T（n ），客戶n的坐標(biāo)位置為 （xn,yn）；物流中心m的坐標(biāo)為 （xm,ym），平均車速v（m ），調(diào)動(dòng)車輛固定費(fèi)用pf，車輛行駛每公里消耗費(fèi)用pc。顯然配送總費(fèi)用為調(diào)用車輛固定費(fèi)用與車輛運(yùn)輸費(fèi)用之和，多中心協(xié)同配送調(diào)度的目標(biāo)就是總費(fèi)用Z最低。由此建立數(shù)學(xué)模型如下：

其中，S（ m,n）=1表示站點(diǎn)n由m中心配送，否則S（ m,n）=0；如果n是該車輛的第一站或最后一站（最后一站完成后返回m中心），F(xiàn)L（ m,n）=1，否則FL（ m,n）=0；L（ m,i,j）=1表示第m中心經(jīng)i站點(diǎn)到達(dá)j站點(diǎn)（i≠j），否則L（ m,i,j）=0。D（ i,j）為兩個(gè)站點(diǎn)i和j之間的距離，D（ m,n）為中心m和站點(diǎn)n之間的距離。

約束條件：

假設(shè)m中心進(jìn)入第i站點(diǎn)的時(shí)刻為Tm,i，下一個(gè)站點(diǎn)為i+1，那么有下列約束條件：

2 基于多物流中心協(xié)同配送路徑優(yōu)化的遺傳算法

2.1 算法描述

2.1.1 編碼選擇和初始群體建立

[8]阿蘭·羅伯-格里耶：《理論有什么用》，《快照集/為了一種新小說》，余中先譯，長(zhǎng)沙：湖南美術(shù)出版社，2001年，第74頁。

本文采用自然數(shù)編碼的編碼方式。m1,m2,…,mm為配送中心，隨機(jī)產(chǎn)生n個(gè)客戶的全排列1,2,3,…,n為各客戶。這樣可以編碼m11 2 m1m13 4 5 6…n-1 n mm表示一種配送方案可行解。其中：m11 2 m1表示由配送中心對(duì)各戶1和2進(jìn)行配送任務(wù)，每個(gè)配送中心的配送必須滿足模型建立中的約束條件，以此類推。各配送中心分別對(duì)自己的客戶進(jìn)行配送就可以表示出來。在編碼選擇配送中心的分配方式上將前一配送中心與下一配送中心結(jié)合，將其假設(shè)是一個(gè)配送中心，像m1m2變成m12，將m12m23m34…mn-1n先后順序依次插入排列中保證相鄰的兩個(gè)之間都有客戶，這樣排列就變成m11 2 m123 4 5 m236…n-1nmm。按照這樣的方法得到該問題的初始可行解也就是初始群體。

2.1.2 適應(yīng)度函數(shù)

對(duì)于配送路徑方案的評(píng)判，由于編碼方法是根據(jù)車輛調(diào)度問題的特點(diǎn)確定的，其隱含每個(gè)客戶都得到配送服務(wù)及每個(gè)客戶僅由一家配送中心配送的約束條件，但是每輛車的載重限定為經(jīng)過多次遺傳操作后則不一定滿足。因此適應(yīng)度函數(shù)的確定要同時(shí)反映解的可行性與對(duì)應(yīng)方案的費(fèi)用。對(duì)于個(gè)體y，設(shè)其對(duì)應(yīng)的配送方案的不可行路徑數(shù)為My（My=0表示該個(gè)體為一個(gè)可行解），其目標(biāo)函數(shù)值為Wy，則該個(gè)體y的適應(yīng)度函數(shù)Fy可以表示為：

其中，pω表示每條不可行路徑的懲罰權(quán)重（該權(quán)重在目標(biāo)函數(shù)取值范圍內(nèi)可以取一個(gè)相對(duì)較大的正數(shù)）結(jié)合實(shí)際情況，此處采用pω為1 000。

2.2 遺傳操作

2.2.1 算子的選擇

在已知的必須滿足要求的前提下隨機(jī)選取p條初始種群（初始染色體），采用以上的編碼方式對(duì)產(chǎn)生的初始染色體進(jìn)行編碼，利用比例選擇的方法對(duì)種群進(jìn)行采樣。這里引入選擇概率的概念，設(shè)種群規(guī)模為p，種群中的一個(gè)個(gè)體i的適應(yīng)度函數(shù)值為Fi，則該個(gè)體被選擇的概率為fi：

2.2.2 變異操作

本文在問題的解決過程中引入n-1個(gè)虛擬客戶，虛擬客戶與真實(shí)的客戶一樣在配送的過程中都有對(duì)貨物運(yùn)輸?shù)男枨?，時(shí)間窗的約束條件。但是其貨運(yùn)量為0，貨物配送中消耗時(shí)間為0。所以引入虛擬客戶用X表示，其貨運(yùn)量為0，允許車輛進(jìn)入站點(diǎn)的最早時(shí)間St（X）=0，最遲時(shí)間Et（X）=0，卸貨消耗時(shí)間T（X）=0。則配送方案就變成：m11 0 2 0 m1m23 0 4 0 5 0 6 0…0 n-1 n 0 mm。

在進(jìn)行基因換（移）位時(shí)可能會(huì)出現(xiàn)客戶由多個(gè)配送中心共同擁有，這樣就讓隨機(jī)的一個(gè)配送中心進(jìn)行配送，依次來實(shí)現(xiàn)配送中心的聯(lián)合，實(shí)現(xiàn)協(xié)同配送。

2.3 算法步驟

步驟1：參數(shù)的初始化包括客戶數(shù)目n，適應(yīng)度函數(shù)值Fi，選擇概率fi，每一代染色體個(gè)數(shù)p，迭代次數(shù)k。

步驟2：按照既定的編碼方式隨機(jī)的產(chǎn)生初始種群，確保每條染色體為一個(gè)可行解。

步驟3：計(jì)算個(gè)體適應(yīng)度。

步驟4：利用比例選擇法，計(jì)算每個(gè)個(gè)體被選擇概率，最優(yōu)個(gè)體替代較劣個(gè)體，實(shí)現(xiàn)最優(yōu)個(gè)體保留。

步驟5：變異操作，引入虛擬客戶進(jìn)行基因移（換）位。計(jì)算每一代染色體的適應(yīng)度函數(shù)值，保留最優(yōu)染色體。

步驟6：結(jié)束條件是否滿足，不滿足轉(zhuǎn)步驟3，滿足輸出滿意解。

3 實(shí)證分析

本文取邯鄲市中3個(gè)物流中心m1,m2,m3，分別負(fù)責(zé)為11個(gè)客戶配送貨物，客戶的編號(hào)分別定義為1,2,3,…,11。物流中心m1負(fù)責(zé)客戶1,4,5的配送，物流中心m2負(fù)責(zé)客戶3,7,8,11的配送，物流中心m3負(fù)責(zé)客戶2,6,9,10的配送。為了便于計(jì)算規(guī)定客戶與配送中心的位置在x,y平面上表示出來，客戶與配送中心的距離用他們的直線距離的十分之一表示。站點(diǎn)貨物需求量、卸貨消耗時(shí)間、時(shí)間窗約束、坐標(biāo)位置等相關(guān)信息如表1所示。

圖1 遺傳算法求解過程圖

表1 配送客戶貨物及配送情況表

配送中心坐標(biāo)分別為：m1（ 10,20）、m2（ 30,40）、m3（ 80,60）

由給定的配送中心及客戶的坐標(biāo)可以得出配送中心和客戶距離如表2所示。

假設(shè)物流中心只有一輛車進(jìn)行配送，最大載重為12t，平均車速為50km/h，單位歷程費(fèi)用為20元/km，車輛調(diào)用費(fèi)用為100元，路徑優(yōu)化前配送路徑及所產(chǎn)生的費(fèi)用，如表3所示。

由表3可以看出配送中心m1和m2的車輛負(fù)載不夠理想，需要協(xié)同配送。其中：配送中心m1發(fā)現(xiàn)客戶1是一個(gè)比較孤立的個(gè)體，由配送中心m3對(duì)其進(jìn)行配送所花費(fèi)的配送費(fèi)用更低。同樣的客戶11對(duì)于配送中心m2來說也是一個(gè)比較孤立的站點(diǎn)，由配送中心m3進(jìn)行配送的情況下產(chǎn)生的運(yùn)輸費(fèi)用會(huì)更低。因此，可以對(duì)3個(gè)配送中心進(jìn)行協(xié)同配送，結(jié)合其中的2個(gè)配送中心選用其中的一個(gè)運(yùn)輸費(fèi)用最低的進(jìn)行配送會(huì)節(jié)約大部分成本。應(yīng)用本文的協(xié)同配送調(diào)度算法，得出協(xié)同配送調(diào)度方案及成本，如表4所示。

表4中得到本問題協(xié)同配送后滿意的解，對(duì)于普通的配送方式能夠看出有明顯的改進(jìn)和優(yōu)勢(shì)。

由表3可知：總成本Z1=436+550+514=1 500（元）

總配送距離L1=60（km）

表2 配送和客戶距離表 單位：km

表3 物流中心配送路徑及費(fèi)用表

表4 協(xié)同配送調(diào)度方案及成本表

由表4可知：協(xié)同配送后的總成本Z2=485+678=1 160（元）

總配送距離為L(zhǎng)2=48（km）

總成本之差為z=Z1-Z2=1 500-1 160=340（元）

總配送距離之差為l=L1-L2=60-40=20（km）

由此可以看出，協(xié)調(diào)配送能夠明顯的降低營(yíng)運(yùn)成本，提高車輛利用效率，減少資源消耗。

4 結(jié)束語

針對(duì)普通物流配送方式運(yùn)營(yíng)成本高，資源消耗大的缺陷，構(gòu)建了基于成本最小化的物流中心與客戶的協(xié)同配送路徑優(yōu)化模型。在遺傳算法對(duì)模型求解過程中引入虛擬客戶的編碼方式和基因換（移）位的基因變異方式，得出協(xié)同配送后最優(yōu)的配送路徑，為以后協(xié)同配送能夠更好的實(shí)現(xiàn)，物流企業(yè)競(jìng)爭(zhēng)力的提高，配送資源消耗的降低提供了一定的指導(dǎo)意義。

[1] Haixin Zhang,Yong Deng,Felix T.S.Chan,et al.A modified multi-criterion optimization genetical gorithm for order distribution in collaborative supply chain[J].Applied Mathematical Modelling,2013,37(14):7855-7864.

[2] 溫惠英，孫博.協(xié)同車輛路徑問題的模糊規(guī)劃模型和算法[J].計(jì)算機(jī)應(yīng)用研究，2011,28(2):442-444.

[3] 李丁，黃遠(yuǎn)新，田紅英,等.虛擬環(huán)境下3PL企業(yè)實(shí)施協(xié)同配送的仿真研究[J].技術(shù)與方法，2009,38(7):117-120.

[4] 劉明，趙林度.應(yīng)急物資混合協(xié)同配送模式研究[J].控制與決策，2011,26(1):96-100.

[5] 楊韜，王明華.協(xié)同配送中成本分?jǐn)偤褪找娣峙淠Ｐ脱芯縖J].科學(xué)技術(shù)與工程，2008,14(8):4033-4036.

[6] 王新平，王海燕.多疫區(qū)多周期應(yīng)急物資協(xié)同優(yōu)化調(diào)度[J].系統(tǒng)工程理論與實(shí)踐，2012,32(2):283-291.