版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、公交車輛調(diào)度問題是指針對一項可分解的運輸任務,在一定的約 束條件下,如何合理安排其組織部分占用資源、 運作時間及先后順序, 以獲得運輸成本或時間最優(yōu)化。包含兩層含義:1.編制行車時刻表,稱為靜態(tài)調(diào)度; 2.由于某種路況信息或突發(fā)事件,使靜態(tài)調(diào)度做出修 改、更新,稱為動態(tài)調(diào)度。傳統(tǒng)的調(diào)度理論方法多采用數(shù)學解析法、運籌學方法和經(jīng)驗模型 等。隨著調(diào)度問題計算復雜性及問題規(guī)模的擴大, 傳統(tǒng)方法遇到了很 大的困難。 人工智能為調(diào)度問題研究開辟了新的道路。 現(xiàn)有的研究方 法有: 1.應用標準遺傳算法進行公交靜態(tài)調(diào)度優(yōu)化; 2.蟻群算法思想 解決車輛優(yōu)化調(diào)度問題;3基于公交運營效益最大化的BRT調(diào)度問題 的
2、數(shù)學模型,并設計了優(yōu)化該問題的禁忌算法;4.粒子群算法解決帶時間窗的公交路徑優(yōu)化問題?;诟倪M遺傳算法在靜態(tài)調(diào)度中的應用,以公交營運商和乘客費 用(包括乘客等車時間費用和車上等待時間費用)最小為目標,建立 公交調(diào)度優(yōu)化的數(shù)學模型,在遺傳算法中引入模擬退火算法的思想, 研究改進的遺傳算法在公交調(diào)度中應用的基本方法和基本理論。公交調(diào)度優(yōu)化問題表現(xiàn)為兩個方面的利益最大化: 1.企業(yè)的收益; 2.乘客利益。且乘客利益優(yōu)先于企業(yè)利益。該問題的研究對象有公交 公司和乘客兩部分組成。公交公司希望提供盡量大的發(fā)車間隔,發(fā)車次數(shù)盡量少,單位車輛上座率盡量高,以減少其可變成本,增加運營收入;乘客則要求獲得更快捷的
3、服務,減低等車、車上和換乘費用;3. 減少公交公司費用意味著增加乘客費用,反之亦然。因此,需要從公交乘客和公交公司雙方利益最大化出發(fā),根據(jù)公交車輛實際運營時乘客流量在時間上的不均衡規(guī)律,以極小化公交公司和 乘客費用總和為目標,對發(fā)車間隔采用分時段多目標組合優(yōu)化處理的 思想,在合理假設的前提下建立優(yōu)化模型。營運成本 Co=/K ) J(Tk/Hk)K為時段總數(shù),將一天劃分為 K個時段;Tk為第k時段公 交車營運時間;Hk為第k時段的發(fā)車間隔;為公交車的 單車營運成本出行者費用Cu由乘客候車耗時費用Cub與不下車乘客由于 公交站點停車所消耗的時間費用Ccb組成:Cu =Cub + Ccb1JCub
4、=-( 山/K) k=i J=i (UkjHk)*為乘客單位時間價值;Ukj為k時段、第j站的乘客到站 密度,假設服從均勻分布;J為公交站點數(shù)C =上1CCb = Kk=iJ=i Dkj?;q: +:q;HkPkji Pkj2為k時段j站點上下車乘客需求;q1q2為上下車平均速率;Dkj為k時段j站點的不下車乘客數(shù)j- 1Dkj =(Bkm - Akm )m=1Bkm為k時段j站點的上課乘客數(shù);Akm為k時段j站點的 下車乘客數(shù)。優(yōu)化模型:選取權重和方法作為多目標函數(shù)優(yōu)化算法,得到目標函數(shù)f,待求變量為發(fā)車間隔Hkmin f= aC0 + 約束條件為:Hmin W Hk 70%kNY Nk/7
5、* * 丁 A %N* = i 12 * * t K F(A*T. 丁oa為權重系數(shù),取正數(shù);Hmin為最小發(fā)車間隔;Hmax為最 大發(fā)車間隔;Qd為公交車額定載客量;Nk為時段k所需車 輛數(shù);T。為車輛的周轉時間;fk為時段k的發(fā)車頻率;n為 第k時段車輛的周轉系數(shù)n = Tk/T0遺傳算法應用于公交車調(diào)度能夠在排班優(yōu)化問題的巨大搜索空間 中可靠地找到近似最優(yōu)解。在具體運算過程中,對乘客流量時間分布 的設置具有很大的假設性,同時認為公交車勻速行駛也不符合實際情 況。但是遺傳算法的收斂性并不依賴于乘客的分布形式或道路的通行 狀況。改進遺傳算法比遺傳算法在迭代全程表現(xiàn)出更好的收斂速度性能。尤其在
6、進化末期,改進遺傳算法也保持著相當?shù)倪m值下降趨勢。改進遺傳算法的收斂效果隨種群的增大而增大。 在引入適值模擬退火拉伸 思想后的改進遺傳算法,能較好地克服遺傳算法前期進化早熟和后期 進化速度緩慢等問題。車輛路徑問題(vehicle routing problem, VRP是指對一系列發(fā)貨點 或收貨點,組成適當?shù)男熊嚶窂?,使車輛有序通過它們,在滿足一定 約束條件的情況下,達到一定的目標(如路程最短、費用最小、耗費 時間盡量少等),屬于完全NP問題。帶時間窗的車輛路徑問題(vehicle routing problem with time windows, VRPTW)是在 VRP問題上加了客戶 要
7、求訪問的時間窗口(如郵政投遞、火車及公共汽車的調(diào)度等) 。先 后有一般啟發(fā)式算法和神經(jīng)網(wǎng)絡、 遺傳算法、 禁忌搜索和模擬退火等 智能化啟發(fā)式算法。還有仿生算法,如模擬鳥群飛行的粒子群算法, 有著個體數(shù)目少、計算簡單、魯棒性好等優(yōu)點,在各類多維連續(xù)空間 優(yōu)化問題上均取得非常好的效果。以及蟻群算法。有時間窗車輛路徑問題的描述及數(shù)學模型:有L項運輸任務(以i表示),i=12L,已知任務i的客運量為g, 配送中心有m輛相同型號的車輛,車輛容量為q,對每輛車執(zhí)行的任 務點有gi q;同時,每項任務都要在規(guī)定時間內(nèi)完成,完成任務i需要的時間為T,任務i的開始時間si要在一定的時間范圍可口內(nèi), 邊界分別為任
8、務 i 的最早開始時間和最晚開始時間;若在車輛行駛線 路上任務i為任務j的前驅,車輛由i行駛到j需要時間5,則有 sj = (si + Ti + tij )成立;問題的優(yōu)化目標為求解滿足客運量要求的費 用(所需車輛或時間、距離等產(chǎn)生的運輸成本) 最小的車輛調(diào)度方案。定義變量:xijk1 車輛 k 從點 i 行駛到點 j0 否則yki =1點i的任務由車輛k完成0 否則cij :從點 i 到點 j 的運輸成本rk :車輛的最長工作時間minZ= i=0數(shù)學模型如下:m k=1L j=1x0jk mm k=1Li=0 xijk= 1 j =1 .LmK=1Lj=0 xijk=1 i=1LmLx0j
9、kmLk=1i=1-k=1jL=1 xLI=1giyki qs.t.j0k = 0j=0k=1 cij xijkSj j = 1 LS0=T0=0Km=1iL=0 xijk si + Ti + tiji=o j=o Xijktij rk k= 1 m蟻群算法的基本規(guī)則按照固定的模式更新信息量和確定路徑選擇 概率,忽略算法搜索的實際狀態(tài),往往產(chǎn)生加速收斂和防止早熟、停 滯現(xiàn)象的矛盾。因此采用根據(jù)搜索狀態(tài)動態(tài)調(diào)整算法路徑選擇策略和 信息量更新策略, 以求在加速收斂和防止停滯之間取得平衡甚為重要粒子群算法中,每個備選解被稱為一個粒子,多個粒子共存、合 作尋優(yōu),每個粒子根據(jù)它自身的經(jīng)驗和相鄰粒子群的最佳經(jīng)驗在問題 空間中向更好的位置飛行, 搜索最優(yōu)解。 在對典型連續(xù)非線性多維函 數(shù)使用粒子群算法尋優(yōu)的經(jīng)驗研究中, 發(fā)現(xiàn)粒子數(shù)與尋優(yōu)結果的相關 性不大; 通過自適應修改慣量的方法, 可以克服在非常復雜空間尋優(yōu) 時收斂于局部最優(yōu)解的問題。單 VRPTW屬于整數(shù)規(guī)劃問題,試驗中 采用自適應修改慣量的方法,并未能解決收斂于
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 服裝倉庫承包合同模板
- 車輛保險談判合同模板
- 土地春耕保合同模板
- 個人財務轉讓合同模板
- 供水設備項目合同模板
- 綠化景觀施工合同模板
- 最租房合同模板pdf
- 廢舊工廠拆遷合同模板
- 普通工種合同模板
- 法人投資入股合同模板
- 班級環(huán)境美化的具體措施計劃
- 2024年高等教育自學考試自考《英語二》試卷及解答參考
- 2025年高考語文一輪復習文言文實詞專練:課內(nèi)文言實詞遷移訓練(三)
- 期中(1至2單元)作業(yè)題(試題)-2024-2025學年一年級上冊數(shù)學青島版
- 牛津譯林版英語2024七年級上冊全冊單元知識清單(默寫版)
- 北師大版數(shù)學七年級上冊單元試卷【全冊合集】
- 《新質(zhì)生產(chǎn)力:發(fā)展新動能》筆記
- 小學生誠信教育主題班會 誠信伴我行守護真善美 課件
- 《8和9的加減法》(省一等獎)課件
- 《人像攝影》PPT課件(完整版)
- 有毒有害氣體應急預案;
評論
0/150
提交評論