本文選題：校車路徑問題 + 開放式車輛路徑問題　； 參考：《河南大學(xué)》2013年碩士論文

【摘要】：為中小學(xué)生提供校車服務(wù)是我國義務(wù)教育發(fā)展的必然要求。然而，規(guī)劃校車路徑是校車運(yùn)行管理中的一個難題。合理的校車路徑規(guī)劃，既能減少所需校車數(shù)量，又可縮短校車運(yùn)行里程，從而節(jié)省校車運(yùn)營服務(wù)成本。本文嘗試建立校車路徑問題（School BusRouting Problem，SBRP）數(shù)學(xué)模型，設(shè)計(jì)元啟發(fā)算法進(jìn)行路徑優(yōu)化，并將優(yōu)化算法集成在GIS中，為校車路徑規(guī)劃提供軟件工具。 因SBRP本質(zhì)上屬于車輛路徑問題（VRP）范疇，本文借鑒VRP模型和算法，針對校車停車場不在學(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中設(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é)果可視化等功能。并用一所初級中學(xué)作為測試實(shí)例進(jìn)行校車路徑規(guī)劃。 實(shí)驗(yàn)結(jié)果表明：使用模擬退火元啟發(fā)算法解決校車問題是可行的。從多個初始解進(jìn)行優(yōu)化的模擬退火算法與ArcGIS中添加禁忌算法的VRP求解算法相比，解的質(zhì)量有所提高。本文算法數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)簡單，占用內(nèi)存少，在針對校車路徑規(guī)劃方面表現(xiàn)出明顯的優(yōu)勢；且將通過ArcGIS網(wǎng)絡(luò)分析功能算出的OD距離矩陣作為算法輸入項(xiàng)，提高了對實(shí)際問題的處理能力。通過工具箱輸入相關(guān)參數(shù)之后，能夠快速的找到近似最優(yōu)的校車安排方案，并且進(jìn)行了可視化的輸出，使規(guī)劃者對規(guī)劃方案有直觀認(rèn)知。
[Abstract]:Providing school bus service for primary and middle school students is an inevitable requirement for the development of compulsory education in China. However, planning the path of school bus is a difficult problem in the operation and management of school buses. The reasonable path planning of school buses can not only reduce the number of school buses, but also shorten the running mileage of the school bus, thus saving the service cost of the school car. This paper tries to establish the school bus path. School BusRouting Problem (SBRP) mathematical model, design meta heuristic algorithm for path optimization, and integrate the optimization algorithm in GIS, to provide software tools for school bus path planning.
Because SBRP is essentially a vehicle routing problem (VRP) category, this paper uses the VRP model and algorithm, and selects the open VRP model to construct SBRP optimization model in view of the school bus parking lot without the actual situation of the school. In the model, the model takes the shortest path length of the school bus as the target, the school bus capacity, the longest train time, and so on as the limiting condition. The optimization algorithm flow is as follows: establish the model, construct the initial solution, optimize the path by using the VRP neighborhood switching operator in the simulated annealing element heuristic framework, and implement the optimization algorithm through the C++ program. In order to verify the effectiveness and calculation efficiency of the algorithm, the simulation data is used to test the algorithm, and the VRP tool in the ArcGIS network analysis module is superior to the tool. Finally, the school bus path planning tool is designed in GIS. In the ArcGIS10 management school, parking lot, student station, traffic network and other geographical data, based on the Geoprocessing framework design and planning tools. Using the Python program design to implement tool parameters setting, model parameters calculation, model modeling, optimization module calls, The function of visualization is optimized, and a junior middle school is used as an example to carry out the school bus path planning.
The experimental results show that it is feasible to solve the school bus problem using the simulated annealing element heuristic algorithm. Compared with the VRP algorithm of adding tabu algorithms in ArcGIS, the quality of the solution is improved. The design of the algorithm is simple and the memory is less, and it is aimed at the path planner of the school bus. The surface shows obvious advantages, and the OD distance matrix calculated by the ArcGIS network is used as the input item of the algorithm, and the processing ability of the actual problem is improved. After input of the relevant parameters in the toolbox, the approximate optimal school bus arrangement can be found quickly, and the visual output is carried out to make the planners to the rules. The plan has a visual cognition.
【學(xué)位授予單位】：河南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2013
【分類號】：P208;TP301.6

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李明;;蟻群算法在土地利用結(jié)構(gòu)優(yōu)化模型中的應(yīng)用[J];安徽農(nóng)業(yè)科學(xué);2011年14期

2 于航;張凱;;基于節(jié)約里程法的鮮活農(nóng)產(chǎn)品物流配送車輛路線的最優(yōu)設(shè)計(jì)[J];安徽農(nóng)業(yè)科學(xué);2011年28期

3 路玉龍;趙扶搖;韓靖;張鴻雁;;城市生活垃圾收運(yùn)路線優(yōu)化的數(shù)學(xué)模型與算法[J];環(huán)境科學(xué)與管理;2010年06期

4 徐新明;陳培友;;物流調(diào)度問題的優(yōu)化方法評述[J];商業(yè)研究;2009年05期

5 楊瑞臣;郝海燕;;改進(jìn)的蟻群算法在物流配送路徑問題求解中的應(yīng)用[J];承德石油高等�？茖W(xué)校學(xué)報(bào);2009年02期

6 劉士新;劉玲;張濤;;求解VRPBTW的變鄰域搜索算法[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

7 廖潔君,陳燕;城市物流中多目標(biāo)配送模型[J];大連海事大學(xué)學(xué)報(bào);2004年04期

8 石麗紅;范厚明;翟志偉;王桂琳;;城市醫(yī)療廢棄物回收處理流程及車行路徑優(yōu)化[J];大連海事大學(xué)學(xué)報(bào);2010年03期

9 石兆旭;魏連雨;;有容量限制路徑選擇優(yōu)化問題的混合螞蟻算法[J];道路交通與安全;2005年06期

10 陳美軍;張志勝;史金飛;;基于自適應(yīng)多態(tài)蟻群算法的多約束車輛路徑問題[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年01期

相關(guān)會議論文 前10條

1 何世偉;宋瑞;魯放;楊永凱;;不確定性群組決策優(yōu)化模型及其在交通運(yùn)輸領(lǐng)域中的應(yīng)用研究[A];第四屆中國青年運(yùn)籌與管理學(xué)者大會論文集[C];2001年

2 錢賢偉;王夢光;;基于VRP模型的熱軋生產(chǎn)批量計(jì)劃及禁忌搜索算法[A];1998中國控制與決策學(xué)術(shù)年會論文集[C];1998年

3 黃輝;屠乃威;馬天牧;鄭秉霖;柴天佑;;基于VRP的模鑄組爐問題模型及其蟻群算法[A];2009中國控制與決策會議論文集（3）[C];2009年

4 黃紅星;鐘一文;黃習(xí)培;;挖掘最大頻繁項(xiàng)集的二進(jìn)制蟻群優(yōu)化算法[A];第四屆中國智能計(jì)算大會論文集[C];2010年

5 師凱;蔡延光;鄒谷山;王濤;;運(yùn)輸調(diào)度問題的蟻群算法研究[A];04'中國企業(yè)自動化和信息化建設(shè)論壇暨中南六省區(qū)自動化學(xué)會學(xué)術(shù)年會專輯[C];2004年

6 ;A TWO-PHASE HEURISTIC ALGORITHM TO SOLVE THE LARGE-SCALE VEHICLE ROUTING PROBLEM[A];2006年中國機(jī)械工程學(xué)會年會暨中國工程院機(jī)械與運(yùn)載工程學(xué)部首屆年會論文集[C];2006年

7 王際洲;;煙草物流配送中若干優(yōu)化問題研究[A];中國煙草學(xué)會2009年年會論文集[C];2009年

8 陸琳;譚清美;;模糊信息動態(tài)車輛調(diào)度優(yōu)化問題研究[A];第八屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2006年

9 陳美軍;張志勝;史金飛;;MDVRPMC問題的智能多態(tài)蟻群算法研究[A];2007第三屆中國智能交通年會論文集[C];2007年

10 Chunhua Meng;Hongguo Wang;Zengzhen Shao;Yanhui Ding;;Heuristic Optimization Algorithms for Solving MRMPT[A];2013年中國智能自動化學(xué)術(shù)會議論文集（第二分冊）[C];2013年

相關(guān)博士學(xué)位論文 前10條

1 彭北青;第三方物流配送車輛路徑問題模型及算法研究[D];華中科技大學(xué);2009年

2 孫麗君;物流配送干擾管理問題的知識表示與建模方法[D];大連理工大學(xué);2011年

3 趙彤;我國突發(fā)自然災(zāi)害應(yīng)急救災(zāi)物資配送系統(tǒng)優(yōu)化研究[D];大連海事大學(xué);2011年

4 蔣麗;以工位為中心的生產(chǎn)物流配送優(yōu)化研究[D];中國科學(xué)技術(shù)大學(xué);2011年

5 鄭俊麗;船舶分段制造車間的模塊空間調(diào)度模型及算法[D];上海交通大學(xué);2011年

6 高貴兵;混流制造系統(tǒng)生產(chǎn)物流關(guān)鍵問題優(yōu)化研究[D];華中科技大學(xué);2011年

7 陳森;基于可變路網(wǎng)結(jié)構(gòu)的應(yīng)急資源調(diào)度問題研究[D];國防科學(xué)技術(shù)大學(xué);2011年

8 石麗紅;城市醫(yī)療廢棄物回收處理模式及其網(wǎng)絡(luò)研究[D];大連海事大學(xué);2011年

9 高貴兵;混流制造系統(tǒng)生產(chǎn)物流優(yōu)化關(guān)鍵問題研究[D];華中科技大學(xué);2011年

10 丁秋雷;物流配送地址變化的干擾管理模型及其求解方法[D];大連理工大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 邵曉路;蟻群群體智能網(wǎng)絡(luò)可視化試驗(yàn)平臺研制[D];浙江理工大學(xué);2010年

2 蔡翱鵬;遺傳算法在動態(tài)車輛調(diào)度問題中的研究[D];長沙理工大學(xué);2010年

3 田野;東北化工銷售公司石化產(chǎn)品運(yùn)輸配送優(yōu)化研究[D];大連海事大學(xué);2010年

4 趙再興;基于改進(jìn)和聲搜索算法的車輛路徑規(guī)劃問題[D];沈陽大學(xué);2011年

5 趙思敏;糧食應(yīng)急物流系統(tǒng)的網(wǎng)絡(luò)構(gòu)建及路徑優(yōu)化[D];武漢理工大學(xué);2011年

6 葉創(chuàng)鑫;物流配送的路徑優(yōu)化與行程時(shí)間預(yù)測[D];暨南大學(xué);2011年

7 任中明;運(yùn)輸調(diào)度問題的智能求解機(jī)制研究[D];廣東工業(yè)大學(xué);2011年

8 葉寶林;分布估計(jì)算法的一種改進(jìn)與應(yīng)用[D];太原科技大學(xué);2011年

9 田宇;基于系統(tǒng)仿真模擬退火算法的VRPTW研究[D];河北工程大學(xué);2011年

10 李朝輝;連續(xù)域蟻群算法的改進(jìn)研究及在參數(shù)估計(jì)中的應(yīng)用[D];中南大學(xué);2011年

本文編號：1917014