基于遺傳算法的智能電能表配送路徑優(yōu)化研究與應(yīng)用

田 廣，羅 蓬，劉朋輝，李鐵成

(1.國網(wǎng)河北省電力公司，石家莊 050021；2.國網(wǎng)河北省電力公司電力科學(xué)研究院，石家莊 050021)

?

基于遺傳算法的智能電能表配送路徑優(yōu)化研究與應(yīng)用

田 廣1，羅 蓬2，劉朋輝1，李鐵成2

(1.國網(wǎng)河北省電力公司，石家莊 050021；2.國網(wǎng)河北省電力公司電力科學(xué)研究院，石家莊 050021)

針對(duì)省級(jí)計(jì)量中心超大規(guī)模智能電能表集中配送業(yè)務(wù)需求，提出一種基于遺傳算法的智能電能表配送路徑優(yōu)化選擇方法。以河北省南部電網(wǎng)二級(jí)庫房配送路徑規(guī)劃應(yīng)用為例，在車輛載容、電能表需求量、最大里程數(shù)等約束條件下，建立集中配送業(yè)務(wù)的規(guī)劃路徑數(shù)學(xué)模型，以配送成本最小化為目標(biāo)，實(shí)現(xiàn)了配送路徑的全局尋優(yōu)，為省級(jí)計(jì)量中心建立經(jīng)濟(jì)高效的智能電能表配送方案提供了科學(xué)的依據(jù)，仿真實(shí)驗(yàn)的結(jié)果驗(yàn)證了該方法的有效性。

智能電能表；配送；遺傳算法；路徑優(yōu)化

0 引言

城市配送系統(tǒng)是多約束條件路徑規(guī)劃問題的一個(gè)典型應(yīng)用[1]，其概念是在一個(gè)有限的區(qū)域范圍內(nèi)，通過統(tǒng)籌管理和動(dòng)態(tài)調(diào)度的物流配送路線，將貨物送至有需求的地點(diǎn)的綜合服務(wù)系統(tǒng)，核心業(yè)務(wù)包括生產(chǎn)調(diào)度、交通運(yùn)輸、貨物存儲(chǔ)以及信息化管理等[2]。在城市配送體系的優(yōu)化管理研究中，配送中心和運(yùn)輸線路的集成管理與優(yōu)化是一個(gè)首要問題，而供電企業(yè)電能表配送業(yè)務(wù)是城市配送系統(tǒng)車輛路徑優(yōu)化問題(Vehicle Routing Problem，VRP)的一個(gè)典型應(yīng)用[3]。

對(duì)于省級(jí)計(jì)量中心，合理安排好配送路線，不僅可以極大地節(jié)約成本，而且還可以大幅提高效率。目前，針對(duì)該問題的研究已成為行業(yè)熱點(diǎn)，文獻(xiàn)[4]采用啟發(fā)式算法對(duì)一些相對(duì)簡單的VRP問題進(jìn)行了探索，文獻(xiàn)[5-6]采用逐次逼近的掃描法尋找配送車輛調(diào)度優(yōu)化方案。然而上述方法均無法求得問題的最優(yōu)解，且算法魯棒性較差，當(dāng)編碼方案較為簡單時(shí)，掃描類算法求解質(zhì)量劣化嚴(yán)重。以下針對(duì)省級(jí)電力計(jì)量中心智能電能表集中配送的路徑選擇問題，建立涵蓋全部二級(jí)庫房的配送規(guī)劃路徑數(shù)學(xué)模型，采用遺傳算法(Genetic Algorithm，GA)的選擇、交叉、變異等算子對(duì)目標(biāo)函數(shù)進(jìn)行規(guī)劃[7]，獲取適應(yīng)性強(qiáng)的選擇方案并將其優(yōu)秀特征遺傳到下一代，最終獲得最優(yōu)配送路線，為建立經(jīng)濟(jì)高效的智能電能表配送方案提供了科學(xué)的依據(jù)。

1 遺傳算法簡述

遺傳算法是目前較為常用的一種全局優(yōu)化算法，通過模仿自然界中生物進(jìn)化的規(guī)律來建立尋優(yōu)方案，采用概率化的尋優(yōu)方法，能夠自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間。該算法的特點(diǎn)是可靠性高、收斂速度快，而且可以不依賴于數(shù)學(xué)模型的梯度信息，是一種自適應(yīng)全局隨機(jī)優(yōu)化方法。

在遺傳算法中，染色體對(duì)應(yīng)的是數(shù)據(jù)或數(shù)組，通常由一維的串結(jié)構(gòu)數(shù)據(jù)來表示，串上各個(gè)位置對(duì)應(yīng)基因取值?；蚪M成的串就是染色體，或者稱為基因型個(gè)體。一定數(shù)量的個(gè)體組成群體，群體中個(gè)體的數(shù)目稱為種群大小，或稱為種群規(guī)模。各個(gè)體對(duì)環(huán)境的適應(yīng)程度稱為適應(yīng)度(fitness)。遺傳算法的基本運(yùn)算過程如下。

a. 編碼。遺傳算法在進(jìn)行搜索之前，需要將解空間轉(zhuǎn)換到遺傳空間。編碼就是將實(shí)際的解空間映射為相應(yīng)的可以被遺傳算法處理的遺傳空間的過程，遺傳算法的編碼就是解的遺傳表示，它是應(yīng)用遺傳算法解決問題的第一步。

b. 初始化種群。遺傳算法解決問題時(shí)，需要隨機(jī)產(chǎn)生N個(gè)初始串并進(jìn)行迭代搜索，初始串的集合及每次迭代生成的一代新串?dāng)?shù)據(jù)就構(gòu)成了一個(gè)種群。遺傳算法以這N個(gè)串結(jié)構(gòu)數(shù)據(jù)構(gòu)成的種群為初始種群，即由該初始種群作為起始點(diǎn)開始進(jìn)化。

c. 適應(yīng)度評(píng)價(jià)。適應(yīng)度是度量種群中個(gè)體在優(yōu)化計(jì)算中可能達(dá)到或接近于最優(yōu)解的優(yōu)良程度，用來評(píng)價(jià)種群中個(gè)體的優(yōu)劣，是遺傳操作的依據(jù)，一般是通過將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)來對(duì)其進(jìn)行計(jì)算并評(píng)價(jià)。

d. 選擇運(yùn)算。選擇運(yùn)算是在適應(yīng)度評(píng)價(jià)的基礎(chǔ)上進(jìn)行的，種群中個(gè)體的適應(yīng)度決定了被選擇的概率，適應(yīng)度越高的個(gè)體被遺傳到下一代的概率較高。選擇過程充分體現(xiàn)了達(dá)爾文的“適者生存”原則，常見和應(yīng)用較多的選擇策略是輪盤賭選擇。

e. 交叉運(yùn)算。交叉運(yùn)算也稱為“基因重組”，在遺傳算法中起著非常關(guān)鍵的作用，決定了遺傳算法的全局搜索能力。交叉運(yùn)算是對(duì)群體中的個(gè)體進(jìn)行隨機(jī)配對(duì)，將2個(gè)配對(duì)的個(gè)體按某種方式相互交換其部分基因，形成2個(gè)新個(gè)體。

f. 變異運(yùn)算。變異運(yùn)算是指?jìng)€(gè)體編碼中的某些基因用其它等位基因來替換，產(chǎn)生新個(gè)體的操作。變異運(yùn)算主要為了改善遺傳算法的局部搜索能力，維持群體多樣性，防止出現(xiàn)早熟現(xiàn)象。由于在生物界中發(fā)生變異的情況很少，所以變異概率一般較低。

圖1 遺傳算法流程

2 智能電能表配送路徑規(guī)劃模型

根據(jù)河北省南部電網(wǎng)智能電能表配送實(shí)際情況，將配送車輛路徑規(guī)劃抽象為典型數(shù)學(xué)模型，并作如下假設(shè)：

a. 智能電能表配送過程專指從省級(jí)計(jì)量中心一級(jí)庫房到各市縣供電公司二級(jí)庫房的過程；

b. 只有省計(jì)量中心一個(gè)一級(jí)庫房，每輛車均從省計(jì)量中心出發(fā)，完成本車路徑上配送任務(wù)后直接返回省計(jì)量中心；

c. 只有一種車型，每輛車的載容已知，單個(gè)供電公司的需求量不超過單車載容；

d. 一級(jí)庫房與二級(jí)庫房的地理坐標(biāo)已知，即省計(jì)量中心與地市供電公司之間的距離已知；

e. 二級(jí)庫房的智能電能表配送需求只能由一輛車配送，每輛車所走的路線不重復(fù)；

f. 每輛配送車根據(jù)智能電能表需求單位在做好區(qū)分標(biāo)示的前提下可以進(jìn)行混裝；

g. 每輛配送車的最大行駛距離已知，不能超過該最大里程；

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

根據(jù)上述描述和相關(guān)假設(shè)，以車輛行駛路程最小為目標(biāo)建立配送車輛路徑規(guī)劃數(shù)學(xué)模型為[1]

目標(biāo)函數(shù)

(1)

約束條件：

(2)

(3)

(4)

(5)

上述模型中，計(jì)量中心編號(hào)為0，各市縣公司二庫房為1,2,…,k；i,j為二級(jí)庫房序號(hào)，s為車輛序號(hào)，gi為二級(jí)庫i的智能表需求量，m為車輛總數(shù)，q為每輛車載容量，cij表示點(diǎn)i到點(diǎn)j的運(yùn)輸成本；xij為決策變量，表示車s是否由i駛向j，如果是xijs值為1，否則為0；yis為決策變量，表示二級(jí)庫i的任務(wù)是否由車s完成，如果是yis值為1，否則為0。

目標(biāo)函數(shù)(1)要求合理安排配送車輛路徑，使得運(yùn)輸成本最小。約束條件式(2)為每輛配送車的載容量；式(3)保證了每個(gè)二級(jí)庫房的配送任務(wù)僅由1輛配送車來完成，而所有的配送任務(wù)則由m輛車共同完成；式(4)和(5)限制了到達(dá)和離開某一個(gè)二級(jí)庫房的配送車有且僅有一輛，并對(duì)xijs和yis的取值分別進(jìn)行了限制。

3 最優(yōu)路徑問題求解

在算法模型構(gòu)建后，應(yīng)用Matlab工具對(duì)上述問題進(jìn)行求解。以河北南網(wǎng)計(jì)量中心向衡水地區(qū)各單位配送電能表為例，實(shí)際配送路線見圖2。結(jié)合配送車輛日常實(shí)際配送里程，建立各二級(jí)庫房之間的等效配送距離表見表1。

圖2 省計(jì)量中心實(shí)際配送路線圖

根據(jù)等效配送距離表，將地理圖轉(zhuǎn)換為坐標(biāo)圖，并設(shè)省計(jì)量中心坐標(biāo)為(0,0)，二級(jí)庫房數(shù)量為11個(gè)，車輛載容為1萬只，各二級(jí)庫房的需求總量為1.9萬只，見表2。在配送分布圖上進(jìn)行模擬找到合理派發(fā)車輛數(shù)和最佳配送路徑。

表1 二級(jí)庫房等效配送距離 km

計(jì)量中心衡水安平饒陽深州武強(qiáng)武邑阜城景縣冀州棗強(qiáng)故城計(jì)量中心012711013085125139167177158165195衡水127090784850204859182961安平11090021265787114126104114144饒陽130782103136636911493102132深州854826310434785957483113武強(qiáng)1255057364303134646679109武邑139208763473102937364079阜城1674811469853429022646787景縣17759126114956437220726652冀州1581810493746636647201950棗強(qiáng)16529114102837940676619050故城1956114413211310979875250320

表2 各二級(jí)庫房位置坐標(biāo)及需求量情況

編號(hào)x軸/kmy軸/km智能電能表需求量/千只000018298125109231412914357715461162679114478114618112137391061161101201142111501251

4 路徑規(guī)劃優(yōu)化分析

用Matlab對(duì)該優(yōu)化問題進(jìn)行模擬運(yùn)算，設(shè)置種群規(guī)模n=500，迭代次數(shù)C=500，交叉概率Pc=0.8，變異概率Pm=0.2，經(jīng)過50次蒙特卡洛模擬計(jì)算，得到的優(yōu)化路徑結(jié)果如圖3所示。

圖3 智能表配送路線優(yōu)化結(jié)果(12節(jié)點(diǎn))

通過結(jié)果的計(jì)算可知，利用該文算法得到的優(yōu)化配送路徑為0→4→2→3→5→6→0→7→8→11→10→9→1→0，總里程799.644 5 km，明顯優(yōu)于隨機(jī)法得到的結(jié)果1 025 km。圖4為目標(biāo)函數(shù)在約束條件下的迭代優(yōu)化過程，可以看出，最優(yōu)適應(yīng)值在約100次迭代后即趨于收斂，表明了該算法的有效性。

圖4 適應(yīng)值遺傳優(yōu)化過程

為了進(jìn)一步驗(yàn)證算法性能，將二級(jí)庫房數(shù)目增加至17個(gè)，按照石家莊周邊分布，調(diào)整車輛容載等限制條件，重新進(jìn)行試驗(yàn)，結(jié)果如圖5所示。

圖5 智能表配送路線優(yōu)化結(jié)果(18節(jié)點(diǎn))

結(jié)果表明，該算法在多節(jié)點(diǎn)中心分布情況下仍能良好工作，將取得的結(jié)果與電能表配送日志系統(tǒng)進(jìn)行比對(duì)，結(jié)果表明算法能夠較為正確地反映配送方案的優(yōu)化趨勢(shì)。

5 結(jié)束語

從計(jì)量中心向n個(gè)二級(jí)庫房配送會(huì)有n!個(gè)可選的路徑方案，考慮到所有路徑均雙向可逆，文中11!個(gè)方案中每個(gè)方案都存在另一個(gè)與之重復(fù)的方案，因此實(shí)際可行解的數(shù)量為0.5×11！=19 958 400個(gè)，但是使用遺傳算法可以方便地從中尋找到最優(yōu)路線方案，當(dāng)庫房個(gè)數(shù)繼續(xù)增加時(shí)，所需要的僅僅是改變編碼的長度而已，設(shè)計(jì)難度基本不變，具有很好的可推廣性。

根據(jù)實(shí)際運(yùn)行情況統(tǒng)計(jì)和測(cè)算，自2015年8月正式推廣應(yīng)用以來，在未增加車輛和配送費(fèi)用的情況下，月度平均配送效率提升18%，百km配送成本降低11%，僅2015年一年節(jié)約配送費(fèi)用42.3萬元，具有非常好的經(jīng)濟(jì)性和可推廣性，建議進(jìn)一步優(yōu)化算法和程序，開發(fā)出適合智能表配送需求的路徑自動(dòng)優(yōu)化系統(tǒng)，進(jìn)一步推廣應(yīng)用。

[1] 李 軍, 郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京: 中國物資出版社, 2001.

[2] 蔣琦瑋, 陳治亞. 物流配送最短徑路的動(dòng)態(tài)規(guī)劃方法研究[J]. 系統(tǒng)工程, 2007, 25(4): 27-29.

[3] 劉慧美, 董富貴, 賈朝輝. 基于遺傳算法的智能電能表配送車輛優(yōu)化調(diào)度[J]. 華北電力技術(shù), 2012, 11(8): 21-25.

[4] S.Salhi, G.Nagy. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research, 2005, 162(1): 126-141.

[5] Z Fu, R.Eglese, L Li. A new tabu search heuristic for the open vehicle routing problem[J]. Journal of the Operational Research Society, 2005, 56(3): 267-274.

[6] 鐘石泉, 杜 綱. 基于核心路徑禁忌算法的開放式車輛路徑問題研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(4): 827-832.

[7] 孫小年, 陳幼林, 楊東援. 裝卸一體化車輛路徑問題的遺傳算法研究[J]. 系統(tǒng)工程理論與實(shí)踐, 2007, 27(2): 149-152.

本文責(zé)任編輯：王洪娟

Research and Application on Distribution Routing Optimization for Intelligent Electric Meter Based on Genetic Algorithm

Tian Guang1,Luo Peng2,Liu Penghui1,Li Tiecheng2

(1.State Grid Hebei Electric Power Company,Shijiazhuang 050021,China;2.State Grid Hebei Electric Power Research Institute,Shijiazhuang 050021,China)

To meet the demand of super large scale intelligent electric meter distribution of provincial metering center,a novel optimization selection method for intelligent electric meter distribution routing is proposed,which is based on genetic algorithm.With the application in subordinate warehouse path planning for southern Hebei network,under the restrained conditions for vehicle capacity, electric meter requirement and maximum mileage,mathematical model of distribution routing is constructed,then the global optimization of distribution path by minimizing the total cost,which providing a scientific basis for the establishment of economical and efficient distribution scheme.The simulation results verifies the efficiency of this method.

intelligent electric meter;distribution;genetic algorithm;routing optimization

2017-01-12

田 廣(1983-)，男，高級(jí)工程師，主要從事督察督辦管理工作。

TM763

A

1001-9898(2017)03-0007-03