基于物聯(lián)網(wǎng)與GS算法的電動(dòng)汽車充電推薦系統(tǒng)

趙雅蘭，張大波，李鴻堯

（遼寧大學(xué) 信息學(xué)院，遼寧 沈陽(yáng) 110031）

0 引 言

在科技發(fā)展和綠色經(jīng)濟(jì)的推動(dòng)下，我國(guó)的電動(dòng)汽車行業(yè)如雨后春筍進(jìn)入高速發(fā)展時(shí)期。電動(dòng)汽車有效解決了日漸枯竭的自然資源與經(jīng)濟(jì)可持續(xù)發(fā)展之間的矛盾。電動(dòng)汽車逐漸走進(jìn)千家萬(wàn)戶的同時(shí)，電動(dòng)汽車充電所引發(fā)的“里程焦慮”（range anxiety）問(wèn)題也逐漸顯露出來(lái)。本文基于物聯(lián)網(wǎng)技術(shù)并運(yùn)用博弈論中的蓋爾-沙普利算法（Gale-Shapley algorithm, GS）為電動(dòng)汽車用戶與汽車充電站提供最佳的選擇方案，在保證充電站吞吐量的同時(shí)，解決車主“里程焦慮”的痛點(diǎn)。

1 國(guó)內(nèi)電動(dòng)汽車發(fā)展現(xiàn)狀

1.1 電動(dòng)汽車充電現(xiàn)狀

數(shù)據(jù)表明，我國(guó)電動(dòng)汽車的銷售量從2010年的不足1萬(wàn)輛一躍增長(zhǎng)到2020年的136.7萬(wàn)輛，2020年的電動(dòng)汽車銷售量占全球電動(dòng)汽車銷售量的41%。我國(guó)新能源汽車市場(chǎng)呈現(xiàn)良好的發(fā)展態(tài)勢(shì)。2019年電動(dòng)汽車的平均續(xù)航里程為362千米，現(xiàn)在也有超長(zhǎng)續(xù)航的電動(dòng)汽車亮相于大眾視野，例如，2020年比亞迪公司推出的“比亞迪漢EV”最長(zhǎng)續(xù)航里程可達(dá)605千米。而電動(dòng)汽車平均充滿電的時(shí)間需要花費(fèi)2小時(shí)，“比亞迪漢EV”充電至電池的80%，也需要0.42個(gè)小時(shí)。相較于傳統(tǒng)的燃油汽車幾分鐘加油時(shí)間可以續(xù)航600多千米來(lái)說(shuō)，電動(dòng)汽車確實(shí)有著明顯的短板。而就目前的充電樁數(shù)量和普及程度來(lái)看，與電動(dòng)汽車配套的基礎(chǔ)設(shè)施建設(shè)尚屬不完善階段。

1.2 現(xiàn)階段存在的問(wèn)題

由于電動(dòng)汽車存在充電相對(duì)較慢的技術(shù)壁壘和當(dāng)下基礎(chǔ)設(shè)施建設(shè)不完善的現(xiàn)狀，電動(dòng)汽車用戶都會(huì)在自己的電動(dòng)汽車電量低于某一閾值時(shí)產(chǎn)生對(duì)電車電量耗盡的恐懼，稱為“里程焦慮”。而反觀充電站，其在運(yùn)營(yíng)過(guò)程中，會(huì)有大量的電動(dòng)汽車進(jìn)行充電，由于沒(méi)有加油站那樣高效的吞吐量，電動(dòng)汽車的充電站常常會(huì)有眾多車主排長(zhǎng)隊(duì)等候充電，這對(duì)于駕駛員以及充電站附近的交通來(lái)說(shuō)都是難以忍受的。

現(xiàn)階段，有很多的充電站或充電樁沒(méi)有連接物聯(lián)網(wǎng)，駕駛員無(wú)法得知這些充電站的基本信息。而對(duì)于一些已經(jīng)聯(lián)網(wǎng)的充電站，雖然可以實(shí)時(shí)顯示站中充電樁的使用情況，但也有可能發(fā)生在駕駛員將電動(dòng)汽車開(kāi)到充電站時(shí)充電樁都被其他車輛占用的情況，駕駛員若想在此充電站充電則要花費(fèi)很長(zhǎng)的時(shí)間排隊(duì)等候。即便有了預(yù)約系統(tǒng)，可能會(huì)出現(xiàn)充電站中有空閑的充電樁，但由于充電樁已被預(yù)約，急需充電的汽車充不上電的情況。

2 解決方案

針對(duì)以上問(wèn)題提出電動(dòng)汽車選擇充電站的推薦系統(tǒng)，該系統(tǒng)將更多的充電站（充電樁）和電動(dòng)汽車進(jìn)行信息整合，采用窄帶物聯(lián)網(wǎng)技術(shù)（Narrow Band-Internet of Things, NB-IoT）進(jìn)行聯(lián)網(wǎng)，獲取充電站中充電樁的使用情況、站中預(yù)約汽車數(shù)量的實(shí)時(shí)情況和電動(dòng)汽車電池使用情況的數(shù)據(jù)等。這些數(shù)據(jù)上傳到云端后，根據(jù)用戶的選擇、當(dāng)前電池電量可以承載的里程、是否順路等情況得出各個(gè)電動(dòng)汽車選擇充電站的偏好，根據(jù)當(dāng)下充電站可以承載的充電數(shù)量、完成預(yù)約充電的時(shí)間，以及電動(dòng)汽車可以到達(dá)充電站且上一輛電車正好完成充電等因素得出充電站選擇汽車的偏好。在云端將兩方的偏好用GS算法進(jìn)行計(jì)算，可以得到既能使電動(dòng)汽車最快充上電，也能使充電站實(shí)現(xiàn)利用率最大化的一種分配方案，并將該方案實(shí)時(shí)傳送到電動(dòng)汽車的應(yīng)用程序和充電站的管理系統(tǒng)中。

3 系統(tǒng)架構(gòu)

本文提出的電動(dòng)汽車充電推薦系統(tǒng)的體系架構(gòu)如圖1所示。

圖1 電動(dòng)汽車充電推薦系統(tǒng)體系架構(gòu)

該體系架構(gòu)由安裝在汽車和充電站的NB-IoT、用于傳輸數(shù)據(jù)和實(shí)現(xiàn)推薦算法的業(yè)務(wù)處理云主機(jī)以及用來(lái)接收信息實(shí)現(xiàn)人機(jī)交互的充電站、電動(dòng)汽車和各手機(jī)終端三個(gè)部分組成。

3.1 NB-IoT終端

在電動(dòng)汽車、充電站中和充電樁上安裝物聯(lián)網(wǎng)的微控制器，可以進(jìn)行汽車的數(shù)據(jù)采集、數(shù)據(jù)的基本運(yùn)算以及數(shù)據(jù)通信。其中的數(shù)據(jù)的傳送采用NB-IoT技術(shù)，具有低功耗、覆蓋廣、速度快、成本低等優(yōu)點(diǎn)，非常適合這個(gè)場(chǎng)景。

3.2 基站和云服務(wù)器

NB-IoT基站是基于NB-IoT協(xié)議用于信息中轉(zhuǎn)的信息傳送系統(tǒng)。汽車和充電站將實(shí)時(shí)的狀態(tài)信息傳送到附近的基站，基站通過(guò)NB-IoT網(wǎng)絡(luò)將信息傳送到業(yè)務(wù)處理云主機(jī)，在云端的服務(wù)主機(jī)通過(guò)優(yōu)化的GS算法，得出在電動(dòng)汽車可以快速排隊(duì)的同時(shí)也能實(shí)現(xiàn)充電樁高效利用的最優(yōu)解，將這個(gè)最優(yōu)解記錄下來(lái)，并將輸出結(jié)果通過(guò)NB-IoT網(wǎng)絡(luò)傳到之前需要預(yù)約的車輛、充電站或者其他人機(jī)交互終端的附近基站。

3.3 人機(jī)交互各終端

人機(jī)交互各終端通過(guò)接收云端的業(yè)務(wù)處理主機(jī)傳送來(lái)的數(shù)據(jù)，進(jìn)行數(shù)據(jù)的展示。此時(shí)云主機(jī)可以對(duì)外提供數(shù)據(jù)獲取接口，各個(gè)應(yīng)用程序在獲得數(shù)據(jù)后，可通過(guò)瀏覽器、APP、小程序或車載應(yīng)用等完成人機(jī)頁(yè)面的互動(dòng)。

4 推薦系統(tǒng)中GS算法的應(yīng)用分析與系統(tǒng)實(shí)現(xiàn)

根據(jù)電動(dòng)汽車對(duì)于充電站的偏好和電動(dòng)汽車目前的車況，通過(guò)云主機(jī)獲得當(dāng)前電動(dòng)汽車對(duì)各個(gè)充電站的喜愛(ài)度偏好排行。而對(duì)于充電站，依照當(dāng)前的路況信息、本充電站當(dāng)前所承載的充電壓力以及可以完成預(yù)約充電的時(shí)間等條件獲得充電站選擇汽車的偏好排名。在云端的處理服務(wù)器，合理處理兩類偏好，計(jì)算得到最佳的汽車充電方案。目前得到的電動(dòng)汽車和充電站偏好如表1所示。

表1 充電站與電動(dòng)汽車充電偏好順序表

根據(jù)表1，應(yīng)用GS算法進(jìn)行計(jì)算：

算法第一輪：CS1充電站沒(méi)有收到預(yù)約，EV1向CS3發(fā)出預(yù)約，EV2、EV3向CS2發(fā)出預(yù)約、EV4向CS4發(fā)出預(yù)約，由于EV3＞EV2，所以電動(dòng)汽車EV2輪空。

算法第二輪，EV2向CS4發(fā)出預(yù)約，CS4的喜愛(ài)偏好中EV2＞EV4，故電動(dòng)汽車EV4輪空。

算法第三輪，EV4向CS3發(fā)出預(yù)約，CS3的喜愛(ài)偏好中EV1＞EV4，故EV4繼續(xù)輪空。

算法第四輪，EV4向CS2發(fā)出預(yù)約，CS2的喜愛(ài)偏好中EV3＞EV4，故EV4再次輪空。

算法第五輪，EV4向CS1發(fā)出預(yù)約，CS1之前沒(méi)有收到過(guò)預(yù)約，故EV4與CS1配對(duì)成功。

至此，充電站和電動(dòng)汽車匹配完畢。通過(guò)此算法的運(yùn)算，如果有些車輛沒(méi)有預(yù)約到合適自己的充電站，在之后的匹配過(guò)程中，沒(méi)有得到預(yù)約最優(yōu)解的車輛會(huì)再次進(jìn)入分配系統(tǒng)，按照算法第一輪的邏輯進(jìn)行運(yùn)算，直至全部電動(dòng)汽車都預(yù)約到合適的充電站為止。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)比較對(duì)象

5.1.1 就近原則充電方案

就近原則充電方案是指在電動(dòng)汽車需要充電的時(shí)候去離自己最近的充電站充電。

5.1.2 喜愛(ài)原則充電方案

每一個(gè)充電汽車車主會(huì)提前標(biāo)記自己喜歡的充電站，喜歡的充電站可能是離車主家比較近，抑或是在某一個(gè)充電站充值了會(huì)員。喜歡原則充電方案即汽車車主去自己喜歡的充電站進(jìn)行充電。

5.2 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)通過(guò)jdk1.7環(huán)境，模擬完成充電汽車進(jìn)入充電站、汽車排隊(duì)等候充電、完成一次充電周期和汽車駛離充電站等任務(wù)。由于充電汽車位置的隨機(jī)性，充電汽車的位置信息和喜好偏向信息通過(guò)java中的Math.random()方法來(lái)實(shí)現(xiàn)，獲得隨機(jī)數(shù)據(jù)。

在實(shí)驗(yàn)過(guò)程中，測(cè)試100輪數(shù)據(jù)，每一輪測(cè)試生成不同的100輛充電汽車的位置信息和汽車對(duì)于充電站的偏好信息，按照就近原則充電方案、喜愛(ài)原則充電方案、GS算法充電方案，得到每一組算法的排隊(duì)峰值、總充電時(shí)間、運(yùn)行總里程以及進(jìn)入汽車喜歡的充電站的總輛數(shù)數(shù)據(jù)，并畫出折線圖。

5.3 實(shí)驗(yàn)數(shù)據(jù)

在測(cè)試的程序中，模擬5個(gè)充電站，充電站之間距離10個(gè)單位長(zhǎng)度，每個(gè)充電站有3個(gè)充電樁。再模擬100輛充電汽車，每個(gè)充電汽車充滿電耗時(shí)20到30個(gè)隨機(jī)單位時(shí)間，隨機(jī)設(shè)置每輛汽車的充電站喜好偏向，隨機(jī)設(shè)置每一個(gè)充電汽車充電的位置。每輛汽車從一個(gè)充電站到另一個(gè)充電站需要1個(gè)單位時(shí)間。每一個(gè)單位時(shí)間會(huì)隨機(jī)出現(xiàn)5輛需要充電的汽車。

5.4 實(shí)驗(yàn)結(jié)果及分析

根據(jù)就近原則、喜愛(ài)原則和GS算法選擇隨機(jī)出現(xiàn)的一百輛電動(dòng)車做實(shí)驗(yàn)，通過(guò)對(duì)所有充電站中排隊(duì)峰值、充滿電總用時(shí)、進(jìn)入喜歡充電站的車輛總數(shù)以及進(jìn)入充電站前運(yùn)行的總單位長(zhǎng)度進(jìn)行對(duì)比，得出如圖2、圖3、圖4、圖5所示的數(shù)據(jù)對(duì)比圖。

圖2 使用不同算法計(jì)算隨機(jī)出現(xiàn)的100輛車在所有充電站中的排隊(duì)峰值

圖3 使用不同算法計(jì)算隨機(jī)出現(xiàn)的100輛車完全充滿電的總用時(shí)

圖4 使用不同算法計(jì)算隨機(jī)出現(xiàn)的100輛車進(jìn)入喜歡充電站的車輛總數(shù)

圖5 使用不同算法計(jì)算隨機(jī)出現(xiàn)的100輛車進(jìn)入充電站前運(yùn)行的總單位長(zhǎng)度

由圖3可知，使用GS算法作為充電汽車的調(diào)度算法，可以明顯降低各個(gè)充電站的排隊(duì)峰值，可以將一些排隊(duì)比較嚴(yán)重的充電站中的排隊(duì)車輛調(diào)度到一些沒(méi)有排隊(duì)壓力的充電站充電。明顯降低整個(gè)系統(tǒng)充電汽車的充電總時(shí)長(zhǎng)。

由圖4可知，使用GS算法，雖然不能像喜愛(ài)原則充電方案那樣保證每一個(gè)車輛都到自己喜歡的充電站進(jìn)行充電，但是在整個(gè)系統(tǒng)中排隊(duì)不嚴(yán)重的情況下，仍然可以保證較大比例的車輛進(jìn)入自己喜歡的充電站充電。進(jìn)而可以推動(dòng)各個(gè)充電站的會(huì)員制，提高充電站的服務(wù)質(zhì)量，獲得更高的經(jīng)濟(jì)效益。

由圖5可知，使用GS算法，雖然不能像就近原則充電方案那樣，整個(gè)系統(tǒng)中所有充電汽車用最短的距離進(jìn)入了充電站進(jìn)行充電，但是充電汽車仍然可以比使用喜愛(ài)原則充電方案運(yùn)行更少的距離。

6 結(jié) 論

該推薦系統(tǒng)旨在通過(guò)物聯(lián)網(wǎng)、互聯(lián)網(wǎng)、電網(wǎng)、交通網(wǎng)的“四網(wǎng)”聯(lián)動(dòng)，實(shí)現(xiàn)充電站使用效率的最大化，并減少駕駛員的“里程焦慮”困擾。在此基礎(chǔ)上運(yùn)用經(jīng)濟(jì)學(xué)中的GS算法，對(duì)汽車和充電樁進(jìn)行雙選，使資源分配達(dá)到最優(yōu)和最合理，從而實(shí)現(xiàn)汽車的快速充電以及充電站利用率的最大化。