遺傳算法在ＶＲＰ問題中的應用

張國英　林賢茂

摘要：配送是物流系統中一個直接與消費者相連的重要環節，對配送系統進行優化，可以提高物流經濟效益、實現物流科學化，因此配送系統的優化問題顯得尤為重要。進行配送系統優化，主要是配送車輛調度的優化。文章在全面分析研究物流配送業務特點的基礎上，針對配送中的核心問題——車輛調度優化問題進行了深入的研究，建立了單源點物流配送車輛調度優化問題的數學模型，并運用遺傳算法對其進行求解，仿真實例證明了該方法的有效性。

關鍵詞：物流配送；車輛調度；遺傳算法

中圖分類號：U116.2文獻標識碼：A

Abstract: Distribution is an important link in logistics, which is joined to consumers directly. Vehicle Routing Problem（VRP）is the main part of optimizing the distribution system. It can advance the economic benefits and make logistics scientific. Firstly, the paper analyzes VRP, and sorts it according to given conditions. Secondly, it chooses a typical one to analyze. It sets a model of the problem, and settles it with a genetic algorithm that is fast and accurate. Lastly, the paper illustrates the process of using the method referred in the paper by an example.

Key words: distribution; VRP; genetic algorithm

0引言

物流配送車輛優化調度問題于1959年由Dantzig和Ramser提出，國外一般稱之為Vehicle Routing Problem（VRP）[1]。車輛調度問題是指為服務于已知的一組顧客的一個車隊，設計一組開始和結束于一個中心出發點的最小費用路徑。每個顧客只能被服務一次，而且一個車輛服務的顧客數不能超過它的能力。VRP已被證明是一個NP問題。

VRP問題的研究起步較早，求解方法也非常豐富，基本上可以分為精確算法和啟發式算法兩大類[2]。由于VRP問題是強NP難題，高效的精確算法存在的可能性不大，所以尋找近似算法是必要和現實的，本論文在建設物流配送體系、改進遺傳算法的應用等方面進行了新的探索與嘗試，主要工作在于：

（1）將改進遺傳算法應用于物流配送優化中實際問題的求解，并采用計算機語言完成對其算法的實現；

（2）通過實證分析，改進遺傳算法用于物流配送優化的效果。

1問題描述

典型的VRP問題可以描述為：從某物流中心用多臺配送車輛向多個客戶送貨，每個客戶的位置和貨物需求量一定，每輛配送車輛的載重量一定，其一次配送的最大行駛距離一定，要求合理安排車輛配送路線，使目標函數得到優化。

2掃描法和遺傳算法介紹

制定從一個物流中心向多個用戶運送貨物的配送計劃時，必須考慮每輛車的運載能力和行駛距離及時間等的限制。掃描法是一種能較好地解決配送路線問題的方法。

遺傳算法最早由美國密切根大學（Michigan）的Holland教授提出，主要特點是群體搜索策略和群體（population）中個體（individual）之間的信息交換。它實際上是模擬由個體組成的群體的整體學習過程，其中每個個體對應研究問題的一個解。

鑒于以上算法的特點，本文將掃描法和遺傳算法結合以來，將VRP問題轉換為TSP問題求解，并且對傳統的遺傳算法進行改進。

3算法的設計

{輸入車輛調度問題的己知條件：

輸入運行參數，如群體規模N，終止進化代數T和最優染色體保留代數N，交叉概率pc，變異概率pm，執行變異操作時的基因換位次數J，對不可行路徑的懲罰權重Pw等；

采用掃描法進行配送線路分區，確定每個客戶點屬于哪輛車，車輛編號為1-m；

Whilei≤mdo

隨機產生初始化群體P0，當前進化代數t=0；

計算P0中每個個體的適應度；

whilet<指定進化終止代數Tdo

{將本代中適應度最高的個體復制一個，直接進入到新群體Pt+1中；

根據本代個體的適應度，計算群體內每個個體的選擇概率pi；然后根據輪盤賭方式選擇染色體復制到新群體Pt+1，使新群體的規模為N；

根據選擇概率pc，從Pt+1中隨機生成兩條染色體作父代，交叉操作生成兩條新染色體，計算四條染色體適應度，保留兩條最優染色體在Pt+1中；

根據選擇概率pm，從Pt+1中隨機生成一條染色體作父代，變異操作生成新染色體，計算父代和子代染色體適應度，保留最優染色體在Pt+1中；

計算Pt+1中每個個體的適應度和成本；

t=t+1；

}

輸出最優染色體的編碼和染色體的成本；

i=i+1；

計算并輸出各輛車最優染色體的成本和。

}

4仿真實驗

實驗：現假設有n個貨物需求點和一個為這些需求點提供貨物的配送中心，配送中心有m輛汽車用于各需求點的貨物配送，每輛車的載重量皆為定值，假設車輛的容量為10 000，每個客戶的需求為0~10 000/7的一個隨機數。

通過實驗遺傳算法和節約型算法的比較（如表1所示），可知：

（1）采用首先掃描后遺傳算法進行配送路徑優化，隨客戶點的增加，計算時間有所增加，但是時間變化近似線性變化，而節約型的算法，隨客戶點的增加，計算時間呈幾何級增長，當客戶點在一千個左右的時候，運行時間超過半個小時；

（2）通過試驗可以得出這樣的結論：若車的容量一定，使每輛車配送的客戶點一定，增加客戶點的個數對程序運行時間影響不是很大。但是若每輛車的配送點增加，這樣程序的運行時間會顯著增加，當每輛車的客戶點超過500時，程序在十分鐘內運行不出結果。對于單車來講，采用此算法最適合的配送點在10, 200區間；

（3）采用不同的交叉和變異對于程序的收斂速度以及程序的準確性有很大的影響；對于不同規模的線路優化問題，應當選取不同的參數值。

5結論

遺傳算法與傳統的算法相比的優越性有：（1）遺傳算法能以很大的概率找到問題的最有解，遺傳算法具有并行性，能有效地處理大規模的優化問題。（2）遺傳算法的結構是開放式的，與問題本身無關，所以容易和其他的算法相結合，共同得到性能更好的混合算法。

參考文獻：

[1] Dantzig G., Ramser J. The Truck Dispatching Problem[J]. Management Sci, 1959(6):80-91.

[2] 李軍. 物流配送車輛優化調度理論與方法[M]. 北京：中國物資出版社，2001.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文