智能電表周轉(zhuǎn)箱回收車輛路徑規(guī)劃研究

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

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

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

1 構建數(shù)學模型

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

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

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

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

4)省計量中心、地市緩存庫的地理坐標已知，即省計量中心與地市緩存庫之間的距離已知。

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

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

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

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

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

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

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

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

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

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

2 求解數(shù)學模型的遺傳算法設計

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

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

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

3)計算每個個體適應度值。適應度是評價個體優(yōu)劣和進行遺傳操作的依據(jù)，度量個體適應度的函數(shù)稱為適應度函數(shù)。基本遺傳算法按與個體適應度成正比的概率來決定當前種群中個體遺傳到下一代種群中的機會。根據(jù)所研究個體的實際情況，擬通過以下公式計算個體適應度值:

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

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

3 實證分析

在構建模型和選擇應用遺傳算法后，可通過matlab工具對上述問題進行計算。假設某省計量中心坐標為(0，0)，各市緩存庫坐標，配送及回收需求如表1所示。

表1 各倉庫坐標、智能電表需求量、周轉(zhuǎn)箱回收需求量

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

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

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

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

4 結(jié)語

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

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

[2]劉洋.逆向物流車輛路徑問題的研究現(xiàn)狀和發(fā)展趨勢[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問題的改進蟻群算法[J].系統(tǒng)工程理論與實踐 .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]馬慶國，孟麗君.基于混合算法的具有硬時間窗口約束的VRPSPD問題[J].西安電子科技大學學報:社會科學版，2009，19(3):41-46.

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

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

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

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