基于數據驅動的電動出租車充電站規劃方法研究

鄧昌棉 張勇

摘 要：為了規劃城市道路網上電動出租車的充電基礎設施，以滿足整個城市電動出租車的充電需求，本文利用出租車乘客起訖點大數據，基于M/M/K排隊模型提出電動出租車在充電站處排隊模型，建立行駛距離最小的充電站選址優化模型及遺傳求解算法。以蘇州市出租車GPS數據為例，對模型進行驗證。研究結果表明：隨著充電速率的增加，將減少電動出租車充電需求的單位成本，從而增加充電站設站數量，由此將縮短電動出租車充電的行駛總距離;基于不同工作日GPS大數據求解的充電站選址在道路網中呈簇狀分布，模型結果具有穩健性，這表明可以在鄰近區域內尋找可布設點建設充電站。研究結果可為出租車充電站規劃和運營提供決策依據。

關鍵詞：電動出租車;充電站選址規劃;GPS大數據;M/M/K排隊模型

Abstract：In order to plan the charging infrastructure of electric taxis on urban roads to meet the charge needs of electric taxis in the entire city， utilizing the big data of taxi passengers， a queueing model of electric taxis charging at charging station based on the M/M/K queuing model and a location optimal model of electric taxi charging stations for minimum total travel distance and models algorithm are all proposed. The GPS data of Suzhou taxi is used to verify the model. The research results show that with the increase of the charging rate， the unit cost of the electric taxi charging demand will be reduced， while the number of charging stations increases， thus reducing the total distance of electric taxis. The locations of charging stations are distributed in clusters in the road network， thus the model results are robust. This means that applicable sites can be found to build charging stations in adjacent areas. The research results can provide decision basis for the planning and operation of taxi charging stations.

Keywords：Electric taxi; battery charging station location planning; GPS big data; M/M/K queueing model

0 引言

電動汽車因其環保、經濟而發展非常迅速[1]，太原、深圳、廣州和北京等城市的電動出租車的市場占有率接近100%。目前電動出租車主要為插電式充電（以下簡稱插電），其耗時較長。例如：北汽慢充8 h、快充2 h;特斯拉慢充10 h、快充1.5 h;比亞迪慢充20 h、快充2 h。由于電動出租車需要全天候運營，其續航里程較短，充電耗時長，制約了電動出租車的普及。因此，如何規劃電動出租車充電基礎設施以滿足其需求，是滿足電動出租車交通運輸的首要問題。

目前，許多學者對插電式電動出租車的充電基礎設施規劃方法開展研究。此類選址研究大致有3類：P-中值問題[2]、P-中心問題[3]和覆蓋問題[4]。第一類P-中值問題是指給定設施數P，確定設施的位置使得需求點到其分配設施的距離與相應的需求量乘積之和最小，如Shahraki等[5]和Ghamami等[6]進行了此類研究。第二類P-中心問題是指在網絡中給定P個設施，使得全部需求點到與其最近設施的距離之中最大值最小化的問題，如Li等[7]和Wong等[8]進行了此類研究。第三類覆蓋問題可分為兩大類[9]，集覆蓋選址問題和最大覆蓋選址問題，前者即在滿足全部需求被覆蓋的情況下，設施數目最少或設施建設成本最低的問題，如Tu等[10]和Hu等[11]進行了此類研究;后者在已知服務站數目和服務半徑的情況下，確定P個服務站的最優位置使得其覆蓋的需求量最大的問題，如Jung等[12]和Asamer等[13]進行了此類研究。

由于乘客搭乘出租車的OD（出租車起終點間的交通出行量）對隨機性大，對電動出租車充電站的選址有較大影響。而出租車GPS采集的數據為分析出租車的運營特性提供了可能，由此也為更好地規劃充電基礎設施提供了新的思路[14]。基于出租車GPS采集的數據可預估充電需求，因此規劃充電站至關重要。Lu等[15]基于時空網絡開發模型優化出租車隊的最佳時間表，實現車隊總運營成本的最小化。Kang等[16]從電動出租車壽命的角度，研究了淘汰燃油出租車的經濟可行性，但并未對出租車充電過程進行研究。上述研究存在兩個缺陷：一方面沒有考慮電動出租車到站時無空閑充電樁的概率，這對出租車充電的影響較大;另一方面，以往研究只能粗略估計出租車出行需求，容易造成規劃的充電站規模出現不足或過剩。這兩方面決定著以往的研究難以滿足電動出租車對電能補充的苛刻要求。因此必須深入考察電動出租車在充電站處有空閑充電樁的概率，同時利用大數據精確掌握路網上的OD需求，由此實現電動出租車充電設施的科學規劃。

本文根據出租車運營大數據獲得高時空精度的出租車充電OD對需求，提出插電式出租車充電設施規劃的科學方法。

（1）為描述插電式出租車充電過程，基于M/M/K排隊模型，建立出租車在站充電的隨機過程的數學描述。

（2）以出租車充電OD對需求最小行駛總距離為目標，考慮總成本和有空閑充電樁概率等約束，建立充電站選址和充電樁數量的一體化決策模型及求解算法。

（3）對不同工作日充電站選址分析，揭示基于出租車大數據的充電站選址的穩健性。

1 模型構建

1.1 基本假設

本文僅考慮研究范圍內的主要路網（包括快速路和主干道），其路網G由路段和節點組成，記為G=V，N。其中，V為節點集合，N為路段集合。研究范圍內的劃分小區記為A。為方便建模，進行以下基本假設：

A1：出租車到達充電站時，以先到先服務的順序進行充電。

A2：有充電需求的電動出租車到達充電站的間隔時間服從泊松分布，充電時間服從負指數分布。

A3：在劃分小區A的出租車充電OD對需求將選擇距離該小區最近的路網節點進入路網。

A4：假設一輛出租車某一訂單結束到下一訂單開始的間隔時間大于1 h認為出租車去充電站進行充電。

A5：出租車司機會在電量耗盡前到達充電站進行充電。

A6：假定出租車司機在到達充電站前是無法準確預知是否有空閑充電樁。

1.2 出租車充電隨機性分析

一輛電動出租車到達后，如果充電站此時有空閑充電樁，那么將會進行充電并充滿電后離開;如果沒有空閑充電樁，將會在充電站處排隊等待。由上述充電過程可知，充電樁數量會影響電動出租車在充電站補充能源的等待時間。根據上述A1假設，出租車隨機到達充電站，以先到先服務原則進行充電。將k個充電樁和電動出租車數量構成的系統視為M/M/K排隊系統。

利用M/M/K排隊理論計算充電站沒有空閑充電樁的概率[17]。令Pn表示系統中出租車數為n的概率（n=0，1，2，3，…，∞），μ為出租車充電的速率，λ為出租車到達充電站的速率，ρ=λ/（k·μ）<1，根據M/M/K排隊理論計算系統中不同出租數量的狀態概率為：

1.3 充電站選址分析

1.3.1 充電需求分析

由于出租車通常安裝GPS設備用于導航和運行監控。利用出租車運營軌跡數據可實現出租車出行需求的準確估計，如：Wang等[18]和Chrysostomou等[19]的研究。根據出租車GPS數據來討論出租車的充電需求。首先根據假設A4，一輛出租車某一訂單結束為O和下一訂單開始為D轉換成充電OD對需求;其次將研究區域主要道路網劃分成1 km×1 km小區，然后根據出租車充電OD對需求，將各個出租車需求匹配到對應的小區，因此可以得到各個小區間的OD對矩陣;最后根據假設A3，通過路網對各個小區間的OD對矩陣進行轉移和分配，得到路網節點OD對矩陣。

由于已知出租車路網OD對矩陣，其他車輛路網流量未知，因此忽略出租車發生擁堵的情況。根據全有全無分配方法來分配電動出租車的充電需求。充電站j的充電需求估計為：

1.3.2 充電站優化模型

在電動出租車電量耗盡之前，電動出租車司機總是會選擇最短的路徑去進行充電。對此，提出了基于出租車充電OD對需求以最小行駛總距離為目標的優化模型，約束條件為總成本（包括建設費用和充電樁費用）和出租車到站沒有空閑充電樁的概率均滿足規劃要求，即

2 求解算法

模型（5）—模型（12）屬于非線性的整數規劃問題，采用傳統的啟發式整數優化方法求解較為困難。本文采用遺傳算法進行求解。該算法是簡單的智能算法，其原理不再贅述。具體步驟如下。

Step 1：輸入參數。初始選址數量g，運用Floyd算法，根據路段矩陣求出距離矩陣和路由矩陣。

Step 2：初始化。建立種群大小J、交叉率、變異率和最大種群代數K，置個體代號m=1，并依據∑Ji=1xi=g，隨機產生M個初始種群 Sm=x1，x2，x3，…，xJ。

Step3：依據公式（5）計算各種群目標函數最小行駛總距離ZSm，并根據目標函數計算各種群的適應度FSm，用公式（13）計算，其中ε為適應度淘汰指數。

Step 4 ：如果k

Step5 ：根據公式（4）及Step 4的Sm計算λj，j∈V。通過遍歷確定滿足公式（7）—公式（12）約束條件的充電樁數量可行解空間Λg。如果可行解空間Λg存在，則g=g+1，返回Step 2;如果可行解空間Λg不存在，則g=g-1，得到選址點集合Sg，可行解空間Λg，進行Step 6。

Step6：即Sg為最優解選址。可行解空間Λg中可行解最小成本即為充電樁最優解。

3 實例分析

將常規出租車的GPS數據作為插電式出租車的需求，開展充電站選址及充電設施的配置研究。根據2014年6月16日至2014年6月22日的中國蘇州出租車GPS數據對充電需求進行估算，有效數據總共有1 125 136條，其中：16號153 463條數據、17號156 819條數據、18號157 118條數據、19號158 228條數據、20號168 192條數據、21號172 986條數據、22號158 330條數據。其中一條數據主要包括出租車OD對起訖點經緯度、時間、行程和車牌號等。

3.1 數據處理

首先根據A4的假設，把出租車GPS數據轉換成充電OD對需求。充電OD對需求經緯度及研究區域主要道路網數據可視化，如圖1所示。由圖1可見，黑色為路網（包括461個結點和723個路段），紫色點為充電OD對需求起訖點。把研究區域劃分成1 km×1 km的方格網小區（總共7 654個小區），見灰色方格網。把出租車充電OD對需求起訖點進行方格網聚集，得到劃分小區的OD對矩陣。

根據路網將方格網小區的OD對矩陣進行分配，得到路網節點的OD對矩陣。出租車充電OD對需求將在O到充電站和充電站到D之間進行2次最短路徑的選擇，按照全有全無的規則分配到道路網絡上去。

由于出租車GPS記錄了出租車每天的訂單起訖點數據。為了確保電動出租車能滿足出行需求，有必要分析出租車需求受到氣象、不同工作日的影響情況。為此，選取2014年6月16日至2014年6月22日一周的數據進行分析，如圖2所示。由圖2可知，2014年6月6日（星期一）有中雨，在16：00—19：00訂單量基本上為零;2014年6月19日（星期四）和2014年6月20日（星期五）有陣雨，分別在1時和18時的訂單量很小。由此可見，降雨量對出租車訂單有影響，降雨量越大實際上會減少乘客對出租車的需求;由于星期六和星期天是周末，GPS數據缺失一部分，所以忽略對周末的數據進行分析。工作日每天的出租車訂單數量趨于穩定，在8：00—10：00和20：00—23：00是訂單高峰時段，符合居民出行的特點。

由訂單分析結果忽略周末數據，根據假設A4和不同工作日的數據進行處理，為了解不同工作日電動出租車充電需求數量進行對比分析，選取2014年6月16日（星期一）至2014年6月20日（星期五）的數據分析。根據圖3進一步驗證了，降雨量對出租車訂單有影響，降雨量越大實際上會減少出租車出行;且發現圖2與圖3形狀相反，在6：00—8：00是充電的高峰期與運營高峰期相差1 h，其符合出租車充電和運營的特點。

3.2 結果分析

選取2014年6月16日6：00—8：00的出租車充電OD對需求進行分析，根據特斯拉的充電站建設指標[20]，充電樁充電速率μ=1（車/h），出租車去充電站有空閑充電樁的最小概率η=0.9，充電站建設成本cs=200萬元、一個充電樁的成本為ck=2萬元，投資總成本為C=6 000萬元。圖4為求解算法的收斂結果，隨著迭代次數的增加行駛總距離減少，其迭代50多次就達到最優值，說明迭代收斂快且迭代過程符合算法設計要求。

隨著充電技術的進步將充電時間縮短，這將對電動出租車充電系統規劃產生重要影響。由圖5可知，在充電速率μ=1（車/h）時，行駛距離為5 725 km，系統內的充電站數量為21個;而μ=2（車/h）時，系統最小行駛距離為5 660 km，系統內的充電站數量為25個。由此可見，隨著充電速率的增加，由于電動出租車充電需求所需的單位成本降低，將有更多的資金建設更多的充電站，由此減少出租車充電的行駛總距離。因此，充電技術的進步將直接提高整個充電設施的運營效率。

具體分析不同工作日出租車GPS數據對充電基礎設施的影響。圖6是關于不同工作日的充電站選址、路網中的路段流量及充電站中充電樁數量的結果，紅色路段寬度表示路段出租車的流量，柱狀圖所在位置為充電站的選址點，藍色代表充電樁數量。由圖6可知，模型求解結果確保了充電站設置在路段需求流量大的路網節點，且在路網上的分布較均勻;另外，利用各個工作日的出租車大數據，對比相同位置充電站的充電樁數量大致相同。結合圖6和圖1進行分析得充電站選址綜合考慮了流量大的區域及城市外圍區域，并滿足整個城市出租車的充電需求。

為了分析不同工作日充電站的選址結果，圖7給出了不同工作日充電站選址。由圖7可知，發現充電站在不同工作日的選址大致出現在同一區域，各個選址點相差1到2個交叉口的距離，其充電站選址呈簇狀分布。這一結果表明，即使各個工作日的出租車需求存在隨機性，但是模型利用這些大數據優化的選址區域是確定的，具體的結果區域內可能相差2 km左右（見圖7中的放大部分）。因此模型結果具有相當的穩健性。對于城市布設充電站時，由于不是每個區域都能布設充電站，其充電站選址呈簇狀分布，說明偏移一定距離其選址也符合出租車充電OD對需求，能夠解決城市某些區域不能布設充電站的問題。

4 結束語

根據出租車乘客起訖點大數據估計充電OD對需求，基于M/M/K排隊理論建立了描述出租車充電的隨機模型，及出租車最小行駛總距離為目標的充電站選址及充電樁配置一體化優化模型，并運用遺傳算法對模型進行求解。利用蘇州市出租車GPS大數據對所建模型進行了驗證。研究發現：隨著充電速率的增加，將減少電動出租車充電需求的單位成本，從而增加充電站設站數量，由此將縮短電動出租車充電的行駛距離;基于不同工作日大數據求解的充電站選址在道路網中呈簇狀分布。這表明基于運營大數據的電動出租車充電站選址優化結果具有穩健性。

研究成果將為充電站選址規劃和充電樁的數量提供決策依據。基于運營大數據的插電式出租車充電設施優化模型，還可以進一步拓展以下方面的研究：①本研究僅考慮了出租車不受社會交通流的影響，該假設較為嚴格，在未來的研究中可以放松該假設，將道路交通流的實際影響考慮進來。②本研究并未考慮地價，只是統一用建設成本表示，不同的區域位置地價成本不一樣。③在實際中，電動出租車充電需要充電位，且充電位及等待充電位的數量將影響電動出租車的充電情況。因此未來可針對該情形進行深入討論。

【參 考 文 獻】

[1]2018年全球電動汽車保有量及市占率走勢分析預測[EB/OL].中國產業信息網， http：//www.chyxx.com/industry/201806/648847.html.2018-6-12.

Analysis and forecast of global electric vehicle ownership and market share trend in 2018[EB/OL]. http：//www.chyxx.com/industry/201806/648847.html.2018-6-12.

[2]HAKIMI S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research， 1964， 12（3）： 450-459.

[3]HAKIMI S L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems[J]. Operations Research， 1965， 13（3）： 462-475.

[4]CHURCH R， REVELLE C. The maximal covering location problem[J]. Papers of the Regional Science Association， 1974， 32（1）： 101-118.

[5]SHAHRAKI N， CAI H， TURKAY M， et al. Optimal locations of electric public charging stations using real world vehicle travel patterns[J]. Transportation Research Part D： Transport and Environment， 2015， 41： 165-176.

[6]GHAMAMI M， ZOCKAIE A， NIE Y M. A general corridor model for designing plug-in electric vehicle charging infrastructure to support intercity travel[J]. Transportation Research Part C： Emerging Technologies， 2016， 68： 389-402.

[7] LI Y H， LUO J， CHOW C Y， et al. Growing the charging station network for electric vehicles with trajectory data analytics[C]// 2015 IEEE 31st International Conference on Data Engineering， Seoul， South Korea， IEEE， 2015.

[8]WONG R C P， SZETO W Y， WONG S C. A cell-based logit-opportunity taxi customer-search model[J]. Transportation Research Part C： Emerging Technologies， 2014， 48：84-96.

[9]DASKIN M S. Location modeling in perspective[J]. Wiley Online Library， 1995： 383-400.

[10]TU W， LI Q Q， FANG Z X， et al. Optimizing the locations of electric taxi charging stations： a spatial-temporal demand coverage approach[J]. Transportation Research Part C： Emerging Technologies， 2016， 65： 172-189.

[11]HU L， DONG J， LIN Z H， et al. Analyzing battery electric vehicle feasibility from taxi travel patterns： The case study of New York City， USA[J]. Transportation Research Part C： Emerging Technologies， 2018， 87： 91-104.

[12]JUNG J， CHOW J Y J， JAYAKRISHNAN R， et al. Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations[J]. Transportation Research Part C： Emerging Technologies， 2014， 40： 123-142.

[13]ASAMER J， REINTHALER M， RUTHMAIR M， et al. Optimizing charging station locations forurban taxi providers[J]. Transportation Research Part A： Policy and Practice， 2016， 85： 233-246.

[14]CAI H， JIA X P， CHIU A S F， et al. Siting public electric vehicle charging stations in Beijing using big-data informed travel patterns of the taxi fleet[J]. Transportation Research Part D： Transport and Environment， 2014， 33： 39-46.

[15]LU C C， YAN S Y， HUANG Y W. Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations[J]. Transportation Research Part C： Emerging Technologies， 2018， 93： 479-500.

[16]KANG S C， LEE H. Economic appraisal of implementing electric vehicle taxis in Seoul[J]. Research in Transportation Economics， 2019， 73： 45-52.

[17]GROSS D， SHORTIE J F， THOMPSON J M， et al. Fundamentals of queueing theory[M]. John Wiley & Sons， 2008.

[18]WANG N， LIU Y F， FU G Z， et al. Cost-benefit assessment and implications for service pricing of electric taxies in China[J]. Energy for Sustainable Development， 2015， 27： 137-146.

[19]CHRYSOSTOMOU K， GEORGAKIS A， MORFOULAKI M， et al. Using big taxi GPS data to investigate the feasibility of electric taxis in Thessaloniki， Greece[C]// 95th Annual Meeting of the Transportation Research Board （TRB）， Washington DC， United States， 2016.

[20]GUO M. How much does it cost to build an electric car charging station[EB/OL]. http：//www.chinairn.com/scfx/20180608/11400154.shtml. 2018-6-8.