改進(jìn)迭代局部搜索算法求解需求拆分的校車路徑問(wèn)題.pdf

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

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

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

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