公交資源優(yōu)化配置

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ī)劃問題，試驗中 采用自適應修改慣量的方法，并未能解決收斂于