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

1、公交車輛調(diào)度問題是指針對(duì)一項(xiàng)可分解的運(yùn)輸任務(wù)，在一定的約 束條件下，如何合理安排其組織部分占用資源、 運(yùn)作時(shí)間及先后順序， 以獲得運(yùn)輸成本或時(shí)間最優(yōu)化。包含兩層含義：1.編制行車時(shí)刻表，稱為靜態(tài)調(diào)度； 2.由于某種路況信息或突發(fā)事件，使靜態(tài)調(diào)度做出修 改、更新，稱為動(dòng)態(tài)調(diào)度。傳統(tǒng)的調(diào)度理論方法多采用數(shù)學(xué)解析法、運(yùn)籌學(xué)方法和經(jīng)驗(yàn)?zāi)Ｐ?等。隨著調(diào)度問題計(jì)算復(fù)雜性及問題規(guī)模的擴(kuò)大， 傳統(tǒng)方法遇到了很 大的困難。 人工智能為調(diào)度問題研究開辟了新的道路。 現(xiàn)有的研究方 法有： 1.應(yīng)用標(biāo)準(zhǔn)遺傳算法進(jìn)行公交靜態(tài)調(diào)度優(yōu)化； 2.蟻群算法思想 解決車輛優(yōu)化調(diào)度問題；3基于公交運(yùn)營(yíng)效益最大化的BRT調(diào)度問題 的

2、數(shù)學(xué)模型，并設(shè)計(jì)了優(yōu)化該問題的禁忌算法；4.粒子群算法解決帶時(shí)間窗的公交路徑優(yōu)化問題?；诟倪M(jìn)遺傳算法在靜態(tài)調(diào)度中的應(yīng)用，以公交營(yíng)運(yùn)商和乘客費(fèi) 用（包括乘客等車時(shí)間費(fèi)用和車上等待時(shí)間費(fèi)用）最小為目標(biāo)，建立 公交調(diào)度優(yōu)化的數(shù)學(xué)模型，在遺傳算法中引入模擬退火算法的思想， 研究改進(jìn)的遺傳算法在公交調(diào)度中應(yīng)用的基本方法和基本理論。公交調(diào)度優(yōu)化問題表現(xiàn)為兩個(gè)方面的利益最大化： 1.企業(yè)的收益； 2.乘客利益。且乘客利益優(yōu)先于企業(yè)利益。該問題的研究對(duì)象有公交 公司和乘客兩部分組成。公交公司希望提供盡量大的發(fā)車間隔，發(fā)車次數(shù)盡量少，單位車輛上座率盡量高，以減少其可變成本，增加運(yùn)營(yíng)收入；乘客則要求獲得更快捷的

3、服務(wù)，減低等車、車上和換乘費(fèi)用;3. 減少公交公司費(fèi)用意味著增加乘客費(fèi)用，反之亦然。因此，需要從公交乘客和公交公司雙方利益最大化出發(fā)，根據(jù)公交車輛實(shí)際運(yùn)營(yíng)時(shí)乘客流量在時(shí)間上的不均衡規(guī)律，以極小化公交公司和 乘客費(fèi)用總和為目標(biāo)，對(duì)發(fā)車間隔采用分時(shí)段多目標(biāo)組合優(yōu)化處理的 思想，在合理假設(shè)的前提下建立優(yōu)化模型。營(yíng)運(yùn)成本 Co=/K ) J(Tk/Hk)K為時(shí)段總數(shù)，將一天劃分為 K個(gè)時(shí)段；Tk為第k時(shí)段公 交車營(yíng)運(yùn)時(shí)間；Hk為第k時(shí)段的發(fā)車間隔；為公交車的 單車營(yíng)運(yùn)成本出行者費(fèi)用Cu由乘客候車耗時(shí)費(fèi)用Cub與不下車乘客由于 公交站點(diǎn)停車所消耗的時(shí)間費(fèi)用Ccb組成：Cu =Cub + Ccb1JCub

4、=-( 山/K) k=i J=i (UkjHk)*為乘客單位時(shí)間價(jià)值；Ukj為k時(shí)段、第j站的乘客到站 密度，假設(shè)服從均勻分布；J為公交站點(diǎn)數(shù)C =上1CCb = Kk=iJ=i Dkj?；q： +:q；HkPkji Pkj2為k時(shí)段j站點(diǎn)上下車乘客需求；q1q2為上下車平均速率；Dkj為k時(shí)段j站點(diǎn)的不下車乘客數(shù)j- 1Dkj =(Bkm - Akm )m=1Bkm為k時(shí)段j站點(diǎn)的上課乘客數(shù)；Akm為k時(shí)段j站點(diǎn)的 下車乘客數(shù)。優(yōu)化模型：選取權(quán)重和方法作為多目標(biāo)函數(shù)優(yōu)化算法，得到目標(biāo)函數(shù)f,待求變量為發(fā)車間隔Hkmin f= aC0 + 約束條件為：Hmin W Hk 70%kNY Nk/7

5、* * 丁 A %N* = i 12 * * t K F(A*T. 丁oa為權(quán)重系數(shù)，取正數(shù)；Hmin為最小發(fā)車間隔；Hmax為最 大發(fā)車間隔；Qd為公交車額定載客量；Nk為時(shí)段k所需車 輛數(shù)；T。為車輛的周轉(zhuǎn)時(shí)間；fk為時(shí)段k的發(fā)車頻率；n為 第k時(shí)段車輛的周轉(zhuǎn)系數(shù)n = Tk/T0遺傳算法應(yīng)用于公交車調(diào)度能夠在排班優(yōu)化問題的巨大搜索空間 中可靠地找到近似最優(yōu)解。在具體運(yùn)算過程中，對(duì)乘客流量時(shí)間分布 的設(shè)置具有很大的假設(shè)性，同時(shí)認(rèn)為公交車勻速行駛也不符合實(shí)際情 況。但是遺傳算法的收斂性并不依賴于乘客的分布形式或道路的通行 狀況。改進(jìn)遺傳算法比遺傳算法在迭代全程表現(xiàn)出更好的收斂速度性能。尤其在

6、進(jìn)化末期，改進(jìn)遺傳算法也保持著相當(dāng)?shù)倪m值下降趨勢(shì)。改進(jìn)遺傳算法的收斂效果隨種群的增大而增大。 在引入適值模擬退火拉伸 思想后的改進(jìn)遺傳算法，能較好地克服遺傳算法前期進(jìn)化早熟和后期 進(jìn)化速度緩慢等問題。車輛路徑問題（vehicle routing problem, VRP是指對(duì)一系列發(fā)貨點(diǎn) 或收貨點(diǎn)，組成適當(dāng)?shù)男熊嚶窂?，使車輛有序通過它們，在滿足一定 約束條件的情況下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用最小、耗費(fèi) 時(shí)間盡量少等），屬于完全NP問題。帶時(shí)間窗的車輛路徑問題（vehicle routing problem with time windows, VRPTW）是在 VRP問題上加了客戶 要

7、求訪問的時(shí)間窗口（如郵政投遞、火車及公共汽車的調(diào)度等） 。先 后有一般啟發(fā)式算法和神經(jīng)網(wǎng)絡(luò)、 遺傳算法、 禁忌搜索和模擬退火等 智能化啟發(fā)式算法。還有仿生算法，如模擬鳥群飛行的粒子群算法， 有著個(gè)體數(shù)目少、計(jì)算簡(jiǎn)單、魯棒性好等優(yōu)點(diǎn)，在各類多維連續(xù)空間 優(yōu)化問題上均取得非常好的效果。以及蟻群算法。有時(shí)間窗車輛路徑問題的描述及數(shù)學(xué)模型：有L項(xiàng)運(yùn)輸任務(wù)（以i表示），i=12L,已知任務(wù)i的客運(yùn)量為g, 配送中心有m輛相同型號(hào)的車輛，車輛容量為q,對(duì)每輛車執(zhí)行的任 務(wù)點(diǎn)有g(shù)i q；同時(shí)，每項(xiàng)任務(wù)都要在規(guī)定時(shí)間內(nèi)完成，完成任務(wù)i需要的時(shí)間為T，任務(wù)i的開始時(shí)間si要在一定的時(shí)間范圍可口內(nèi)， 邊界分別為任

8、務(wù) i 的最早開始時(shí)間和最晚開始時(shí)間；若在車輛行駛線 路上任務(wù)i為任務(wù)j的前驅(qū)，車輛由i行駛到j(luò)需要時(shí)間5,則有 sj = （si + Ti + tij ）成立；問題的優(yōu)化目標(biāo)為求解滿足客運(yùn)量要求的費(fèi) 用（所需車輛或時(shí)間、距離等產(chǎn)生的運(yùn)輸成本） 最小的車輛調(diào)度方案。定義變量：xijk1 車輛 k 從點(diǎn) i 行駛到點(diǎn) j0 否則yki =1點(diǎn)i的任務(wù)由車輛k完成0 否則cij ：從點(diǎn) i 到點(diǎn) j 的運(yùn)輸成本rk ：車輛的最長(zhǎng)工作時(shí)間minZ= i=0數(shù)學(xué)模型如下：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ī)則按照固定的模式更新信息量和確定路徑選擇 概率，忽略算法搜索的實(shí)際狀態(tài)，往往產(chǎn)生加速收斂和防止早熟、停 滯現(xiàn)象的矛盾。因此采用根據(jù)搜索狀態(tài)動(dòng)態(tài)調(diào)整算法路徑選擇策略和 信息量更新策略， 以求在加速收斂和防止停滯之間取得平衡甚為重要粒子群算法中，每個(gè)備選解被稱為一個(gè)粒子，多個(gè)粒子共存、合 作尋優(yōu)，每個(gè)粒子根據(jù)它自身的經(jīng)驗(yàn)和相鄰粒子群的最佳經(jīng)驗(yàn)在問題 空間中向更好的位置飛行， 搜索最優(yōu)解。 在對(duì)典型連續(xù)非線性多維函 數(shù)使用粒子群算法尋優(yōu)的經(jīng)驗(yàn)研究中， 發(fā)現(xiàn)粒子數(shù)與尋優(yōu)結(jié)果的相關(guān) 性不大； 通過自適應(yīng)修改慣量的方法， 可以克服在非常復(fù)雜空間尋優(yōu) 時(shí)收斂于局部最優(yōu)解的問題。單 VRPTW屬于整數(shù)規(guī)劃問題，試驗(yàn)中 采用自適應(yīng)修改慣量的方法，并未能解決收斂于