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

趙雅蘭，張大波，李鴻堯

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

0 引 言

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

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

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

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

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

由于電動(dòng)汽車(chē)存在充電相對(duì)較慢的技術(shù)壁壘和當(dāng)下基礎(chǔ)設(shè)施建設(shè)不完善的現(xiàn)狀，電動(dòng)汽車(chē)用戶都會(huì)在自己的電動(dòng)汽車(chē)電量低于某一閾值時(shí)產(chǎn)生對(duì)電車(chē)電量耗盡的恐懼，稱為“里程焦慮”。而反觀充電站，其在運(yùn)營(yíng)過(guò)程中，會(huì)有大量的電動(dòng)汽車(chē)進(jìn)行充電，由于沒(méi)有加油站那樣高效的吞吐量，電動(dòng)汽車(chē)的充電站常常會(huì)有眾多車(chē)主排長(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)汽車(chē)開(kāi)到充電站時(shí)充電樁都被其他車(chē)輛占用的情況，駕駛員若想在此充電站充電則要花費(fèi)很長(zhǎng)的時(shí)間排隊(duì)等候。即便有了預(yù)約系統(tǒng)，可能會(huì)出現(xiàn)充電站中有空閑的充電樁，但由于充電樁已被預(yù)約，急需充電的汽車(chē)充不上電的情況。

2 解決方案

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

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

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

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

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

3.1 NB-IoT終端

在電動(dòng)汽車(chē)、充電站中和充電樁上安裝物聯(lián)網(wǎng)的微控制器，可以進(jìn)行汽車(chē)的數(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)。汽車(chē)和充電站將實(shí)時(shí)的狀態(tài)信息傳送到附近的基站，基站通過(guò)NB-IoT網(wǎng)絡(luò)將信息傳送到業(yè)務(wù)處理云主機(jī)，在云端的服務(wù)主機(jī)通過(guò)優(yōu)化的GS算法，得出在電動(dòng)汽車(chē)可以快速排隊(duì)的同時(shí)也能實(shí)現(xiàn)充電樁高效利用的最優(yōu)解，將這個(gè)最優(yōu)解記錄下來(lái)，并將輸出結(jié)果通過(guò)NB-IoT網(wǎng)絡(luò)傳到之前需要預(yù)約的車(chē)輛、充電站或者其他人機(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、小程序或車(chē)載應(yīng)用等完成人機(jī)頁(yè)面的互動(dòng)。

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

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

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

根據(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)汽車(chē)EV2輪空。

算法第二輪，EV2向CS4發(fā)出預(yù)約，CS4的喜愛(ài)偏好中EV2＞EV4，故電動(dòng)汽車(chē)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)汽車(chē)匹配完畢。通過(guò)此算法的運(yùn)算，如果有些車(chē)輛沒(méi)有預(yù)約到合適自己的充電站，在之后的匹配過(guò)程中，沒(méi)有得到預(yù)約最優(yōu)解的車(chē)輛會(huì)再次進(jìn)入分配系統(tǒng)，按照算法第一輪的邏輯進(jìn)行運(yùn)算，直至全部電動(dòng)汽車(chē)都預(yù)約到合適的充電站為止。

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

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

5.1.1 就近原則充電方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由圖5可知，使用GS算法，雖然不能像就近原則充電方案那樣，整個(gè)系統(tǒng)中所有充電汽車(chē)用最短的距離進(jìn)入了充電站進(jìn)行充電，但是充電汽車(chē)仍然可以比使用喜愛(à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ì)汽車(chē)和充電樁進(jìn)行雙選，使資源分配達(dá)到最優(yōu)和最合理，從而實(shí)現(xiàn)汽車(chē)的快速充電以及充電站利用率的最大化。