改進遺傳算法的保定郵政車輛調度問題研究

張凡華北理工大學建筑工程學院

改進遺傳算法的保定郵政車輛調度問題研究

張凡
華北理工大學建筑工程學院

為解決保定市郵政車輛調度的問題，基于傳統遺傳算法，建立數學模型。針對傳統遺傳算法存在的“早熟”問題，融入自適應變異算子，設計一種改進遺傳算法。通過matlab仿真實驗，對保定市各縣區郵政局間配送車輛路徑進行優化，實驗證明改進遺傳算法優于傳統遺傳算法。

郵政車輛調度；遺傳算法；自適應變異算子；數學模型

近年來，民營企業發展迅速，給郵政帶來一定的壓力。郵政在民營快遞面前價格競爭力不強，而且現在的客戶對郵件配送的服務質量要求較高。進行成本控制是郵政物流企業所面臨的挑戰。保定市郵政車輛調度是由有經驗的調度人員編制計劃，根據經驗擬訂方案，計劃編制勞動強度太大，難以保證方案最優。設計郵政車輛調度模型和算法用計算機來實現很有必要。

目前，專家針對車輛調度問題已經提到過一些方法，如上世紀六十年代，Balinski提到VRP的集分割[1]，而且對此作出了優化，構建了最基本的VRP模型；尹曉峰等人[2]就蟻群算法中的“早熟”問題，融入節省量以及車輛載重利用率對蟻群算法進行了完善。李嘉等人提出了混合車隊求解框架，設計了基于遺傳算法和禁忌搜索啟發式的混合算法[3]。本文在傳統遺傳算法基礎上融入自適應性變異算子，構造一種改進的遺傳算法來進一步分析保定郵政車輛調度問題。

一、郵政車輛調度數學模型

（1）為目標函數，車輛完成調度任務的最少總運輸里程；（2）為車輛能力約束，某車所訪問的縣區局的需求量不可超過自身的載重量；（3）為縣區i由車輛k完成的唯一性；（4）為縣區i由車輛k完成與否；（5）、（6）為到達某縣區車輛唯一性；（7）為車輛k從縣區i行駛到縣區j與否。

二、改進的遺傳算法

（一）傳統的遺傳算法容易出現過早收斂的現象，很難找到全局最優解。這就需要我們對傳統的遺傳算法加以改進，引入一些新的方法來增強全局搜索能力，防止出現局部最優。本文采用自適應變異方法，處理變異概率Pm,使之隨個體適應度值變化.取Pc=0.85。Pm按如下方法動態調整。

若fmax＞f＞favg,對交叉和變異概率自適應調整.若f＜favg,進行大概率變異,以便迅速淘汰適應值較低的個體,來增大解間。

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

三、實驗分析

用matlab對改進遺傳算法進行仿真,結果如圖.通過仿真結果,得出如下結論：隨著迭代次數的增加，計算結果是逐步收斂于某個數值。相對于傳統遺傳算法，改進遺傳算法是較優秀的，避免出現過早收斂；傳統的遺傳算法有很大可能找到的解是局部最優解。改進的遺傳算法尋優能力相對較強，最終得到的解比傳統的遺傳算法得到的解還要優秀，更加說明融入自適應性變異算子的改進遺傳算法在解決保定郵政車輛調度問題的有效性。

圖1

最優路徑為：保定——順平縣——望都縣——清苑區——高陽縣——保定——安新縣——容城縣——徐水區——保定——定興縣——淶水縣——易縣——滿城區——保定。

四、結束語

本文針對傳統遺傳算法存在搜索能力差、易過早收斂的缺點,引入自適應變異算子，對傳統遺傳算法進行改進。仿真結果說明改進算法具備抗“早熟”、良好的尋優能力。改進的算法為保定郵政車輛調度問題提供了一個較為有效的解決方法。

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

[2]尹曉峰，杜艷萍.車輛路徑問題的蟻群算法研究[J].太原科技大學學報，2005（4）：279-283.

[3]李嘉等.一類特殊車輛路徑問題（VRP）[J].東北大學學報（自然科學版），2001.22（3）：245-248.

張凡（1994-），女，河北保定人，華北理工大學建筑工程學院，物流工程專業。