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

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

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

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

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

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

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

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

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

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