改進蟻群算法求解多目標校車路徑優(yōu)化問題.pdf

1、隨我國社會經(jīng)濟的發(fā)展，為中小學學生提供校車服務成為教育主管部門和學校面臨的新問題。校車路徑規(guī)劃是校車運營管理中的一個重要環(huán)節(jié)，但路徑規(guī)劃涉及學校、學生、車隊和交通網(wǎng)絡，是一項難度極高的任務。與校車路徑規(guī)劃密切相關的校車路徑問題(SBRP)是在滿足學生交通服務各種約束條件的前提下，尋求最優(yōu)的校車路徑方案，將學生從乘車站點運送到學校，達到一定的服務質(zhì)量目標和校車運營效率目標。
　　針對一個區(qū)域內(nèi)多個學校校車路徑規(guī)劃問題，通常將SBRP

2、分解單校SBRP和校車調(diào)度問題(SBSP)分別進行求解。本文在建立單校SBRP和SBSP數(shù)學模型的基礎上，分別改進蟻群系統(tǒng)算法（ACS）和改進最大最小螞蟻算法（MMAS）進行求解，使用基準案例數(shù)據(jù)集測試算法的性能。主要完成了以下工作：
　　(1)建立了單校SBRP和SBSP數(shù)學模型。
　　由于SBRP屬于車輛路徑問題（VRP）的范疇，本文針對單校 SBRP建立了開放VRP整型線性規(guī)劃數(shù)學模型；SBSP建立了混合整形規(guī)劃數(shù)學模

3、型。
　　(2)針對單校SBRP和SBSP分別設計了改進ACS算法和改進MMAS算法。
　　根據(jù)單校SBRP的特性，在校車容量和學生最大乘車時間約束下，將減少路徑數(shù)量作為第一目標，縮減路徑總長度為第二目標。按照制定的優(yōu)化目標，著重探討了使用改進 ACS算法進行校車路徑構造方法、與優(yōu)化目標相關的信息素更新策略、局部搜索的路徑改進等內(nèi)容；本文將單校SBRP生成的每條路徑轉(zhuǎn)化為虛擬站點，將SBSP轉(zhuǎn)換為有時間窗的車輛路徑問題（VR

4、PTW），同時設定了以減少車輛數(shù)為主要目標同時兼顧降低車輛的總行車里程為優(yōu)化目標。依據(jù)優(yōu)化目標，在MMAS和局部搜索的策略的基礎上，設計了針對SBSP的改進MMAS。
　　(3)使用基準案例數(shù)據(jù)集，測試和分析了ACS算法和MMAS算法的性能。
　　使用改進ACS求解SBRP的結果與Cplex精確算法求解結果對比表明：對于Cplex能獲得最優(yōu)路徑數(shù)量的案例，改進ACS算法也能獲得相同的路徑數(shù)量,而針對Cplex僅能獲得可行解的

5、大規(guī)模案例，改進 ACS算法在求解路徑數(shù)量和計算效率方面具有明顯的優(yōu)勢；使用改進MMAS求解SBSP的結果與文獻41報道的結果進行對比表明：對于Park Heuristic能獲得最優(yōu)校車數(shù)量的案例，改進MMAS算法也能獲得相同的校車數(shù)量；而針對Park Heuristic不能獲得最優(yōu)校車數(shù)量的案例，改進MMAS算法在求解校車數(shù)量具有優(yōu)勢。
　　(4)校車路徑優(yōu)化案例研究。
　　將改進ACS算法、改進MMAS算法，在ArcGI

6、S的Geoprossing框架下，通過Python語言，進行算法與GIS平臺的集成。使用河南省鞏義市初級中學數(shù)據(jù)，進行校車路徑優(yōu)化案例的研究。
　　本文的主要研究結論如下：
　　(1)本研究對于SBRP建立了開放VRP整型線性規(guī)劃數(shù)學模型進行求解，通過實際案例的研究，表明該模型在實際的應用中有很強的實用性，符合現(xiàn)實情況；對于SBSP建立了混合整形規(guī)劃數(shù)學模型求解，通過實驗表明，這個模型能夠很好的表達SBSP。
　　（2

7、）使用改進ACS算法求解單校SBRP是可行的，在算法的設計過程中，根據(jù)多目標組合優(yōu)化的特點，使用兩階段結構，同時加入逐點插入和兩點交換等局部搜索策略，求解結果與Cplex使用精確算法求解的結果比較具有一定的優(yōu)勢，表明了本算法具有更強的性能，更貼近實際問題；
　?。?）采用改進MMAS算法求解SBSP是有效的，在算法的設計過程中，使用最大最小信息素策略，與優(yōu)化目標相關的信息素更新策略，同時引入逐點插入和兩點交換等局部搜索策略，實驗結