劉陽東， 劉海洋

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

0 引言

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

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

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

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

1 問題描述與建模

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

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

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

1.2 參數(shù)與變量

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

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

基于Nourinejad et al[4-5]的研究，構(gòu)建確定性共享汽車調(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)為目標函數(shù)，其主要目標是系統(tǒng)成本最小化，包括車輛使用成本和車輛調(diào)度成本；式(2)保證了每個用戶的用車需求都能得到滿足；式(3)為流量守恒公式；式(4)保證了調(diào)度方案的可行性，當(dāng)xij=1時，調(diào)度任務(wù)能夠在用戶j出發(fā)前完成；式(5)表示使用的車輛總數(shù)；式(6)表示xij為0-1整數(shù)變量。

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

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

(7)

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

(8)

它等價于

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

(9)

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

2 案例分析

2.1 案例概況

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

表1 共享汽車站點間距離[1] km

表2 用戶需求信息

2.2 結(jié)果分析

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

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

圖1展示了確定性模型和魯棒模型在不同的用戶出行時間不確定性上限下(ε)最壞情況發(fā)生時的系統(tǒng)成本變化情況。可看出：

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

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

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

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

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

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

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

3 結(jié)論

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