改進迭代局部搜索算法求解需求拆分的校車路徑問題.pdf

1、隨著我國經(jīng)濟社會的發(fā)展，近年來越來越多的地區(qū)和學校開始為中小學生提供校車服務。然而與發(fā)達國家相比，校車服務在我國起步較晚，校車的運營方式及路線規(guī)劃手段等都在探索之中。校車路線規(guī)劃是校車運營管理的關鍵環(huán)節(jié)，合理地安排校車路線，既能節(jié)約校車服務成本，又能提高校車服務質(zhì)量。
　　與校車路線規(guī)劃密切相關的學術問題是校車路徑問題(SBRP)，該問題是組合優(yōu)化領域的NP-hard問題。經(jīng)典的SBRP問題中同一站點乘車的學生必須由一輛校車服務，

2、在一定程度上影響了校車的利用率。在我國人口密度大，居住相對集中。學生的乘車站點一般設置在居民區(qū)附近，導致在一個站點乘車的學生人數(shù)較多，甚至可能超過校車最大載客量，使得經(jīng)典的SBRP無法直接應用于該情形下的路徑規(guī)劃。已有的關于需求拆分的車輛路徑問題研究表明，允許需求拆分能夠進一步減低服務成本。因此，本文將SBRP擴展為站點乘車需求拆分的校車路徑問題(SDSBRP)，優(yōu)化目標包括最小化校車數(shù)量和最小化校車的行駛距離兩個目標，并設計改進的迭代

3、局部搜索算法進行求解。
　　本文所做的工作主要包括以下幾個方面：
　　（1）對需求拆分車輛路徑問題及單校校車路徑問題進行了系統(tǒng)的梳理分析，將經(jīng)典的SBRP擴展為需求拆分的校車路徑問題，在此基礎上設計了求解SDSBRP的啟發(fā)式算法所需要的鄰域算子。
　?。?）設計了求解SDSBRP問題的改進迭代局部搜索算法
　　針對已有關于SDSBRP研究偏少，已有的啟發(fā)式算法難以獲取高質(zhì)量解的問題，設計了基于迭代局部搜索算法(I

4、LS)的元啟發(fā)式求解算法。ILS算法的關鍵在于局部搜索和擾動，合理的局部搜索和擾動策略能夠提高算法的性能。局部搜索易于陷入局部最優(yōu)，使問題偏離最優(yōu)解。本文考慮到模擬退火算法具有較強的局部搜索能力，在局部搜索算法過程中鄰域解的目標值評估時以最小化校車數(shù)量為首要目標，最小化校車行駛距離為第二目標，在進行第二目標的判斷時采用了模擬退火算法思想，允許接受一部分使目標值變差的解。
　　本文采用了一種基于破壞重建思想的擾動策略，從當前解中刪除