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

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