[發(fā)明專利]基于公共交通的人員路線規(guī)劃方法及裝置

有效

• 申請?zhí)枺?/td>: 201910870544.6
• 申請日: 2019-09-16
• 公開（公告）號: CN110689174B
• 公開（公告）日: 2023-09-26
• 發(fā)明（設(shè)計）人: 張鋆;蔡如昕;林丹英;閔奕波;符海林;張建兵
• 申請（專利權(quán)）人: 深圳市威豹聯(lián)合金融服務(wù)有限公司;深圳市北斗智能科技有限公司
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06Q50/26;G06N3/126
• 代理公司: 廣州嘉權(quán)專利商標事務(wù)所有限公司 44205
• 代理人: 洪銘福

本發(fā)明公開了基于公共交通的人員路線規(guī)劃方法及裝置。涉及路線規(guī)劃領(lǐng)域，其中，方法通過獲取人員的出行信息，基于公共交通的路線信息獲取滿足出行信息的多條公共交通路線信息，根據(jù)節(jié)約算法從多條公共交通路線信息中獲取一條初始規(guī)劃路線，從獲取的所有初始規(guī)劃路線中生成大量初始種群，結(jié)合遺傳算法進行迭代得到最優(yōu)規(guī)劃路線?？朔爽F(xiàn)有技術(shù)中路線規(guī)劃效率低、計算成本高、規(guī)劃結(jié)果效果差或者基于人工經(jīng)驗缺乏變通性的缺點，能夠智能實現(xiàn)路線規(guī)劃，并且算法復(fù)雜度低、運行效率高，同時可以并行擴展計算，能夠處理大批量的數(shù)據(jù)?？蓮V泛應(yīng)用于路線規(guī)劃領(lǐng)域。

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

本發(fā)明涉及路線規(guī)劃領(lǐng)域，尤其是一種基于公共交通的人員路線規(guī)劃方法及裝置。

背景技術(shù)

根據(jù)業(yè)務(wù)需求規(guī)劃公共交通出行路線屬于NP-hard問題，隨著復(fù)雜度愈來愈高，傳統(tǒng)方法，例如人工經(jīng)驗法、線性規(guī)劃法、動態(tài)規(guī)劃法等，逐漸滿足不了問題的需求，傳統(tǒng)方法的計算精度高，能夠列出問題的全部可行解，并求出確定最優(yōu)解，但計算量非常大，只能解決一些非常簡單的、小規(guī)模路線排線規(guī)劃徑問題。所以尋找其他方法來解決現(xiàn)有路線規(guī)劃問題十分必要，隨著計算機的迅猛發(fā)展，啟發(fā)式算法在解決此類問題上表現(xiàn)出巨大優(yōu)勢，尤其是群體智能算法在解決路線規(guī)劃問題等上應(yīng)用非常廣泛。現(xiàn)有智能算法大多都能較快速地解決路線排線規(guī)劃，相比于人工調(diào)度而言優(yōu)勢顯然。但每種智能算法都有自身的缺點，僅僅用單種智能算法解決路線排線規(guī)劃問題，既容易陷入局部最優(yōu)，無法找到近似最優(yōu)解，迭代求解花費的時間也會十分長，不符合現(xiàn)實當中每日要求的實時計算。因此需要提出一種能夠智能調(diào)度路線，同時算法復(fù)雜度低運算效率高的基于公共交通人員路線規(guī)劃方法。

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

本發(fā)明旨在至少在一定程度上解決相關(guān)技術(shù)中的技術(shù)問題之一。為此，本發(fā)明的目的是提供一種能夠智能調(diào)度路線，同時算法復(fù)雜度低運算效率高的基于公共交通人員路線規(guī)劃方法。

本發(fā)明所采用的技術(shù)方案是：

第一方面，本發(fā)明提供一種基于公共交通的人員路線規(guī)劃方法，包括：

獲取人員的出行信息，所述出行信息包括：起始地址、目標地址、出發(fā)時間、業(yè)務(wù)時間窗；

基于公共交通的路線信息獲取滿足所述出行信息的多條公共交通路線信息，所述公共交通路線信息包括：路線用時、路線距離、具體交通方式；

根據(jù)節(jié)約算法從多條所述公共交通路線信息中獲取一條初始規(guī)劃路線；

從獲取的所有初始規(guī)劃路線中生成大量初始種群，結(jié)合遺傳算法進行迭代得到最優(yōu)規(guī)劃路線。

進一步地，還包括進行地圖經(jīng)緯度查詢，判斷所述起始地址和所述目標地址是否符合真實坐標信息。

進一步地，所述根據(jù)節(jié)約算法從多條所述公共交通路線信息中獲取一條初始規(guī)劃路線具體為：

選擇距離所述起始地址最近的站點，對其他的站點用節(jié)約算法進行評估判斷是否作為選中的站點，直至達到迭代條件，將所有選中的站點按照時間順序構(gòu)成所述初始規(guī)劃路線。

進一步地，通過隨機順序?qū)λ谐跏家?guī)劃路線進行排列，將每一種排列方式作為一個染色體，多個所述染色體構(gòu)成所述初始種群。

進一步地，所述遺傳算法的適應(yīng)性評價函數(shù)表示為：

其中，f_i(T)為第T代種群中染色體i的適應(yīng)值，z_i(T)為T代種群中染色體i的目標函數(shù)值，即染色體i對應(yīng)的運輸總成本。

進一步地，所述節(jié)約算法和所述遺傳算法在基于Hadoop分布式集群的spark架構(gòu)下實現(xiàn)運算過程。

第二方面，本發(fā)明還提供一種基于公共交通的人員路線規(guī)劃裝置，包括：