[發(fā)明專(zhuān)利]一種基于組合拍賣(mài)算法的城市公交實(shí)時(shí)調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201811383523.3
• 申請(qǐng)日: 2018-11-20
• 公開(kāi)（公告）號(hào): CN109523172A
• 公開(kāi)（公告）日: 2019-03-26
• 發(fā)明（設(shè)計(jì)）人: 李湘黔
• 申請(qǐng)（專(zhuān)利權(quán)）人: 湖南智慧暢行交通科技有限公司
• 主分類(lèi)號(hào): G06Q10/06
• 分類(lèi)號(hào): G06Q10/06;G06Q10/10;G06Q50/30
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明涉及公交實(shí)時(shí)調(diào)度方法技術(shù)領(lǐng)域，尤其為一種基于組合拍賣(mài)算法的城市公交實(shí)時(shí)調(diào)度方法，是利用公交車(chē)輛智能終端設(shè)備傳輸給調(diào)度監(jiān)控中心的時(shí)間和GPS位置信息判斷事故車(chē)輛發(fā)生的時(shí)間和位置，根據(jù)時(shí)刻表計(jì)算出每?jī)商酥g的價(jià)值矩陣，這里主要是兩趟之間的連接需要運(yùn)行的時(shí)間，從而運(yùn)用前向和后向組合的拍賣(mài)算法，得到最終的調(diào)度方案。本發(fā)明，可以在營(yíng)運(yùn)車(chē)輛發(fā)生突發(fā)狀況導(dǎo)致車(chē)輛無(wú)法按照既定的計(jì)劃時(shí)刻表運(yùn)行的時(shí)候，在給定車(chē)輛和司機(jī)的情況下，對(duì)剩余營(yíng)運(yùn)時(shí)段迅速作出合理的調(diào)度決策，并及時(shí)上報(bào)給公交企調(diào)度監(jiān)控中心，在保證乘客服務(wù)水平的前提下，盡可能的使公交企業(yè)付出的額外成本最小，保證了調(diào)度低延時(shí)的基本原則。

技術(shù)領(lǐng)域

本發(fā)明涉及公交實(shí)時(shí)調(diào)度方法技術(shù)領(lǐng)域，具體為一種基于組合拍賣(mài)算法的城市公交實(shí)時(shí)調(diào)度方法。

背景技術(shù)

公交車(chē)輛實(shí)時(shí)調(diào)度是指公交企業(yè)實(shí)時(shí)發(fā)現(xiàn)營(yíng)運(yùn)車(chē)輛發(fā)生突發(fā)事故而導(dǎo)致無(wú)法按照計(jì)劃的時(shí)刻表繼續(xù)運(yùn)行時(shí)，公交企業(yè)迅速做出合理的調(diào)度決策，使得后續(xù)的公交營(yíng)運(yùn)時(shí)段能正常的運(yùn)行。傳統(tǒng)公交企業(yè)的公交調(diào)度系統(tǒng)是由調(diào)度室及排班人員組成，依靠公交線路上的調(diào)度人員根據(jù)經(jīng)驗(yàn)及車(chē)輛的到達(dá)情況每天制定調(diào)度計(jì)劃，實(shí)際公交運(yùn)營(yíng)過(guò)程中，還主要依靠調(diào)度人員調(diào)度安排車(chē)輛發(fā)車(chē)時(shí)刻和班次，但在實(shí)際運(yùn)營(yíng)過(guò)程中，計(jì)劃趕不上變化，單純照搬安排好的調(diào)度策略(在靜態(tài)調(diào)度模式中包括發(fā)出時(shí)刻表編排，運(yùn)力安排等)是不可能的。交通擁堵、惡劣天氣、不良事件對(duì)既有調(diào)度計(jì)劃存在不同程度的干擾，盡可能貼近原開(kāi)行方案，盡可能縮小實(shí)際情況與計(jì)劃之間的差距是我們所要重點(diǎn)關(guān)注的。減小這種差距的最好辦法就是施行動(dòng)態(tài)調(diào)度，即實(shí)時(shí)調(diào)度。基于調(diào)度經(jīng)驗(yàn)?zāi)Ｊ降膫鹘y(tǒng)公交調(diào)度應(yīng)變能力較差，不能保證經(jīng)驗(yàn)數(shù)據(jù)的準(zhǔn)確性，無(wú)法及時(shí)應(yīng)對(duì)客流的動(dòng)態(tài)變化，使得公交調(diào)度系統(tǒng)的整體運(yùn)行效率大大降低，增加了公交運(yùn)營(yíng)企業(yè)的成本。在現(xiàn)有的技術(shù)方案中，例如像遺傳算法，粒子群算法等啟發(fā)式算法進(jìn)行對(duì)公交車(chē)輛實(shí)時(shí)調(diào)度優(yōu)化是個(gè)不錯(cuò)的選擇。但是，顯然針對(duì)不同的應(yīng)用場(chǎng)景，現(xiàn)有研究的算法難以通用化，特別是大規(guī)模、高實(shí)時(shí)性的車(chē)輛調(diào)度問(wèn)題，傳統(tǒng)啟發(fā)式算法是難以在實(shí)際生產(chǎn)中達(dá)到實(shí)時(shí)性的需求，而且啟發(fā)式算法對(duì)初始種群較為敏感。

例如文獻(xiàn)《基于GPS/GIS協(xié)同的動(dòng)態(tài)車(chē)輛調(diào)度和路徑規(guī)劃問(wèn)題研究》采用混合遺傳算法，對(duì)復(fù)雜環(huán)境下基于實(shí)時(shí)信息的動(dòng)態(tài)物流配送路徑優(yōu)化模型進(jìn)行求解，從而實(shí)現(xiàn)GPS/GIS協(xié)同下的實(shí)時(shí)動(dòng)態(tài)車(chē)輛調(diào)度，該方法，可以實(shí)現(xiàn)對(duì)物流配送過(guò)程和車(chē)輛運(yùn)行路徑的動(dòng)態(tài)調(diào)整和優(yōu)化，但遺傳算法對(duì)初始的種群以及最大的迭代次數(shù)等參數(shù)較為敏感，且容易陷入局部最優(yōu)解，無(wú)法保證全局最優(yōu)。

又如文獻(xiàn)《基于混合啟發(fā)式算法的單線公交車(chē)輛調(diào)度問(wèn)題研究》研究了基于混合啟發(fā)式算法的單線公交車(chē)輛調(diào)度問(wèn)題，建立了一種上下行發(fā)車(chē)頻率不同的公交組合調(diào)度模型。該模型結(jié)合了全程車(chē)調(diào)度和區(qū)間車(chē)調(diào)度，并進(jìn)行了更加符合實(shí)際情況的假設(shè)。針對(duì)該調(diào)度模型，提出了一種粒子群優(yōu)化算法和模式搜索算法相結(jié)合的混合啟發(fā)式算法，該算法能有效避免粒子群算法陷入局部最優(yōu)。但兩種算法的融合容易使算法的計(jì)算效率難以達(dá)到需求，尤其是車(chē)輛規(guī)模較大時(shí)。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種基于組合拍賣(mài)算法的城市公交實(shí)時(shí)調(diào)度方法，以解決上述背景技術(shù)中提出的問(wèn)題。該基于組合拍賣(mài)算法的城市公交實(shí)時(shí)調(diào)度方法計(jì)算出的調(diào)度方案更符合實(shí)際生產(chǎn)中乘客的需求和企業(yè)的利益。

為實(shí)現(xiàn)上述目的，本發(fā)明提供如下技術(shù)方案：

一種基于組合拍賣(mài)算法的城市公交實(shí)時(shí)調(diào)度方法，包括如下步驟：

步驟一：根據(jù)車(chē)輛排班時(shí)刻表，車(chē)輛實(shí)時(shí)位置和到離站信息判斷車(chē)輛實(shí)時(shí)位置是否發(fā)生異常，如有異常，則發(fā)生突發(fā)事故車(chē)輛的司機(jī)將相關(guān)的信息上報(bào)給調(diào)度監(jiān)控中心，確定發(fā)生異常的時(shí)間和地點(diǎn)，如未發(fā)現(xiàn)有異常，則按照原定計(jì)劃的時(shí)刻表進(jìn)行發(fā)車(chē)；

步驟二：根據(jù)發(fā)車(chē)時(shí)刻表構(gòu)建所有能解決此異常連接計(jì)劃上所有趟次的可能性網(wǎng)絡(luò)，如發(fā)生事故的車(chē)輛無(wú)法繼續(xù)營(yíng)運(yùn)，需要增加額外的車(chē)輛構(gòu)建連接網(wǎng)絡(luò)，則增加額外車(chē)輛進(jìn)行構(gòu)建；

步驟三：根據(jù)事先計(jì)劃的發(fā)車(chē)時(shí)刻表計(jì)算出每?jī)商酥g的價(jià)值矩陣；