本文關(guān)鍵詞：大規(guī)�；燧d校車路徑問(wèn)題優(yōu)化算法研究　出處：《河南大學(xué)》2014年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 校車路徑問(wèn)題 混載 元啟發(fā)算法 時(shí)空鄰域 空間優(yōu)化

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

【參考文獻(xiàn)】

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

1 許文龍;李小娟;宮輝力;孫永華;;校車最優(yōu)路徑規(guī)劃算法[J];地理空間信息;2011年04期

2 楊衛(wèi)安;鄔志輝;;“校車”還是“寄宿”——農(nóng)村學(xué)校布局調(diào)整后兩者的優(yōu)劣比較及選擇[J];上海教育科研;2012年12期

3 謝秉磊,郭耀煌,郭強(qiáng);動(dòng)態(tài)車輛路徑問(wèn)題:現(xiàn)狀與展望[J];系統(tǒng)工程理論方法應(yīng)用;2002年02期

4 余明珠;李建斌;雷東;;裝卸一體化的車輛路徑問(wèn)題及基于插入法的新禁忌算法[J];中國(guó)管理科學(xué);2010年02期

5 李妍峰;李軍;高自友;;動(dòng)態(tài)規(guī)劃啟發(fā)式算法求解時(shí)變車輛調(diào)度問(wèn)題[J];系統(tǒng)工程理論與實(shí)踐;2012年08期

6 涂偉;李清泉;方志祥;;一種大規(guī)模車輛路徑問(wèn)題的啟發(fā)式算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2013年03期

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

1 陳萍;啟發(fā)式算法及其在車輛路徑問(wèn)題中的應(yīng)用[D];北京交通大學(xué);2009年

2 潘立軍;帶時(shí)間窗車輛路徑問(wèn)題及其算法研究[D];中南大學(xué);2012年

本文編號(hào)：1407012