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

《改進迭代局部搜索算法求解需求拆分的校車路徑問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、單位代碼１〇４７５學號１０４７５３］３０７５２分類號ＴＰ３化鄭雜乂聲碩壬學位論文中－改進迭代局部搜索算法求解需求祝分的校車路徑問題－產(chǎn)Ｌ－學科、專業(yè)：計算機應用技術(shù)研究方向：智能優(yōu)化算法申請學位類別：理學碩±申請人：李雙星指導教師：鄭逢斌教授二〇－六年六月ImprovedIteratedLocalSearchAlgorithmsforSplitDemandSchoolBusRoutingProblemADissertationSubmittedtotheGraduateSchoolofHenanUnive

2、rsityinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceByLiShuangxingSupervisor:Prof.ZhengFengbinJune2016關(guān)于學位論文獨創(chuàng)齊明和學術(shù)誠信承諾泰人向巧南大孚巧出頌壬學位申請，本人擇重聲明：所呈交的學位論文是本人在奪鄉(xiāng)的拍導下巧立完成的，對所巧定的巧題資新的見解。據(jù)我所知，除文中特莉加ａ說明、株注和致編的地方外，託文中不狂括其他人史經(jīng)發(fā)表女誤寫過的研完成《，也不包括乂化人為獲得妊何教育一巧王作的巧事對、料研機巧的學化或化書

3、病使?jié)M過的材料，與我本研完所化的任何貢獻均巳么論文中作了巧確的說巧并表示了謝素，在化本人新重承諾：巧至交的學化論文不每在舞奔作約行污，義責自資．Ａ雲(yún)學往申請人（學拉論文作者）簽名：名？２０?。陚湓铝x曰關(guān)于學位論支著作巧使用授極書衣人巧河南大學審棱扯難巧子巧去學位。作話學位誰文的作者，本人完全了解并巧，枯《巧南太學有關(guān)保留、巧巧怎、使巧學位論文的要求，郵河南大學有化向國《里書巧化構(gòu)、數(shù)絕化集機婚和本校圖書館等提供學位論文（包泌紙廣文本和電子文本）ａ供公眾檢索、查閑，本人搜權(quán)河南欠學出于畫巧、展覽學較學術(shù)發(fā)展和進巧學術(shù)交流等ａ的，可＆采

4、巧巧印、巧印、擔巧和轉(zhuǎn)男等復制手段巧存、匯編學位論文（包括化巧文本和電子文本）。（涉義保密內(nèi)容的學位絡義在解密后連用本巧杖書）學位巧巧者？呈（學位論文巧者）癥名２０１＾卑食月文日ｉ學位論文指導教師簽名；２０１＾年《月３ｇ摘要隨著我國經(jīng)濟社會的發(fā)展，近年來越來越多的地區(qū)和學校開始為中小學生提供校車服務。然而與發(fā)達國家相比，校車服務在我國起步較晚，校車的運營方式及路線規(guī)劃手段等都在探索之中。校車路線規(guī)劃是校車運營管理的關(guān)鍵環(huán)節(jié)，合理地安排校車路線，既能節(jié)約校車服務成本，又能提高校車服務質(zhì)量。與校車路線規(guī)劃密切相關(guān)的學術(shù)問題是校車路徑問題

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

6、文所做的工作主要包括以下幾個方面：（1）對需求拆分車輛路徑問題及單校校車路徑問題進行了系統(tǒng)的梳理分析，將經(jīng)典的SBRP擴展為需求拆分的校車路徑問題，在此基礎(chǔ)上設計了求解SDSBRP的啟發(fā)式算法所需要的鄰域算子。（2）設計了求解SDSBRP問題的改進迭代局部搜索算法針對已有關(guān)于SDSBRP研究偏少，已有的啟發(fā)式算法難以獲取高質(zhì)量解的問題，設計了基于迭代局部搜索算法(ILS)的元啟發(fā)式求解算法。ILS算法的關(guān)鍵在于局部搜索和擾動，合理的局部搜索和擾動策略能夠提高算法的性能。局部搜索易于陷入局部最優(yōu)，使問題偏離最優(yōu)解。本文考慮到模擬退火算法具有較強的局部搜索能力，在局部搜索算法

7、過程中鄰域解的目標值評估時以最小化校車數(shù)量為首要目標，最小化校車行駛距離為第二目標，在進行第二目標的判斷時采用了模擬退火算法思想，允許接受一部分使目標值變差的解。本文采用了一種基于破壞重建思想的擾動策略，從當前解中刪除一部分路徑，然后進行重建，增加ILS算法跳出局部最優(yōu)解的概率。（3）用本文所提出的算法具有廣泛的適用性，能夠求解站點乘車需求拆分和不拆I分兩種情形下的校車路徑問題。針對設計的算法進行了仿真實驗與分析，驗證了算法的有效性。關(guān)鍵詞：校車路徑問題；迭代局部搜索算法；需求拆分；元啟發(fā)式算法IIAbstractWithth