一類VRPSDP的建模及其算法設(shè)計(jì)

吳天智

重慶大學(xué)，重慶 400030

0 引言

在經(jīng)濟(jì)信息化的推動(dòng)下，物流已被公認(rèn)為提高企業(yè)競爭力的重要途徑之一。而物流中一個(gè)非常重要的環(huán)節(jié)就是配送。配送的主要包括車輛的集裝、分揀和運(yùn)送等過程，是整個(gè)物流中效益最為關(guān)鍵的一環(huán)。在實(shí)際配送情形中，企業(yè)或客戶會(huì)有同時(shí)送貨和回收的需求。同時(shí)考慮了前向物流和逆向物流的車輛路徑問題，稱為同時(shí)送貨和取貨車輛路徑問題(VRPSDP)。

1 VRPSDP 研究現(xiàn)狀

有關(guān)送貨車輛路徑問題和取貨車輛路徑問題的研究比較多，但關(guān)于同時(shí)送貨和取貨車輛路徑問題（VRPSDP）的研究比較少，VRPSDP 與這些問題一定程度上存在著內(nèi)在聯(lián)系。與VRPSDP 相似的有以下三種車輛路徑問題：1）VRPB：車輛裝滿貨物從配送中心出發(fā)，先完成客戶處的所有送貨任務(wù)后，然后再完成其他客戶處的取貨任務(wù)，最后返回配送中心。這種就是帶回程的車輛路徑問題(VRPB)。特別地，若只有一輛車來完成所有服務(wù)時(shí)，稱該問題是回程的旅行商問題(TSPB)。對(duì)于VRPB 模型，Mingozzi 等人通過研究并用精確算法對(duì)其進(jìn)行了求解；2）VRPBM∶送貨任務(wù)和取貨任務(wù)無先后之分，即送貨和取貨是混合的情形，這種情況稱為混合送貨和取貨車輛路徑問題（VRPBM）。Salhi 等人通過允許多個(gè)送貨點(diǎn)同時(shí)插入到取貨點(diǎn)的插入啟發(fā)式算法求解了該問題，同時(shí)指出該算法改進(jìn)了VRPBM 的計(jì)算結(jié)果和對(duì)同時(shí)送貨和取貨車輛路徑問題求解思路；3）PDP：取貨點(diǎn)和送貨點(diǎn)在任務(wù)中是成對(duì)的，取貨點(diǎn)在送貨點(diǎn)之前，任務(wù)要求將取貨點(diǎn)的貨物裝載后，再配送到送貨點(diǎn)，且是由同一輛車完成客戶的取貨和送貨任務(wù),稱這種問題為取貨和送貨問題 (PDP)。運(yùn)用啟發(fā)式算法求解該問題的學(xué)者有很多，如Madsen 等。

2 VRPSDP 的遺傳算法設(shè)計(jì)

2.1 數(shù)學(xué)模型的建立

首先定義相關(guān)參數(shù)。

R = {i}，i = 0為車場(配送中心)，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í)取貨送貨車輛路徑問題數(shù)學(xué)模型如下：

其中， 1）式是車輛運(yùn)輸成本最小的目標(biāo)函數(shù)； 2）式限定了對(duì)客戶點(diǎn)的訪問次數(shù)有且只有一次； 3）式是車輛的最大載重量約束； 4）式是出發(fā)時(shí)車輛最開始的載重要等于各個(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ù)。

2.2 改進(jìn)遺傳算法設(shè)計(jì)

2.3 算法分析

通過實(shí)驗(yàn)算例驗(yàn)證得出，因初始解在開始階段是隨機(jī)生成的，所以其取值往往不符合最小運(yùn)輸成本的目標(biāo)。但根據(jù)算法的搜索方式，解隨著迭代計(jì)算的進(jìn)行不斷向最優(yōu)目標(biāo)收斂并逼近，該收斂過程表明本文建立的VRPSDP 模型的合理性和算法的可行性。

與基本遺傳算法相比：基于傳統(tǒng)輪盤賭選擇算子的基本遺傳算法，解呈現(xiàn)出較大波動(dòng)性和較慢收斂速度。采用基于排序的多輪輪盤賭選擇算子有相對(duì)較快收斂速度。此外，通過改進(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.