基於最短路徑泰森多邊形的電動汽車充電站搜索方法與流程
2023-12-09 17:06:16 2
本發明屬於車聯網技術領域，尤其是涉及一種基於最短路徑泰森多邊形的電動汽車充電站搜索方法。
背景技術：
隨著新能源汽車的推廣，需要建設足夠覆蓋面積的充電樁作為電動汽車能源的主要供給方式。泰森多邊形是對空間平面的一種剖分，其特點是:1)任何一個多邊形內的任何位置離該多邊形內的離散點的距離最近，離相鄰多邊形內離散點的距離遠，2)每個泰森多邊形內僅含有一個離散點，3)位於泰森多邊形邊上的點到其兩邊的離散點的距離相等。
傳統充電設施規劃方式是以一定長度為半徑,通過畫圓的方式形成電動汽車充電站的服務範圍，這種方式往往存在服務範圍無法實現全面覆蓋、覆蓋範圍存在重疊，或者所確定的服務範圍相對與電動汽車來講並非是最優的選擇。這就造成用戶搜尋最近設施的困難，無法最快定位距離用戶最近的設施。泰森基於多邊形方法，可以合理涵蓋所有區域，實現全覆蓋、不重疊，快速知道距離用戶最近的充電設施。
電動汽車剛處於發展階段，充電設施的選址規劃遠遠達不到傳統加油站的普及程度，目前只是在自貿區、大型停車場、醫院的區域分布，加之本身續航等因素，基於最短路徑的充電設施路徑選取的重要意義日益凸顯。傳統路徑選取需要建立模型分析，求解計算並分析靈敏度，不僅過程複雜，耗時費力，而且模型覆蓋區域會出現空白或重疊的現象，結果的準確程度也是有待考證。
技術實現要素：
有鑑於此，本發明旨在提出一種基於最短路徑泰森多邊形的電動汽車充電站搜索方法。
為達到上述目的，本發明的技術方案是這樣實現的：
一種基於最短路徑泰森多邊形的電動汽車充電站搜索方法，包括如下步驟：
S1，獲得所在區域可用的所有充電站的具體地理位置，以每個充電站所在的位置作為離散點，構建Delaunay三角形網絡；
S2，求得Delaunay三角網內所有三角形的外接圓，記錄外接圓的圓心位置；依次連接離散點周圍的Delaunay三角形外接圓的圓心，得到離散點的泰森多邊形；
S3，車聯網系統根據上述泰森多邊形和離散點信息搜索距離電動汽車最便捷的充電站所在位置並反饋給電動汽車，其中車聯網系統實時收集車輛和充電站信息。
進一步的，在步驟S3中搜索距離電動汽車最便捷的充電站的方法包括如下步驟：
S31，求得電動汽車所在位置A點到每個離散點的最短路徑S1，S2，S3,……，取其中最短和次短的兩條路徑，並記下它們所對應的兩個離散點P1、P2，將得到的這兩條路線合成連通的一條路徑為L；
S32，在L上找一個點P,使P點到兩個控制點P1，P2的最短路程相等(即P為L的中點)，則P點是由P1、P2所控制的兩個擴展泰森多邊形的交點,點P作為兩個多邊形分界點，使得在PP1(PP2)上找不到一點B，使得B到其他控制點的最短路程小於B到P1(P2)的最短路程；
S33，車聯網系統實時跟蹤P1、P2充電設施的設備情況，用戶可根據實際情況自由選擇P1、P2，若用戶點為C，點C若在PP1上，可以沿PP1到P1，此時到P1距離最短；若C在PP1上，但選擇P2充電，則可以沿CP、PP2到P2，此時到P2的距離最短。
進一步的，步驟S2中，對於三角網邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構成泰森多邊形。
進一步的，步驟S2中，車聯網系統根據所得的泰森多邊形，可得到各充電站通過泰森多邊形得到的供電區域範圍；車聯網平臺對供電區域範圍的輪廓邊界、外接圓圓心、半徑信息進行記錄。
進一步的，還包括步驟S4，在電動汽車未到達目標充電站地點前，如果目標點被佔據，則車聯網系統返回步驟S1，去除已被佔用的離散點，根據記錄供電區域範圍的輪廓邊界、外接圓圓心、半徑信息重新構建Delaunay三角形網絡。
進一步的，還包括步驟S4，在電動汽車未到達目標充電站地點前，如果目標點被佔據，則車聯網系統返回步驟S1，去除已被佔用的離散點，重新構建Delaunay三角形網絡。
相對於現有技術，本發明具有以下優勢：
(1)依託車聯網技術，通過GPS、RFID、傳感器、攝像頭圖像處理裝置、中心處理器等技術手段，車輛可以完成自身環境和狀態信息的採集；通過網際網路技術，所有的車輛可以將自身的各種信息、充電站離散點信息傳輸匯聚到中央處理器；通過計算機技術，這些大量的信息可以被分析和處理，重新計算泰森多邊形，從而計算出不同車輛的最佳路線。
(2)當電動汽車行駛至某一點，因電池電量不足報警或其他原因需要進行充電服務。此時需要在地圖上尋找充電站進行充電，通過對區域內所有充電站站點供電服務區域進行泰森多邊形剖分分析，得到距車輛最近的充電站推送給需求車輛，方便車輛及時進行充電。基於泰森多邊形對整體區域進行劃分，可以達到無需測距的定位方法，降低路徑選取難度。
附圖說明
構成本發明的一部分的附圖用來提供對本發明的進一步理解，本發明的示意性實施例及其說明用於解釋本發明，並不構成對本發明的不當限定。在附圖中：
圖1為本發明實施例充電站選址點作為離散點，建立的散點集；
圖2為本發明實施例構建的Delaunay三角形網絡。
圖3為本發明實施例的泰森多邊形剖分圖。
具體實施方式
需要說明的是，在不衝突的情況下，本發明中的實施例及實施例中的特徵可以相互組合。
下面將參考附圖並結合實施例來詳細說明本發明。
本發明基於最短路徑泰森多邊形的電動汽車充電站搜索方法，以天津機場自貿區為例進行說明，
步驟1，獲得自貿區此時可用的所有充電站的具體地理位置，以每個充電站所在的位置作為離散點，如圖1所示，構建Delaunay三角形網絡，本實施例採用如下Lawson算法構建Delaunay三角形網絡，如圖2所示：
1)確定所有已建的充電設施的具體地理位置，並以散點的方式順序標註在圖中，所有散點構成點集V；
2)構建一個超級三角形，包含點集V內的所有散點，放入三角形鍊表；
3)將點集V中的散點依次插入，在三角形鍊表中找出其外接圓包含插入點的三角形(稱為該點的影響三角形)，刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連接起來，從而完成一個點在Delaunay三角形鍊表中的插入；
4)根據優化準則對局部新形成的三角形進行優化，將形成的三角形放入Delaunay三角形鍊表；
5)循環執行上述第3)步，直到所有散點插入完畢。此時已構建完Delaunay三角網。
步驟2，求得Delaunay三角網內所有三角形的外接圓，記錄外接圓的圓心位置；依次連接散點周圍的Delaunay三角形外接圓的圓心，得到離散點的泰森多邊形；其中，對於三角網邊緣的泰森多邊形，可作垂直平分線與圖廓(及自貿區邊界)相交，與圖廓一起構成泰森多邊形，如圖3所示；根據所得的泰森多邊形，可得到各充電站通過泰森多邊形得到的供電區域範圍；車聯網平臺對供電區域範圍的輪廓邊界、外接圓圓心、半徑等信息進行記錄，方便以後重新繪製泰森多邊形，提高運行速度；構建泰森多邊形的步驟具體為：
1)對離散點和Delaunay三角網中的三角形編號，記錄每個三角形是由哪三個離散點構成；
2)找出與每個離散點相鄰的所有三角形的編號，並記錄下來，即只要在已構建的Delaunay三角網中找出具有一個相同頂點的所有三角形即可；
3)對與每個離散點相鄰的三角形按順時針或逆時針方向排序，以便下一步連接生成泰森多邊形；假設離散點為o，找出以o為頂點的一個三角形，設為A；取三角形A除o以外的另一頂點，設為a，則另一個頂點也可找出，即為f；則下一個三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點為e，則下一三角形是以oe為邊的；如此重複進行，直到回到oa邊；
4)計算每個三角形的外接圓圓心，並記錄之；
5)根據每個離散點的相鄰三角形，連接這些相鄰三角形的外接圓圓心，即得到泰森多邊形。
6)將繪製區域的邊界與實際邊界進行對比，剪裁，保證結果的準確性。上述步驟6)將繪製區域的邊界與實際邊界進行對比剪裁的具體方法為：
61)將自貿區邊界頂點和構建的泰森多邊形最外層的頂點定向排序；
62)找出目標規劃區域多邊形和已構建泰森多邊形的交叉點，並將這些點按順序插入預先建立的用於存儲裁剪結果的泰森多邊形頂點鍊表。
63)選取任一個交點為起點，將其輸出到62)的頂點鍊表中。
64)若該交點為出點(已構建的泰森多邊形為被剪裁多邊形，從被剪裁對象來看，由內到外穿出的交點稱為出點，反之是入點，出點與入點成對出現)，便開始跟蹤計算區域多邊形的頂點，否則跟蹤泰森多邊形頂點。
65)跟蹤泰森多邊形，將頂點輸出到結果多邊形頂點鍊表中，直至遇到新的交點。
66)將新的交點輸出到結果多邊形的頂點鍊表中，如果在第64)步中跟蹤的是泰森多邊形，那麼就跟蹤計算區域多邊形，反之類似。
67)重複第(6)、第(7)步，直至回到起點，形成一個結果多邊形。
68)重複第(7)～(12)步，直至所有的交點都被訪問過。
步驟3，車聯網系統根據上述泰森多邊形和離散點信息搜索距離電動汽車最便捷的充電站所在位置並反饋給電動汽車，其中車聯網系統實時收集車輛和充電站信息；搜索最便捷的充電站的方法包括如下步驟：
1)求得電動汽車所在位置A點到每個離散點的最短路徑S1，S2，S3,……，取其中最短和次短的兩條路徑，並記下它們所對應的兩個離散點P1、P2，將得到的這兩條路線合成連通的一條路徑為L；
2)在L上找一個點P,使P點到兩個控制點P1，P2的最短路程相等，即P為L的中點，則P點是由P1、P2所控制的兩個擴展泰森多邊形的交點；以P點為界，L的兩段(可設為PP1，PP2)分屬於這兩個基於最短路徑的擴展泰森多邊形；使得在PP1、PP2上找不到一點B，使得B到其他控制點的最短路程小於B到P1、P2的最短路程；
3)車聯網系統實時跟蹤P1、P2充電設施的設備情況，用戶可根據實際情況自由選擇P1、P2，若用戶點為C，點C若在PP1上，可以沿PP1到P1，此時到P1距離最短；若C在PP1上，但選擇P2充電，則可以沿CP、PP2到P2，此時到P2的距離最短結合導航系統，判斷電動汽車此時所在位置是否在PP1或PP2上，如果均不在，判斷電動汽車此時所在位置所屬的道路是否與PP1或PP2有交叉；如果在PP1上或者與PP1有交叉則選擇P1所指的充電站為目的地行駛；否則選擇P2所指的充電站為目的地行駛。
另外，在電動汽車未到達目標充電站地點前，如果目標點被佔據，則車聯網系統返回步驟1，去除已被佔用的離散點，重新構建Delaunay三角形網絡。
傳統的泰森多邊形是對空間不考慮實際路徑的一種分割方式,使得其在很多領域的應用受到了限制,尤其是在城市規劃和沿路徑分析等方面表現更為突出。所以只依靠泰森多邊形進行定位還達不到實際需求，電動汽車的發展速度快於充電設施建設速度，往往出現無樁可用的現象，這就需要重新生成泰森多邊形，對路徑重新規劃，通過車聯網系統進行解決。
本發明車聯網系統，是指通過在車輛儀表臺安裝車載終端設備，實現對車輛所有工作情況和靜、動態信息的採集、存儲並發送。系統分為三大部分：車載終端、雲計算處理平臺、數據分析平臺。車輛的運行往往涉及多項開關量、傳感器模擬量、CAN信號數據等等，駕駛員在操作車輛運行過程中，產生的車輛數據不斷回發到後臺資料庫，形成海量數據，由雲計算處理平臺實現對海量數據的「過濾清洗」，數據分析平臺對數據進行報表式處理，供管理人員查看。
依託車聯網技術，通過GPS、RFID、傳感器、攝像頭圖像處理裝置、中心處理器等技術手段，車輛可以完成自身環境和狀態信息的採集；通過網際網路技術，所有的車輛可以將自身的各種信息、充電站離散點信息傳輸匯聚到中央處理器；通過計算機技術，這些大量的信息可以被分析和處理，重新計算泰森多邊形，從而計算出不同位置車輛搜索充電站的最佳路線。
以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。