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

大規(guī)?；燧d校車路徑問題優(yōu)化算法研究為中小學(xué)校學(xué)生提供校車服務(wù)是縣市級地方政府的一項(xiàng)重要職能，也是我國當(dāng)前義務(wù)教育發(fā)展中面臨的新問題。校車運(yùn)營管理中，合理規(guī)劃校車路徑能減少所需的校車數(shù)量和總體行駛里程，從而節(jié)約運(yùn)營成本。針對多個學(xué)校進(jìn)行校車路徑規(guī)劃是一項(xiàng)復(fù)雜度極高的任務(wù)，與其關(guān)系密切的校車路徑問題(SBRP)研究雖然取得了明顯的進(jìn)展，但與現(xiàn)實(shí)中實(shí)際需求相比，仍有諸多難題尚未解決。SBRP是在保證滿足校車服務(wù)各種約束條件的前提下，合理地安排校車路徑方案，達(dá)到特定目標(biāo)的組合優(yōu)化問題，它屬于車輛路徑問題(VRP)的一個分支。在針對一個區(qū)域規(guī)劃校車路徑時(shí)，若允許校車混載不同學(xué)校的學(xué)生，能夠顯著地減少所需校車數(shù)量和行駛里程。本文針對求解大規(guī)?；燧dSBRP這一難題，重點(diǎn)研究相關(guān)的數(shù)學(xué)模型和元啟發(fā)求解算法。本文研究思路是：①分析混載SBRP的基本構(gòu)成要素，將校車服務(wù)質(zhì)量和公平性指標(biāo)作為模型約束條件，將效率作為優(yōu)化目標(biāo)，提出一般化的混載SBRP數(shù)學(xué)模型。②基于SBRP模型進(jìn)行算法設(shè)計(jì)。首先，設(shè)計(jì)適合多種應(yīng)用場景的校車路徑問題算法框架，包括問題數(shù)據(jù)結(jié)構(gòu)、常用函數(shù)和基本算法庫。其次，基于該框架設(shè)計(jì)SBRP求解算法。為提升算法求解質(zhì)量和計(jì)算效率，引入時(shí)空鄰域、搜索策略等進(jìn)行算法改進(jìn)。③使用案例數(shù)據(jù)對算法進(jìn)行性能測試，分析各種策略及參數(shù)設(shè)置對算法的影響，并基于優(yōu)化結(jié)果分析對算法進(jìn)行優(yōu)化。④最后將算法與GIS進(jìn)行集成，在GIS中管理數(shù)據(jù)、調(diào)用算法、輸出結(jié)果。本文的主要工作和結(jié)論如下：(1)完成了混載SBRP算法框架設(shè)計(jì)。算法框架提供通用的數(shù)據(jù)結(jié)構(gòu)、常用函數(shù)、鄰域算子和常見啟發(fā)式算法，也包含模擬退火、變鄰域搜索和大規(guī)模鄰域搜索等多種元啟發(fā)算法。該框架支持鄰域算子的選擇和組合，能調(diào)整算法執(zhí)行過程中解的接受策略、鄰域搜索策略和算法參數(shù)等，具有通用性和可擴(kuò)展性。(2)完成了兩階段混載SBRP算法設(shè)計(jì)。以最小化校車數(shù)量為主要目標(biāo)的記錄更新法(RRT)元啟發(fā)算法，引入求解帶時(shí)間窗的裝卸一體化問題(PDPTW)時(shí)使用的單個點(diǎn)對路徑間移動(SPI)、兩個點(diǎn)對路徑間交換(SBR)和單個點(diǎn)對路徑內(nèi)調(diào)整(WRI)三個鄰域算子優(yōu)化路徑數(shù)，減少使用的校車數(shù)量。以優(yōu)化總運(yùn)營里程為主要目標(biāo)的大規(guī)模鄰域搜索算法(LNS)，通過站點(diǎn)對的移除和再插入對現(xiàn)有解進(jìn)一步改進(jìn)，縮減了總的運(yùn)營里程。在鄰域搜索過程中引入時(shí)空距離概念，基于站點(diǎn)間的時(shí)空相關(guān)度減小了鄰域搜索的規(guī)模，提高了算法的執(zhí)行效率。利用國際上的標(biāo)準(zhǔn)案例對混載SBRP算法進(jìn)行測試，結(jié)果表明基于PDPTW鄰域算子的RRT算法在求解質(zhì)量上明顯優(yōu)于國際上的現(xiàn)有算法。在循環(huán)30次的情況下，站點(diǎn)隨機(jī)分布的案例(RSRB)車輛數(shù)平均減少了10.14%；站點(diǎn)聚集分布的案例(CSCB)車輛數(shù)平均減少10.61%。RRT算法在減少車輛數(shù)的同時(shí)，使兩類案例的平均運(yùn)營里程分別下降了7.34%和6.30%。繼續(xù)執(zhí)行LNS算法之后，運(yùn)營里程下降程度分別達(dá)到10.84%和9.91%。時(shí)空相關(guān)的鄰域搜索算法能在保持解的質(zhì)量基本不降低的情況下，算法的平均執(zhí)行時(shí)間下降50%左右。(3)完成了大規(guī)?；燧dSBRP算法策略和參數(shù)設(shè)置探討。針對算法中不同算子組合、參數(shù)設(shè)置的實(shí)驗(yàn)表明：①SPI算子能有效減少路徑數(shù)量，WRI和SBR本身不能縮減路徑數(shù)量，但是所做的站點(diǎn)調(diào)整使得SPI縮減路徑數(shù)的機(jī)會增加。整體上三個算子按照SPI、WRI和SBR的順序執(zhí)行效果最好。②鄰域搜索過程中，優(yōu)先選擇短路徑上的站點(diǎn)對優(yōu)于隨機(jī)選擇策略。③解的接收策略上最優(yōu)接受和最先接受各有優(yōu)劣，在大規(guī)模案例中解的接受策略規(guī)律性并不明顯。④增加循環(huán)次數(shù)有進(jìn)一步減少車輛數(shù)和運(yùn)營里程的機(jī)會，表明在延長算法執(zhí)行時(shí)間的情況下，可能會得到更好的解。(4)完成了一個案例實(shí)驗(yàn)。收集鞏義市初級中學(xué)的學(xué)校、學(xué)生和道路網(wǎng)絡(luò)數(shù)據(jù)，使用ArcGIS10進(jìn)行數(shù)據(jù)管理、道路網(wǎng)絡(luò)分析和混載SBRP建模，調(diào)用SBRP算法進(jìn)行求解。案例研究表明：本文算法在求解質(zhì)量方面優(yōu)于ArcGIS10網(wǎng)絡(luò)分析模塊的車輛路徑問題算法。本文在多個方面拓展了大規(guī)?；燧dSBRP算法設(shè)計(jì)：首次驗(yàn)證了基于PDPTW算子進(jìn)行混載SBRP算法設(shè)計(jì)的可行性；與現(xiàn)有算法相比，本算法顯著地提高了求解的