數學建模優化物流運輸路徑可行解的改進算法及其應用

沈 澄，方 偉

（1.浙江工商職業技術學院，浙江 寧波 315012；2.寧波永耀信息科技有限公司，浙江 寧波 315020）

數學建模優化物流運輸路徑可行解的改進算法及其應用

沈 澄1，方 偉2

（1.浙江工商職業技術學院，浙江 寧波 315012；2.寧波永耀信息科技有限公司，浙江 寧波 315020）

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

物流運輸；路徑優化；目標函數；最優解；適應度；可行解

1 引言

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

2 問題描述與數學模型建立

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

表1 物流運輸路徑優化的數學模型參數

那么，目標函數[2-3]：

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

3 改進算法的分析與實現

3.1 模擬退火算法（SA）

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

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

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

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

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

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

（4）若達到熱平衡轉到第五步，否則轉到第二步。

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

3.2 遺傳算法（GA）

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

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

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

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

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

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

3.3 改進算法（GA&SA)

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

下面針對9個目標點的物流運輸路徑優化問題的可行解為算例，展開算法的應用分析。

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

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

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

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

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

圖1 改進算法求解步驟框圖

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

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

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

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

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

（9）算法終止。經p代進化后，以新生種群中目標函數最小值fmin的變化為判據，如果連續q代未出現變化，那么當前解為最優解輸出。

4 模型檢測與算例驗證

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

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

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

（1）最佳方案。改進算法求得四組可行解，運輸路程分別為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。為研究的方便,車輛行駛的單位路程與所需的單位成本在數值上可視為一致，那么該運輸方案的總費用為65.5單位成本，因此最佳方案的路徑最短、成本最低、車輛的裝載量得到了最大限度的使用。

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

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

5 結語

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

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

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

[3]吳燁.物流配送網絡選址的模糊數學模型及其算法[J].經濟數學,2008,(3):277-282.

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

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

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

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

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

[9]孫君.應急物流能力優化研究[M].北京:科學出版社,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-），女，浙江工商職業技術學院副教授，主要研究方向：數學課程教育與應用數學；方偉（1963-），男，寧波永耀信息科技有限公司工程師，主要研究方向：信息技術管理與計算機編程應用。