鄭建國，祁光輝

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

在大型城市，停車難問題和高昂的停車成本使得普通的上班族來講擁有私家車不再具有吸引力.汽車共享系統(tǒng)是私人車輛所有權(quán)的替代方案.家庭或企業(yè)不必?fù)碛幸惠v或多輛汽車，而是共同使用一些車輛來滿足需求，這一類系統(tǒng)在20世紀(jì)70年代到80年代通過試點(diǎn)實(shí)施，近幾年取得了相當(dāng)大的發(fā)展.

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

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

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

在第2 節(jié)中，將要回顧文獻(xiàn)中的相關(guān)著作.在第3 節(jié)中，定義了本文研究的問題之后，提供了ILP 公式的細(xì)節(jié)和模型所需的預(yù)處理程序.最后，進(jìn)行了模擬仿真實(shí)驗(yàn)的結(jié)果，對(duì)其進(jìn)行分析.

1 相關(guān)研究

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

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

除了上面提到的優(yōu)化模型，文獻(xiàn)[5]提供了一個(gè)基于離散事件模擬的模型，該模型評(píng)估了汽車共享系統(tǒng)中策略變化的影響，例如創(chuàng)建新站，增加車站容量，合并或分離站.作者通過對(duì)加拿大蒙特利爾汽車共享組織數(shù)據(jù)的幾種策略評(píng)估了他們的模型.

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

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

2 問題定義

該模型的動(dòng)機(jī)是規(guī)劃汽車共享系統(tǒng)中單向行駛，并且時(shí)間不能自由浮動(dòng)的，其中共享使用的汽車用于為特定地理區(qū)域內(nèi)的旅行提供服務(wù).在介紹問題制定之前，我們從系統(tǒng)的需求和供給特征兩個(gè)方面對(duì)系統(tǒng)進(jìn)行了描述.

(1)車輛

整個(gè)系統(tǒng)中使用同一種類型的電動(dòng)汽車，任何類型的旅行請(qǐng)求都可以被任何可用的車輛所提供服務(wù).

(2)車站

車輛在指定的車站出發(fā)和?？?車站有必要的基礎(chǔ)設(shè)施來停車和為車輛充電；每個(gè)車站提供特定數(shù)量的停車位，這決定了車站的大小.站的大小因站而異，每個(gè)站的大小決定了它的容量.

(3)時(shí)間間隔

每個(gè)周期劃分為不同的時(shí)間間隔(不一定一樣長)，車輛出發(fā)的操作在時(shí)間間隔開始時(shí)開始，車輛到達(dá)和充電完成操作在時(shí)間間隔結(jié)束時(shí)結(jié)束.

(4)運(yùn)營操作

這個(gè)系統(tǒng)的運(yùn)營涉及兩項(xiàng)操作:租賃；充電.

①該系統(tǒng)是在預(yù)定的基礎(chǔ)上運(yùn)行并允許單程租用車輛.在預(yù)定時(shí)，用戶的出發(fā)地點(diǎn)、到達(dá)地點(diǎn)、出發(fā)時(shí)間、到達(dá)時(shí)間是可獲得的.在預(yù)定做出的時(shí)間段，車輛在用戶在出發(fā)地點(diǎn)可訪問的車站獲得車輛；并在到達(dá)地點(diǎn)可訪問的車站停放.假定每一次租賃都是從一個(gè)時(shí)間間隔的開始時(shí)開始，然后在一個(gè)時(shí)間間隔結(jié)束時(shí)結(jié)束.

②本文所建立的模型采用了電動(dòng)汽車.為了對(duì)電動(dòng)汽車充電時(shí)間進(jìn)行建模，假設(shè)車輛返回車站后，必須在車站停留一段固定的時(shí)間，這代表了車輛的充電時(shí)間.

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

在該模型中，需求中心表示可以由同一組(候選)站點(diǎn)服務(wù)的需求點(diǎn).為了說明中心是如何定義的，圖1 描繪了需求的來源和目的地以及站點(diǎn)位置.圖2 示出了通過不同的起點(diǎn)和目的地位置可訪問的站點(diǎn).請(qǐng)注意，一個(gè)給定的起點(diǎn)/終點(diǎn)可以有多個(gè)對(duì)應(yīng)的車站站點(diǎn).可以訪問同一組車站的原點(diǎn)/目的點(diǎn)聚集在一起，構(gòu)成一個(gè)中心.圖3 表示與這些中心相關(guān)聯(lián)的兩個(gè)中心(陰影區(qū)域)和旅程(需求).將需求分組減少了變量的數(shù)量，因?yàn)榫哂邢嗤鹪春湍康牡刂行牡穆眯斜唤M合在一起.這種分組允許解決較大的問題實(shí)例.

(6)需求

需求有時(shí)間和空間兩個(gè)維度.需求表示擁有用戶的起點(diǎn)和終點(diǎn)并具有出發(fā)時(shí)間和到達(dá)時(shí)間的訂單的集合.能夠?yàn)橐粋€(gè)訂單提供服務(wù)需要滿足以下兩個(gè)條件:

①在出發(fā)時(shí)間間隔開始時(shí)可從起始位置相應(yīng)的車站獲得車輛；

②在到達(dá)時(shí)間時(shí)間間隔結(jié)束時(shí)到達(dá)位置相應(yīng)的車站擁有停車位.

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

(7)成本和收入

該模型的目標(biāo)函數(shù)是最大化運(yùn)營商的利潤.運(yùn)營商的收入包括車輛租賃收入，而成本包括車輛的維護(hù)，運(yùn)營以及車站開放后運(yùn)營費(fèi)用.

3 實(shí)驗(yàn)分析

在這一部分中，首先定義了用于描述模型的集合和索引，以及4.2 節(jié)中的函數(shù)、變量和參數(shù).第4.2 節(jié)給出混合整數(shù)規(guī)劃模型，并對(duì)其目標(biāo)函數(shù)和約束條件進(jìn)行了詳細(xì)的描述.

3.1 輸入

(1)索引和集合:

①p,jJ:潛在站點(diǎn)的索引；

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

(2)參數(shù)定義:

①V=f1,···,ng:為節(jié)點(diǎn)的集合；

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

③fj:開放車站j的成本，它是關(guān)于充電站車位數(shù)量Cj的線性函數(shù)；

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

⑤g:電動(dòng)汽車運(yùn)行成本；

⑥G:電動(dòng)汽車購買成本；

⑦T=f0,···,τg:時(shí)間節(jié)點(diǎn)；

⑧k=fOk,Dk,Tk,Tk+dk,Pk,δijg:Ok為請(qǐng)求k的起點(diǎn)；c 為請(qǐng)求k的終點(diǎn)，Tk為請(qǐng)求k的起始時(shí)間，Tk+dk為請(qǐng)求k的終止時(shí)間，Pk為請(qǐng)求k的利潤；δij為請(qǐng)求k的電量.

(3)輔助變量:

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

圖1 T時(shí)間內(nèi)的需求K

圖3 請(qǐng)求最終的可行結(jié)果

預(yù)處理程序的偽代碼，偽代碼如下:

算法1.預(yù)處理程序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:請(qǐng)求h所使用的車輛在t時(shí)刻已經(jīng)在車站j充電，否則為0；

②=1:請(qǐng)求h所要使用的車輛在t時(shí)刻從車站j出發(fā)，否則為0；

(4)決策變量:

①uh=1:請(qǐng)求h被 服務(wù)；

②:車站j在t時(shí)刻擁有的電動(dòng)汽車的數(shù)量；

④Cj:站點(diǎn)j的能力；

⑤yj:車站j是否打開.

3.2 模型建立

s.t.

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

4 仿真實(shí)驗(yàn)

這一部分通過創(chuàng)建一組實(shí)例測試了模型，其中將街道網(wǎng)絡(luò)建模為網(wǎng)格圖，其參數(shù)在一下部分中詳細(xì)描述.

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

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

在表1中，總結(jié)了每個(gè)解決問題實(shí)例的預(yù)處理結(jié)果.在該表中，列給出了從模擬數(shù)據(jù)中獲取的請(qǐng)求數(shù)量，為潛在站點(diǎn)的數(shù)量，為可能被服務(wù)請(qǐng)求的數(shù)量，為預(yù)處理期間可能服務(wù)的潛在的路徑數(shù)量，p_t顯示預(yù)處理期間可能服務(wù)的潛在的路徑數(shù)量(以秒為 單位).

表1 預(yù)處理結(jié)果

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

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

表2 資金限制為5000時(shí)的解和gap

表3 資金限制為10 000時(shí)的解和gap

表4 資金限制為15 000時(shí)的解和gap

當(dāng)資金比較缺乏時(shí)，該模型更傾向于建設(shè)更多的充電點(diǎn)為更多的客戶提供服務(wù)；資金由5000 變?yōu)?0 000時(shí)更加明顯.從以上求解結(jié)果可以看到，每種求解結(jié)果PF 和LP 之間的Gap 小于2%.除了表2中的PF 和LP 之間的Gap 比較大；說明給模型能夠得到一個(gè)比較好的求解結(jié)果.當(dāng)資金足夠充足時(shí)，該模型能夠服務(wù)到充電站覆蓋范圍內(nèi)的所有請(qǐng)求.

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

表5 資金限制為5000時(shí)求解時(shí)間

表6 資金限制為10 000時(shí)求解時(shí)間

表7 資金限制為15 000時(shí)求解時(shí)間

5 結(jié)論和展望

將電動(dòng)汽車引入共享汽車的系統(tǒng)，為這些系統(tǒng)的運(yùn)營帶來了新的挑戰(zhàn).在本文中，我們介紹了資金約束下單向電動(dòng)汽車共享系統(tǒng)中充電站的潛在站點(diǎn)的選擇和車輛數(shù)量的配置的問題.

該整數(shù)規(guī)劃模型可以很容易的將共享模式進(jìn)行擴(kuò)展，應(yīng)用到大規(guī)模.通過模擬仿真實(shí)驗(yàn)表明，我們的模型能夠在合理時(shí)間內(nèi)解決規(guī)模相當(dāng)大的問題，下一步主要進(jìn)行潛在站點(diǎn)的選擇方法的研究和啟發(fā)式算法求解問題的創(chuàng)新.