基于雙種群混合遺傳算法的車輛調度問題研究

胡云清 （山西交通職業技術學院，山西 太原030031）

HU Yun-qing (Shanxi Traffic Vocational and Technical College, Taiyuan 030031, China)

0 引 言

物流活動作為企業的“第三方利潤源泉”，在提高企業經濟效益、降低企業成本等方面發揮著重要作用。而車輛路徑優化作為企業物流活動的關鍵，更是廣受學者們的關注[1]。特別是在配送成本較高、嚴重影響企業生存發展和城市交通擁堵越來越嚴重的情況下，通過對企業車輛配送路徑的優化，降低企業配送成本、緩解城市交通擁堵，更是意義重大。

分析現有相關文獻可知，車輛路徑優化問題的求解算法可以分為精確算法和近似算法。精確算法指能夠求出全局最優解的算法，而近似求解算法則無法求出問題最優解、只能求得最優解的近似值[2]。由于精確算法的計算量會隨著問題規模的增大而呈指數增長，所以它在實際問題中應用較為有限。相比之下，對于近似算法的研究更為廣泛。其中遺傳算法由于具有搜索空間較大、求解精度較高等優點，更是倍受學者的青睞。如文獻[3-5]均對車輛路徑問題的遺傳算法進行了研究。但傳統遺傳算法也存在著容易陷入局部最優解、收斂速度較慢等問題，影響著算法的求解性能。對此，本文對傳統遺傳算法進行了改進，提出了求解車輛路徑優化問題的雙種群混合遺傳算法。

1 車輛路徑優化問題模型

車輛路徑優化問題一般可以描述為：企業配送中心需要用多輛車輛完成不同客戶點的需求配送任務。配送中心位置已知，客戶點需求量和位置信息已知，每輛車的載重量一定，且具有載重約束，即車輛所載貨物不能超過車輛最大載重量，要求合理規劃車輛行駛路徑，使車輛總行駛距離最短，同時必須滿足如下幾個條件：（1） 企業車輛足夠多，能夠完成企業配送任務，且車輛類型相同；（2） 每個客戶的需求量均不超過車輛的最大載重量；（3） 必須滿足所有客戶的需求，并且一個客戶只能由一輛車服務。

設需要服務的客戶數量為K，完成此次配送任務所需要的車輛數為m；企業配送中心用0 表示，各客戶點用表示；每個客戶的需求量為車輛的最大載重量為q，且gi ＜q；dij表示客戶i到j的距離。定義模型決策變量如下：

則車輛路徑優化問題的數學模型為：

其中，式（1） 表示車輛總行駛距離最短的優化目標。式（2） 為車輛載重約束，即車輛不能超載。式（3） 有兩層意義，首先表示每個需求點只能由一臺車進行配送服務；其次表示所有車輛從配送中心出發，且完成配送任務后必須返回配送中心。式（4） 和式（5） 表示兩決策變量之間的關系。式（6） 和式（7） 表示0-1 變量約束。

2 雙種群混合遺傳算法

遺傳算法局部尋優能力較強，而且并發性較好。但同人的進化一樣，隨著算法的進行，種群中的個體逐漸靠近最優解，其特性逐漸穩定，種群達到了一種平衡狀態。此時種群的特性基本不再變化。因此在傳統遺傳算法后期，算法往往容易陷入局部最優解。本文提出的雙種群混合遺傳算法正是針對這種情況，在算法中同時使用兩個種群進行優化，并且在每一次迭代結束后，都將由兩個種群中選出的小種群進行互換，進而不斷打破種群的平衡，跳出局部最優解，提高算法求解性能。雙種群混合遺傳算法具體的操作為：第一步，建立兩個規模相同的種群。第二步，以不同的交叉概率和變異概率分別獨自進行交叉和變異操作。第三步，在每一次迭代完后，從兩個種群中分別取出由各自最優個體與一定數量的隨機個體組成的小種群，將各自的小種群進行交換，進入對方種群中。同時，為了提高算法的求解速度，本文還利用2-opt 算子將種群中的最優個體進行了進一步優化。

雙種群混合遺傳算法中，每個種群都是按相同的方式進行選擇、交叉和變異等遺傳操作，因此如下的相關介紹均是針對兩個種群同時進行的。

2.1 編碼策略。 參照文獻[3]，采用自然數串編碼機制將每條配送路徑編制成長度為K +m+1 的橫向量（0,i1,i2,…,ie,0,if,…,ik,0,…,0,ip,…,iq,0 ），其中0 為配送中心，ik表示序號為ik的客戶。

2.2 初始種群生成。在初始種群生成算法上，首先隨機產生n個客戶的全排列；然后，在全排列首尾添加0；最后，將m-1 個0 隨機插入到全排列中，但兩個0 不能相鄰。

2.3 適應度函數選取。一般情況下，個體適應度值越高，表示個體越優秀，解的質量越高。所以本文對式（1） 進行如下改進，作為遺傳算法的適應度函數。

式中，b為常數，根據車輛路徑優化問題的規模而設定。

2.4 遺傳算子。遺傳算法的遺傳算子包括選擇算子、交叉算子和變異算子。在選擇算子上，本文采用輪盤賭算子選取優秀個體；交叉算子和變異算子均采用傳統遺傳算法的相應算子，由于現有文獻多有闡述，再此就不再一一介紹。

2.5 種群交叉。隨機從種群A 中選取num個個體（num的值根據具體問題設定） 和最優個體，同時也從種群B 中選取num個隨機個體和最優個體。將兩個種群對應的num+1 個染色體進行互換，進入對方種群中。同時，由于在算法進化過程中，種群中的優秀個體往往存在交叉點，這不僅降低了算法的收斂速度，同時還影響了算法的全局尋優能力。為了加快算法收斂速度、提高算法全局優化能力，采用文獻[6]中的2-opt 算子消除最優個體的交叉點，提高優秀個體的質量。具體操作如下：

隨機選精英個體中的兩條邊，記為（i,j）和（i+1,j+1 ），將其拆分后重新連接起來組成新的路徑（i,i+ 1 ）和（j,j+ 1 ），如果更新后的路徑滿足車輛載重約束，且使目標函數更小，則說明該交叉點可以消除，執行上述操作。重復上述操作，直到所有交叉點消除完為止。

3 算例分析

采用有能力約束的車輛調度問題的標準算例進行仿真實驗①。為了驗證算法的求解性能，分別利用傳統遺傳算法（GA）、禁忌搜索算法（TS） 和本文算法對算例進行求解，并對求解結果進行了統計，結果如表1 所示。

從表1 中可知，在問題規模較小時，三個算法都具有較高的求解精度，但GA 算法和本文算法求解精度更高。而隨著問題規模的逐漸增大，GA 算法和TS 算法明顯陷入局部最優解，本文算法在求解精度上雖然有所下降，但仍然能夠取得較好的求解結果。說明通過對傳統遺傳算法的改進，本文算法在全局優化能力上有所提高，優于GA 算法和TS 算法。這是由于通過兩個種群之間的交叉，使種群始終保持著多樣性，進而提高了算法的全局尋優能力。

表1 標準算例測試結果

4 結束語

車輛路徑優化問題有利降低企業配送成本，促進企業的發展。針對傳統遺傳算法存在的諸如容易陷入局部最優解等問題，本文提出了求解車輛路徑優化問題的雙種群混合遺傳算法，為車輛路徑問題的求解提供了新的研究思路。當然，本文仍然存在一些不足的地方，有待進一步改進，如：本文假設企業擁有的車輛類型相同，這與企業配送的實際情況具有一定的差距，論文的下一步研究方向即為考慮多車型的車輛路徑優化問題。

注：①數據來源于：http://ftp.ics.uci.edu/pub/machine-learning-databases/。

[1] 許茂增，余國印. 城市配送研究的新進展[J]. 中國流通經濟，2014(11):29-36.

[2] 李娟，余國印. 綜合成本最小的車輛調度問題及混沌螢火蟲優化算法[J]. 物流技術，2015(7):180-183.

[3] 許茂增，余國印，周翔,等. 綜合成本最小的低碳車輛調度問題及算法[J]. 計算機集成制造系統，2015(1):26.

[4] 楊渝華，李敏. 基于改進遺傳算法的成品油配送車輛調度問題研究[J]. 物流科技，2015(1):148-153.

[5] 王永，楊曉潔，胥冬川,等. 基于禁忌遺傳算法的郵政運輸車輛調度問題[J]. 系統工程，2014(8):102-109.

[6] BIANCHI L, KNOWLES J, BOWLER J. Local search for the probabilistic traveling salesman problem: correction to the 2-ppt and 1-shift algorithms[J]. European Journal of Operational Research, 2005,162(1):206-219.