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

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

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

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

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

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

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

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