吳天智
重慶大學(xué),重慶 400030
在經(jīng)濟(jì)信息化的推動(dòng)下,物流已被公認(rèn)為提高企業(yè)競(jìng)爭(zhēng)力的重要途徑之一。而物流中一個(gè)非常重要的環(huán)節(jié)就是配送。配送的主要包括車輛的集裝、分揀和運(yùn)送等過(guò)程,是整個(gè)物流中效益最為關(guān)鍵的一環(huán)。在實(shí)際配送情形中,企業(yè)或客戶會(huì)有同時(shí)送貨和回收的需求。同時(shí)考慮了前向物流和逆向物流的車輛路徑問(wèn)題,稱為同時(shí)送貨和取貨車輛路徑問(wèn)題(VRPSDP)。
有關(guān)送貨車輛路徑問(wèn)題和取貨車輛路徑問(wèn)題的研究比較多,但關(guān)于同時(shí)送貨和取貨車輛路徑問(wèn)題(VRPSDP)的研究比較少,VRPSDP 與這些問(wèn)題一定程度上存在著內(nèi)在聯(lián)系。與VRPSDP 相似的有以下三種車輛路徑問(wèn)題:1)VRPB:車輛裝滿貨物從配送中心出發(fā),先完成客戶處的所有送貨任務(wù)后,然后再完成其他客戶處的取貨任務(wù),最后返回配送中心。這種就是帶回程的車輛路徑問(wèn)題(VRPB)。特別地,若只有一輛車來(lái)完成所有服務(wù)時(shí),稱該問(wèn)題是回程的旅行商問(wèn)題(TSPB)。對(duì)于VRPB 模型,Mingozzi 等人通過(guò)研究并用精確算法對(duì)其進(jìn)行了求解;2)VRPBM∶送貨任務(wù)和取貨任務(wù)無(wú)先后之分,即送貨和取貨是混合的情形,這種情況稱為混合送貨和取貨車輛路徑問(wèn)題(VRPBM)。Salhi 等人通過(guò)允許多個(gè)送貨點(diǎn)同時(shí)插入到取貨點(diǎn)的插入啟發(fā)式算法求解了該問(wèn)題,同時(shí)指出該算法改進(jìn)了VRPBM 的計(jì)算結(jié)果和對(duì)同時(shí)送貨和取貨車輛路徑問(wèn)題求解思路;3)PDP:取貨點(diǎn)和送貨點(diǎn)在任務(wù)中是成對(duì)的,取貨點(diǎn)在送貨點(diǎn)之前,任務(wù)要求將取貨點(diǎn)的貨物裝載后,再配送到送貨點(diǎn),且是由同一輛車完成客戶的取貨和送貨任務(wù),稱這種問(wèn)題為取貨和送貨問(wèn)題 (PDP)。運(yùn)用啟發(fā)式算法求解該問(wèn)題的學(xué)者有很多,如Madsen 等。
首先定義相關(guān)參數(shù)。
R = {i},i = 0為車場(chǎng)(配送中心),i = 1,2, … ,n表示客戶節(jié)點(diǎn)。R 表示客戶點(diǎn)的集合,其中 U = R∪ { 0},U 為節(jié)點(diǎn)集合。
V 表示車輛集合,V = { k},k = 1,2,… ,m。
Q 為車輛的載重能力。
C 為各客戶點(diǎn)間的距離,C = {cij}, i, j ∈ U 。
α 為單位距離的運(yùn)輸費(fèi)用。
β 車輛啟用費(fèi)用。
di:客戶點(diǎn)i 的送貨量,i ∈ R。
pi:客戶點(diǎn)i 的取貨量,i ∈ R。
。
yijk:車輛k 從節(jié)點(diǎn)i 到節(jié)點(diǎn)j 的載重。
運(yùn)輸成本最小的同時(shí)取貨送貨車輛路徑問(wèn)題數(shù)學(xué)模型如下:
其中, 1)式是車輛運(yùn)輸成本最小的目標(biāo)函數(shù); 2)式限定了對(duì)客戶點(diǎn)的訪問(wèn)次數(shù)有且只有一次; 3)式是車輛的最大載重量約束; 4)式是出發(fā)時(shí)車輛最開(kāi)始的載重要等于各個(gè)客戶節(jié)點(diǎn)送貨量的總和; 5)式表示各個(gè)客戶節(jié)點(diǎn)的取貨量等于車輛返回時(shí)的載重量;6)式表示任一客戶點(diǎn)處,車輛的載重等于該處取貨量和剩余送貨量;7)式表示出發(fā)時(shí)車輛最大載重量限制;8)式表示返回時(shí)車輛最大載重量限制;9)式表示車輛在任意節(jié)點(diǎn)的載重為正;10)式表示送貨與取貨量非負(fù),車輛最大載重能力是正數(shù)。
通過(guò)實(shí)驗(yàn)算例驗(yàn)證得出,因初始解在開(kāi)始階段是隨機(jī)生成的,所以其取值往往不符合最小運(yùn)輸成本的目標(biāo)。但根據(jù)算法的搜索方式,解隨著迭代計(jì)算的進(jìn)行不斷向最優(yōu)目標(biāo)收斂并逼近,該收斂過(guò)程表明本文建立的VRPSDP 模型的合理性和算法的可行性。
與基本遺傳算法相比:基于傳統(tǒng)輪盤賭選擇算子的基本遺傳算法,解呈現(xiàn)出較大波動(dòng)性和較慢收斂速度。采用基于排序的多輪輪盤賭選擇算子有相對(duì)較快收斂速度。此外,通過(guò)改進(jìn)遺傳算法能得到更符合實(shí)際要求的最優(yōu)目標(biāo)值,因此,改進(jìn)遺傳算法比基本遺傳算法在VRPSDP 中具有更好的有效性和可行性。
[1]Ming0zziA,Gi0rgiS.Anexactmeth0df0rthevehic 1er0utingpr0b1emwithbackhau1s.Transp0rtati0nScien ce,1999,(33):315-29.
[2]Sa1hiS,NagyG.Ac1usterinserti0nheuristicf0 rsing1eandmu1tip1edep0tvehic1er0utingpr0b1emswith backhau1ing.J0urna10fthe0perati0na1ResearchS0cie ty,1999,(50):1034-1042.
[3]Madsen0B,RavnHF,RygaardJR.Asystemf0rdynamicvehi c1er0utingf0rtheC0penhagenFireFightingC0mpany.Research Rep0rt2/1993,IMS0R,1yngby,Denmark,1993.