校車路徑問題元啟發(fā)算法設(shè)計(jì)與GIS集成.pdf

1、為中小學(xué)生提供校車服務(wù)是我國義務(wù)教育發(fā)展的必然要求。然而,規(guī)劃校車路徑是校車運(yùn)行管理中的一個(gè)難題。合理的校車路徑規(guī)劃,既能減少所需校車數(shù)量,又可縮短校車運(yùn)行里程,從而節(jié)省校車運(yùn)營服務(wù)成本。本文嘗試建立校車路徑問題(School Bus Routing Problem,SBRP)數(shù)學(xué)模型,設(shè)計(jì)元啟發(fā)算法進(jìn)行路徑優(yōu)化,并將優(yōu)化算法集成在GIS中,為校車路徑規(guī)劃提供軟件工具。
　　因SBRP本質(zhì)上屬于車輛路徑問題(VRP)范疇,本文借鑒

2、VRP模型和算法,針對(duì)校車停車場不在學(xué)校的實(shí)際情況,選擇開放 VRP模型構(gòu)建SBRP優(yōu)化模型。模型中,以校車運(yùn)行總路徑長度最短為目標(biāo),以校車容量、學(xué)生最長乘車時(shí)間等為限制條件。模型優(yōu)化算法流程如下:建立模型,構(gòu)造初始解,在模擬退火元啟發(fā)框架中利用 VRP鄰域交換算子優(yōu)化路徑,通過C++程序設(shè)計(jì)實(shí)現(xiàn)優(yōu)化算法。為驗(yàn)證本算法的有效性和計(jì)算效率,利用模擬數(shù)據(jù)進(jìn)行算法測試,并與ArcGIS網(wǎng)絡(luò)分析模塊中VRP工具優(yōu)化結(jié)果進(jìn)行比較。最后,在GIS中

3、設(shè)計(jì)校車路徑規(guī)劃工具。在ArcGIS10中管理學(xué)校、停車場、學(xué)生乘車站點(diǎn)、交通網(wǎng)絡(luò)等地理數(shù)據(jù),基于Geoprocessing框架設(shè)計(jì)規(guī)劃工具。利用Python程序設(shè)計(jì)實(shí)現(xiàn)工具參數(shù)設(shè)置、模型參數(shù)計(jì)算、模型建模、優(yōu)化模塊調(diào)用、優(yōu)化結(jié)果可視化等功能。并用一所初級(jí)中學(xué)作為測試實(shí)例進(jìn)行校車路徑規(guī)劃。
　　實(shí)驗(yàn)結(jié)果表明:使用模擬退火元啟發(fā)算法解決校車問題是可行的。從多個(gè)初始解進(jìn)行優(yōu)化的模擬退火算法與ArcGIS中添加禁忌算法的VRP求解算法相