《校車調(diào)度的算法選擇與設(shè)計(jì)案例綜述》3900字

校車調(diào)度的算法選擇與設(shè)計(jì)案例綜述目錄TOC\o"1-2"\h\u29935校車調(diào)度的算法選擇與設(shè)計(jì)案例綜述 1198081.1遺傳算法適用性分析 1284501.2編碼策略 2327201.3初始種群 318009則對(duì)于后λmax位基因bi，滿足 3147681.4過(guò)程仿真 314531則對(duì)于第o次車到達(dá)第i個(gè)站點(diǎn)時(shí)，可上車的人數(shù)can滿足 4262271.5適應(yīng)度計(jì)算 431258（1）多優(yōu)化目標(biāo)的處理 420657（2）模型約束的處理 58501（3）適應(yīng)度函數(shù)計(jì)算 5225301.6進(jìn)化操作 62815（1）選擇操作 614987（2）交叉操作 69803（3）變異操作 614353（4）終止進(jìn)化 71.1遺傳算法適用性分析車輛發(fā)車時(shí)刻表問(wèn)題的求解問(wèn)題中，主要采用非線性數(shù)學(xué)方法尋求非精確性滿意解[44]。國(guó)內(nèi)在運(yùn)輸車輛調(diào)度的研究相對(duì)于國(guó)外較偏向于工程車輛，尤其是對(duì)貨運(yùn)車輛的調(diào)度研究較多且時(shí)間較晚，大多采用數(shù)學(xué)分析與優(yōu)化算法結(jié)合方式[41-47]。而在城市公共交通運(yùn)輸車輛調(diào)度方法上的系統(tǒng)應(yīng)用研究很少，現(xiàn)有研究有采用系統(tǒng)分析方法，如層次分析法；模糊評(píng)價(jià)方法如模糊數(shù)學(xué)、灰色系統(tǒng)理論及神經(jīng)網(wǎng)絡(luò)技術(shù)等，只解決車輛調(diào)度中的某些個(gè)別方面的問(wèn)題[48-51]。而本文研究場(chǎng)景下，車輛發(fā)車時(shí)刻表問(wèn)題是非確定型多項(xiàng)式綜合尋優(yōu)問(wèn)題，屬于NP-hard難題，不易通過(guò)上述方式求精確解，而更傾向于采用智能優(yōu)化算法進(jìn)行多目標(biāo)下的求解[52]。在發(fā)車時(shí)刻表的求解研究中，有學(xué)者嘗試了遺傳算法、模擬退火算法、BP神經(jīng)網(wǎng)絡(luò)、貪心算法等優(yōu)化算法，或基于上述算法進(jìn)行算法混合和算法改進(jìn)，從而加強(qiáng)算法尋優(yōu)能力與收斂速度，其中由于遺傳算法較強(qiáng)的全局搜索能力和魯棒性，常作為重要基礎(chǔ)算法[53]。如黃艷國(guó)等在遺傳算法思想基礎(chǔ)上采用了快速非支配及精英保留策略，使研究的多目標(biāo)規(guī)劃下的車輛發(fā)車間隔問(wèn)題得到了應(yīng)用性較強(qiáng)的帕累托解[54]。林鑫等在考慮路網(wǎng)的車道、信號(hào)燈控控制等復(fù)雜不確定因素后，利用兩階段的遺傳算法-神經(jīng)網(wǎng)絡(luò)算法求解了擁堵、禁行導(dǎo)致的特殊情況下的車輛調(diào)度模型[55]。代存杰利用改進(jìn)的遺傳算法求解了考慮BRT車輛的發(fā)車間隔特征和沿線乘客出行需求的時(shí)間依賴的發(fā)車間隔問(wèn)題，并在蘭州市的實(shí)例下實(shí)現(xiàn)了22%的優(yōu)化率[56]。王健等將定制公交調(diào)度問(wèn)題轉(zhuǎn)化為多TSP問(wèn)題，基于貪心算法思想推導(dǎo)可行解范圍，并用自然編碼的遺傳算法求解，在確定調(diào)度策略的同時(shí)，給出了車輛到達(dá)的準(zhǔn)確度[57]。因此，本文基于遺傳算法并結(jié)合問(wèn)題進(jìn)行設(shè)計(jì)，以對(duì)A高校校車調(diào)度優(yōu)化模型進(jìn)行求解。遺傳算法本質(zhì)是群體智能搜索，用染色體表示問(wèn)題的一組可行解，通過(guò)對(duì)當(dāng)前染色體加以遺傳操作來(lái)產(chǎn)生新一代的染色體群，并設(shè)計(jì)篩選方式，逐步使染色體群向近似最優(yōu)解的狀態(tài)進(jìn)化。由于遺傳算法是遺傳學(xué)和計(jì)算科學(xué)的混合研究形成的尋優(yōu)方法，因此遺傳算法的實(shí)現(xiàn)與設(shè)計(jì)中會(huì)用到與進(jìn)化過(guò)程相關(guān)的基礎(chǔ)術(shù)語(yǔ)，其中術(shù)語(yǔ)的對(duì)應(yīng)關(guān)系如表1-1所示。表1-1遺傳算法術(shù)語(yǔ)對(duì)應(yīng)關(guān)系表遺傳學(xué)術(shù)語(yǔ)遺傳算法術(shù)語(yǔ)群體可行解的集合個(gè)體各可行解染色體可行解編碼基因可行解編碼的分量基因形式遺傳編碼適應(yīng)度評(píng)價(jià)函數(shù)值選擇選擇操作交叉交叉操作變異變異操作1.2編碼策略本模型中最終解的維度受到實(shí)際調(diào)度方案的影響，因此可能出現(xiàn)不同染色體中基因數(shù)量不等情況。為解決此問(wèn)題，采用“最大基因數(shù)”方案。在運(yùn)營(yíng)終止時(shí)間Timee與Timeb確定情況下，最大發(fā)車次數(shù)應(yīng)滿足(1-1)同時(shí)，由于調(diào)度方案中對(duì)發(fā)車類型進(jìn)行了考慮，則每一個(gè)可行解所對(duì)應(yīng)的基因數(shù)應(yīng)為2倍的。其編碼示意如圖1-1所示。圖1-1算法編碼示意圖在進(jìn)行選擇、交叉與變異操作時(shí)，不對(duì)基因位數(shù)進(jìn)行限制，使染色體群體的各基因進(jìn)行設(shè)定參數(shù)下的進(jìn)化行為，但在進(jìn)行適應(yīng)度計(jì)算時(shí)，將發(fā)車間隔換算成發(fā)車時(shí)間，并通過(guò)對(duì)發(fā)車時(shí)間基因中的每一位基因進(jìn)行判斷，當(dāng)基因to超出運(yùn)營(yíng)時(shí)間限制時(shí)，to至tλ及其對(duì)應(yīng)發(fā)車類型基因不參與計(jì)算，從而使超過(guò)運(yùn)營(yíng)時(shí)間限制的基因不對(duì)適應(yīng)度造成影響。1.3初始種群遺傳算法的尋優(yōu)過(guò)程需要有一個(gè)初始種群作為進(jìn)化開(kāi)始種群。與上節(jié)中分段編碼策略類似，初始種群亦為分段產(chǎn)生。染色體的前λmax位具有連續(xù)特征，區(qū)間為[xmin,xmax]，因此采用線性插值方法生成，即對(duì)于每一個(gè)初始染色體中的前λmax位基因ti，有(1-2)ri為取值滿足[0,1]的隨機(jī)數(shù)。后λ位為0-1變量，為方便后續(xù)的進(jìn)化操作，引入二進(jìn)制與十進(jìn)制數(shù)換算進(jìn)行種群生成。對(duì)于確定的λmax值，后λmax位所組成的二進(jìn)制數(shù)取值滿足[0,m]10，m的計(jì)算為(1-3)則對(duì)于后λmax位基因bi，滿足(1-4)rand為取值為[0,1]的隨機(jī)數(shù)。對(duì)于不滿足長(zhǎng)度要求的，即存在空位的情況，空位由0補(bǔ)齊。1.4過(guò)程仿真通過(guò)第四章模型建立研究可以發(fā)現(xiàn)，乘客搭乘中的到達(dá)、等待（滯留）及上車行為均與時(shí)間緊密相關(guān)，即可通過(guò)時(shí)間函數(shù)進(jìn)行表達(dá)。因此，對(duì)于每一個(gè)染色體（解）的產(chǎn)生，都可將其轉(zhuǎn)換為發(fā)車的具體時(shí)間，通過(guò)數(shù)學(xué)方法將搭乘過(guò)程進(jìn)行仿真計(jì)算，并基于計(jì)算結(jié)果進(jìn)行適應(yīng)度函數(shù)的計(jì)算，從而實(shí)現(xiàn)遺傳算法的進(jìn)化迭代。對(duì)于每一個(gè)染色體（解），其前λmax位基因?yàn)榘l(fā)車間隔，則容易得出第o次車的具體發(fā)車時(shí)間為：(1-5)則對(duì)于第o次車，到達(dá)第i個(gè)站點(diǎn)的時(shí)間矩陣AT，可通過(guò)遞推法得出：(1-6)其中，停車時(shí)間和移動(dòng)時(shí)間可由每個(gè)站點(diǎn)的上車人數(shù)計(jì)算得出，其計(jì)算亦具有遞推性，此處不再贅述。運(yùn)營(yíng)時(shí)間內(nèi)不同時(shí)間節(jié)點(diǎn)下，各站點(diǎn)已經(jīng)到達(dá)的乘客數(shù)為：(1-7)則對(duì)于第o次車到達(dá)第i個(gè)站點(diǎn)時(shí)，可上車的人數(shù)can滿足(1-8)對(duì)以上矩陣進(jìn)行重復(fù)運(yùn)算，可得到每一個(gè)染色體（解）對(duì)應(yīng)方案下，每一個(gè)車次到達(dá)每一個(gè)站點(diǎn)時(shí)的搭乘行為情況，從而實(shí)現(xiàn)適應(yīng)度函數(shù)的計(jì)算。1.5適應(yīng)度計(jì)算（1）多優(yōu)化目標(biāo)的處理由上一章節(jié)，本研究問(wèn)題模型為多目標(biāo)規(guī)劃，目標(biāo)函數(shù)中的各部分存在量綱不一致等問(wèn)題，較難統(tǒng)一求解。對(duì)于多目標(biāo)規(guī)劃問(wèn)題，可選擇在“事前”、“事中”及“事后”三個(gè)階段進(jìn)行處理[58]。事前處理指決策前進(jìn)行確定，即在求解問(wèn)題之前就根據(jù)決策者需求對(duì)目標(biāo)函數(shù)進(jìn)行處理，常用評(píng)價(jià)函數(shù)法、約束法及目標(biāo)規(guī)劃法。評(píng)價(jià)函數(shù)法指運(yùn)用模糊評(píng)價(jià)、AHP法等方法對(duì)多目標(biāo)的重要性進(jìn)行評(píng)價(jià)，賦予不同的權(quán)重進(jìn)行處理；約束法將某些目標(biāo)加入系統(tǒng)約束條件，使求解結(jié)果必然滿足目標(biāo)要求；目標(biāo)規(guī)劃法則引入偏離概念，將求解向量與目標(biāo)向量間距離最小作為目標(biāo)求解。事中處理指“交互規(guī)劃”，指進(jìn)行求解過(guò)程中與決策者、決策信息進(jìn)行動(dòng)態(tài)交互，逐步求得優(yōu)化結(jié)果。如建立多層目標(biāo)規(guī)劃，依次滿足目標(biāo)求解。事后處理則在求解后為決策者提供多個(gè)可行方案，決策者可根據(jù)自己的偏好進(jìn)行選擇。回顧模型的目標(biāo)函數(shù)（式4-10），目標(biāo)函數(shù)從關(guān)聯(lián)方角色來(lái)看由運(yùn)營(yíng)成本、乘客成本與外部性成本三個(gè)目標(biāo)構(gòu)成；從影響因素來(lái)看，由固定成本、變動(dòng)成本與運(yùn)營(yíng)期望構(gòu)成。其中，車隊(duì)的一次性投入既為模型約束，也為運(yùn)營(yíng)固定成本一部分，可采用事后處理法進(jìn)行處理；線路均衡率量綱偏差較大，難以衡量，可將其作為系統(tǒng)約束進(jìn)行求解[58]。其余目標(biāo)將采用評(píng)價(jià)函數(shù)進(jìn)行加權(quán)處理。（2）模型約束的處理遺傳算法等智能優(yōu)化算法的研究中，如何保證求得解為可行的或如何進(jìn)行解的修復(fù)是重要研究問(wèn)題。在約束研究中，常用方法有拉格朗日乘數(shù)法、分支界限法、懲罰函數(shù)法等，其中運(yùn)用懲罰函數(shù)進(jìn)行約束處理是一個(gè)較常用方法[59]。懲罰函數(shù)的基本思想為，將約束條件處理成與解取值有關(guān)的函數(shù)，賦予一個(gè)較為顯著大的系數(shù)，并加入到目標(biāo)函數(shù)中。當(dāng)解落入懲罰區(qū)間，即不滿足約束時(shí)，將對(duì)目標(biāo)函數(shù)值造成較大影響?；仡櫛灸Ｐ图s束，約束條件為：發(fā)車間隔最大最小約束、滿載率限制、總規(guī)模限制、運(yùn)營(yíng)時(shí)間限制、0-1變量限制和總運(yùn)輸限制。其中，發(fā)車間隔、運(yùn)營(yíng)時(shí)間、0-1變量及滿載率限制在編碼設(shè)計(jì)時(shí)即完成處理；總規(guī)模限制由上節(jié)中“事后處理”方法進(jìn)行處理。總運(yùn)輸限制則采用懲罰函數(shù)方法進(jìn)行限制。與實(shí)際問(wèn)題相一致，認(rèn)為當(dāng)總運(yùn)輸能力低于需求，即提供的運(yùn)輸能力無(wú)法滿足所有乘客要求時(shí)，會(huì)極大偏離目標(biāo)，造成巨大損失；當(dāng)運(yùn)輸能力超過(guò)乘客要求時(shí)則會(huì)造成浪費(fèi)，但不會(huì)造成巨大影響，則只需與綜合成本一起考慮尋優(yōu)。（3）適應(yīng)度函數(shù)計(jì)算經(jīng)歷上述處理，適應(yīng)度函數(shù)即為每一個(gè)染色體（解）所對(duì)應(yīng)方案下，所對(duì)應(yīng)的成本加和。其計(jì)算如式(4-1)-(4-9)所示。1.6進(jìn)化操作（1）選擇操作本文在進(jìn)行選擇操作時(shí)，采用輪盤賭法對(duì)本代染色體群中的某一染色體是否選中進(jìn)行判定；綜合最優(yōu)個(gè)體保存策略進(jìn)行迭代。輪盤賭法下適應(yīng)度函數(shù)值越大的染色體會(huì)獲得更大選中機(jī)會(huì)。模型的目標(biāo)函數(shù)是求成本最小，因此，在選擇操作前將對(duì)適應(yīng)度函數(shù)做倒數(shù)處理。利用輪盤賭法選擇個(gè)體的具體操作為：a.計(jì)算現(xiàn)有染色體的適應(yīng)度倒數(shù)Fi，i=1,2,…,size,size為群體規(guī)模；b.計(jì)算第i個(gè)染色體被選中概率Pi；c.計(jì)算染色體累積概率Xi；d.產(chǎn)生rand（0,1）數(shù)pick，若累計(jì)概率Xi不小于pick，則選中染色體i；e.多次進(jìn)行d步驟，直到新群體數(shù)達(dá)到size。在輪盤賭法操作后，采用最有個(gè)體保留策略，即用n+1代染色體群中表現(xiàn)最好的個(gè)體替代n代種群中表現(xiàn)最差的個(gè)體，最終得到效果比較好的子代染色體群。（2）交叉操作本算法設(shè)計(jì)中，染色體編碼存在分段情況，因此為增強(qiáng)進(jìn)化效率，采用兩個(gè)交叉點(diǎn)的交叉策略，即對(duì)于前λmax位和后λmax分別設(shè)置一個(gè)交叉點(diǎn)。其步驟為：a.生成兩個(gè)區(qū)間滿足（0,1）的隨機(jī)數(shù)，并以點(diǎn)乘size作為交叉操作索引index；b.生成區(qū)間滿足（0,1）的隨機(jī)數(shù)k，當(dāng)隨機(jī)數(shù)不小于交叉概率pc時(shí)，進(jìn)行交叉操作；c.分別在染色體的兩段生成隨機(jī)數(shù)，并以點(diǎn)乘染色體長(zhǎng)度len作為基因交叉索引pos；d.進(jìn)行交叉互換，并檢驗(yàn)交叉后是否滿足約束；e.完成交叉操作。（3）變異操作為了提高搜索精度和細(xì)調(diào)能力，本研究設(shè)計(jì)了非均勻變異操作，使變異方向及變異量均具有較好的隨機(jī)性。變異方向與變異量的確定方式為如下：對(duì)于已經(jīng)確定的變異基因值v，確定其變異空間范圍為[v1,v2]，計(jì)算為（1-9）生成一個(gè)取值區(qū)間為[0,1]的變異方向臨界值mut，變異量delta滿足（1-10）