程昭立，郝悅辰，周丹妮，張艷馥

(華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京 102206)

智能電網(wǎng)建設(shè)步伐的加快對(duì)智能電表的配送提出了更高的要求。與智能電表的正向配送相比，周轉(zhuǎn)箱回收由于發(fā)生的時(shí)間、地點(diǎn)、數(shù)量等存在不確定性，其回收車輛路徑規(guī)劃更為復(fù)雜。通常情況下，回收物流車輛路徑規(guī)劃分為回程回收和純回收兩類路徑規(guī)劃[1]。回程回收適合于正逆結(jié)合的逆向物流網(wǎng)絡(luò)，主要分為先配送后回收(VRPB)、混合的配送回收(VRPBM)、配送與回收同時(shí)發(fā)生(VRPSPD)三類[2]。國(guó)內(nèi)外對(duì)回程回收中的VRPSPD的研究是近幾年才興起的。有的學(xué)者以車輛行駛路程限制為基礎(chǔ)展開(kāi)研究，如文獻(xiàn)[3]提出了配送車輛有最大行程約束的VRPSPD數(shù)學(xué)模型，文獻(xiàn)[4]從單車型、有載重量限制，需求量己知等限制條件展開(kāi)，構(gòu)建混合整數(shù)規(guī)劃模型，文獻(xiàn)[5]對(duì)該問(wèn)題具體的定義、條件、具體標(biāo)準(zhǔn)進(jìn)行詳細(xì)敘述。有的學(xué)者在時(shí)間約束的基礎(chǔ)上展開(kāi)研究，如文獻(xiàn)[6]從單類型、載容、需求確定展開(kāi)粒子群算法對(duì)該問(wèn)題進(jìn)行求解，文獻(xiàn)[7]針對(duì)單配送中心在文獻(xiàn)[5]的基礎(chǔ)上提出硬時(shí)間窗約束條件，并對(duì)有時(shí)間窗的和無(wú)時(shí)間窗的仿真結(jié)果進(jìn)行比較，文獻(xiàn)[8]則從是模糊時(shí)間窗限制的角度開(kāi)展研究。在模型算法上，主要有禁忌算法、蟻群算法、啟發(fā)式算法、粒子群法、遺傳算法等?；诖耍疚尼槍?duì)同時(shí)滿足緩存庫(kù)中兩種需求的回程回收車輛路徑規(guī)劃(VRPSPD)進(jìn)行研究，并采用遺傳算法對(duì)其進(jìn)行分析。

1 構(gòu)建數(shù)學(xué)模型

為將現(xiàn)實(shí)中同時(shí)具有智能電表配送及周轉(zhuǎn)箱回收的車輛路徑規(guī)劃抽象為數(shù)學(xué)模型，本文對(duì)VRPSPD作如下假設(shè):

1)只有省電網(wǎng)公司計(jì)量中心一個(gè)車場(chǎng)，每輛車均從省計(jì)量中心出發(fā)，完成本車路徑上的智能電表配送和周轉(zhuǎn)箱回收任務(wù)后返回省計(jì)量中心。

2)只有一種車型，每輛車的載容已知，單個(gè)地市緩存庫(kù)的配送量和回收量不能超過(guò)單車載容。

3)通過(guò)計(jì)量管控一體化平臺(tái)，省計(jì)量中心可以獲取各地市緩存庫(kù)的智能電表配送需求和周轉(zhuǎn)箱回收需求。

4)省計(jì)量中心、地市緩存庫(kù)的地理坐標(biāo)已知，即省計(jì)量中心與地市緩存庫(kù)之間的距離已知。

5)每個(gè)地市緩存庫(kù)的智能電表配送需求和周轉(zhuǎn)箱回收需求只能由一輛車服務(wù)。

6)配送的智能電表和回收的周轉(zhuǎn)箱可以混裝。

7)開(kāi)展智能電表配送和周轉(zhuǎn)箱回收的車輛最大行駛距離已知，不能超過(guò)該路程。

8)車輛在地市緩存庫(kù)處可以同時(shí)完成智能電表配送和周轉(zhuǎn)箱回收任務(wù)。

9)智能電表的配送需求量以周轉(zhuǎn)箱為單位，每地市緩存庫(kù)的需求為整數(shù)個(gè)周轉(zhuǎn)箱。

10)車輛運(yùn)輸成本與行駛路程呈正比例關(guān)系，車輛行駛路徑?jīng)Q定車輛行駛路程，當(dāng)路徑距離最短時(shí)運(yùn)輸成本最優(yōu)。

11)每條行駛路徑上的車載智能電表配送數(shù)量和周轉(zhuǎn)箱回收數(shù)量之和小于或等于車輛的載容。

根據(jù)上述描述和相關(guān)假設(shè)，以車輛行駛路程最小為目標(biāo)建立同時(shí)具有智能電表配送和周轉(zhuǎn)箱回收需求的車輛路徑規(guī)劃數(shù)學(xué)模型為

式中:s為各庫(kù)的集合，s={0，1，2，．．．，s}，其中 S0為省計(jì)量中心;v 為車輛集合，v={1，2，．．．，v};R為車輛的載容;Cij為省計(jì)量中心、地市緩存庫(kù)之間的距離，且有 Cij=0，?i=j，i，j∈s;Di為地市緩存庫(kù)i的智能電表配送需求量，i∈s;Pi為地市緩存庫(kù)i的周轉(zhuǎn)箱回收需求量，i∈s;Xijv為車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j時(shí)，是否由車輛k服務(wù)，當(dāng)Xijk=1時(shí)表示車輛k服務(wù)于節(jié)點(diǎn)i與節(jié)點(diǎn)j之間，否則Xijk=0;Yijv為車輛k從緩存庫(kù)i到緩存庫(kù)j行駛時(shí)承載的已回收周轉(zhuǎn)箱數(shù)量;Zijv為車輛k從緩存庫(kù)i到緩存庫(kù)j行駛時(shí)承載的裝有尚未配送的智能電表周轉(zhuǎn)箱數(shù)量;MD為車輛最大行駛距離;Uiv為緩存庫(kù)i是否由車輛v服務(wù)，當(dāng)Uiv=1時(shí)表示車輛 k服務(wù)于節(jié)點(diǎn) i，否則Uiv=0。

函數(shù)目標(biāo)式(1)表示目標(biāo)函數(shù)為所有車輛的行駛路程之和最小化.在約束式中:式(2)表示駛進(jìn)駛離每個(gè)緩存庫(kù)的車輛為同一輛車，且每庫(kù)只由一輛車服務(wù);式(3)表示省計(jì)量中心是所有車輛必須服務(wù)，而每個(gè)緩存庫(kù)只能由一輛車服務(wù);式(4)保證每輛車的行駛路程不超過(guò)最大距離;式(5)表示車輛k從緩存庫(kù)i直接到緩存庫(kù)j時(shí)車輛取貨物量的變化;式(6)表示車輛k從節(jié)點(diǎn)i直接到節(jié)點(diǎn)j時(shí)車輛送貨物量的變化;式(7)表示任何一條車輛的行駛路徑上的配送量和需求量之和都必須小于或等于車輛的最大載容;式(8)表示配送車輛在任何行駛路徑上承載的周轉(zhuǎn)箱回收量或未送智能電表量都滿足車輛最大車容的限制;式(9)表示每輛車離開(kāi)省計(jì)量中心時(shí)的車載量為該路徑上各個(gè)緩存庫(kù)智能電表的配送需求量之和;式(10)表示每輛車回到省計(jì)量中心時(shí)的裝載周轉(zhuǎn)箱的數(shù)量為該路徑上各個(gè)緩存庫(kù)回收量之和。

2 求解數(shù)學(xué)模型的遺傳算法設(shè)計(jì)

應(yīng)用遺傳算法來(lái)解決智能電表配送及周轉(zhuǎn)箱回收的車輛路徑，就是要根據(jù)各市級(jí)緩存庫(kù)提出的配送和回收需求，在滿足車輛載容、路程等約束條件下，以成本最小化為目標(biāo)來(lái)規(guī)劃回程回收車輛路徑。通過(guò)對(duì)目標(biāo)函數(shù)的大小評(píng)價(jià)各路線的優(yōu)劣，獲取適應(yīng)性強(qiáng)的方案并將其優(yōu)秀特征遺傳到下一代，獲得最優(yōu)解，規(guī)劃出最優(yōu)的車輛回程路徑。遺傳算法的具體流程如下:

1)參數(shù)編碼。應(yīng)用自然數(shù)對(duì)參數(shù)進(jìn)行編碼，對(duì)各緩存庫(kù)用1到n表示，形成排列S1，S2，…，Sn，每個(gè)數(shù)出現(xiàn)一次且僅一次。在求解數(shù)學(xué)模型時(shí)，運(yùn)用搜索空間限定法處理其中的約束條件。比如對(duì)于車輛路程限制和車載容量的條件約束，通過(guò)對(duì)已構(gòu)成的緩存庫(kù)序列，按照路程和容量限制兩個(gè)約束條件，依次將各客戶劃入各條配送及回收路徑中，限定其搜索空間，以提高遺傳算法的效率。

2)初始回程回收路徑方案。通過(guò)編碼產(chǎn)生的n個(gè)緩存庫(kù)，群體規(guī)模為npop，則通過(guò)隨機(jī)產(chǎn)生npop個(gè)這樣的個(gè)體，并按路程和車載容量限制的約束條件插入0，即可形成初始回程回收路徑方案群。

3)計(jì)算每個(gè)個(gè)體適應(yīng)度值。適應(yīng)度是評(píng)價(jià)個(gè)體優(yōu)劣和進(jìn)行遺傳操作的依據(jù)，度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)?；具z傳算法按與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前種群中個(gè)體遺傳到下一代種群中的機(jī)會(huì)。根據(jù)所研究個(gè)體的實(shí)際情況，擬通過(guò)以下公式計(jì)算個(gè)體適應(yīng)度值:

其中 average Cost為所有個(gè)體總成本的平均值，Cost(i)為第i個(gè)體的總成本。

4)遺傳操作設(shè)計(jì)。各車輛路徑規(guī)劃方案的適應(yīng)度值是遺傳算法中衡量方案優(yōu)劣的一個(gè)準(zhǔn)則，遺傳算法的優(yōu)化過(guò)程是在適應(yīng)度的指引下，通過(guò)各種遺傳操作(即遺傳算子)來(lái)逐代進(jìn)化。同時(shí)對(duì)產(chǎn)生的新一代種群進(jìn)行遺傳操作，直至滿足收斂結(jié)束條件。遺傳算法的算子包括選擇算子、交叉算子、變異算子[9-11]。

3 實(shí)證分析

在構(gòu)建模型和選擇應(yīng)用遺傳算法后，可通過(guò)matlab工具對(duì)上述問(wèn)題進(jìn)行計(jì)算。假設(shè)某省計(jì)量中心坐標(biāo)為(0，0)，各市緩存庫(kù)坐標(biāo)，配送及回收需求如表1所示。

表1 各倉(cāng)庫(kù)坐標(biāo)、智能電表需求量、周轉(zhuǎn)箱回收需求量

設(shè)選擇概率為0.9，交叉概率為0.3，變異概率為0.01，最大迭代次數(shù)為200，最優(yōu)個(gè)體保持?jǐn)?shù)為100，S∈(0，1，2…，30)，車輛最大行駛距離 MD=10×80=800(km/d)，單車載容為300，計(jì)量中心與各庫(kù)之間的距離采用直線距離，通過(guò)以下公式計(jì)算:

由計(jì)算程序計(jì)算得到的最優(yōu)車輛路徑方案如表2所示。

表2 最優(yōu)車輛路徑方案

經(jīng)分析，在本案例中，計(jì)量中心只需派出6輛車，并按照上述最優(yōu)路線行駛，就能同時(shí)滿足18個(gè)地市緩存庫(kù)和12個(gè)典型縣直配庫(kù)的智能電表配送和周轉(zhuǎn)箱回收需求?？傂旭偮烦虨? 566.1 km，智能電表配送量為1 735，出發(fā)時(shí)車輛平均滿載率為96%，周轉(zhuǎn)箱回收量為1 719，返程時(shí)車輛平均滿載率為95.5%。

4 結(jié)語(yǔ)

從智能電表配送和同時(shí)回收周轉(zhuǎn)箱的的角度，研究了車輛路徑最優(yōu)方案。為了方便求解對(duì)其進(jìn)行了假設(shè)，即在此基礎(chǔ)上，建立了符合實(shí)際的數(shù)學(xué)優(yōu)化模型，并基于遺傳算法的工作流程對(duì)該優(yōu)化方案進(jìn)行了解釋。通過(guò)案例及運(yùn)用matlab工具的計(jì)算驗(yàn)證，構(gòu)建的最優(yōu)回收車輛路徑方案能滿足實(shí)際工作需求。

[1]胡天軍，程文科.帶回程取貨的逆向物流車輛路徑建模及其蟻群算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2010，10(3):110-114.

[2]劉洋.逆向物流車輛路徑問(wèn)題的研究現(xiàn)狀和發(fā)展趨勢(shì)[J].商業(yè)文化，2007，8:200-201.

[3]MONTANE F A T，GALVAO R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computer ＆ OperationResearch，2006，33:595-691.

[4]張濤，田文馨，張杰，劉士新.帶車輛行程約束的VRPSPD問(wèn)題的改進(jìn)蟻群算法[J].系統(tǒng)工程理論與實(shí)踐 .2008，(1):132-140.

[5]EMMANOUIL E，CHRISTORS D，CHRIS T.A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service[J].Expert Systems with Applications，2007(5):152-161.

[6]AI T J，KACHITVICHYANUKL V.A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery[J].Computers ＆ Operations Research，2009，36:1693-1702.

[7]馬慶國(guó)，孟麗君.基于混合算法的具有硬時(shí)間窗口約束的VRPSPD問(wèn)題[J].西安電子科技大學(xué)學(xué)報(bào):社會(huì)科學(xué)版，2009，19(3):41-46.

[8]李華，趙冬梅.具有同時(shí)配送和回收需求的車輛路徑問(wèn)題研究[D].成都.西南交通大學(xué)，2010.

[9]宋遠(yuǎn)清，李水生，梁慎清，等.需求隨機(jī)車輛調(diào)度問(wèn)題的遺傳算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(2):230-233.

[10]李軍，謝秉磊，郭耀煌.非滿載車輛調(diào)度問(wèn)題的遺傳算法田[J].系統(tǒng)工程理論方法應(yīng)用，2000，9(3):235-239.

[11]鐘石泉，王雪蓮.多車場(chǎng)集送一體化車輛調(diào)度問(wèn)題及其遺傳算法研究田[J].西安電子科技大學(xué)學(xué)報(bào):社會(huì)科學(xué)版，2009，19(1):63-68.