資金約束下單向共享電動汽車系統的充電站選址①

鄭建國，祁光輝

(東華大學 旭日工商管理學院，上海 200050)

在大型城市，停車難問題和高昂的停車成本使得普通的上班族來講擁有私家車不再具有吸引力.汽車共享系統是私人車輛所有權的替代方案.家庭或企業不必擁有一輛或多輛汽車，而是共同使用一些車輛來滿足需求，這一類系統在20世紀70年代到80年代通過試點實施，近幾年取得了相當大的發展.

汽車共享系統越來越多的采用環保型車輛，不僅可以減少移動性對環境的負面影響，也更加容易進入擁擠的城市地區.其中在汽車共享系統中的環保型車輛首選是電動汽車.現實中存在著一下幾種類型的電動汽車，主要有僅使用電池提供能量和電力的插入式電池電動車輛；在行駛期間能夠恢復能量的插電式混合動力電動車輛，并且可以給電池充電，但是仍然擁有內燃機[1].在本文中，汽車共享系統中使用的是僅使用電池提供能量和電力的插入式電池電動車輛.

根據用戶是否應該將租借的車輛歸還給他們的方式不同，汽車的共享系統可分為靈活的“單向”和受到限制較多的“雙向”兩種類型.根據停車位限制，“單向”的系統被分為“自由浮動的系統”和“非自由浮動的系統”.前者是指用戶可以在特定區域內的任意的停車點借還車輛；后者定義為指定停車點來借還車輛.在“自由浮動的系統”中，不能采用預訂的模式的.而“非自由浮動的系統”模型為用戶提供了預訂能力和單程旅行的靈活性.最近的一項研究表明采用預訂模式可以提高汽車共享系統的服務質量[2].

本文研究的問題是在單向共享電動車系統中車站的數量和位置以及每一個車站的初始化車輛數量，目標為最大化利潤，這種方式考慮到可以服務的客戶獲得的收入、建設車站的成本以及購買電動汽車的成本.本文將這個問題作為一個整數線性規劃模型(Integer Linear Programming，ILP)，并利用這個模型，決定所要服務的客戶.

在第2 節中，將要回顧文獻中的相關著作.在第3 節中，定義了本文研究的問題之后，提供了ILP 公式的細節和模型所需的預處理程序.最后，進行了模擬仿真實驗的結果，對其進行分析.

1 相關研究

關于汽車共享系統的大多數現有研究都集中在戰術和操作層面的決策問題上.在這些研究中，一方面研究的問題是汽車的重新安置，以避免車站的汽車不平衡.另一方面，關于汽車共享系統中車站位置的研究.

文獻[3]提出了一種用于單向汽車共享系統中站點最佳定位的混合整數規劃模型.文獻[3]中通過考慮所有成本和收入因素來最大化公司的利潤.根據三種服務策略分析了該模型:(1)運營商可以自由選擇客戶的服務請求；(2)必須提供所有請求；(3)只有在起點時沒有可用的汽車才能拒絕請求.對來自葡萄牙里斯本市的實際數據的三種模型進行評估后發現，滿足所有客戶要求可能會顯著降低公司的利潤.這些模型基于這樣的假設:客戶只能使用距離其原點和目的地最近的站點，并且這種假設被認為是非常嚴格的.文獻[4]將這些模型擴展到更靈活的環境，其中包括客戶可以使用距離原點和目的地不是最近的車站.對同一數據的案例研究表明，引入這種用戶靈活性和車輛庫存信息增加了公司的利潤.

除了上面提到的優化模型，文獻[5]提供了一個基于離散事件模擬的模型，該模型評估了汽車共享系統中策略變化的影響，例如創建新站，增加車站容量，合并或分離站.作者通過對加拿大蒙特利爾汽車共享組織數據的幾種策略評估了他們的模型.

文獻[6]考慮了電動汽車共享系統中充電站位置的研究.文獻[6]提出了一種多目標混合整數線性規劃模型，該模型結合了單向共享電動汽車系統中的戰略(站點位置)和戰術(車輛重新定位)決策.由于大量重定位變量而導致解決實際大小問題的模型難以處理，因此使用了聚合需求結構.該模型的第一個目標函數旨在最大化運營商的凈利潤，而第二個目標最大化用戶的凈收益.在文獻[6]中，假設充電周期明確地作為輸入參數給出.作者評估了他們的方法在法國尼斯的實際數據上的表現.文獻[7]提出了一種混合整數線性規劃模型來解決單向共享電動汽車系統中充電站位置選擇問題，文獻[7]中的目標函數為運營商的利潤最大化，其中每一個潛在站點的最大容量是已知的，并沒有考慮到充電站建造和電動汽車購買成本.本文則需要確定每個潛在站點的最大容量，并且有充電站建造和電動汽車購買成本有限制.

另一組相關研究是關于私人電動汽車充電站的位置，文獻[7-12]介紹了具體的方法.文獻[13，14]使用啟發式算法解決了公共充電問題.

2 問題定義

該模型的動機是規劃汽車共享系統中單向行駛，并且時間不能自由浮動的，其中共享使用的汽車用于為特定地理區域內的旅行提供服務.在介紹問題制定之前，我們從系統的需求和供給特征兩個方面對系統進行了描述.

(1)車輛

整個系統中使用同一種類型的電動汽車，任何類型的旅行請求都可以被任何可用的車輛所提供服務.

(2)車站

車輛在指定的車站出發和停靠.車站有必要的基礎設施來停車和為車輛充電；每個車站提供特定數量的停車位，這決定了車站的大小.站的大小因站而異，每個站的大小決定了它的容量.

(3)時間間隔

每個周期劃分為不同的時間間隔(不一定一樣長)，車輛出發的操作在時間間隔開始時開始，車輛到達和充電完成操作在時間間隔結束時結束.

(4)運營操作

這個系統的運營涉及兩項操作:租賃；充電.

①該系統是在預定的基礎上運行并允許單程租用車輛.在預定時，用戶的出發地點、到達地點、出發時間、到達時間是可獲得的.在預定做出的時間段，車輛在用戶在出發地點可訪問的車站獲得車輛；并在到達地點可訪問的車站停放.假定每一次租賃都是從一個時間間隔的開始時開始，然后在一個時間間隔結束時結束.

②本文所建立的模型采用了電動汽車.為了對電動汽車充電時間進行建模，假設車輛返回車站后，必須在車站停留一段固定的時間，這代表了車輛的充電時間.

(5)需求中心(潛在車站)

在該模型中，需求中心表示可以由同一組(候選)站點服務的需求點.為了說明中心是如何定義的，圖1 描繪了需求的來源和目的地以及站點位置.圖2 示出了通過不同的起點和目的地位置可訪問的站點.請注意，一個給定的起點/終點可以有多個對應的車站站點.可以訪問同一組車站的原點/目的點聚集在一起，構成一個中心.圖3 表示與這些中心相關聯的兩個中心(陰影區域)和旅程(需求).將需求分組減少了變量的數量，因為具有相同起源和目的地中心的旅行被組合在一起.這種分組允許解決較大的問題實例.

(6)需求

需求有時間和空間兩個維度.需求表示擁有用戶的起點和終點并具有出發時間和到達時間的訂單的集合.能夠為一個訂單提供服務需要滿足以下兩個條件:

①在出發時間間隔開始時可從起始位置相應的車站獲得車輛；

②在到達時間時間間隔結束時到達位置相應的車站擁有停車位.

其中，“訂單”不必分配給最鄰近起點/終點的車站，而是分配給可訪問的車站.

(7)成本和收入

該模型的目標函數是最大化運營商的利潤.運營商的收入包括車輛租賃收入，而成本包括車輛的維護，運營以及車站開放后運營費用.

3 實驗分析

在這一部分中，首先定義了用于描述模型的集合和索引，以及4.2 節中的函數、變量和參數.第4.2 節給出混合整數規劃模型，并對其目標函數和約束條件進行了詳細的描述.

3.1 輸入

(1)索引和集合:

①p,jJ:潛在站點的索引；

②h,kH:需求訂單索引.

(2)參數定義:

①V=f1,···,ng:為節點的集合；

②J=f1,···,mg:潛在車站的集合，其中JV；

③fj:開放車站j的成本，它是關于充電站車位數量Cj的線性函數；

④Fj:建造車站j的固定成本；

⑤g:電動汽車運行成本；

⑥G:電動汽車購買成本；

⑦T=f0,···,τg:時間節點；

⑧k=fOk,Dk,Tk,Tk+dk,Pk,δijg:Ok為請求k的起點；c 為請求k的終點，Tk為請求k的起始時間，Tk+dk為請求k的終止時間，Pk為請求k的利潤；δij為請求k的電量.

(3)輔助變量:

設計了一個預處理程序對輔助變量進行計算，使用一個很小的例子對程序設計進行說明.在這個例子中，考慮了潛在站點的位置以及T時間內的需求K(如圖1所示)，其中i1、i2、i3、i4為已建好的車站的位置，k1、k2、k3為請求(包含了起始點Ok、終止點Dk、開始時間Tk、收入pk)，模型中一個請求訂單的完成有三部分組成(如圖2所示)，連接任何起始點和起始站稱為接入段(如Ok到i)；連接任何終止點和終點站稱為出口段(如Dk到j)；連接始發站和終點站稱為出租段(如i到j).預處理程序主要將請求和車站進行連接，形成接入段和出口段.對于一個請求有可能被接入多個接入段和出口段，形成集合Hk(kK)，如果出租段滿足電量和和接入段和出口段步行閾值滿足要求，則該請求hH=UkKHk是可行的.對于一個請求形成的結果(如圖3所示).由預處理程序進行實現.

圖1 T時間內的需求K

圖3 請求最終的可行結果

預處理程序的偽代碼，偽代碼如下:

算法1.預處理程序1)Π←Φ 2)for k←1 to K 3)Hk←Φ 4)for i←1 to m dOki≤β 6)for j←1 to m 7)if dDki≤β 8)b[h][Tk]=1 9)u[j][Tk+dk]=1 10)λ[h][j][Tk+dk+dk/ρ]=1 11)Ph={i，j，Tk+dk}12)Hk=Hk∪Ph 13)H=H∪Hk 14)return b，u，λ，H

①=1:請求h所使用的車輛在t時刻已經在車站j充電，否則為0；

②=1:請求h所要使用的車輛在t時刻從車站j出發，否則為0；

(4)決策變量:

①uh=1:請求h被 服務；

②:車站j在t時刻擁有的電動汽車的數量；

④Cj:站點j的能力；

⑤yj:車站j是否打開.

3.2 模型建立

s.t.

這是基于路徑建立的模型(Pathbased Formulation，PF)，目標函數(1)為最大化利潤，第一部分所服務請求的總收入，第二部分為車站建設后的運營成本，第三部分為車輛的運營成本；約束條件(2)是車站的建設費用和車輛的購買費用必須在預算范圍內；約束條件(3)是確保每一個請求接入一個接入段和出口段；約束條件(4)確保一個請求若被服務則要求請求的起點和終點的車站都要打開；約束條件(5)在t時刻每個車站的需求的車輛數量不能超過其能夠提供的車輛數量；約束條件(6)為在任意時刻j車站上的車輛數量不能超過車站的充電站的能力值；約束條件(7)為在t時刻j車站上的車輛數量等于上一時刻該車站車輛數量加上充電完成的車輛數量減去出站的車輛數量；約束條件(8)為車輛最大數量的限制；約束條件(9)為初始車輛數量為正整數；約束條件(10)為請求是否被滿足；約束條件(11)為車站是否進行打開.

4 仿真實驗

這一部分通過創建一組實例測試了模型，其中將街道網絡建模為網格圖，其參數在一下部分中詳細描述.

網格實例:利用一定的規則產生隨機矩陣，進行模擬.其中街道網絡G=(V,A)由尺寸30×30的網格圖表示，其中相鄰節點的最大距離為5，潛在站點的服務半徑為f3,6,10g.每個潛在充電站點pJ的容量Cp是未知的，而車站的建造成本Fp被設置為α+βCp，其中α=100 和β=10，車輛的購買成本為G=50，車站的運營成本為fp=(0.2α+0.05βCp)yp，車輛的運營成本為g=0.01G.潛在充電站的數量J=50，請求的數量Kf1000,3000,5000g，時間的集合Tmax=24.每個行程kK的參數被選擇如下:原點Ok和目的地Dk被隨機選擇，開始時間Tk從隨機選擇，結束時間Tk+dk從fTk,···,Tmaxg里面選擇，利潤為pk=2dk，充電站的充電率為ρ=10/3，也就是說一個請求運行完畢后，需要0.3dk的時間進行再次充電.

在Intel Core i3-6300處理器上使用IBM ILOG CPLEX 12.8 進行了實驗，該處理器CPU 為3.80 GHz，內存為8 GB.為了考慮到不同資金約束下模型的可行性，在仿真實驗中，使用了資金約束在factor_cost=f2500,5000,7500g的選擇.

在表1中，總結了每個解決問題實例的預處理結果.在該表中，列給出了從模擬數據中獲取的請求數量，為潛在站點的數量，為可能被服務請求的數量，為預處理期間可能服務的潛在的路徑數量，p_t顯示預處理期間可能服務的潛在的路徑數量(以秒為 單位).

表1 預處理結果

在表2、3、4中詳細測試了模型PF opt、RPF opt(使用0 ≤uh≤1,8hH替代uhf0,1g)和LP(完全放開整數約束)分別從，其中LP_GAP和LP_GAP的值分別使用公式(100*(LP opt - PF opt)/ PF opt)和(100*(RPF opt - PF opt)/ PF opt)，被服務的請求數量、建設的車站.

表2、3、4中看到，RPF 和PF 在每個實例中的值都是一致的；RPF中的解 在某些情況下不是整數.隨著充電站服務半徑的增加，能夠服務的請求和利潤都獲得了增加.但是求解時間和預處理過程花費時間也增加了.

表2 資金限制為5000時的解和gap

表3 資金限制為10 000時的解和gap

表4 資金限制為15 000時的解和gap

當資金比較缺乏時，該模型更傾向于建設更多的充電點為更多的客戶提供服務；資金由5000 變為10 000時更加明顯.從以上求解結果可以看到，每種求解結果PF 和LP 之間的Gap 小于2%.除了表2中的PF 和LP 之間的Gap 比較大；說明給模型能夠得到一個比較好的求解結果.當資金足夠充足時，該模型能夠服務到充電站覆蓋范圍內的所有請求.

表5、6、7中的求解時間，在半小時內解決了每個實例，除了表6中資金約束需求量為5000，服務半徑為10的實例.此外，解決LP所需時間通常小于PF的求解時間，RPF的求解時間大于PF的求解時間.

表5 資金限制為5000時求解時間

表6 資金限制為10 000時求解時間

表7 資金限制為15 000時求解時間

5 結論和展望

將電動汽車引入共享汽車的系統，為這些系統的運營帶來了新的挑戰.在本文中，我們介紹了資金約束下單向電動汽車共享系統中充電站的潛在站點的選擇和車輛數量的配置的問題.

該整數規劃模型可以很容易的將共享模式進行擴展，應用到大規模.通過模擬仿真實驗表明，我們的模型能夠在合理時間內解決規模相當大的問題，下一步主要進行潛在站點的選擇方法的研究和啟發式算法求解問題的創新.