多車型校車路徑問題優(yōu)化算法研究.pdf

1、為中小學(xué)學(xué)生提供安全、高效的校車服務(wù)是我國義務(wù)教育發(fā)展中面臨的新要求。校車路徑規(guī)劃是校車運(yùn)營的基礎(chǔ)環(huán)節(jié)，合理地規(guī)劃校車路徑可以顯著地提高服務(wù)效率，降低運(yùn)營成本。校車路徑問題(SBRP)涉及學(xué)校、學(xué)生乘車站點(diǎn)、場站、校車類型、交通網(wǎng)絡(luò)、學(xué)區(qū)地理環(huán)境、約束條件和規(guī)劃目標(biāo)等眾多因素，是一類復(fù)雜度極高的NP-hard問題。SBRP通常是在保障校車服務(wù)質(zhì)量的前提下，盡量減少車輛購置、維護(hù)等固定成本和校車的日常運(yùn)營成本。
　　校車路徑規(guī)劃實(shí)踐

2、中，校車車隊往往由多種類型的車輛構(gòu)成。同時，受學(xué)生站點(diǎn)分布、道路狀況等現(xiàn)實(shí)條件的影響，多種類型的校車組合能更好地滿足實(shí)際需求。然而，相對于單車型SBRP，多車型SBRP(HSBRP)的研究較少。而且，現(xiàn)有HSBRP的求解主要采用構(gòu)造啟發(fā)算法或改進(jìn)啟發(fā)算法，優(yōu)化性能有限，也難以適應(yīng)較復(fù)雜的規(guī)劃場景。鑒于此，本文針對HSBRP，在問題定義和數(shù)學(xué)建模的基礎(chǔ)上，設(shè)計一個適用于多種應(yīng)用場景的算法框架，進(jìn)而探索單校、多校、車型混合和車輛數(shù)限制等不同

3、場景下HSBRP的元啟發(fā)優(yōu)化算法。
　　研究思路如下：①針對不同應(yīng)用場景下校車路徑規(guī)劃的需求，考慮校車類型、校車容量、校車數(shù)量、學(xué)校時間窗、學(xué)生最大乘車時間等約束條件，以校車固定成本和運(yùn)營成本為目標(biāo)建立HSBRP的數(shù)學(xué)模型，并嘗試使用模型精確求解。②探討HSBRP的求解策略，設(shè)計一個通用HSBRP算法框架，包括基本數(shù)據(jù)結(jié)構(gòu)、常用操作函數(shù)、初始解構(gòu)造算法、各種局部提升算子和啟發(fā)策略；開發(fā)基礎(chǔ)算法庫，便于構(gòu)造常見元啟發(fā)算法。③利用算法

4、庫，針對單校車型混合、單校車輛數(shù)限制、多校多車型等問題類型，分別實(shí)現(xiàn)HSBRP算法，引入鄰域解接受策略和車型調(diào)整策略提升解的質(zhì)量；并使用基準(zhǔn)案例進(jìn)行算法測試和性能分析。④使用實(shí)際案例驗(yàn)證本文算法的實(shí)用性。
　　本文的主要工作和結(jié)論如下：
　　(1)完成了一個滿足單校和多校問題求解的HSBRP算法框架。算法框架提供通用的數(shù)據(jù)結(jié)構(gòu)、基礎(chǔ)函數(shù)、初始解構(gòu)造算法和鄰域搜索算子，支持搜索算子選擇、車型調(diào)整、鄰域解接受、搜索擾動等啟發(fā)策略

5、的組合使用?；谒惴蚣軐?shí)現(xiàn)了迭代局部搜索、變鄰域搜索和貪婪隨機(jī)自適應(yīng)等元啟發(fā)算法。算法的設(shè)計與實(shí)現(xiàn)表明：該算法框架不僅具有通用性，而且能夠快速實(shí)現(xiàn)求解SBRP的元啟發(fā)算法和混合元啟發(fā)算法。
　　(2)針對單校HSBRP問題，分別完成車型混合HSBRP(FSMSBRP)和車輛數(shù)限制HSBRP(HFSBRP)的求解算法。針對FSMSBRP，設(shè)計貪婪隨機(jī)自適應(yīng)算法(GRASP)，并通過參數(shù)自適應(yīng)選擇對算法進(jìn)行改進(jìn)。該算法適用于求解總成

6、本、固定成本和可變成本三種優(yōu)化目標(biāo)的FSMSBRP問題。在國際基準(zhǔn)測試案例上的實(shí)驗(yàn)表明：參數(shù)自適應(yīng)選擇優(yōu)于參數(shù)隨機(jī)或固定選擇；與現(xiàn)有FSMSBRP求解算法相比，GRASP算法具有明顯的優(yōu)勢，三類問題的求解質(zhì)量比RRH算法分別改進(jìn)了5.28％、4.84%和7.22%，比自適應(yīng)基于位置啟發(fā)(ALBH)算法分別改進(jìn)了6.26%、6.02%和7.55%。針對HFSBRP，建立了基于車型的整型規(guī)劃數(shù)學(xué)模型，并設(shè)計一種迭代局部搜索算法和可變鄰域下降

7、算法混合的元啟發(fā)算法(HILS)進(jìn)行求解。使用HILS算法分別求解優(yōu)化目標(biāo)為總成本和可變成本的兩類HFSBRP問題，測試表明所設(shè)計的HILS算法能夠在較短的時間內(nèi)獲得高質(zhì)量的解，并且算法穩(wěn)定性較高。
　　(3)完成了混載和不混載兩種運(yùn)營模式下多校HSBRP的迭代局部搜索算法(ILS)。鑒于多校問題與帶時間窗裝卸一體化問題(PDPTW)模型具有相似性，在ILS算法中引入PDPTW問題求解中使用的SPI、SBR和WRI三個鄰域算子優(yōu)化

8、總成本，并改進(jìn)這三個算子允許車型調(diào)整。利用國際標(biāo)準(zhǔn)案例庫對ILS算法進(jìn)行測試，與隨機(jī)基于位置啟發(fā)算法(RLBH)和ALBH算法相比，ILS算法在不混載模式下的總成本平均下降了29.01%和34.84%，而在混載模式下ILS算法的總成本則平均下降了平均28.93%和34.66%。
　　(4)完成了一個案例實(shí)驗(yàn)。收集整理了無錫市惠山區(qū)的道路、學(xué)校和學(xué)生等信息，在ArcGIS10.2內(nèi)完成數(shù)據(jù)整理、OD矩陣計算和網(wǎng)絡(luò)分析等功能，完成單校

9、和多校的案例研究。實(shí)驗(yàn)結(jié)果表明：使用多種車型規(guī)劃校車路徑優(yōu)于單一車型的路徑規(guī)劃，多校運(yùn)營模式比單校運(yùn)營所需要的總成本更少。對于單校多車型校車路徑規(guī)劃，本文的GRASP算法優(yōu)于ArcGIS網(wǎng)絡(luò)分析中的VRP算法；對于多校多車型路徑規(guī)劃，本文設(shè)計的不混載和混載兩種規(guī)劃方案比現(xiàn)有方案分別節(jié)約了3.20%和6.62%的成本。
　　本文針對多車型SBRP問題的多種應(yīng)用場景，設(shè)計了一個靈活通用的元啟發(fā)算法框架，支持單校、多校以及不同優(yōu)化目標(biāo)H