大規(guī)?；燧d校車路徑問題優(yōu)化算法研究.pdf

1、為中小學(xué)校學(xué)生提供校車服務(wù)是縣市級地方政府的一項重要職能，也是我國當(dāng)前義務(wù)教育發(fā)展中面臨的新問題。校車運營管理中，合理規(guī)劃校車路徑能減少所需的校車數(shù)量和總體行駛里程，從而節(jié)約運營成本。針對多個學(xué)校進行校車路徑規(guī)劃是一項復(fù)雜度極高的任務(wù)，與其關(guān)系密切的校車路徑問題(SBRP)研究雖然取得了明顯的進展，但與現(xiàn)實中實際需求相比，仍有諸多難題尚未解決。
　　SBRP是在保證滿足校車服務(wù)各種約束條件的前提下，合理地安排校車路徑方案，達到特定

2、目標的組合優(yōu)化問題，它屬于車輛路徑問題(VRP)的一個分支。在針對一個區(qū)域規(guī)劃校車路徑時，若允許校車混載不同學(xué)校的學(xué)生，能夠顯著地減少所需校車數(shù)量和行駛里程。本文針對求解大規(guī)模混載SBRP這一難題，重點研究相關(guān)的數(shù)學(xué)模型和元啟發(fā)求解算法。
　　本文研究思路是:①分析混載SBRP的基本構(gòu)成要素，將校車服務(wù)質(zhì)量和公平性指標作為模型約束條件，將效率作為優(yōu)化目標，提出一般化的混載SBRP數(shù)學(xué)模型。②基于SBRP模型進行算法設(shè)計。首先，設(shè)計

3、適合多種應(yīng)用場景的校車路徑問題算法框架，包括問題數(shù)據(jù)結(jié)構(gòu)、常用函數(shù)和基本算法庫。其次，基于該框架設(shè)計SBRP求解算法。為提升算法求解質(zhì)量和計算效率，引入時空鄰域、搜索策略等進行算法改進。③使用案例數(shù)據(jù)對算法進行性能測試，分析各種策略及參數(shù)設(shè)置對算法的影響，并基于優(yōu)化結(jié)果分析對算法進行優(yōu)化。④最后將算法與GIS進行集成，在GIS中管理數(shù)據(jù)、調(diào)用算法、輸出結(jié)果。
　　本文的主要工作和結(jié)論如下:
　　(1)完成了混載SBRP算法框

4、架設(shè)計。算法框架提供通用的數(shù)據(jù)結(jié)構(gòu)、常用函數(shù)、鄰域算子和常見啟發(fā)式算法，也包含模擬退火、變鄰域搜索和大規(guī)模鄰域搜索等多種元啟發(fā)算法。該框架支持鄰域算子的選擇和組合，能調(diào)整算法執(zhí)行過程中解的接受策略、鄰域搜索策略和算法參數(shù)等，具有通用性和可擴展性。
　　(2)完成了兩階段混載SBRP算法設(shè)計。以最小化校車數(shù)量為主要目標的記錄更新法(RRT)元啟發(fā)算法，引入求解帶時間窗的裝卸一體化問題(PDPTW)時使用的單個點對路徑間移動(SPI)

5、、兩個點對路徑間交換(SBR)和單個點對路徑內(nèi)調(diào)整(WRI)三個鄰域算子優(yōu)化路徑數(shù)，減少使用的校車數(shù)量。以優(yōu)化總運營里程為主要目標的大規(guī)模鄰域搜索算法(LNS)，通過站點對的移除和再插入對現(xiàn)有解進一步改進，縮減了總的運營里程。在鄰域搜索過程中引入時空距離概念，基于站點間的時空相關(guān)度減小了鄰域搜索的規(guī)模，提高了算法的執(zhí)行效率。利用國際上的標準案例對混載SBRP算法進行測試，結(jié)果表明基于PDPTW鄰域算子的RRT算法在求解質(zhì)量上明顯優(yōu)于國際

6、上的現(xiàn)有算法。在循環(huán)30次的情況下，站點隨機分布的案例(RSRB)車輛數(shù)平均減少了10.14％;站點聚集分布的案例(CSCB)車輛數(shù)平均減少10.61％。RRT算法在減少車輛數(shù)的同時，使兩類案例的平均運營里程分別下降了7.34％和6.30％。繼續(xù)執(zhí)行LNS算法之后，運營里程下降程度分別達到10.84％和9.91％。時空相關(guān)的鄰域搜索算法能在保持解的質(zhì)量基本不降低的情況下，算法的平均執(zhí)行時間下降50％左右。
　　(3)完成了大規(guī)?；?/p>

7、載SBRP算法策略和參數(shù)設(shè)置探討。針對算法中不同算子組合、參數(shù)設(shè)置的實驗表明:①SPI算子能有效減少路徑數(shù)量，WRI和SBR本身不能縮減路徑數(shù)量，但是所做的站點調(diào)整使得SPI縮減路徑數(shù)的機會增加。整體上三個算子按照SPI、WRI和SBR的順序執(zhí)行效果最好。②鄰域搜索過程中，優(yōu)先選擇短路徑上的站點對優(yōu)于隨機選擇策略。③解的接收策略上最優(yōu)接受和最先接受各有優(yōu)劣，在大規(guī)模案例中解的接受策略規(guī)律性并不明顯。④增加循環(huán)次數(shù)有進一步減少車輛數(shù)和運營

8、里程的機會，表明在延長算法執(zhí)行時間的情況下，可能會得到更好的解。
　　(4)完成了一個案例實驗。收集鞏義市初級中學(xué)的學(xué)校、學(xué)生和道路網(wǎng)絡(luò)數(shù)據(jù)，使用ArcGIS10進行數(shù)據(jù)管理、道路網(wǎng)絡(luò)分析和混載SBRP建模，調(diào)用SBRP算法進行求解。案例研究表明:本文算法在求解質(zhì)量方面優(yōu)于ArcGIS10網(wǎng)絡(luò)分析模塊的車輛路徑問題算法。
　　本文在多個方面拓展了大規(guī)?；燧dSBRP算法設(shè)計:首次驗證了基于PDPTW算子進行混載SBRP算法設(shè)計