基于改進差分進化算法的多重交通網絡運輸調度問題研究

徐釗

摘要：文章認為多重交通網絡運輸調度問題就是在特定的約束條件下允許采用不同交通運輸工具的組合，差分進化算法以其自身的智能算法優勢在解決這個問題時具有獨特優勢。然而這種算法在解決多重交通網絡運輸調度問題時容易陷入局部搜索困局，采用構造梯度算子可解決這一不足，并通過實例證明了這種改進算法是可行的。

關鍵詞：多重交通網絡;差分進化算法;梯度算子;遺傳算法

中圖分類號：U491 文獻標識碼：A DOI：10.13282/j.cnki.wccst.2019.10.043

文章編號：1673-4874（2019）10-0156-03

0引言

隨著我國經濟的快速發展，我國的公路、鐵路、航運以及航空運輸都得到了迅猛發展。隨著市場經濟的開放，我國的交通運輸壓力也隨之增加，在多重交通網絡運輸條件下，如何提高交通運輸的效率以及經濟效益成為了一個難題，并從最初的基本車輛路徑問題上衍生出了多重交通運輸網絡綜合調度問題。

對于這個問題，國內外學者進行了大量研究。文獻基于大量數據分析，研究了在多重交通運輸情況下，最優化線路以及交通運輸方式組合對于提高交通運輸效率和經濟性的必要性。文獻采用數字模擬技術分析了多重交通運輸網絡的優化組合問題。文獻通過借鑒最新數學算法問題對多重運輸網絡調度問題進行了深入的分析和研究。

多重交通網絡問題的優化和組合，其本質就是采用數學計算理論，結合該問題設計的環境污染、經濟效益以及社會影響等因素，為交通運輸選擇經濟性最好且節能環保的綠色運輸組合。對多重交通網絡問題進行研究，并提出最優化運輸組合方式，對我國經濟發展及節能減排具有重大意義。本文基于差分進化算法，對多重交通網絡問題進行了研究，并通過實例進行分析，證明該方法對解決多重交通網絡問題是可行的。

1差分進化算法介紹

差分進化算法是由國外學者Rainer和Kenneth在1997年提出的，是在遺傳算法基礎上進行改進的，其本質就是多目標的優化算法，這種計算方法常用于多維空間最優化問題的求解。

和遺傳算法相比，兩種計算方法共同點都是隨機生成初始的種群，以種群中每個個體的適應度作為選擇標準。這個過程包括選擇、變異以及交叉三個步驟。兩種算法不同之處在于：差分進化算法變異是由父代差分向量產生，和父代的個體進行選擇;而遺傳算法是根據適應度來控制的。差分進化算法相對于遺傳算法逼近目標效果更加有效。

差分進化算法的計算過程如圖1所示。

通過對多重交通網絡的分析，建立交通網絡最優化數學模型，充分利用差分進化算法的優勢，同時考慮對計算結果會產生影響的時間價值以及時間窗口等因素，對最優化組合的交通運輸方式進行分析。通過一個實例的分析驗證，表明差分進化算法能夠有效解決多重交通網絡的組合選擇問題。

2 多重交通運輸網絡問題分析

多重交通運輸網絡問題的本質，就是選擇最優化組合。下面以某鋼鐵企業運輸問題為例進行分析，鋼鐵企業需要將一批貨物從A地運輸到B地。在運輸過程中需要經過m個中轉站，兩個中轉站之間有n種運輸方式可以選擇，每種運輸方式的費用、耗費時間以及運輸能力都是不同的。且從一個運輸方式轉換為另外一種運輸方式需要支付中轉費用以及耗費一定中轉時間。貨物需要在規定的期限內運輸到目的地，如何選擇合理的運輸組合方式，使規定時間內運輸到目的地經濟性最好，這就需要研究多重運輸網絡問題。

在上述約束條件情況下，求出式（1）的最優解，就能解決多重交通運輸網絡問題。下面采用改進差分進化算法，對上述問題進行分析。

3 改進差分進化算法

目前差分進化算法在迭代計算取得某一代種群最優解后，不能充分利用梯度信息進一步進行局部探索最優解，因此傳統差分進化算法局部搜索能力不足。改進差分進化算法基于梯度尋求最優解的思想，通過構造梯度加速算子，提高了差分進化算法的局部搜索能力。為了避免計算過程中出現無效計算，在計算分析時設置一個啟用要求：如果在求解某一代最優解陷入停滯狀態時，啟用附加操作算子，算子設計如下：

參數λ有多種計算方法，如搜索法、試算法以及微分法等。為了提高算法的效率采取了試算，即初始假定一個λ值，然后檢驗判定條件是否成立，如果成立就采用計算步長;如果檢驗條件不滿足，就減小步長迭代計算。

4 算例分析

假定某鋼鐵廠需要將一批鋼材，從場地O運輸到目的地D，運輸過程中需要經過P1、P2、P3、P4中轉城市，在各個點之間交通運輸方式有航空、火車、水運以及輪船四種方式，各種運輸方式的運輸費用F、時間T、能力A如表1所示。

在每個中轉點轉換交通運輸工具，就會涉及到中轉時間和中轉費用，在各個中轉城市之間的中轉時間以及中轉費用如表2所示。

采用改進的差分進化算法對綜合交通運輸方案進行分析，假定需要運輸鋼材800t，根據相關市場調研資料，各參數取值如下：Fmin=0.65、Fmox=0.92、θ=110，每個步驟迭代次數為300次，進行10次迭代計算。計算過程如圖2所示。

通過分析可以看出，最低運輸費用為8192元，各種交通運輸組合方式為起點O→P1→P2→P3采用火車運輸，P3→P4采用汽車運輸，P4→D采用輪船進行運輸。

5 結語

多重交通運輸調度問題其本質就是對于多種交通運輸方式組合的最優化選擇問題，從而使得經濟性和效率達到最優。差分進化算法以其自身全局并行和直接搜索的特點，在解決這個多重交通組合的問題上，比其他智能算法更具有優越性。但是差分進化算法在求解后期，容易陷入局部最優解的求解問題。為了解決這個問題，在既有的差分進化算法基礎上，構造了梯度算子，解決了算法最優化求解問題，提高了計算效率和精度。通過實例分析表明，改進的差分進化算法在解決多重交通運輸調度問題上具有較高的計算速度和準確性。