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

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

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

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

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

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

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

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