導語：物流配送途徑優化問題研討一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

1.前言

1.1問題描述與研究意義

物流配送運輸指的是短途運輸，適合多客戶、小批量的貨物運輸。雖然配送路線比較固定，但由于同一路線往返次數較多，即使一次節約的費用不多，但由于運輸次數多，總費用也能降低很多，所以合理的規劃配送路線對運輸成本的影響較大。在物流配送中存在多種優化策略，但是車輛配送路徑優化問題是其中較關鍵的一個，選擇合理有效的車輛路徑方案，盡量減少車輛的配送里程數，有利于節約時間和運輸成本。

1.2本文主要工作

物流配送的一個重要方面是，力爭實現車輛行駛里程最短、運輸總費用最低等目標。針對車輛路徑優化這一典型的NP難題，本文運用遺傳算法來求解該問題的最優解。本文使用圖和邊來表示路徑問題，任意邊的權重為兩個端點的歐幾里得距離。圖中的結點代表城市，用數字1到n編號，d(Ci,Ci+1)表示城市Ci到城市Ci+1的距離，其中Ci、Ci+1坐標分別為(xi,yi)，(xi+1,yi+1)。另外數字0代表配送中心的出發點C。物流配送的路徑問題就是搜索整數子集x={0,1,2,3,…,n}的一個排列{C,C1,C2,C3,…,Cn}，需要使目標函數總路徑距離dis（C）取最小值。其中，dis（C）=d(C,Ci)+∑i=1n-1d(Ci,Ci+1)+d(C,Cn)d(Ci,Ci+1)=(xi-xi+1)2-(yi-yi+1)2。

2.遺傳算法基本原理概述

遺傳算法（GA—GeneticAlgorithm）是模擬生物自然選擇和遺傳學機理的生物進化過程的計算模型，按照“優勝劣汰，適者生存”的原則對目標函數進行優化。經過多次迭代計算，得到最優結果。它最初由美國Michigan大學J.Holland教授于1975年提出來。GA涉及到五大要素：編碼、初始種群的設定、適應度函數的設計、遺傳操作的設計和控制參數的設計。五大要素中最重要的是參數編碼和遺傳操作的設計。參數編碼決定了算法的計算效率，遺傳操作決定了算法的優化成功與否。遺傳操作主要由三部分組成：選擇(selection)、交叉(crossover)和變異(mutation)。

2.1編碼

經典GA編碼多采用二進制表示形式。另外，在實際應用中還有多種編碼形式：動態參數編碼、實數編碼、整數和字母排列編碼等。

2.2初始種群的設定

初始種群的設定是由于GA的群體型操作需要。為遺傳操作準備一個由若干初始解組成的初始群體。通常初始種群采用隨機生成的形式，數量一般要根據染色體的長度而定。

2.3適應度函數的設計

GA在搜索進化過程中用評估函數值來評估個體或解的優劣，并作為以后遺傳操作的依據。評估函數值又稱為適應度(fitness)。因此，適應度函數就是我們要優化的指標函數。

2.4遺傳操作的設計

①選擇選擇提供了GA的驅動力。主要的選擇方式有：適應值比例選擇、聯賽選擇、精英選擇等。適應值比例選擇是最基本的選擇方法，其中每個個體被選擇的期望數量與其適應值和群體平均適應值的比例有關，通常采用輪盤賭的方式實現。這種方式首先計算每個個體的適應值，然后計算出此適應值在群體適應值總和中所占的比例，表示該個體在選擇過程中的概率。②交叉操作交叉操作是GA具備的原始性的獨有特征，是模仿自然界有性繁殖的基因重組過程，其作用在于將原有的優良基因模式遺傳給下一代個體，并生成包含更復雜基因結構的新個體。③變異操作變異操作模擬自然界生物進化中染色體上某一位基因發生的突變現象，從而改變了染色體的結構和物理性狀。在GA中，變異算子通過按變異概率，隨機反轉某一位等位基因的二進制字符值來實現。

2.5控制參數的設計

①交叉概率一般在0.7～0.85之間，通常用Pc表示。主要的交叉方法有：單點交叉、多點交叉、均勻交叉、洗牌交叉等。單點交叉的染色體長n時，可能有n-1個不同的交叉。交叉的過程分為兩步：隨機產生交叉點；對匹配的位串進行交叉繁殖，產生新位串。②變異概率一般在0.001～0.1之間，通常用Pm表示。變異是防止因過渡成熟而丟失重要信息的保險策略，可起到恢復位串字符多樣性的作用，并可以適當提高GA的搜索效率。

2.6GA的運行過程

GA的運行過程是一個迭代過程，其必須完成的工作內容的基本步驟如下：

(1)選擇編碼策略；

(2)定義適應度函數f(x)；

(3)參數初始化，包括選擇群體大小，迭代次數，確定選擇、交叉、變異方法，以及確定交叉概率Pc、變異概率Pm等遺傳參數；

(4)隨機初始化生成群體P；

(5)計算群體中個體解碼后的適應度f(x)；

(6)按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代，保留最好解；

(7)迭代，判斷群體性能是否滿足指標或達到迭代次數，不滿足則返回(6)；滿足則轉到(8)；

(8)獲得最優解，計算結束。

3.GA在物流配送路徑問題中的應用

3.1編碼策略

用GA求解物流配送的路徑問題，編碼的方式很重要。這里采用自然數編碼的方法，即直接采用城市在路徑中的位置來表示，例如有六個城市，配送順序為：0-2-4-5-6-1-3-0，編碼表示成()，其表示的一條配送路線，是從配送中心出發，依次經過城市2、4、5、6、1、3，最后回到配送中心。這種編碼方法自然、直觀，路徑表示易于加入啟發式信息，便于遺傳交叉操作。在保證較好性能的同時，還可以簡化找出最優染色體后解碼的過程，減小計算量。

3.2確定適應度函數

為了將解物流配送的路徑問題空間轉到GA空間中，首先要確定適應度函數，將一個合法的城市序列S=（C,C1,C2,C3,…,Cn,C）作為一個個體。這個序列中相鄰兩城之間的距離的總和的倒數就可作為相應個體S的適應度，適應度函數為f(S)=1dis(C)。

3.3選擇算子

使用輪盤賭選擇法，定義某一染色體被選中的概率Pc（選擇概率）為Pc=f(xi)/∑f(xi)。式中xi為種群中第i個染色體對應的數字串，f(xi)是第i個染色體的適應度值，∑f(xi)是種群中所有染色體的適應度值之和。在GA中，整個群體被各個個體所分割，各個個體的適應度占全部個體的適應度值總和的比例大小不一，以比例分配整個賭盤盤面，盤面大小代表個體下一代群體遺傳上一代各個個體的概率。在輪盤賭選擇方法中，個體適應度高低按比例轉化為選中概率，適應度低的個體就可能被淘汰，而適應度高的個體被選中的幾率就大。

3.4交叉策略

本文使用單點交叉操作。例如：設城市數目為5，設種群里的其中兩個個體：P1=0123450，P2=0152430，如圖1所示（兩點間的數值為距離）。它們產生的子代分別是C1和C2。首先隨機選擇一個交叉位，接著父代各自保留左邊的部分，右邊的部分交換，則產生了兩個子代。若有重復的基因（最后一位除外），那么要進行修正。例如選擇第四位，C1''''=0123430，C2''''=0152450，修正后分別為C1=0125430，C2=0132450。3.5變異策略這里采用換位變異操作，隨機選擇兩個城市（配送中心除外），然后把這兩個城市進行換位。例如：對于個體(0123450)，若隨機選擇城市1和城市4，則換位后的新個體為（0423150）。3.6初始化設種群大小N=50，交叉概率Pc=0.9，變異概率Pm=0.1，迭代次數T=100。3.7算法的步驟step1：讀入城市的坐標數據以及控制參數種群規模N和終止的迭代次數T；step2：計算城市間的距離，形成一個城市距離二維矩陣dn×n；step3：隨機生成初始種群，N個個體分別為：S1{C,C1'''',C2'''',C3'''',…,Cn'''',C}，S2{C,C1'''''''',C2'''''''',C3'''''''',…,Cn'''''''',C}，S3{C,C1'''''''''''',C2'''''''''''',C3'''''''''''',…,Cn'''''''''''',C}……計算各個體的適應度，f(Si)=1dis(Ci)（i=1,2,3,…,N），將個體按照適應度降序排列。初始化終止進化代數計數器t=0；step4：根據交叉概率Pc，選擇父代進行交叉操作以及按變異概率Pm，隨機抽取個體進行變異操作，產生下一代種群，并計算出其個體的適應度，保留當前代最好解；step5：終止進化代數計數器t加1；如果t小于T，轉step4；如果t大于T，停止迭代，轉step6；step6：在當前種群中獲得該問題的最優解，計算結束。

4.數據實驗

4.1實驗環境

CPU：IntelCoreT64002.0G；內存：2G；操作系統：WindowsXPSP3；編譯工具：MicrosoftVisualC++6.0。

4.2實驗數據該實驗中，各控制參數分別為：種群大小N=50，交叉概率Pc=0.9，變異概率Pm=0.1，迭代次數T=100。上面的實驗截圖，表示從第1至第100代的運行結果，每一代中的50個個體的行車路線以及各自的總路徑距離。

4.3實驗分析經過多次實驗發現，本文的實驗數據再迭代40次左右，結果就趨于穩定，達到最優解。

5.結束語

本文運用了遺傳算法來求解物流配送路徑優化問題，進行了遺傳算法的設計、編程和數據仿真研究等，經多次實驗測試，計算得出了實際問題的最優解，且效率比較高，說明遺傳算法是求解路徑優化問題的一種有效方法。