[發(fā)明專(zhuān)利]基于最短路徑泰森多邊形的電動(dòng)汽車(chē)充電站搜索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201611230831.3
• 申請(qǐng)日: 2016-12-28
• 公開(kāi)（公告）號(hào): CN106643783B
• 公開(kāi)（公告）日: 2020-06-09
• 發(fā)明（設(shè)計(jì)）人: 王小宇;劉易;姜浩;張郁靜;王晨飛;朱昊;黃子健
• 申請(qǐng)（專(zhuān)利權(quán)）人: 國(guó)網(wǎng)天津市電力公司東麗供電分公司
• 主分類(lèi)號(hào): G01C21/36
• 分類(lèi)號(hào): G01C21/36
• 代理公司: 天津?yàn)I海科緯知識(shí)產(chǎn)權(quán)代理有限公司 12211
• 代理人: 馬倩倩

本發(fā)明提供了一種基于最短路徑泰森多邊形的電動(dòng)汽車(chē)充電站搜索方法，包括如下步驟：S1，獲得所在區(qū)域可用的所有充電站的具體地理位置，以每個(gè)充電站所在的位置作為離散點(diǎn)，構(gòu)建Delaunay三角形網(wǎng)絡(luò)；S2，根據(jù)Delaunay三角網(wǎng)內(nèi)所有三角形的外接圓，得到離散點(diǎn)的泰森多邊形；S3，車(chē)聯(lián)網(wǎng)系統(tǒng)根據(jù)上述泰森多邊形和離散點(diǎn)信息搜索距離電動(dòng)汽車(chē)最便捷的充電站所在位置并反饋給電動(dòng)汽車(chē)，其中車(chē)聯(lián)網(wǎng)系統(tǒng)實(shí)時(shí)收集車(chē)輛和充電站信息。本發(fā)明通過(guò)對(duì)區(qū)域內(nèi)所有充電站站點(diǎn)供電服務(wù)區(qū)域進(jìn)行泰森多邊形剖分分析，得到距車(chē)輛最近的充電站推送給需求車(chē)輛，方便車(chē)輛及時(shí)進(jìn)行充電。

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

本發(fā)明屬于車(chē)聯(lián)網(wǎng)技術(shù)領(lǐng)域，尤其是涉及一種基于最短路徑泰森多邊形的電動(dòng)汽車(chē)充電站搜索方法。

背景技術(shù)

隨著新能源汽車(chē)的推廣，需要建設(shè)足夠覆蓋面積的充電樁作為電動(dòng)汽車(chē)能源的主要供給方式。泰森多邊形是對(duì)空間平面的一種剖分，其特點(diǎn)是:1)任何一個(gè)多邊形內(nèi)的任何位置離該多邊形內(nèi)的離散點(diǎn)的距離最近，離相鄰多邊形內(nèi)離散點(diǎn)的距離遠(yuǎn)，2)每個(gè)泰森多邊形內(nèi)僅含有一個(gè)離散點(diǎn)，3)位于泰森多邊形邊上的點(diǎn)到其兩邊的離散點(diǎn)的距離相等。

傳統(tǒng)充電設(shè)施規(guī)劃方式是以一定長(zhǎng)度為半徑,通過(guò)畫(huà)圓的方式形成電動(dòng)汽車(chē)充電站的服務(wù)范圍，這種方式往往存在服務(wù)范圍無(wú)法實(shí)現(xiàn)全面覆蓋、覆蓋范圍存在重疊，或者所確定的服務(wù)范圍相對(duì)與電動(dòng)汽車(chē)來(lái)講并非是最優(yōu)的選擇。這就造成用戶搜尋最近設(shè)施的困難，無(wú)法最快定位距離用戶最近的設(shè)施。泰森基于多邊形方法，可以合理涵蓋所有區(qū)域，實(shí)現(xiàn)全覆蓋、不重疊，快速知道距離用戶最近的充電設(shè)施。

電動(dòng)汽車(chē)剛處于發(fā)展階段，充電設(shè)施的選址規(guī)劃遠(yuǎn)遠(yuǎn)達(dá)不到傳統(tǒng)加油站的普及程度，目前只是在自貿(mào)區(qū)、大型停車(chē)場(chǎng)、醫(yī)院的區(qū)域分布，加之本身續(xù)航等因素，基于最短路徑的充電設(shè)施路徑選取的重要意義日益凸顯。傳統(tǒng)路徑選取需要建立模型分析，求解計(jì)算并分析靈敏度，不僅過(guò)程復(fù)雜，耗時(shí)費(fèi)力，而且模型覆蓋區(qū)域會(huì)出現(xiàn)空白或重疊的現(xiàn)象，結(jié)果的準(zhǔn)確程度也是有待考證。

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

有鑒于此，本發(fā)明旨在提出一種基于最短路徑泰森多邊形的電動(dòng)汽車(chē)充電站搜索方法。

為達(dá)到上述目的，本發(fā)明的技術(shù)方案是這樣實(shí)現(xiàn)的：

一種基于最短路徑泰森多邊形的電動(dòng)汽車(chē)充電站搜索方法，包括如下步驟：

S1，獲得所在區(qū)域可用的所有充電站的具體地理位置，以每個(gè)充電站所在的位置作為離散點(diǎn)，構(gòu)建Delaunay三角形網(wǎng)絡(luò)；

S2，求得Delaunay三角網(wǎng)內(nèi)所有三角形的外接圓，記錄外接圓的圓心位置；依次連接離散點(diǎn)周?chē)腄elaunay三角形外接圓的圓心，得到離散點(diǎn)的泰森多邊形；

S3，車(chē)聯(lián)網(wǎng)系統(tǒng)根據(jù)上述泰森多邊形和離散點(diǎn)信息搜索距離電動(dòng)汽車(chē)最便捷的充電站所在位置并反饋給電動(dòng)汽車(chē)，其中車(chē)聯(lián)網(wǎng)系統(tǒng)實(shí)時(shí)收集車(chē)輛和充電站信息。

進(jìn)一步的，在步驟S3中搜索距離電動(dòng)汽車(chē)最便捷的充電站的方法包括如下步驟：

S31，求得電動(dòng)汽車(chē)所在位置A點(diǎn)到每個(gè)離散點(diǎn)的最短路徑S1，S2，S3,……，取其中最短和次短的兩條路徑，并記下它們所對(duì)應(yīng)的兩個(gè)離散點(diǎn)P1、P2，將得到的這兩條路線合成連通的一條路徑為L(zhǎng)；

S32，在L上找一個(gè)點(diǎn)P,使P點(diǎn)到兩個(gè)控制點(diǎn)P1，P2的最短路程相等(即P為L(zhǎng)的中點(diǎn))，則P點(diǎn)是由P1、P2所控制的兩個(gè)擴(kuò)展泰森多邊形的交點(diǎn),點(diǎn)P作為兩個(gè)多邊形分界點(diǎn)，使得在PP1(PP2)上找不到一點(diǎn)B，使得B到其他控制點(diǎn)的最短路程小于B到P1(P2)的最短路程；

S33，車(chē)聯(lián)網(wǎng)系統(tǒng)實(shí)時(shí)跟蹤P1、P2充電設(shè)施的設(shè)備情況，用戶可根據(jù)實(shí)際情況自由選擇P1、P2，若用戶點(diǎn)為C，點(diǎn)C若在PP1上，可以沿PP1到P1，此時(shí)到P1距離最短；若C在PP1上，但選擇P2充電，則可以沿CP、PP2到P2，此時(shí)到P2的距離最短。