新冠疫情防控下的電動網(wǎng)約車拼車調(diào)度優(yōu)化模型

李詠潔，袁鵬程

（上海理工大學管理學院，上海 200093）

在新冠疫情COVID-19 防控時期， 隨著復工復學程度增加，對通勤交通需求也逐漸上升。 為避免乘車過程中病毒交叉?zhèn)魅粳F(xiàn)象，“健康碼”已成為居民搭乘公共交通的通行憑證[1]。我國健康碼（Health code）主要分為3 種顏色：綠色、黃色和紅色，不同顏色表示不同的新型冠狀病毒感染風險，綠色為低感染風險，可憑碼通行；黃色為中感染風險；紅色則表示具有高傳染病毒的風險；目前國內(nèi)公共交通系統(tǒng)僅對“綠碼”乘客開放乘車服務。 網(wǎng)約車作為公共交通工具的補充是居民通勤的主要出行工具[2]，當前網(wǎng)約車服務范圍僅適用于“綠碼”乘客，同時網(wǎng)約車運營商為防止病毒傳播所采取的臨時性措施難以長期獲得乘客的安全信任[3]。 當疫情復發(fā)時，網(wǎng)約車出行服務將受到嚴重的影響，同時無車一族極易受到疫情影響出現(xiàn)“打車難”的局面。 網(wǎng)約車服務范圍的局限性和安全性反映當前網(wǎng)約車運營模式在疫情防控時期不再適用，如何提升網(wǎng)約車出行安全性的同時滿足不同乘客的出行需求是提升網(wǎng)約車核心競爭力的關鍵之一，同時也是對網(wǎng)約車應急管理方面提出的重大挑戰(zhàn)。 與此同時，各地政府為推動網(wǎng)約車行業(yè)的汽車電氣化發(fā)展， 提出未來新網(wǎng)約車類型均為新能源汽車并對電動網(wǎng)約車提供購車補貼等相關政策[4]，在政策引導下電動汽車已成為網(wǎng)約車行業(yè)的發(fā)展趨勢。

1 相關研究

當前，針對常規(guī)公共交通運能與居民安全出行需求難以達到平衡的問題，不同的學者開始對新冠疫情防控時期下的通勤交通進行研究。 申嬋等[5]提出疫情防控時期下的常規(guī)公交與定制公交協(xié)調(diào)優(yōu)化的方法，建立協(xié)同優(yōu)化模型規(guī)劃不同疫情風險等級下的公交線路，通過優(yōu)化方案與常規(guī)公交運行方案對比證明定制公交對疫情防控有有益的效果。Chen 等[6]針對疫情防控特點，規(guī)劃定制公交上下車站點位置減少乘客的接觸次數(shù)，構(gòu)建優(yōu)化模型證明其優(yōu)化方案能有效降低通勤者交叉感染的風險。 同樣地，馬昌喜等[7]通過對定制公交的線路優(yōu)化最大程度滿足大部分通勤者安全出行的需求。 周繼彪等[8]則以居民需求為導向制定以城市公交、地鐵為代表的公共交通非常規(guī)防疫策略，通過多種策略制定保障疫情時期居民的出行安全。 曹源等[9]以列車編組與調(diào)度為研究對象, 提出疫情防控下基于虛擬編組的列車動態(tài)編組與調(diào)度方法，對城市軌道交通列車的調(diào)度進行優(yōu)化從而降低列車乘客的感染風險。通過以上文獻發(fā)現(xiàn)，針對疫情防控特點以降低乘客出行風險為導向，制定非常規(guī)運營模式是防止疫情傳播并滿足出行安全的有效手段之一。 但當前大部分文獻都是針對公交[5-7，10]及軌道交通[8-9]為代表的大型共享出行模式進行優(yōu)化，忽略居民在疫情期間更傾向于選擇相對更安全的小型共享出行交通方式——網(wǎng)約車出行[11]，導致網(wǎng)約車現(xiàn)實運營困境難以通過現(xiàn)有研究找到針對性的建議。 網(wǎng)約車作為城市公共交通系統(tǒng)的補充[12]，有必要對疫情防控期間的網(wǎng)約車運營模式進行深入研究。

隨著電動汽車使用率的提高，其路徑問題的研究也逐漸受到重視。 由于電動汽車主要通過電力驅(qū)動，其行駛路線和行駛時間往往受到電池的限制[13]。關于電動汽車路徑問題的研究主要集中在充電規(guī)劃方面。 Schneider 等[14]在傳統(tǒng)路徑規(guī)劃模型中加入車輛充電約束，建立了關于電動汽車的路徑規(guī)劃模型對其充電需求進行路線規(guī)劃， 但沒有考慮充電時間優(yōu)化問題。 隨后學者平衡車輛充電時間和服務 時 間 之 間 的 關 系[14-16]，F(xiàn)elipe 等[13]和Keskin 等[17]提出部分充電策略，即車輛充電時電量無需充滿即可停止充電，大大降低了充電時長并以模型目標規(guī)劃車輛路線。 王琪瑛等[18]通過解決充電站選址問題來優(yōu)化車輛充電路徑， 從而縮短車輛充電總時長。同時，揭婉晨等[19]考慮多類型電動車輛路徑問題并建立混合整數(shù)模型，通過分支定價算法解決車輛最短路問題。 馬儉[20]以車輛續(xù)航里程與充電規(guī)劃為背景對新能源汽車拼車調(diào)度問題進行研究， 通過啟發(fā)式算法求解調(diào)度模型， 并根據(jù)案例分析解決新能源汽車拼車定價問題。

不同以往的拼車模型，本文將對低風險乘客和中高風險乘客提供兩種不同的乘車服務， 同時為解決車輛充電和消毒問題將車輛消毒站和充電站元素納入模型中， 并以此構(gòu)建基于疫情防控的電動網(wǎng)約車拼車調(diào)度模型， 最后通過算例驗證模型的有效性。

2 問題描述

疫情防控時期，需要擴大電動網(wǎng)約車拼車服務范圍，盡可能滿足居民經(jīng)濟、安全的出行需求。 假設電動網(wǎng)約車服務區(qū)域內(nèi)有多個地理位置已知的消毒站點、充電站點、乘客上車點和對應下車點，車輛統(tǒng)一從車站出發(fā)到各自等候點等待乘客訂單。 為降低乘客乘車時交叉感染的風險同時滿足居民經(jīng)濟出行需求，將乘客分為兩類：第一類為低風險乘客，第二類為中高風險乘客。 網(wǎng)約車服務策略如下：當車輛服務低風險乘客時采取拼車服務策略，即車輛在滿足車載容量約束條件下允許同時對多名低風險乘客提供接送服務。 當車輛服務存在暴露風險的乘客時采取專車服務策略，當車輛將中高風險乘客送至相應下車點后車輛必須前往消毒站進行車輛消毒， 車輛完成消毒后才被允許服務下一名乘客。采取部分充電策略，即車輛在充電站充電時的電池電量只需充至規(guī)定最小電量要求即可結(jié)束充電；車輛在接送乘客過程中不允許進行車輛充電，車輛只有完成服務后才能前往充電站充電，并且當車輛電池電量不滿足完成乘客訂單時不允許接受乘客訂單請求。

3 模型建立

3.1 問題描述

存在一定數(shù)量的電動汽車和乘客隨機分布在不同位置上， 假設任何乘客都同意與他人進行拼車。 令nlow表示需要被服務的低感染乘客數(shù)量，nmed表示需要被服務的中高感染乘客數(shù)量，則在該區(qū)域范圍內(nèi)所有乘客數(shù)量為np=nlow+nmed。 該地區(qū)范圍內(nèi)存在nh輛電動汽車可為上述np名乘客提供乘車服務。該區(qū)域可為nh輛電動汽車提供充電服務和消毒服務的充電樁數(shù)量和消毒站數(shù)量分別為nf和ns。 存在有向圖G=（V，A）， 其中，V=Vlow∪Vmed∪VH∪VF∪VS∪VO∪VD，VO和VD表示虛擬節(jié)點，即所有車輛需要從VO出發(fā)，到達終點VD，VO={0}，VD={nveh+2np+ns+nf+1}；VH表示車輛當前位置節(jié)點，VH={1，2， …，nh}；Vlow和Vmed分別表示低感染乘客上下車節(jié)點和中高感染乘客上下車節(jié)點， 其中Vlow=Plow∪Dlow，Plow表示低感染乘客上車節(jié)點集合，Dlow表示低感染乘客下車節(jié)點集合，Plow={nh+1，…，nh+nlow}，Dlow={nh+np+1，…，nh+np+nlow}； 同理Vmed=Pmed∪Dmed表示中高感染乘客上下車點集合，Pmed={nh+nlow+1，…，nh+np}，Dmed={nh+np+nlow+1， …，nh+2np}；VP和VS分別表示充電站點集合和消毒站點集合，VF={nh+2np+ns+1，…，nh+2np+ns+nf}，VS={nh+2np+1，…，nh+2np+ns}。

假設nh輛電動汽車均同質(zhì)，H 表示車輛集合，每輛電動車輛h∈H，m 是車輛h 最大車容量。節(jié)點i處的負荷為qi，dij和tij分別表示i 點到j 點的行駛里程和行駛時間。 車輛h 最長服務時長為Th，乘客i在車輛h 上的乘車時長為，假設每位乘客最長乘車時間均為L。 為實現(xiàn)車輛能在一定時間范圍內(nèi)為乘客提供服務，車輛到達時間需滿足乘客點的時間窗約束[ei，li]，i∈Vlow∪Vmed。 車輛每服務完一名乘客可獲得的基本報酬為z。 假設每輛電動汽車的電池容量均為K， 且每輛車從VO出發(fā)時的初始電量為。車輛耗電量與車輛行駛里程相關，車輛h 單位行駛里程的電量消耗率為g，電池充電率為μ。 車輛h 在返回VD時電量需要不小于αK，其中α 為車輛h 最小電池水平比率。 車輛單位行駛成本和單位充電成本分別為c 和τ， 而為提高車輛服務中高感染乘客訂單數(shù)量，假設政府對服務完中風險乘客的司機提供補貼為r。

對于每位乘客i∈Plow∪Pmed，若車輛對乘客提供服務，則si=1，否則為零。 若車輛h∈H 途徑?。╥，j）∈A，則=1，否則為零；對于每輛車h∈H，其在節(jié)點i∈V 處的到達時間、車載容量、電池電量分別為，和； 車輛h 在充電站點i∈VF的充電時長為； 車輛h 在乘客上車點i∈Plow∪Pmed處的等待時間為wi。

在建立模型之前作出基本假設：每位乘客最多只能被服務一次，且乘客在受服務期間不存在換乘情況；車輛上一個乘客服務類型不影響下一個乘客服務類型；所有乘客上下車點、車輛等候點、節(jié)點間距離、時間窗要求、需求數(shù)都是提前已知的；乘客與司機不發(fā)生接觸傳播情況且司機不具有傳染風險；疫情傳播風險主要來自乘客之間近距離接觸；電動汽車采取部分充電策略且同一輛電動汽車只能經(jīng)過同一個充電站最多一次。

廣播里主持人輕聲講道：“小時候收到人家送的巧克力，總是小心翼翼地藏在口袋里，最后全都融化。長大后見多了不經(jīng)意間路過的風景，無意間到的美酒，沒有留下電話號碼的人。學會了從第一眼到最后一眼，好好享用。把人愛夠，把酒喝光，不去瞻前顧后。學會了在最快樂時說，我們干了這杯。不為什么，就現(xiàn)在?！?/p>

3.2 目標成本結(jié)構(gòu)分析

Bongiovanni 等[16]同樣研究了含時間窗的電動汽車拼車問題， 其模型的目標是使時間成本最小，其時間成本不僅包括行駛時間成本還考慮乘客延誤到達上車點的延誤費用。 本文參考了電量約束和充電時間約束，在其基礎上進行擴展，目標函數(shù)由司機總利潤最大和時間窗懲罰成本最小結(jié)合建立多目標優(yōu)化的混合整數(shù)規(guī)劃模型。 其中司機總利潤由司機服務報酬、政府補貼、車輛行駛成本和車輛充電成本組成。

3.2.1 司機服務報酬

司機每將一名乘客送達其下車點后均會獲得基本服務報酬，服務報酬與行駛里程有關，車輛完成訂單的行駛里程越遠，其獲得的服務報酬越高，但相應的行駛成本也越高。 服務報酬數(shù)學表達式如下

3.2.2 政府補貼

從司機和運營商角度來看，服務中高風險乘客帶來的經(jīng)濟效益遠沒有低風險乘客高，通過政府補貼的手段致使司機服務中高風險乘客時可獲利。 利用補貼政策激勵司機選擇服務中高風險乘客，政府補貼費用數(shù)學表達式如下

3.2.3 車輛行駛成本

車輛行駛成本指的是車輛在行駛過程中所產(chǎn)生的費用，車輛行駛成本與行駛里程直接相關。 本文將延用傳統(tǒng)拼車模型[21]中的車輛行駛成本，表達式如下

3.2.4 車輛充電成本

車輛充電成本與充電技術、充電策略、電池充電率、充電時長及單位電費等因素有關，本文假設充電站的充電技術均相同， 采取部分充電的策略，車輛電池剩余電量越少，車輛充電時長越長，充電成本越高。 本文車輛充電成本的數(shù)學表達式如下

3.3 數(shù)學模型

疫情防控期間電動汽車拼車調(diào)度優(yōu)化模型的優(yōu)化目標函數(shù)如下

式（5）為司機總利潤最大為優(yōu)化目標，式（6）為時間窗懲罰成本最小為優(yōu)化目標。 式（6）中θ1和θ2分別為車輛早、晚到達節(jié)點的懲罰系數(shù)；當車輛在時間窗內(nèi)到達時，θ1=0，θ2=0；當車輛到達i 點處的時間早于ei時，θ1＞0，θ2=0； 當?shù)竭_i 點時間晚于li時，θ1=0，θ2＞0。

模型需要滿足的約束條件包括：

1） 路徑約束，車輛統(tǒng)一從車站出發(fā)在各自等候點等待訂單請求，一名乘客最多只能由一名司機服務，乘客的上車點先于下車點服務，車輛停止服務后返回車站。

2） 時間約束，司機和乘客分別有最長行駛時間和乘車時間約束。

3） 容量約束，車輛車載量不允許超過最大車載容量，車站、車輛等候點、消毒站、充電站處的車輛載客量均為零。

4） 電量約束， 車輛電池容量恒定且電量消耗與路況、車速、充電狀態(tài)無關，只與車輛行駛里程、車輛耗電率有關；車輛訪問充電站次數(shù)不作限制，車輛在充電站的電量滿足最低電量水平比率時可結(jié)束充電； 車輛在返回車站時電量不允許低于最低電量。

5） 消毒約束，車輛將存在暴露風險（黃碼）的乘客送至其相應下車點后必須前往消毒站進行消毒，車輛可多次訪問同一消毒站。

基于以上所述建立對應的約束條件式如下

式（7）為所有被服務乘客總數(shù)。 式（8）和（9）分別表示車站為車輛的起始站和終點站。 式（10）保證車輛行駛弧連續(xù)。 式（11）和（12）保證乘客最多只能被服務一次， 且只由同一輛車提供服務。 式（13）為不同車輛可到相同消毒站進行消毒，式（14）保證車輛最多訪問一次充電站。 式（15）～式（18）約束車輛服務中高風險乘客時的行駛路線；式（15） 保證車輛將中高風險乘客送達至目的地后前往消毒站進行消毒，式（16）和式（18）保證中高風險乘客不進行拼車服務，式（17）約束車輛消毒后的行駛路線；式（19）～式（21）保證車輛服務時間的連貫性，式（22）、式（23）分別約束車輛的服務時長和乘客的乘車時長；式（24）約束車輛的車載容量，式（25）規(guī)定車輛充電容量不超過電池容量；式（26）表示車輛在等候點電量為初始狀態(tài)；式（27）～式（31）關于車輛電池電量約束，其中式（27）和式（28）表示車輛未充電前的耗電約束，式（29）和式（30）表示車輛充電后的電量充電約束。式（31）保證車輛在返回終點站時電量不低于αK；式（32）和式（33）規(guī)定車輛充電時間的上下限，其中約束條件式（24）、式（32）和式（33）中的M 為無限大數(shù)值。 式（34）～式（36）分別對決策變量進行取值約束。

4 算例分析

由于本文模型規(guī)模較大且決策變量個數(shù)較多，使用Lingo18.0 求解器求解模型的時間過長， 本節(jié)將通過3 個小規(guī)模算例驗證模型有效性。

4.1 算例描述

使用Matlab 軟件在二維矩形平面[0，50]2內(nèi)隨機生成23 個節(jié)點，各節(jié)點位置分布如圖1 所示。 其中23 個節(jié)點包括：1 個車站站點，4 個車輛等候點，7 個乘客上車點及對應7 個乘客下車點，2 個消毒站點和3 個充電站點。 本節(jié)設計3 組算例S1、S2 和S3，3 組算例所有節(jié)點個數(shù)、位置、參數(shù)數(shù)值相同，區(qū)別在于不同算例中高傳染風險乘客訂單數(shù)量不一致。 算例S1 乘客類型均為低風險乘客，即為無傳染風險型的拼車環(huán)境；算例S2 和算例S3 中風險乘客數(shù)量分別為2 名和4 名。 通過算例結(jié)果驗證模型在不同環(huán)境中均具有有效性；各算例中節(jié)點含義及參數(shù)數(shù)值參照表1。

圖1 各節(jié)點位置分布圖Fig.1 Location map of the nodes

表1 各算例中節(jié)點含義及參數(shù)數(shù)值Tab.1 Meaning of nodes and values of parameters in each calculation example

算例中關于車輛電池相關參數(shù)取值參考文獻[16]，其中包括車輛電池容量K 和車輛初始電量KhO均為14.85 kW·h， 電池消耗率和充電率均為0.055 kW/h。車輛所有行駛路段消耗的電池電量與路段行駛里程成正比，車載容量為3 人，所有乘客的最大乘車時間為30 min， 每輛車最長服務時長30 min，司機服務報酬10 元/km。 令算例中中高風險乘客盡可能被服務，設政府補貼為100 元/km，單位行駛成本2 元/km。

為簡化算例求解過程，本文假設所有車輛在開始服務時處于滿電狀態(tài)， 車輛最小電池比率為10%。 使用Dijkstra 路徑算法計算各節(jié)點間的距離，車輛節(jié)點間的行駛時間等于節(jié)點間的行駛里程，乘客上車點請求數(shù)qi=1，下車節(jié)點qi=-1，其余節(jié)點處的qi=0。具體參數(shù)取值參考表2，其中圖2 為各乘客上下車點時間窗示意圖。

表2 各參數(shù)取值Tab.2 Value of each parameter

圖2 乘客上下車點時間窗Fig.2 Passenger drop-off and boarding time windows

4.2 算例結(jié)果及分析

本文所構(gòu)建的模型為混合整數(shù)規(guī)劃模型是車輛路徑問題的拓展，屬于NP 難題[23]。 其中變量類型包含0-1 變量，約束條件為線性規(guī)劃。 Lingo 是用來求解線性和非線性優(yōu)化問題的簡易工具，但是隨著模型規(guī)模越大，其求解效率也會逐漸降低。 考慮到模型的復雜性， 為了在有限時間內(nèi)快速求解結(jié)果，算例規(guī)模不宜過大。 優(yōu)化路徑結(jié)果及乘客乘車信息如表3 所示，本文所有算例中車輛統(tǒng)一出發(fā)和返回的車站站點坐標為[0，0]。

表3 算例最優(yōu)接送路徑Tab.3 Example result

3 個場景下的所有乘客均被服務， 不同場景下派出相同車輛數(shù)但提供服務的車輛數(shù)量有所不同。在所有乘客均是無傳染風險的場景下（算例S1）只需要3 輛電動網(wǎng)約車提供服務，車輛的總服務里程為22.8 km。 算例S2 使用4 輛車服務所有乘客，車輛總服務里程為29 km， 服務總里程增加了27.19%。 案例S3 使用4 輛電動網(wǎng)約車提供服務，優(yōu)化后的司機總利潤為756.97 元，車輛總服務里程為39.7 km， 相較于算例S2 其司機總利潤增長了37.6%，服務總里程增加了36.90%。 表3 詳細記錄每輛車的優(yōu)化路徑和服務里程等信息，表4 為各算例求解結(jié)果比較。 從圖3 可以觀察到，隨著拼車場景中高風險乘客訂單數(shù)量的增加，車輛前往消毒站的次數(shù)也增加，車輛總服務里程也隨之上升。

圖3 不同算例的優(yōu)化結(jié)果Fig.3 Optimization results for different cases

表4 算例求解結(jié)果比較Tab.4 Comparison of the solution results of the algorithms

5 結(jié)論

1） 考慮了乘客傳染風險性因素，在常規(guī)電動汽車拼車模型的基礎上增加車輛消毒站元素，構(gòu)建了基于疫情防控條件下的電動網(wǎng)約車拼車調(diào)度優(yōu)化模型， 并使用Lingo18.0 求解器求解小規(guī)模算例驗證模型的有效性。

2） 給出了不同拼車服務環(huán)境下的算例求解結(jié)果。 通過案例分析可知，無論服務環(huán)境中是否存在傳染風險的乘客，車輛調(diào)度安排都能滿足所有傳染風險類型乘客的出行需求。 車輛服務路線保證了中高風險乘客與低風險乘客乘車期間的零接觸，車輛在接送完中高風險乘客后車輛強制前往消毒站進行消毒，有效降低網(wǎng)約車拼車模式下的乘客交叉感染的概率。

3） 可為城市交通的疫情防控管理提供借鑒，可為網(wǎng)約車運營商在疫情防控時期下的電動網(wǎng)約車應急管理提供一定的參考。