基于遺傳算法的運輸路徑選擇問題

王榮 檀小璐

摘要：近年來，車輛路徑問題一直作為物流配送領域研究中的熱門話題，由于運輸路徑選取的不同，直接決定了物流配送問題中運輸成本的差異，企業的管理者積極尋找著各種有效的配送策略。本文分析了車輛路徑問題的實際背景，設計并實現了一個基于遺傳算法的車輛路徑問題的求解方法。

關鍵詞：遺傳算法；路徑選擇1VRP問題描述

物流配送車輛問題歸納為一般的網絡模型：設G=(V，E，A)是一個連通的混合網絡，V是頂點集(表示物流公司、客戶等)，E、A分別為無向的邊集和有向的弧集，E中的邊和A中的弧均被賦權(可以表示配送的距離、時問或費用)，V、E、A分別為V、E、A的子集，求滿足約束條件(包括客戶的貨物需求或供應數量約束、需求或供應時間約束、配送車輛一次配送的最大行駛距離約束、車輛的最大載重約束等)，并包含V、E、A的一些巡回路線，使目標函數取得優化，目標函數可以取配送總里程最短、配送車輛總噸位公里數最少、配送總費用最低、配送總時間最少、使用的配送車輛最少、配送車輛的滿載率最高等。

2VRP問題的界定

一個物流公司向多個客戶送貨；物流公司和客戶的位置一定；物流公司運送的貨物能夠達到所有客戶的需求。各個客戶需求的貨物均可以相互混裝，即可以裝在同一配送車輛內；每個客戶的需求量不超過配送車輛的最大載重量；每個客戶的送貨要求必須滿足，且僅能一次性完成，不允許分批配送。每臺車輛的最大載重量一定，不允許超載；配送時，每臺車輛都從物流公司出發，向一些客戶提供配送服務后，最終返回物流公司。對于客戶要求將需求貨物送到的時間，無時間限制。物流中心與客戶之間以及客戶相互之間的最短距離已知且固定；不考慮運輸網絡中車輛流量的限制。

3VRP問題的數學建模

設配送中心用K輛車對所有需求點進行配送(K的值由算法動態決定)。每個車的載重為bk(k=1,2,3…K)，每個需求點的需求量為di(i=1,2,3…L)，L為需求點的個數。需求點i到j的距離為Cij。設nk為第k輛車要負責運送的需求點總數，用集合Rk={rki|0≤i≤nk|}來對應第k輛車要送貨的需求點，rki表示第k輛車要送達的第i個需求點，rko表示第k輛車起始點。數學建模：

歸結出有約束條件的最優化問題：

上述表達式中，(1)式為所有需求點都應得到配送；不等式(2)為每條路徑的需求量不超過配送車輛的載重量：不等式(3)為每個車輛對應的需求點總和不大于總的需求點數；(4)式為每需求點只有一輛車進行配送。

4VRP問題的遺傳算法設計

從上述模型可知，求解VRP問題的關鍵是合理確定車輛與各需求點的關系，在滿足車輛載重和各需求點的約束條件的情況下使得總路徑成本最小，因此可以構造以下遺傳算法：

(1)染色體結構編碼二進制字符集{0,1}產生通常的0,1字符串來表示問題空間的候選解。用矢量(s1,s2,…sL)表示一個染色體(也稱個體)G，其中sj的取值范圍為[1,L]中任一個自然數，sj表示第j個被考慮的需求點。每個染色體G是1到L之間L個不重復自然數的一組隨機排列。隨機產生這樣一組染色體Gm(m=1,2,…,M)(其中M為一代種群中的個體數)，構成初始種群。

(2)可行化過程 將染色體的編碼向量映射為滿足全部約束條件的可行解的過程稱為可行化。在VRP問題中，可行化就是將編碼的個體映射為一組可行的路徑選擇方案。過程設計如下：

(a)令車輛的初始剩余裝載量

(b)考慮第j個基因sj對應的需求點，令k=1即從第一輛車開始考慮；

(c)若sj對應的需求點的待運貨物重量 ，則令；如果 ，則令K=k；否則K不變，轉5；如果 ，轉(d)。

(d)令k=k+1，即考慮下一輛車是否能裝載，轉(c)。

(e)令j=j+1，即考慮下一個需求點，轉(b)，重復上面的過程，直到j=L。

(f)此時K記錄了所用車輛總數，即路徑總數，Rk包含了第k條路徑中依次配送的需求點，即Rk(k=1,2,…K)記錄了一組可行的路徑。

(3)適應度分析 初始種群形成以后，霈要通過種群的適應度函數，對種群中的每個染色體進行評價，并以此為標準選擇最優解。對某一代種群中每個染色體Gh(s1,s2,…sL)，將可行化路徑帶入目標函數：

將得到該個體對應的路徑代價。路徑代價越小，表示該染色體越優。令Gh的適應度函數為fk=1/Zh，fk表示染色體在生命競爭中的能力，fk越大對應的個體越接近最優解。

(4)判斷停止條件 當迭代搜索的次數滿足要求的代數N，則停止，選出該代種群中適應度最優的個體，將其對應的可行路徑集合作為該VRP問題的優化解輸出；反之，繼續進行(5)。

(5)自然選擇 將一代種群中M個個體按適應度fk由大到小排列。排在最先的直接進入下一代，而下代中另外M-1個個體從前代種群M個染色體中采用輪轉法選取，即按以下概率選擇個體Gh進入下一代： ，其中， 共選擇M-1次。用輪轉選擇法，既保證了最優個體進入下一代，又避免個體間因適應度大小不同而被選擇進入下一代機會相差懸殊，保證了下一代的多樣性并提高了算法的收斂速度。

(6)交叉操作 交叉概率PC控制著交叉操作被使用的頻度。交叉概率PC在0.6--0.8之間時，進化性能較好，選擇交叉概率為 PC=0.7，并引入一種新穎的交叉算子，這種交叉算子的最大特點是當兩父代相同時，仍能產生全新的兩個個體，這就減弱了對群體多樣性的要求，能夠有效避免傳統遺傳算法“早熟收斂”的缺點。

任意選取兩個互不相同的個體A和B，設每個染色體含有n個基因，隨機產生1--n之間的兩個不等的整數S和 ，將染色體A和B同樣分成三個部分，其中1→s-1為第一部分，s→ι為第二部分，ι+1→n為第三部分。將A的第三部分移到B的個體首部，并除去B中相同的基因，得到新的個體B'；同時將原B中的第一部分移到A的尾部，并將于A中相同的基因除去，便得到一個新的個體A'。交叉后分別計算個體A'、B'和A、B的適應度，選取適應度最大的兩個個體進入下一代。采用新的交叉算子，當個體都相同時仍能夠進行迭代進化，繼續尋找問題的最優解，避免陷入局部最優解，克服了“早熟收斂”的缺點。

(7)變異操作 主要目的是維持解群體的多樣性。低頻度的變異可防止群體中重要的、單一基因的可能丟失，高頻度的變異將使遺傳算法趨于純粹的隨機搜索。變異概率Pm為0.02左右。變異策略是隨機變換選中的一個染色體中任意兩個基因值。對變異后的個體產生對應的可行路徑并計算適應度，將其適應度與變異前個體進行比較，擇優進入下一代。返回(3)、(4)步重復以上循環，直到滿足終止條件。

根據上一節對VRP問題遺傳算法的設計，對實現的各個步驟進行抽象提取，共構造了12個函數，包括：newcode()(生成隨機個體)、initGA()(產生初始種群)、avFitness()(平均適應度函數)、natureChek()(自然選擇函數)、crossover()(交叉操作)、mutation()(變異操作)等等，使用純java編寫代碼，完成了設計的每一步操作函數。為了減少系統中的耦合性，在實現中采用EJB對路徑選擇算法進行模塊封裝，該模塊封裝了多個函數的調用關系，留給客戶的只有一個輸入接口，客戶可以通過用戶界面對系統參數進行設置，包括：種群大小M、遺傳搜索的代數N、變異概率Pm，交叉概率Pc等，確認輸入后，系統開始對用戶選擇的訂單(含配送要求)進行處理，并自動讀取數據庫中的路徑關系表，最后得出一個優化后的配送方案。

[參考文獻]

[1]李敏強.遺傳算法的基本理論與應用[M].科學出版社,2002.