沈 澄，方 偉

（1.浙江工商職業(yè)技術(shù)學(xué)院，浙江 寧波 315012；2.寧波永耀信息科技有限公司，浙江 寧波 315020）

數(shù)學(xué)建模優(yōu)化物流運輸路徑可行解的改進(jìn)算法及其應(yīng)用

沈 澄1，方 偉2

（1.浙江工商職業(yè)技術(shù)學(xué)院，浙江 寧波 315012；2.寧波永耀信息科技有限公司，浙江 寧波 315020）

針對帶時間窗物流運輸最優(yōu)化路徑選擇問題，基于概率分布算理的共同機制，將遺傳算法全局搜索優(yōu)勢與模擬退火算法局部搜索優(yōu)勢有機整合，有效規(guī)避二者算法尋優(yōu)性能的不足，使構(gòu)建的改進(jìn)算法兼顧優(yōu)越的全局搜優(yōu)能力和計算效率。針對9個目標(biāo)點物流運輸路徑優(yōu)化問題的可行解，展開算法應(yīng)用的試驗驗證。結(jié)果顯示，若目標(biāo)點數(shù)量較少能夠求得最優(yōu)解，若目標(biāo)點數(shù)量較多則能夠求得滿意解。

物流運輸；路徑優(yōu)化；目標(biāo)函數(shù)；最優(yōu)解；適應(yīng)度；可行解

1 引言

在物流運輸業(yè)中存在許多優(yōu)化策略問題，運輸路徑的優(yōu)化作為NP-C問題，計算復(fù)雜性很高，難以通過全局搜索實現(xiàn)最優(yōu)化求解[1]。眾所周知，遺傳算法（GA）具有突出的全局搜索能力，但在實際運用中時常早熟收斂，后期搜索效率不高，為此許多學(xué)者采用蟻群算法、粒子群算法等對遺傳算法進(jìn)行混合改進(jìn)，取得了較好的尋優(yōu)效果。模擬退火算法（SA）具有優(yōu)秀的局部搜索能力，本文根據(jù)物流運輸?shù)奶攸c，建立相應(yīng)的數(shù)學(xué)模型，將模擬退火算法置入遺傳算法，優(yōu)化改進(jìn)遺傳算法，并展開算法應(yīng)用的試驗驗證。

2 問題描述與數(shù)學(xué)模型建立

將貨物從集散中心配送到多個目標(biāo)，先要確定每個目標(biāo)的位置和需求量、選擇最優(yōu)配送路徑，達(dá)到運輸效率高、成本最低，還需滿足[1-2]：①每條線路的貨運量不得超出運輸車輛的裝載量；②每條線路目標(biāo)點的需求必須滿足，且僅由一輛車在限定時間內(nèi)送貨；③每一運輸車輛自集散中心出發(fā)，均必須在限定時間內(nèi)返回集散中心。為此設(shè)該運輸系統(tǒng)中的目標(biāo)點集合i=0表示集散中心，車輛數(shù)集合，引入決策變量，，其中i,j∈N,i≠j,k∈H。假設(shè)每條配送路徑對應(yīng)一輛貨車，且一輛貨車可以滿足這條線路上目標(biāo)點的配送要求，每一目標(biāo)僅由單一車輛完成一次配送，建立數(shù)學(xué)模型的相關(guān)參數(shù)見表1。

表1 物流運輸路徑優(yōu)化的數(shù)學(xué)模型參數(shù)

那么，目標(biāo)函數(shù)[2-3]：

模型中（1）為目標(biāo)函數(shù)，（2）至（12）為約束條件。（2）規(guī)定集散中心是運輸車輛的起點與終點；（3）規(guī)定派出的車輛數(shù)不超過擁有的車輛數(shù)；（4）規(guī)定車輛不能從本地到本地；（5）規(guī)定車輛路徑連續(xù)約束；（6）和（7）規(guī)定每一目標(biāo)點恰好被一輛車服務(wù)一次；（8）規(guī)定每一路徑貨運總量的車載重約束；（9）規(guī)定車輛運輸準(zhǔn)時的時間約束；（10）至（12）為時間窗約束。

3 改進(jìn)算法的分析與實現(xiàn)

3.1 模擬退火算法（SA）

該算法來自熱力學(xué)中的固體退火原理，固體加熱溫度至充分高，其內(nèi)能增大，而冷卻過程在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。N.Metropolis于1953年提出，用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)f，溫度T演化成控制參數(shù)t，由初始解s和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，當(dāng)溫度終止在低溫時內(nèi)能極小，即目標(biāo)函數(shù)值最小，此時算法終止的當(dāng)前解即為近似最優(yōu)解。

這是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，搜優(yōu)過程隨著溫度的不斷下降，賦予一種時變且最終趨于零的概率突跳性，在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解，具有跳出局部最優(yōu)陷阱的能力，隨著溫度的不斷下降至最低溫度，搜索過程以概率l收斂于最優(yōu)解，即在局部的最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)，具有概率的全局優(yōu)化性能。

設(shè)目標(biāo)函數(shù)為min f(Si)，Si∈S，S是離散有限狀態(tài)空間（即可行解集合），求解過程如下：

（1）初始化，任選初始解Si∈S，給定初始溫度T0足夠高，終止溫度Tf足夠低，令迭代計數(shù)器k=0，Tk=T0。

（2）隨機產(chǎn)生一個鄰域解，Sj∈N(Si)，N(Si)表示Si的鄰域，計算目標(biāo)值增量，Δf=f(Sj)-f(Si)。

（3）若Δf<0，令Sj=Si轉(zhuǎn)到第四步，否則產(chǎn)生一個隨機數(shù)ξ∈U(0，1)，若exp(-Δf/Tk)>ξ，則令Sj=Si。

（4）若達(dá)到熱平衡轉(zhuǎn)到第五步，否則轉(zhuǎn)到第二步。

（5）k=k+1降低Tk，若Tk

3.2 遺傳算法（GA）

該算法1975年由美國J.Holland教授提出，它是借鑒生物界適者生存的遺傳機制形成的隨機搜索最優(yōu)解的方法。該算法采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力，可使問題的解一代又一代地優(yōu)化逼近最優(yōu)解。GA應(yīng)用遺傳算子經(jīng)選擇、交叉、變異運算，模擬生物種群自然選擇、優(yōu)勝劣汰、不斷進(jìn)化的規(guī)律，逐代產(chǎn)生出代表新的解集的種群，后生代種群比前代更加適應(yīng)環(huán)境，解碼末代種群的最優(yōu)個體作為近似最優(yōu)解。求解過程如下：

（1）初始化求解空間。設(shè)進(jìn)化代數(shù)計數(shù)器k=0，最大進(jìn)化代數(shù)K，隨機生成M個個體作為初始種群的染色體并進(jìn)行編碼。

（3）個體評價。計算適應(yīng)度函數(shù)Fit(Si)的值,即當(dāng)前種群Z(k)中各Si的適應(yīng)度。

（4）遺傳算子操作。經(jīng)過選擇、交叉、變異運算生成子代種群Z(k+1)。

（5）終止條件判斷。若k=K,則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解輸出；否則返回第三步。

選擇算子選擇Fit(Si)值較大的個體提高個體被復(fù)制的概率，促進(jìn)算法收斂速度加快，優(yōu)秀個體Si被選擇的概率為，F(xiàn)iti越大Pi就越大；交叉算子置換兩個父系基因，促進(jìn)算法搜索能力提升，搜索得到更優(yōu)的個體（或解）；當(dāng)交叉運算已接近最優(yōu)解鄰域時，變異算子的局部隨機搜索能力能加速向最優(yōu)解收斂，同時維持群體的多樣性，這有利于促進(jìn)算法規(guī)避局部最優(yōu)。但實際應(yīng)用中遺傳算法在進(jìn)化后期效率不高，容易未成熟收斂，且局部搜索能力較弱，因此有必要引入其他優(yōu)秀算法對遺傳算法進(jìn)行改進(jìn)，實現(xiàn)高效運算、快速搜優(yōu)，防止早熟現(xiàn)象。

3.3 改進(jìn)算法（GA&SA)

GA和SA算法都是基于概率分布機制的優(yōu)化算法，具有算法理論的共同契機，改進(jìn)算法是將模擬退火算法設(shè)置為一個獨立的算子，置入遺傳算法中，對選擇、交叉、變異操作生成的每一個新個體獨立進(jìn)行模擬退火，經(jīng)模擬退火操作后的個體設(shè)置為子代個體，迭代次數(shù)作為退火時間，迭代直到滿足終止條件求得最優(yōu)解。求解過程如圖1所示[4-5]。

下面針對9個目標(biāo)點的物流運輸路徑優(yōu)化問題的可行解為算例，展開算法的應(yīng)用分析。

（1）染色體編碼。用字符串表示種群的染色體，染色體中的數(shù)字代表目標(biāo)點，基因的順序代表運輸車輛的線路與方向，解表示長度為n的定長整形字符串，n表示被訪問的目標(biāo)點個數(shù)。那么該物流運輸系統(tǒng)可編碼為248517963，要求路徑m的最后目標(biāo)點和路徑m+1的開始目標(biāo)點連接，按車輛的裝載量劃分線路，解碼時將基因依序插入到新路徑之中，即得到路徑1:0→2→4→8→5→0；路徑2:0→1→7→9→6→3→0，能使得路徑數(shù)量最少便可實現(xiàn)運輸成本最低。

（2）生成初始種群。隨機產(chǎn)生1至n這n個自然數(shù)的不重復(fù)排列，作為該運輸路徑種群的個體[6]，依據(jù)數(shù)學(xué)建模的約束條件，在運輸系統(tǒng)中設(shè)定最低費用的目標(biāo)點，產(chǎn)生的一部分初始可行解記作S0，隨機生成的剩余部分可行解記作S1，S0和S1共同組成初始種群，記種群規(guī)模為M。

（3）確定初始溫度。k取充分大，確定初溫T0=kδ，δ=fmax-fmin，操作中令k=20、80、150、…進(jìn)行試驗，f是初始種群的目標(biāo)函數(shù)。

（4）構(gòu)建適應(yīng)度函數(shù)。適應(yīng)度用于度量個體在優(yōu)化計算中有可能達(dá)到或有助于找到最優(yōu)解的優(yōu)良程度，直接關(guān)系到父代中的優(yōu)秀基因如何遺傳到子代種群。適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成，構(gòu)建時要考慮具備單值、連續(xù)、非負(fù)、最大化的特征，還要考慮計算量小、通用性強、符合問題實際、一致性好的要求[7]。本文根據(jù)研究問題的目標(biāo)函數(shù)，列出全部父代個體的目標(biāo)函數(shù)值按降序排列，設(shè)xi(i=1,2,…,M)表示降序排列后的第i個個體，適應(yīng)度函數(shù)定義為Fit(xi)=1/(a(1-a)i)（0

（5）選擇、交叉與變異操作。選擇操作采用輪盤賭方法，旋轉(zhuǎn)一次即挑選一個優(yōu)質(zhì)個體作為父代個體繁殖到新生種群，選擇準(zhǔn)則是由第四步計算出父代的所有個體xi的適應(yīng)度值以及被選擇的概率，經(jīng)多輪輪盤賭選擇出的個體進(jìn)入后續(xù)的交叉變異操作。

圖1 改進(jìn)算法求解步驟框圖

根據(jù)交叉概率，對種群中的個體隨機兩兩組合，并交換二者的部分基因，二個染色體通過交配重組產(chǎn)生新個體，決定著GA的全局搜索能力。由于物流運輸路徑問題按十進(jìn)制編碼，長度固定排列有序，整數(shù)基因只會出現(xiàn)一次，因此選用部分匹配交叉法，在二個父代染色體中隨機產(chǎn)生兩個交叉點，交叉基因位交換基因碼并繼承基因。

重組過程的染色體編碼中部分基因座的基因值以變異概率變更為該基因座的其他等位基因，從而形成新個體[8]，決定著GA的局部搜索能力。采用倒位變異法，在性質(zhì)相同的編碼中隨機選擇一個子串以變異概率逆向排列生成新個體，這使得染色體在小范圍變化，進(jìn)一步強化了種群的多樣性。變異和交叉相互補充，配合完成全局搜索與局部搜索的最優(yōu)化問題搜優(yōu)。

（6）自適應(yīng)選擇。交叉概率與變異概率的取值極大地影響著GA的運算效果，取值太小產(chǎn)生的新個體就少，抑制早熟的能力就會變差，取值較大，雖能產(chǎn)生較多的新個體，但也有可能破壞優(yōu)良個體。關(guān)于自適應(yīng)性變異概率，采用方差來計算，公式為，其中。如果 λ≥MINPOPDEV=5，那么 Pm=Pmin=0.06；否則Pm=Pmin+0.1×(MINPOPDEV-λ)。在這里自適應(yīng)性變異概率能夠在不成熟收斂與優(yōu)良個體被破壞的二個問題間尋求解決方法[9-10]。

（7）模擬退火局部搜優(yōu)。根據(jù)退溫函數(shù)Tk+1=αTk（0<α<1），對選擇、交叉、變異操作生成的每一個新個體，獨立進(jìn)行模擬退火，并記住優(yōu)秀個體。

（8）復(fù)制新個體。初始種群經(jīng)歷了交叉、變異、退火的過程，基于Metropolis復(fù)制策略，①保留最優(yōu)個體，②在染色體i的鄰域中隨機生成新個體j，優(yōu)勝劣汰決定i 與j誰進(jìn)入子代種群。計算它們的目標(biāo)函數(shù)值，令Δf=f(xj)-f(xi)，如果Δf<0，便接收xj；如果Δf>0，需滿足條件exp(-Δf/Tk)>ξ（ξ是0到1之間的一個隨機數(shù)），方能將xj復(fù)制到子代種群。再求出子代種群目標(biāo)函數(shù)的最小值，便得到運輸路徑最短、成本最低的近似最佳路線，擬作為服務(wù)于全部目標(biāo)點的最佳方案。

（9）算法終止。經(jīng)p代進(jìn)化后，以新生種群中目標(biāo)函數(shù)最小值fmin的變化為判據(jù)，如果連續(xù)q代未出現(xiàn)變化，那么當(dāng)前解為最優(yōu)解輸出。

4 模型檢測與算例驗證

已知該9個目標(biāo)點的物流運輸各配送目的地貨物需求量(mi)噸=（1,2,2,3,3,2,3,4,3），各地間的距離矩陣(dij)公里如圖2，表2為時間窗。

表2 車輛路徑時間窗（時刻）

設(shè)置仿真試驗相關(guān)參數(shù)：M=100，退溫系數(shù)α=0.9，終止條件q=200，h=2，交叉概率 pc=0.9，變異概率Pm=0.06，a=0.01，vh=12×103kg，ui=25min，rh=15min。根據(jù)參數(shù)編程并將數(shù)據(jù)分別錄入三種算法的運行程序，最優(yōu)率為求得最優(yōu)值的次數(shù)占總求解次數(shù)的比例，方差δk=(f(k)-fopt)/fopt，其中 f(k)為最終目標(biāo)函數(shù)值、fopt為最優(yōu)目標(biāo)函數(shù)值，驗證改進(jìn)算法的性能。求解結(jié)果如圖2。

（1）最佳方案。改進(jìn)算法求得四組可行解，運輸路程分別為70.5、69、67、65.5，第四組解比前三組解更滿意，即最佳路徑1：0→2→4→8→5→0的運輸量12t、路程29.5km；路徑2：0→1→7→9→6→3→0的運輸量11t、路程36km。為研究的方便,車輛行駛的單位路程與所需的單位成本在數(shù)值上可視為一致，那么該運輸方案的總費用為65.5單位成本，因此最佳方案的路徑最短、成本最低、車輛的裝載量得到了最大限度的使用。

（2）性能分析。相同條件下三種算法GA&SA、GA、SA獲得的最優(yōu)率分別為96%、85%、74%，方差分別為1.3、6.1、5.6，可見GA&SA的最優(yōu)率最高、方差最?。籗A的解比GA的解分布較均勻，但SA的計算時間較長，求得的最優(yōu)解比GA較好，然而GA的最優(yōu)率遠(yuǎn)遠(yuǎn)高于SA，說明GA的全局搜索性能優(yōu)于SA，SA的局部搜索性能優(yōu)于GA，改進(jìn)的GA&SA擁有最佳性能，計算最優(yōu)解的能力明顯優(yōu)于兩者。

（3）算法優(yōu)勢。遺傳算法的早熟現(xiàn)象是因為種群陷入局部最優(yōu)而喪失了群體的多樣性，退火策略直接對所選個體實施交叉、變異后的退火操作，隨著迭代次數(shù)的增加，推進(jìn)局部最優(yōu)點趨于全局最優(yōu)點。因此改進(jìn)算法GA&SA改善了遺傳算法的全局收斂性，提高了算法的收斂速度，強化了全局與局部兩種環(huán)境下的搜索能力，全面優(yōu)化了搜優(yōu)功能。

5 結(jié)語

建立數(shù)學(xué)模型優(yōu)化物流運輸路徑是現(xiàn)代科學(xué)發(fā)展帶給物流技術(shù)的一大便利，本文針對帶時間窗物流運輸最優(yōu)化路徑的選擇問題，將遺傳算法全局搜索的優(yōu)勢和模擬退火算法局部搜索的優(yōu)勢進(jìn)行有機整合，有效規(guī)避了二者算法尋優(yōu)性能的不足，使得改進(jìn)的GA&SA兼顧了全局尋優(yōu)能力和計算效率。若目標(biāo)點數(shù)量較少能夠求得最優(yōu)解，若目標(biāo)點數(shù)量較多則能夠求得滿意解。傳統(tǒng)算法受諸多因素限制，獲得的運輸方案不夠經(jīng)濟，憑借經(jīng)驗嘗試調(diào)整運輸車輛的數(shù)量以獲得較為合理的安排方案，但欠缺科學(xué)依據(jù)，改進(jìn)的GA&SA算法為解決物流運輸優(yōu)化方案提供了有力的技術(shù)支持。

[1]張維澤,林劍波,吳洪森,等.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化[J].浙江大學(xué)學(xué)報(工學(xué)版),2008,(4):574-578

[2]李珍萍，周文峰.物流配送中心選址與路徑優(yōu)化問題—建模與求解[M].北京:機械工業(yè)出版社,2014.

[3]吳燁.物流配送網(wǎng)絡(luò)選址的模糊數(shù)學(xué)模型及其算法[J].經(jīng)濟數(shù)學(xué),2008,(3):277-282.

[4]羅耀波,孫延明,劉小龍.多約束選址—路徑問題的改進(jìn)混合遺傳算法研究[J].計算機應(yīng)用研究,2013,(8):2 283-2 287.

[5]吳燁，李應(yīng)逑.供應(yīng)鏈中物流配送的數(shù)學(xué)模型及其混合蟻群算法[J].經(jīng)濟數(shù)學(xué),2007,(4):398-401.

[6]王旭升，尤小霞.基于混合遺傳算法的物流配送路徑分析[J].物流技術(shù),2014,(3):269-271.

[7]張全生.基于聚類-遺傳混合算法的物流配送路徑優(yōu)化研究[D].淮南:安徽理工大學(xué),2011.

[8]鐘惟鈺.遺傳算法在物流配送運輸車輛路徑優(yōu)化中的應(yīng)用與改進(jìn)[J].物流技術(shù),2014,(5):323-325.

[9]孫君.應(yīng)急物流能力優(yōu)化研究[M].北京:科學(xué)出版社,2015.

[10]Lan H C W,Chen T M,Tsui W T,Pang W K.Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem[J].Automation Science and Engineering,IEEE,2010,7(2): 383-392.

M athematical Modeling and Im proved A lgorithm for Feasible Solution of Logistics Transportation Route Model and Its App lication

Shen Cheng1,FangWei2
(1.ZhejiangBusiness Technology Institute,Ningbo 315012;2.Ningbo Yongyao Information TechnologyCo.,Ltd.,Ningbo 315020,China)

In this paper,in view of the logistics transportation route optimization problem with time window and based on the common mechanism of the probabilistic distribution principle,we integrated the genetic algorithm with the strength of global searching and the simulated annealing algorithm which exceled in local searching and then in the numerical example of a logistics transportation route problem withninedestination points,demonstrated and validated thealgorithm.

logistics transportation;routeoptimization;objective function;optimalsolution;degreeof fitness;feasiblesolution

F224.0;F512.6

A

1005-152X(2017)05-0103-05

10.3969/j.issn.1005-152X.2017.05.023

2017-04-05

沈澄（1963-），女，浙江工商職業(yè)技術(shù)學(xué)院副教授，主要研究方向：數(shù)學(xué)課程教育與應(yīng)用數(shù)學(xué)；方偉（1963-），男，寧波永耀信息科技有限公司工程師，主要研究方向：信息技術(shù)管理與計算機編程應(yīng)用。