馮芳媛,張麗華,李阿慧(沈陽師范大學(xué),遼寧 沈陽110034)
由于B2C 電子商務(wù)市場的發(fā)展在社會消費(fèi)品零售總額中的比重逐年增加,使得電子商務(wù)企業(yè)之間的競爭越來越大,企業(yè)為贏取更大的效益必須不斷完善其物流配送體系。然而近幾年來隨著電子商務(wù)的發(fā)展以及消費(fèi)者維權(quán)意識的增強(qiáng),使得產(chǎn)品退回事件趨于增多,這就要求在發(fā)展正向物流配送的同時考慮逆向物流配送,以減少因退貨帶來的損失,為此本文討論了一個B2C電子商務(wù)下帶退貨的多配送站點(diǎn)車輛路徑優(yōu)化問題。
針對B2C電子商務(wù)下的車輛路徑優(yōu)化問題的研究成果較少[1-3],而且都是研究不帶退貨的情形,而對帶退貨車輛路徑優(yōu)化問題,多數(shù)學(xué)者只研究了單配送中心的情形[4-8],少數(shù)學(xué)者研究了多配送中心的情形[9-11],但這些研究中未考慮車輛的啟動費(fèi)用,而且有的文獻(xiàn)還要求送貨優(yōu)先于退貨,本文在加入車輛啟動費(fèi)用的同時改進(jìn)車輛的車載限制約束,極小化車輛使用數(shù)目和總的運(yùn)輸費(fèi)用,建立了更符合實際情況的帶退貨的多配送站點(diǎn)車輛路徑優(yōu)化問題的模型并給出用一次禁忌搜索算法直接求解的方法。
一個B2C電子商務(wù)企業(yè)在一個小區(qū)域內(nèi)建有m個配送站點(diǎn)負(fù)責(zé)完成為n顧客配送的任務(wù)。當(dāng)有客戶訂貨(或退貨)時,要求根據(jù)客戶的地理位置及需求(或退貨)量,在配送站點(diǎn)中進(jìn)行選擇并確定實際配送路線,完成配送訂貨和取回退貨任務(wù),使得總費(fèi)用(包括車輛行駛費(fèi)用和車輛一次啟動費(fèi)用)最小。
當(dāng)m=1并限定配送站點(diǎn)的車輛數(shù)為1、各個客戶只有需求時,上述問題就是旅行商問題,因此旅行商問題是本文所討論問題的子問題。因旅行商問題是NP-h(huán)ard的,所以本文的問題也是NP-h(huán)ard的。
假設(shè)每個配送站點(diǎn)的可用車輛數(shù)一定、車型一樣,且每輛車僅隸屬于一個配送站點(diǎn);每輛車從各自所屬的配送站點(diǎn)出發(fā),完成配送和取貨任務(wù)后裝載回收的退貨返回其所屬配送站點(diǎn);每個客戶僅能由一個配送站點(diǎn)的一輛車服務(wù);每個配送站點(diǎn)無存儲量限制。
用1,2,…,m表示配送站點(diǎn)編號,令D={1,2 , …,m};m+1,…,m+n表示客戶編號(其中既包括訂貨的客戶也包括退貨的客戶,還有可能一個客戶既有退貨又有訂貨),令C={m+1,…,m+n};dij、cij分別表示i與j之間的距離和i與j之間單位距離的運(yùn)輸費(fèi)用,(i,j∈D∪C,且當(dāng)i=j時dij=0,cij=0);qj、pj分別表示客戶j(j∈C)的需求量與退貨量;Ki、Ai、mi、ni分別表示配送站點(diǎn)i(i∈D)的車輛集合、可用車輛數(shù)、要配送的貨物總量、收到的顧客的退貨總量,且當(dāng)i,j∈D,i≠j時Ki∩Kj=?;K表示所有車輛的集合;R、B分別表示每輛車的車載限制和一次性啟動費(fèi)用;Qjk、Pjk(k∈ K)當(dāng)j∈D時分別表示車輛k在其所屬的配送站點(diǎn)j的載貨量和車輛k從其所屬的配送站點(diǎn)j出發(fā)或返回所屬的配送站點(diǎn)時回收的退貨總量,當(dāng)j∈C時分別表示車輛k到達(dá)顧客j處裝載的還未配送的貨物總量(不包括j處的需求量)與車輛k從其所屬的配送站點(diǎn)出發(fā)到達(dá)顧客j處回收的退貨總量(包括j處的退貨量);設(shè)決策變量為:
那么當(dāng)ωi=0且k∈Ki時,有Qjk=0,Pjk=0,?j∈D∪C;當(dāng)ωi=1時,如果yjk=0,也有Qjk=0,Pjk=0,?j∈D∪C。于是本文的問題可用下列的0-1整數(shù)規(guī)劃模型描述:
上式(1)表示車輛行駛費(fèi)用和車輛一次性啟動費(fèi)用之和,其中車輛一次性啟動費(fèi)用按車輛使用數(shù)量計算;(2)每個客戶只能由一輛車服務(wù)且僅能服務(wù)一次;(3)保證如果客戶由一輛車服務(wù)則該車恰好訪問此客戶一次;(4)車輛不在配送站點(diǎn)之間行駛;(5)每個客戶屬于且僅屬于一個配送站點(diǎn);(6)每個客戶由它所屬的配送站點(diǎn)的一輛車進(jìn)行服務(wù);(7)配送站點(diǎn)的總供應(yīng)量小于等于其客戶的需求量;(8)配送站點(diǎn)回收的退貨總量等于其客戶的所有退貨之和;(9)每個配送站點(diǎn)的可用車輛數(shù)限制;(10)~(12)配送過程中的車載限制;(13)保證每輛車從各自的配送站點(diǎn)出發(fā),完成任務(wù)后返回原配送站點(diǎn);(14)若配送站點(diǎn)沒有選用則無客戶由此配送站點(diǎn)服務(wù)。
由于本文討論的問題是NP-hard的,所以下面給出一個禁忌搜索算法來對其進(jìn)行求解。
因為禁忌搜索算法對初始解具有很大的依賴性,即最終解的質(zhì)量以及收斂速度都與初始解有很大的關(guān)系,所以在本文給出的禁忌搜索算法中首先調(diào)用下面的算法1來產(chǎn)生一個較好的初始可行解。
算法 1:
第一步:修改文獻(xiàn)[12]的算法對配送站點(diǎn)和顧客按著下列方法進(jìn)行分組:
(1)針對每一個配送站點(diǎn)計算其可接收的貨物總量=其可用車輛數(shù)×車載。
(3)取一適當(dāng)?shù)摩模?≤δ≤1),比較r(i)與δ的大小,若r(i)<δ就稱點(diǎn)i為非臨界點(diǎn),否則稱點(diǎn)i為臨界點(diǎn)。
(4)對非臨界點(diǎn)的分派如下:①將所有非臨界點(diǎn)客戶按r(i)從小到大進(jìn)行排列;②將各個配送站點(diǎn)總的配送量和總的回收量都賦值為空;③按著①的順序?qū)γ恳环桥R界點(diǎn)客戶執(zhí)行下列操作:a將各個配送站點(diǎn)按與該非臨界點(diǎn)客戶的距離由小到大順序排列;b按a的順序?qū)ふ业谝粋€滿足下列條件的配送站點(diǎn):這個配送站點(diǎn)原來總的配送量+要分派的這個非臨界點(diǎn)客戶的需求量不超過它所擁有的車數(shù)×R,并且它原來的總回收量+要分派的這個非臨界點(diǎn)客戶的退貨量不超過它所擁有的車數(shù)×R,將該非臨界點(diǎn)客戶分配給它,更新這個配送站點(diǎn)總的配送量=原來總的配送量+要分派的這個非臨界點(diǎn)客戶的需求量,總的回收量=它原來的總回收量+要分派的這個非臨界點(diǎn)客戶的退貨量。
(5)對臨界點(diǎn)的分派如下:將所有臨界點(diǎn)顧客按需求量與退貨量的和從大到小排列,若同時存在幾個客戶的需求量與退貨量之和相等,則按r(i)從小到大的順序?qū)⑦@些客戶進(jìn)行排列,之后按此順序依次對它們執(zhí)行對非臨界點(diǎn)分派的③中的a與b操作。
注:對非臨界點(diǎn)而言,最近距離與次近距離相差較大,所以對其分派主要考慮的是距離,而對臨界點(diǎn)而言,最近距離與次近距離相差較小,所以對其分派主要考慮的是運(yùn)量。
由此可得到一種分派,每個被選的配送站點(diǎn)都有一組要服務(wù)的顧客且能夠滿足其服務(wù)的顧客要求。
第二步:將文獻(xiàn)[12]的C-W節(jié)約算法進(jìn)行修改來實現(xiàn)對每個配送站點(diǎn)和其服務(wù)的顧客進(jìn)行路徑優(yōu)化,其過程如下:
(1)計算節(jié)約值s(i,j)=di0+d0j-dij,令M={s(i,j)>0|i,j∈C∪D,i≠j}。
(2)在M內(nèi)按s(i,j)從大到小的順序排列。
(3)若M=?,終止,否則對M中第一項s(i,j)考察對應(yīng)的(i,j),若滿足下述條件之一就轉(zhuǎn)(4),否則轉(zhuǎn)(7):
①點(diǎn)i與點(diǎn)j均不在已構(gòu)成的線路上;
②點(diǎn)i或點(diǎn)j在已構(gòu)成的線路上,但不是線路的內(nèi)點(diǎn)(即不與車場相連);
③點(diǎn)i與點(diǎn)j位于已構(gòu)成的不同線路上,均不是內(nèi)點(diǎn),且一個是起點(diǎn),一個是終點(diǎn)。
(4)計算點(diǎn)i與點(diǎn)j連接后線路上的總需求量Qi與總退貨量Pi,若Qi≤R且Pi≤R,(R為車載)轉(zhuǎn)(5),否則轉(zhuǎn)(7)。
(5)從起始點(diǎn)(配送站點(diǎn))開始依次計算車輛到達(dá)線路上每一個客戶點(diǎn)時的裝載量(裝載量的計算方法為:起點(diǎn)的裝載量為整個線路上所有客戶的配送量之和,而線路上各個客戶處的裝載量為線路上該客戶緊前點(diǎn)的裝載量-該客戶的配送量+該客戶的退貨量),若滿足車載限制則轉(zhuǎn)(6),否則轉(zhuǎn)(7)。
(6)連接點(diǎn)i和點(diǎn)j。
(7)令M=M-s(i,j),轉(zhuǎn)(3)。
本文參考文獻(xiàn)[13]給出求解帶退貨的多配送站點(diǎn)車輛路徑優(yōu)化問題一種新的解的表示方法,下面舉例對該方法進(jìn)行說明:假設(shè)有3個配送站點(diǎn),6個顧客的問題,若其解為x=(14711282359363),則表示:配送站點(diǎn)1:可用車輛數(shù)為2輛,第一輛車的行駛路線為1-4-7-1;第二輛車行駛路線為1-1即未使用;配送站點(diǎn)2:可用車輛數(shù)為1輛,行駛路線為2-8-2;配送站點(diǎn)3:可用車輛數(shù)為2輛,第一輛車的行駛路線為3-5-9-3;第二輛車行駛路線為3-6-3。由此種解的表示方法既可以表示出每輛車的行駛路線又可以表示出每個配送中心擁有的可用車輛數(shù)目,所以是一種有效的表示方法。
本文針對多配送中心車輛調(diào)度問題的特點(diǎn)對頂點(diǎn)重新指派法[14]進(jìn)行改進(jìn),按此方法實施鄰域操作可以實現(xiàn)線路的調(diào)整與合并。改進(jìn)后的頂點(diǎn)重新指派方法步驟為:隨機(jī)從解中選取兩個節(jié)點(diǎn),按如下情況進(jìn)行操作:若所選的兩個節(jié)點(diǎn)均為配送中心,則不進(jìn)行節(jié)點(diǎn)間的重新指派;若所選的兩個節(jié)點(diǎn)均為客戶,則將第二個節(jié)點(diǎn)從其線路中取出并插入到所選的第一個節(jié)點(diǎn)的位置之前;若所選的第一個節(jié)點(diǎn)為客戶,第二個節(jié)點(diǎn)為配送中心,那么如果第二個節(jié)點(diǎn)的緊前點(diǎn)為異于該配送中心的其它配送中心,則不進(jìn)行節(jié)點(diǎn)間的重新指派;否則,將第一個節(jié)點(diǎn)從其線路中取出并插入到所選的第二個節(jié)點(diǎn)的位置之前;若所選的第一個節(jié)點(diǎn)為配送中心,第二個節(jié)點(diǎn)為客戶,此時需分情況討論:(1)若第一個節(jié)點(diǎn)為總線路的起點(diǎn),則不進(jìn)行節(jié)點(diǎn)間的重新指派;(2)若第一個節(jié)點(diǎn)的緊前點(diǎn)為異于該配送中心的其它配送中心,則不進(jìn)行節(jié)點(diǎn)間的重新指派;否則,將第二個節(jié)點(diǎn)從其線路中取出并插入到所選的第一個節(jié)點(diǎn)的位置之前。
本文所研究的模型因為車輛行駛具有啟動費(fèi)用,而一般認(rèn)為啟動費(fèi)用是一個非常大的數(shù),多用一輛車所增加的啟動費(fèi)用要遠(yuǎn)遠(yuǎn)大于其總行駛路程縮短而帶來的節(jié)省,因此將極小化車輛使用數(shù)目作為第一目標(biāo),極小化車輛行駛費(fèi)用作為第二目標(biāo)[14]。為了充分對解空間進(jìn)行搜索,接受導(dǎo)致不可行解的鄰域變換,當(dāng)違反了車輛裝載能力限制時,其不可行性的程度可以引進(jìn)一個懲罰值將該約束條件包含到目標(biāo)函數(shù)中去進(jìn)行度量,為此設(shè)p為懲罰因子,在本文中令,用E(x)表示對給定的解x的不可行程度實施懲罰的量,其計算方式如下:若x中共有ux條線路不可行,則,設(shè)x對應(yīng)的目標(biāo)函數(shù)值為fx,那么解x的評價值等于p×E(x)+fx。
本文將每次迭代得到的局部最好解(評價值最?。﹍ocalbestjie(不一定可行)作為禁忌對象放入禁忌表中;取禁忌長度為一個常數(shù)l,其值根據(jù)問題的規(guī)模來確定;將從當(dāng)前解的鄰域中隨機(jī)選擇N個鄰居作為候選集合;采用迭代指定步數(shù)T的終止準(zhǔn)則。
禁忌搜索算法:
步驟1:初始化:為dij(i,j∈D∪C)、qj,pj(j∈C)、K、T、l、N、p賦值,調(diào)用上面的算法1求得一個初始可行解x0,初始化禁忌表H←{x0},令迭代步數(shù)t←0;用localbestjiezhi記錄localbestjie的評價值,用Sbest與Ebest分別記錄次優(yōu)可行解和其目標(biāo)函數(shù)值,并令Sbest←x0,Ebest←x0的評價值;M是所有解的評價值的一個上界,令,x記錄每次迭代時用于實施鄰域操作的解,并令x←x。0
步驟2:當(dāng)t<T時重復(fù)下列操作,否則轉(zhuǎn)步驟3:
(1)localbestjie←?,localbestjiezhi←M;n←1。
(2)當(dāng)n<N時重復(fù)下列操作,否則轉(zhuǎn)(3):
①對x用頂點(diǎn)重新指派法實施鄰域操作,得到x的一個鄰居x';
②對x'執(zhí)行下列操作:若x'?H,求x'的評價值,若x'的評價值小于localbestjiezhi,令localbestjie←x',localbestjiezhi←x'的評價值,n←n+1轉(zhuǎn)①,否則令n←n+1轉(zhuǎn)①;若x'∈H,令n←n+1轉(zhuǎn)①。
(3)若 localbestjiezhi≥Ebest轉(zhuǎn)(4),否則令 Sbest←localbestjie;Ebest←localbestjiezhi轉(zhuǎn)(4)。
(4)如果禁忌長度<l將localbestjie放在禁忌表的末尾,令x←localbestjie,t←t+1轉(zhuǎn)步驟2,否則將禁忌表的第一個元素解禁,之后將localbestjie放在禁忌表的末尾,令x←localbestjie,t←t+1轉(zhuǎn)步驟2。
步驟 3:輸出Sbest和 Ebest。
假設(shè)某一B2C電子商務(wù)企業(yè)在某一區(qū)域內(nèi)建有3個配送站點(diǎn),其中第一個配送站點(diǎn)擁有2輛車,第二個配送站點(diǎn)擁有3輛車,第三個配送站點(diǎn)擁有2輛車,每輛車的車型都一樣載重都為10噸,某一時刻有17個需要服務(wù)的顧客,客戶的需求量或退貨量以及點(diǎn)對之間的距離分別如下面的表1和表2所示。要求在配送站點(diǎn)中合理選擇車輛并安排行駛路線使總費(fèi)用最小。
表1 各客戶點(diǎn)的需求量和退貨量
用禁忌搜索算法進(jìn)行求解,其中迭代步數(shù)取400,每次迭代共搜索當(dāng)前解的40個鄰居,禁忌長度取5,車輛一次啟動費(fèi)用為300,在本例中設(shè)單位距離的運(yùn)輸費(fèi)用cij=1,i,j∈{1,2 , …,20}。
應(yīng)用算法1得到初始可行解及其目標(biāo)函數(shù)值分別為:
用禁忌搜索算法求得的可行解及其目標(biāo)函數(shù)值分別為:
由此例可以看出,禁忌搜索算法對初始可行解的改進(jìn)效果是比較明顯。
本文對帶退貨的多配送站點(diǎn)車輛路徑優(yōu)化問題進(jìn)行了描述,為求解該問題提出了一種新的解的表示方法和鄰域變換,從而構(gòu)造了直接求解帶退貨的多配送站點(diǎn)車輛路徑優(yōu)化問題的禁忌搜索算法,該算法具有良好的尋優(yōu)性能,所設(shè)計的解的表示方法直觀且操作簡便,易于理解。此外為了更符合B2C電子商務(wù)的經(jīng)營特點(diǎn)可加入時間窗約束,我們將下一步對其進(jìn)行研究。
表2 各點(diǎn)對之間的距離
[1]李維健.B2C電子商務(wù)模式下物流配送路徑優(yōu)化問題研究[D].北京:北京交通大學(xué)(碩士學(xué)位論文),2006.
[2]許志生.B2C網(wǎng)上超市與敏捷配送相結(jié)合的新零售模式研究[D].鎮(zhèn)江:江蘇大學(xué)(碩士學(xué)位論文),2010.
[3]蔣忠中,汪定偉.B2C電子商務(wù)中物流配送路徑優(yōu)化的模型與算法[J].信息與控制,2005,34(4):481-485.
[4]隆穎.用遺傳算法求解帶同樣取貨的車輛路徑問題[J].遼寧師專學(xué)報:自然科學(xué)版,2005,7(3):86-88.
[5]郭伏,隆穎.帶時窗同時取貨的車輛路徑問題的算法[J].東北大學(xué)學(xué)報,2006,27(5):575-578.
[6]胡天軍,程文科.帶回程取貨的逆向物流車輛路徑建模及蟻群算法[J].交通運(yùn)輸系統(tǒng)工程與信息,2010,10(3):110-114.
[7]Zhang H.G.,WU Y.X..Study on the model and improved immune algorithm for vehicle routing problem with backhauls[C]//International Conference on Computing,Control and Industrial Engineering,2010:371-374.
[8]Shu C.L.,Chich H.C..A heuristic method for the vehicle routing problem with backhauls and inventory[J].Journal of Intelligent Manufacturing,2009,20:29-42.
[9]Fan J.H.,Wang X.F.,Chen Q.S..A heuristic algorithm for multiple depots vehicle routing problem with backhauls[C]//Fourth International Conference on Fuzzy Systems and Knowledge Discovery,2007.
[10]Ren C.Y.,Wang X.B..Study on improved hybrid genetic algorithm for multi-depot vehicle routing problem with backhauls[C]//International Conference on Artificial Intelligence and Computational Intelligence,2009:347-350.
[11]Ren C.Y.,Wang X.B..Study on hybrid genetic algorithm for multi-type vehicles and multi-depot vehicle routing problem with backhauls[C]//Second International Conference on Intelligent Computation Technology and Automation,2009:197-200.
[12]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社,2001.
[13]郎茂祥,胡思繼.車輛路徑問題的禁忌搜索算法研究[J].管理工程學(xué)報,2004,18(1):81-84.
[14]符卓.帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究[J].系統(tǒng)工程理論與實踐,2004(3):123-128.