改進(jìn)遺傳算法的保定郵政車(chē)輛調(diào)度問(wèn)題研究

張凡華北理工大學(xué)建筑工程學(xué)院

改進(jìn)遺傳算法的保定郵政車(chē)輛調(diào)度問(wèn)題研究

張凡
華北理工大學(xué)建筑工程學(xué)院

為解決保定市郵政車(chē)輛調(diào)度的問(wèn)題，基于傳統(tǒng)遺傳算法，建立數(shù)學(xué)模型。針對(duì)傳統(tǒng)遺傳算法存在的“早熟”問(wèn)題，融入自適應(yīng)變異算子，設(shè)計(jì)一種改進(jìn)遺傳算法。通過(guò)matlab仿真實(shí)驗(yàn)，對(duì)保定市各縣區(qū)郵政局間配送車(chē)輛路徑進(jìn)行優(yōu)化，實(shí)驗(yàn)證明改進(jìn)遺傳算法優(yōu)于傳統(tǒng)遺傳算法。

郵政車(chē)輛調(diào)度；遺傳算法；自適應(yīng)變異算子；數(shù)學(xué)模型

近年來(lái)，民營(yíng)企業(yè)發(fā)展迅速，給郵政帶來(lái)一定的壓力。郵政在民營(yíng)快遞面前價(jià)格競(jìng)爭(zhēng)力不強(qiáng)，而且現(xiàn)在的客戶(hù)對(duì)郵件配送的服務(wù)質(zhì)量要求較高。進(jìn)行成本控制是郵政物流企業(yè)所面臨的挑戰(zhàn)。保定市郵政車(chē)輛調(diào)度是由有經(jīng)驗(yàn)的調(diào)度人員編制計(jì)劃，根據(jù)經(jīng)驗(yàn)擬訂方案，計(jì)劃編制勞動(dòng)強(qiáng)度太大，難以保證方案最優(yōu)。設(shè)計(jì)郵政車(chē)輛調(diào)度模型和算法用計(jì)算機(jī)來(lái)實(shí)現(xiàn)很有必要。

目前，專(zhuān)家針對(duì)車(chē)輛調(diào)度問(wèn)題已經(jīng)提到過(guò)一些方法，如上世紀(jì)六十年代，Balinski提到VRP的集分割[1]，而且對(duì)此作出了優(yōu)化，構(gòu)建了最基本的VRP模型；尹曉峰等人[2]就蟻群算法中的“早熟”問(wèn)題，融入節(jié)省量以及車(chē)輛載重利用率對(duì)蟻群算法進(jìn)行了完善。李嘉等人提出了混合車(chē)隊(duì)求解框架，設(shè)計(jì)了基于遺傳算法和禁忌搜索啟發(fā)式的混合算法[3]。本文在傳統(tǒng)遺傳算法基礎(chǔ)上融入自適應(yīng)性變異算子，構(gòu)造一種改進(jìn)的遺傳算法來(lái)進(jìn)一步分析保定郵政車(chē)輛調(diào)度問(wèn)題。

一、郵政車(chē)輛調(diào)度數(shù)學(xué)模型

（1）為目標(biāo)函數(shù)，車(chē)輛完成調(diào)度任務(wù)的最少總運(yùn)輸里程；（2）為車(chē)輛能力約束，某車(chē)所訪問(wèn)的縣區(qū)局的需求量不可超過(guò)自身的載重量；（3）為縣區(qū)i由車(chē)輛k完成的唯一性；（4）為縣區(qū)i由車(chē)輛k完成與否；（5）、（6）為到達(dá)某縣區(qū)車(chē)輛唯一性；（7）為車(chē)輛k從縣區(qū)i行駛到縣區(qū)j與否。

二、改進(jìn)的遺傳算法

（一）傳統(tǒng)的遺傳算法容易出現(xiàn)過(guò)早收斂的現(xiàn)象，很難找到全局最優(yōu)解。這就需要我們對(duì)傳統(tǒng)的遺傳算法加以改進(jìn)，引入一些新的方法來(lái)增強(qiáng)全局搜索能力，防止出現(xiàn)局部最優(yōu)。本文采用自適應(yīng)變異方法，處理變異概率Pm,使之隨個(gè)體適應(yīng)度值變化.取Pc=0.85。Pm按如下方法動(dòng)態(tài)調(diào)整。

若fmax＞f＞favg,對(duì)交叉和變異概率自適應(yīng)調(diào)整.若f＜favg,進(jìn)行大概率變異,以便迅速淘汰適應(yīng)值較低的個(gè)體,來(lái)增大解間。

（二）基本數(shù)據(jù)。保定市郵政局到滿(mǎn)城、順平、望都、清苑、高陽(yáng)、安新、容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：26、34、34、12、35、45、47、57、77、63、25。滿(mǎn)城郵政局到順平、望都、清苑、高陽(yáng)、安新、容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：21、35、36、59、63、77、80、80、58、38.順平郵政局到望都、清苑、高陽(yáng)、安新、容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：23、41、72、96、85、88、88、93、66.望都郵政局到清苑、高陽(yáng)、安新、容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：33、74、82、90、106、109、113、80.清苑郵政局到高陽(yáng)、安新、容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：31、18、65、37、87、63、35.高陽(yáng)郵政局到安新、容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：36、52、88、110、123、54.安新郵政局到容城、定興、淶水、易縣、徐水郵政局的距離（千米）為：19、49、72、80、37.容城郵政局到定興、淶水、易縣、徐水郵政局的距離（千米）為：32、54、62、21.定興郵政局到淶水、易縣、徐水郵政局的距離（千米）為：20、29、33.淶水郵政局到易縣、徐水郵政局的距離（千米）為：20、49.易縣郵政局到徐水郵政局的距離（千米）為48。

三、實(shí)驗(yàn)分析

用matlab對(duì)改進(jìn)遺傳算法進(jìn)行仿真,結(jié)果如圖.通過(guò)仿真結(jié)果,得出如下結(jié)論：隨著迭代次數(shù)的增加，計(jì)算結(jié)果是逐步收斂于某個(gè)數(shù)值。相對(duì)于傳統(tǒng)遺傳算法，改進(jìn)遺傳算法是較優(yōu)秀的，避免出現(xiàn)過(guò)早收斂；傳統(tǒng)的遺傳算法有很大可能找到的解是局部最優(yōu)解。改進(jìn)的遺傳算法尋優(yōu)能力相對(duì)較強(qiáng)，最終得到的解比傳統(tǒng)的遺傳算法得到的解還要優(yōu)秀，更加說(shuō)明融入自適應(yīng)性變異算子的改進(jìn)遺傳算法在解決保定郵政車(chē)輛調(diào)度問(wèn)題的有效性。

圖1

最優(yōu)路徑為：保定——順平縣——望都縣——清苑區(qū)——高陽(yáng)縣——保定——安新縣——容城縣——徐水區(qū)——保定——定興縣——淶水縣——易縣——滿(mǎn)城區(qū)——保定。

四、結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)遺傳算法存在搜索能力差、易過(guò)早收斂的缺點(diǎn),引入自適應(yīng)變異算子，對(duì)傳統(tǒng)遺傳算法進(jìn)行改進(jìn)。仿真結(jié)果說(shuō)明改進(jìn)算法具備抗“早熟”、良好的尋優(yōu)能力。改進(jìn)的算法為保定郵政車(chē)輛調(diào)度問(wèn)題提供了一個(gè)較為有效的解決方法。

[1]BalinskiM,Quand R.on an integer program fora delivery problem[J].OperationsResearch,1962.12：300-304.

[2]尹曉峰，杜艷萍.車(chē)輛路徑問(wèn)題的蟻群算法研究[J].太原科技大學(xué)學(xué)報(bào)，2005（4）：279-283.

[3]李嘉等.一類(lèi)特殊車(chē)輛路徑問(wèn)題（VRP）[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2001.22（3）：245-248.

張凡（1994-），女，河北保定人，華北理工大學(xué)建筑工程學(xué)院，物流工程專(zhuān)業(yè)。