考慮用戶(hù)行程時(shí)間不確定性的共享汽車(chē)調(diào)度魯棒優(yōu)化研究

劉陽(yáng)東， 劉海洋

(1.上海交通大學(xué) 船舶海洋與建筑工程學(xué)院，上海 200240；2.深圳市城市交通規(guī)劃設(shè)計(jì)研究中心有限公司，廣東 深圳 518021；3. 同濟(jì)大學(xué) 城市風(fēng)險(xiǎn)管理研究院，上海 200070)

0 引言

近年來(lái)，共享汽車(chē)這一新興交通模式，因其在減少環(huán)境污染、緩解道路資源及停車(chē)資源緊張、提高城市居民出行機(jī)動(dòng)性等方面的良好表現(xiàn)，逐漸在全世界范圍內(nèi)的高人口密度城市中興起和發(fā)展。傳統(tǒng)的共享汽車(chē)運(yùn)營(yíng)模式要求用戶(hù)將車(chē)輛歸還至借出站點(diǎn)，即 “雙程共享汽車(chē)服務(wù)”(“two-way carsharing service”)，該模式的優(yōu)點(diǎn)是不會(huì)造成共享汽車(chē)在各站點(diǎn)間的重新分布，因而很少需要在站點(diǎn)間調(diào)配車(chē)輛，也無(wú)需擔(dān)心歸還車(chē)輛數(shù)超過(guò)站點(diǎn)容量，簡(jiǎn)化了共享汽車(chē)企業(yè)運(yùn)營(yíng)管理流程，成本較少。但這一模式也極大地限制了用戶(hù)的使用自由，對(duì)于全出行鏈中起訖點(diǎn)不同或需要在行程中途作長(zhǎng)時(shí)間停留的用戶(hù)，該模式不僅會(huì)增加用戶(hù)不必要的出行成本，而且會(huì)因共享汽車(chē)閑置而造成資源浪費(fèi)。因此，為了更好地服務(wù)用戶(hù)，共享汽車(chē)企業(yè)紛紛推出“單程共享汽車(chē)服務(wù)”(“one -way carsharing service”)，在該模式下，用戶(hù)可以將車(chē)輛歸還至任一站點(diǎn)。此舉極大地增加了用戶(hù)用車(chē)的靈活性,豐富了共享汽車(chē)的應(yīng)用場(chǎng)景，但同時(shí)也促成了車(chē)輛在站點(diǎn)間的重新分布，導(dǎo)致部分站點(diǎn)出現(xiàn)無(wú)車(chē)可用或有車(chē)難還的情況，需要運(yùn)營(yíng)企業(yè)在站點(diǎn)間調(diào)度車(chē)輛以緩解這種供需不平衡的問(wèn)題。

目前，國(guó)內(nèi)針對(duì)共享汽車(chē)站點(diǎn)間調(diào)度的研究較少，國(guó)外因共享汽車(chē)應(yīng)用較早，研究文獻(xiàn)相對(duì)較多[1]。Bruglieri et al[2]針對(duì)站點(diǎn)間靜態(tài)人員調(diào)度問(wèn)題，建立了一個(gè)考慮時(shí)間窗的混合整數(shù)規(guī)劃模型，并提出了一個(gè)簡(jiǎn)單、高效的啟發(fā)式算法求解模型。Kek et al[3]利用時(shí)空網(wǎng)絡(luò)模型建立了一個(gè)基于混合整數(shù)規(guī)劃的“優(yōu)化—趨勢(shì)—仿真”3階段決策支持系統(tǒng)，解決了調(diào)度人員在站點(diǎn)間動(dòng)態(tài)調(diào)度問(wèn)題。Nourinejad et al[4]先是研究了有預(yù)約情況下的車(chē)輛調(diào)度問(wèn)題，通過(guò)將用戶(hù)還車(chē)視作事件(Event)，采用離散事件仿真法對(duì)模型進(jìn)行求解。隨后，Nourinejad et al[5]將模型進(jìn)一步拓展，同時(shí)考慮車(chē)輛調(diào)度和人員調(diào)度問(wèn)題，構(gòu)建了多層旅行商(m-TSP，multi-traveling salesman problem)模型，并通過(guò)基于分解算法(decomposition method)的啟發(fā)式方法求解模型。Xu et al[6]研究了戰(zhàn)略層面的車(chē)隊(duì)規(guī)模和租車(chē)定價(jià)問(wèn)題，同時(shí)整合了運(yùn)營(yíng)層面的車(chē)輛及人員動(dòng)態(tài)調(diào)度問(wèn)題，建立起非線(xiàn)性、非凸的混合整數(shù)規(guī)劃模型，并通過(guò)基于外逼近算法的全局最優(yōu)法求得模型的最優(yōu)解或 ε-最優(yōu)解( ε-optimal solution)，最后通過(guò)新加坡案例驗(yàn)證了模型及算法的有效性。上述文獻(xiàn)從不同角度研究了共享汽車(chē)調(diào)度問(wèn)題，但模型中均假定參數(shù)等于某一定值或符合確定的函數(shù)關(guān)系。然而，實(shí)際生活中的不確定因素往往具備偶然性和隨機(jī)性，其完全信息難以提前獲知。因此，有必要研究信息不完全已知的不確定因素影響下的車(chē)輛調(diào)度問(wèn)題。

現(xiàn)有文獻(xiàn)中研究的共享汽車(chē)系統(tǒng)不確定因素主要為起訖點(diǎn)間的用戶(hù)需求量。Nair et al[7]建立了包含機(jī)會(huì)約束的隨機(jī)整數(shù)規(guī)劃模型，通過(guò)分治法(divide and conquer)產(chǎn)生多個(gè)p-有效點(diǎn)，進(jìn)而將模型劃為多組不相容且凸的混合整數(shù)規(guī)劃模型進(jìn)行求解。Fan[8-9]建立了多階段隨機(jī)整數(shù)線(xiàn)性規(guī)劃模型，采用隨機(jī)規(guī)劃等方法進(jìn)行求解，解決了用戶(hù)隨機(jī)性需求影響下車(chē)輛動(dòng)態(tài)分配問(wèn)題。冉倫等[10]對(duì)比了3種不同需求特征下(確定、隨機(jī)和部分不確定)的調(diào)度模型，通過(guò)在Matlab中調(diào)用CVX并嵌入mosek和gurobi求解器對(duì)模型完成求解；冉倫等[11]建立了分布式魯棒優(yōu)化機(jī)會(huì)約束車(chē)輛調(diào)度模型，采用Ghaoui方法將模型轉(zhuǎn)化為易求解的混合整數(shù)線(xiàn)性規(guī)劃模型，進(jìn)而求解。

然而，以上研究均未考慮用戶(hù)行程時(shí)間不確定性對(duì)運(yùn)營(yíng)企業(yè)車(chē)輛調(diào)度的影響。眾所周知，共享汽車(chē)站點(diǎn)內(nèi)的存車(chē)狀態(tài)是企業(yè)安排調(diào)度方案的決策基礎(chǔ)，不同的存車(chē)狀態(tài)可能產(chǎn)生不同的調(diào)度方案。而用戶(hù)行程時(shí)間的不確定性(通常表現(xiàn)為還車(chē)時(shí)間的不確定)導(dǎo)致站點(diǎn)內(nèi)的存車(chē)狀態(tài)同樣具備了不確定性，若對(duì)此不加考慮，將導(dǎo)致提前制定的調(diào)度方案可能與實(shí)際需求不符，影響企業(yè)運(yùn)營(yíng)成本和用戶(hù)使用體驗(yàn)。因此，在Nourinejad et al[4-5]的研究基礎(chǔ)上，將共享汽車(chē)用戶(hù)行程的時(shí)間不確定性納入模型，對(duì)模型進(jìn)行改進(jìn)，建立了魯棒優(yōu)化調(diào)度模型，并通過(guò)算例對(duì)模型進(jìn)行驗(yàn)證。最后，對(duì)共享汽車(chē)企業(yè)的運(yùn)營(yíng)調(diào)度提出建議。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述及假設(shè)

在共享汽車(chē)運(yùn)營(yíng)調(diào)度中，當(dāng)運(yùn)營(yíng)企業(yè)獲悉用戶(hù)的用車(chē)需求信息(如起始站點(diǎn)、終到站點(diǎn)、行程時(shí)間)后，可以據(jù)此安排站點(diǎn)內(nèi)的備車(chē)數(shù)量以及站點(diǎn)間的車(chē)輛調(diào)度計(jì)劃。而用戶(hù)行程時(shí)間的不確定性對(duì)站點(diǎn)備車(chē)和車(chē)輛調(diào)度均有影響，例如，用戶(hù)1預(yù)計(jì)在9:00抵達(dá)站點(diǎn)A，用戶(hù)2預(yù)期在9:05從站點(diǎn)A出發(fā)，且站點(diǎn)A在時(shí)間段9:00～9:05沒(méi)有閑置存車(chē)，若用戶(hù)1如期抵達(dá)站點(diǎn)，則用戶(hù)2可駕乘用戶(hù)1的歸還車(chē)輛以滿(mǎn)足需求，但若用戶(hù)1未能如期抵達(dá)站點(diǎn)A時(shí)，則需另外從其他站點(diǎn)調(diào)度車(chē)輛至站點(diǎn)A來(lái)滿(mǎn)足用戶(hù)2的用車(chē)需求。因此，在規(guī)劃調(diào)度方案時(shí)，若不將用戶(hù)行程時(shí)間的不確定性納入考慮范疇，則可能導(dǎo)致提前預(yù)定車(chē)輛的用戶(hù)在出發(fā)時(shí)刻無(wú)車(chē)可用，長(zhǎng)此以往，將對(duì)公司的市場(chǎng)信譽(yù)造成較大的負(fù)面影響?；诖?，在已有文獻(xiàn)的研究基礎(chǔ)上，進(jìn)一步將用戶(hù)行程時(shí)間不確定性加入模型進(jìn)行改進(jìn)，建立了以運(yùn)營(yíng)企業(yè)成本為目標(biāo)函數(shù)、以站點(diǎn)間車(chē)輛調(diào)度策略為決策變量的魯棒優(yōu)化模型。

相關(guān)假設(shè)：①用戶(hù)均能按時(shí)從起點(diǎn)站點(diǎn)出發(fā)，行程時(shí)間的不確定性可以用終到站點(diǎn)時(shí)刻的波動(dòng)進(jìn)行表征；②所有用戶(hù)的行程時(shí)間不確定性符合同樣特征(同質(zhì)性)；③用戶(hù)需求均得到滿(mǎn)足。

1.2 參數(shù)與變量

決策變量：xij為調(diào)度指示變量，若xij=1，表示一輛共享汽車(chē)從用戶(hù)i的行程終點(diǎn)站調(diào)度至用戶(hù)j的行程起點(diǎn)車(chē)站，否則為0。

1.3 確定性調(diào)度模型

基于Nourinejad et al[4-5]的研究，構(gòu)建確定性共享汽車(chē)調(diào)度優(yōu)化模型(DRM，Deterministic Relocation Model)如下

(1)

(2)

(3)

xij(Dj-tr(Ni,Mj)-Ai)≥0, ?i,j∈U

(4)

(5)

xij={0,1}, ?i,j∈U

(6)

其中，式(1)為目標(biāo)函數(shù)，其主要目標(biāo)是系統(tǒng)成本最小化，包括車(chē)輛使用成本和車(chē)輛調(diào)度成本；式(2)保證了每個(gè)用戶(hù)的用車(chē)需求都能得到滿(mǎn)足；式(3)為流量守恒公式；式(4)保證了調(diào)度方案的可行性，當(dāng)xij=1時(shí)，調(diào)度任務(wù)能夠在用戶(hù)j出發(fā)前完成；式(5)表示使用的車(chē)輛總數(shù)；式(6)表示xij為0-1整數(shù)變量。

1.4 基于用戶(hù)行程時(shí)間不確定性的魯棒優(yōu)化調(diào)度模型

用戶(hù)在行程中可能受到道路擁堵、紅燈過(guò)多、對(duì)終到站點(diǎn)位置不清晰等主客觀情況干擾，導(dǎo)致行程時(shí)間出現(xiàn)變化：早于或遲于預(yù)計(jì)終到時(shí)刻，使得實(shí)際終到時(shí)刻相對(duì)預(yù)計(jì)終到時(shí)刻表現(xiàn)出一定波動(dòng)性。假設(shè)終到時(shí)刻的波動(dòng)為不確定的隨機(jī)變量，其概率分布信息不完全已知，但已知其波動(dòng)上下界。即

(7)

因隨機(jī)變量只存在于確定性模型的式(4)中，則在魯棒優(yōu)化模型中可將式(4)改寫(xiě)為

(8)

它等價(jià)于

xij[Dj-tr(Ni,Mj)-(Ai+ε(Ai-Di))]≥0, ?i,j∈U

(9)

因此，基于用戶(hù)行程時(shí)間不確定性的魯棒優(yōu)化調(diào)度模型(RRM，Robust Relocation Model)的組成主要包括：目標(biāo)函數(shù)式(1)，約束條件式(2)、式(3)、式(9)、式(5)、式(6)。

2 案例分析

2.1 案例概況

案例數(shù)據(jù)主要包括站點(diǎn)網(wǎng)絡(luò)數(shù)據(jù)和用戶(hù)需求數(shù)據(jù)2部分。選取文獻(xiàn)[1]中公開(kāi)的位于上海市嘉定區(qū)的5個(gè)“Evcard”共享汽車(chē)站點(diǎn)信息作為站點(diǎn)網(wǎng)絡(luò)數(shù)據(jù)(如表1所示)，其中，站點(diǎn)0為添加的虛擬站點(diǎn)，假設(shè)系統(tǒng)內(nèi)的共享汽車(chē)車(chē)輛都由該虛擬站點(diǎn)發(fā)出，其他各站點(diǎn)與虛擬站點(diǎn)間的距離均為0，并且，為計(jì)算方便，模型中涉及到的站點(diǎn)間行程時(shí)間直接采用表1中的數(shù)值，不再做路程—時(shí)間之間的進(jìn)一步轉(zhuǎn)換(如：表1中的數(shù)值10在模型中代表10個(gè)單位時(shí)間)；用戶(hù)需求數(shù)據(jù)因較難獲取，參考文獻(xiàn)[4]、文獻(xiàn)[5]中的處理方式，通過(guò)隨機(jī)產(chǎn)生每位用戶(hù)的起始站點(diǎn)(Mi)、終到站點(diǎn)(Ni)和出發(fā)時(shí)刻(Di)等數(shù)據(jù)，用戶(hù)終到時(shí)刻以出發(fā)時(shí)刻加上站點(diǎn)間平均行程時(shí)間獲得(Ai=Di+tr(Mi,Ni))，產(chǎn)生的用戶(hù)需求信息如表2所示；考慮到實(shí)際生活中，共享汽車(chē)站點(diǎn)間車(chē)輛失衡情況主要發(fā)生在早晚高峰期，針對(duì)此，將研究時(shí)長(zhǎng)取為2 h,以2 min為1個(gè)單位時(shí)間，共劃分為60個(gè)單位時(shí)間，假設(shè)用戶(hù)用車(chē)和調(diào)度任務(wù)均在該2 h內(nèi)完成；參數(shù)δ和β分別取為200和10。

表1 共享汽車(chē)站點(diǎn)間距離[1] km

表2 用戶(hù)需求信息

2.2 結(jié)果分析

調(diào)度模型通過(guò)在Visual Studio 2015操作平臺(tái)使用C++編程并嵌入CPLEX12.6進(jìn)行求解，計(jì)算機(jī)為64位操作系統(tǒng)，處理器為Intel(R) Core(TM) i7-8550U CPU @ 1.80 GHz，安裝內(nèi)存為 2 GHz。

圖1 最壞情況下的系統(tǒng)成本隨用戶(hù)出行時(shí)間不確定性變化而變化的情況

圖1展示了確定性模型和魯棒模型在不同的用戶(hù)出行時(shí)間不確定性上限下(ε)最壞情況發(fā)生時(shí)的系統(tǒng)成本變化情況?？煽闯觯?/p>

(1)用戶(hù)出行時(shí)間不確定性對(duì)于系統(tǒng)成本變化具有重要影響。根據(jù)圖中曲線(xiàn)走向趨勢(shì)，在整體上，最壞情況發(fā)生時(shí)系統(tǒng)成本隨用戶(hù)出行時(shí)間不確定性的增大而增大。

(2)魯棒模型在最壞情況發(fā)生時(shí)的系統(tǒng)成本增長(zhǎng)幅度遠(yuǎn)小于確定性模型。當(dāng)用戶(hù)出行時(shí)間不確定性表征系數(shù)ε從0.1增長(zhǎng)到1.0時(shí)，確定性模型最壞情況下的系統(tǒng)成本從1 850元增長(zhǎng)到3 000元，增長(zhǎng)幅度達(dá)62.2%，而魯棒模型從1 280元增長(zhǎng)到2 030元，增長(zhǎng)幅度僅為58.6%，這在一定程度上表明，魯棒模型在應(yīng)對(duì)用戶(hù)出行時(shí)間不確定性風(fēng)險(xiǎn)時(shí)更具成本節(jié)約的特點(diǎn)。

(3)確定性模型系統(tǒng)成本變化呈現(xiàn)出“躍遷式”特點(diǎn)，而魯棒模型成本變化則相對(duì)平緩。確定性模型因只針對(duì)某一特定情況制定對(duì)應(yīng)的調(diào)度方案，調(diào)度方案本身缺乏靈活性，在文中，當(dāng)用戶(hù)出行時(shí)間不確定性最壞情況發(fā)生時(shí)，確定性模型下的調(diào)度方案只會(huì)出現(xiàn)2種情況：①原調(diào)度方案仍能滿(mǎn)足最壞情況下的用戶(hù)需求，系統(tǒng)成本不變化；②因受公式(4)嚴(yán)格限制，導(dǎo)致部分用戶(hù)需求難以通過(guò)原調(diào)度方案中在站點(diǎn)間調(diào)配車(chē)輛來(lái)滿(mǎn)足，而需額外在站點(diǎn)內(nèi)增加備車(chē)數(shù)量，考慮到系統(tǒng)成本結(jié)構(gòu)中備車(chē)成本的權(quán)重遠(yuǎn)大于調(diào)度車(chē)輛成本的權(quán)重，此時(shí)，系統(tǒng)成本增長(zhǎng)較為明顯。因此，確定性模型的成本變化表現(xiàn)為“躍遷式”。魯棒模型因可提前預(yù)判風(fēng)險(xiǎn)，減少了車(chē)站內(nèi)的總備車(chē)數(shù)量，同時(shí)增強(qiáng)了系統(tǒng)應(yīng)對(duì)風(fēng)險(xiǎn)的魯棒性，使得用戶(hù)需求盡可能地通過(guò)在站點(diǎn)間調(diào)度車(chē)輛而非額外在站點(diǎn)內(nèi)增加備車(chē)來(lái)滿(mǎn)足，因此，其成本增長(zhǎng)表現(xiàn)得更為平緩。

圖2展示了魯棒模型中系統(tǒng)成本隨參數(shù)ε變化的敏感性分析。由圖2可見(jiàn)，隨著ε的增大，系統(tǒng)成本逐漸遞增，其中，當(dāng)ε從0增長(zhǎng)到0.8以及從1.4增長(zhǎng)到1.8的過(guò)程中，系統(tǒng)成本增長(zhǎng)相對(duì)較快，分別從1 280元上漲到2 030元和從2 030元上漲到2 400元，而當(dāng)ε在0.8～1.4之間時(shí)，系統(tǒng)成本則基本保持不變，維持在2 030元左右。

圖2 魯棒模型中參數(shù)ε的敏感性分析

圖3 魯棒模型中參數(shù)ρ隨ε變化而變化的情況

綜合以上分析，建議共享汽車(chē)企業(yè)結(jié)合運(yùn)營(yíng)數(shù)據(jù)，掌握用戶(hù)群體的行程延誤時(shí)長(zhǎng)分布特征，以確定適合的ε取值，從而更加靈活有效地制定系統(tǒng)車(chē)輛調(diào)度方案，在增強(qiáng)系統(tǒng)抵抗不確定性風(fēng)險(xiǎn)能力的同時(shí)，增強(qiáng)系統(tǒng)控制成本的能力。

3 結(jié)論

在確定性共享汽車(chē)車(chē)輛調(diào)度模型基礎(chǔ)上，創(chuàng)新性地考慮了用戶(hù)行程時(shí)間不確定性對(duì)共享汽車(chē)企業(yè)車(chē)輛調(diào)度的影響，案例分析結(jié)果為共享汽車(chē)企業(yè)的實(shí)際調(diào)度和成本控制提供了新思路。但為了研究方便，設(shè)定了嚴(yán)格的假設(shè)條件以簡(jiǎn)化模型，未考慮調(diào)度人員在調(diào)度過(guò)程中行程時(shí)間不確定性對(duì)系統(tǒng)的影響，也未考慮調(diào)度人員因在站點(diǎn)間調(diào)度車(chē)輛而產(chǎn)生的分布不均衡問(wèn)題，對(duì)于電動(dòng)汽車(chē)的“里程焦慮”(“range anxiety”)問(wèn)題也未加討論。未來(lái)可對(duì)這些問(wèn)題做進(jìn)一步研究。