導(dǎo)語：物流配送途徑優(yōu)化問題研討一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

1.前言

1.1問題描述與研究意義

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

1.2本文主要工作

物流配送的一個(gè)重要方面是，力爭(zhēng)實(shí)現(xiàn)車輛行駛里程最短、運(yùn)輸總費(fèi)用最低等目標(biāo)。針對(duì)車輛路徑優(yōu)化這一典型的NP難題，本文運(yùn)用遺傳算法來求解該問題的最優(yōu)解。本文使用圖和邊來表示路徑問題，任意邊的權(quán)重為兩個(gè)端點(diǎn)的歐幾里得距離。圖中的結(jié)點(diǎn)代表城市，用數(shù)字1到n編號(hào)，d(Ci,Ci+1)表示城市Ci到城市Ci+1的距離，其中Ci、Ci+1坐標(biāo)分別為(xi,yi)，(xi+1,yi+1)。另外數(shù)字0代表配送中心的出發(fā)點(diǎn)C。物流配送的路徑問題就是搜索整數(shù)子集x={0,1,2,3,…,n}的一個(gè)排列{C,C1,C2,C3,…,Cn}，需要使目標(biāo)函數(shù)總路徑距離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）是模擬生物自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，按照“優(yōu)勝劣汰，適者生存”的原則對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化。經(jīng)過多次迭代計(jì)算，得到最優(yōu)結(jié)果。它最初由美國Michigan大學(xué)J.Holland教授于1975年提出來。GA涉及到五大要素：編碼、初始種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)計(jì)。五大要素中最重要的是參數(shù)編碼和遺傳操作的設(shè)計(jì)。參數(shù)編碼決定了算法的計(jì)算效率，遺傳操作決定了算法的優(yōu)化成功與否。遺傳操作主要由三部分組成：選擇(selection)、交叉(crossover)和變異(mutation)。

2.1編碼

經(jīng)典GA編碼多采用二進(jìn)制表示形式。另外，在實(shí)際應(yīng)用中還有多種編碼形式：動(dòng)態(tài)參數(shù)編碼、實(shí)數(shù)編碼、整數(shù)和字母排列編碼等。

2.2初始種群的設(shè)定

初始種群的設(shè)定是由于GA的群體型操作需要。為遺傳操作準(zhǔn)備一個(gè)由若干初始解組成的初始群體。通常初始種群采用隨機(jī)生成的形式，數(shù)量一般要根據(jù)染色體的長(zhǎng)度而定。

2.3適應(yīng)度函數(shù)的設(shè)計(jì)

GA在搜索進(jìn)化過程中用評(píng)估函數(shù)值來評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。評(píng)估函數(shù)值又稱為適應(yīng)度(fitness)。因此，適應(yīng)度函數(shù)就是我們要優(yōu)化的指標(biāo)函數(shù)。

2.4遺傳操作的設(shè)計(jì)

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

2.5控制參數(shù)的設(shè)計(jì)

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

2.6GA的運(yùn)行過程

GA的運(yùn)行過程是一個(gè)迭代過程，其必須完成的工作內(nèi)容的基本步驟如下：

(1)選擇編碼策略；

(2)定義適應(yīng)度函數(shù)f(x)；

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

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

(5)計(jì)算群體中個(gè)體解碼后的適應(yīng)度f(x)；

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

(7)迭代，判斷群體性能是否滿足指標(biāo)或達(dá)到迭代次數(shù)，不滿足則返回(6)；滿足則轉(zhuǎn)到(8)；

(8)獲得最優(yōu)解，計(jì)算結(jié)束。

3.GA在物流配送路徑問題中的應(yīng)用

3.1編碼策略

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

3.2確定適應(yīng)度函數(shù)

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

3.3選擇算子

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

3.4交叉策略

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

4.數(shù)據(jù)實(shí)驗(yàn)

4.1實(shí)驗(yàn)環(huán)境

CPU：IntelCoreT64002.0G；內(nèi)存：2G；操作系統(tǒng)：WindowsXPSP3；編譯工具：MicrosoftVisualC++6.0。

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

4.3實(shí)驗(yàn)分析經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)，本文的實(shí)驗(yàn)數(shù)據(jù)再迭代40次左右，結(jié)果就趨于穩(wěn)定，達(dá)到最優(yōu)解。

5.結(jié)束語

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