鄧昌棉 張勇

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

關鍵詞：電動出租車;充電站選址規(guī)劃;GPS大數(shù)據(jù);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 引言

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

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

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

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

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

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

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

1 模型構建

1.1 基本假設

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

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

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

A3：在劃分小區(qū)A的出租車充電OD對需求將選擇距離該小區(qū)最近的路網(wǎng)節(jié)點進入路網(wǎng)。

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

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

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

1.2 出租車充電隨機性分析

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

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

1.3 充電站選址分析

1.3.1 充電需求分析

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

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

1.3.2 充電站優(yōu)化模型

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

2 求解算法

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

Step 1：輸入?yún)?shù)。初始選址數(shù)量g，運用Floyd算法，根據(jù)路段矩陣求出距離矩陣和路由矩陣。

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

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

Step 4 ：如果k

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

Step6：即Sg為最優(yōu)解選址?？尚薪饪臻gΛg中可行解最小成本即為充電樁最優(yōu)解。

3 實例分析

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

3.1 數(shù)據(jù)處理

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

4 結(jié)束語

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

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

【參 考 文 獻】

[1]2018年全球電動汽車保有量及市占率走勢分析預測[EB/OL].中國產(chǎn)業(yè)信息網(wǎng)， 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.