考慮疫情擴散傳播風險的多目標拼車應急管理優(yōu)化調(diào)度模型

摘 要：為了解決在疫情背景下傳統(tǒng)拼車出行模式面臨的交互傳染風險，對疫情背景下的拼車管理進行分析，提出了將低風險及潛在風險乘客分開服務的拼車策略。在進一步考慮拼車系統(tǒng)應兼顧的社會效益及服務質(zhì)量的基礎上，構建了在滿足基本額定盈利及最小化等待時長的雙目標拼車應急管理優(yōu)化調(diào)度模型，并給出了求解該模型的組合模擬退火算法。通過具體算例對模型的有效性進行驗證，結果表明模型能夠較快收斂到一個穩(wěn)定值，且計算結果能夠反映實際場景，說明了模型及算法的有效性。最后，通過一個仿真實驗對所構建模型在病毒傳播中的作用進行了分析，結果顯示所構建的模型可以有效抑制拼車導致的病毒傳播速度。

關鍵詞：新冠疫情；拼車調(diào)度；應急管理；組合模擬退火算法

中圖分類號：TP393.04 文獻標志碼：A

文章編號：1001-3695（2022）11-024-3351-07

doi：10.19734/j.issn.1001-3695.2022.04.0172

Multi-objective optimal ridesplitting scheduling model considering risk of epidemic spread

Yuan Pengcheng¹，Lin Xuxun²，Han Yin¹

（1.Business School，University of Shanghai for Science amp; Technology，Shanghai 200093，China；2.Business School of Changzhou University，Changzhou Jiangsu 213164，China）

Abstract：Under the background of COVID-19 epidemic，the traditional ridesplitting scheduling mode is facing the potential risk of cross infection，which brings insecurity to travellers.In order to solve this contradiction，this paper firstly analyzed the matching constraints among travellers under the background of the epidemic，proposed a ridesplitting strategy to separate low-risk and potential risk passengers.Considering the social benefits and service quality of the platform under the COVID-19，this paper developed a dual objective ridesplitting emergency management optimization scheduling model which minimized the wai-ting time on the basis of rated profit，and proposed a combined simulated annealing algorithm for this model.The effectiveness of the model and algorithm was verified by a specific example.The results show that the model can converge to a stable value，and the calculation results can truly reflect the actual scene，which shows the effectiveness of the model and algorithm.Finally，through a simulation experiment，this paper analyzed the role of the model in virus transmission.The results show that the model can effectively inhibit the virus transmission speed caused by ridesplitting.

Key words：COVID-19 epidemic；ridesplitting scheduling；emergency management；hybrid simulated annealing algorithm

作者簡介：袁鵬程（1982-），男，山西晉城人，副教授，博士，主要研究方向為交通系統(tǒng)建模與分析（danis_cx@126.com）；林徐勛（1984-），男，浙江溫州人，講師，博士，主要研究方向為交通行為博弈；韓印（1964-），男，黑龍江綏化人，教授，博士，主要研究方向為交通系統(tǒng)優(yōu)化.

0 引言

自2019年末爆發(fā)的新冠肺炎（COVID-19）疫情對我國及世界各國人民的生產(chǎn)生活都造成了巨大影響。新冠病毒以其極易感和快速傳播的特性，在爆發(fā)后短短的幾個月內(nèi)便席卷了全世界^［1，2］。為應對新冠疫情，我國政府采取了強有力的管控措施阻止疫情擴散，其舉措主要包括切斷感染源以及控制人群聚集傳播兩個方面^［3］。城市公共交通系統(tǒng)是城市居民出行所依賴的主要系統(tǒng)，也是人群集散的主要系統(tǒng)，人群集散過程大大增加了交叉感染的風險，對病毒的傳播蔓延起著重要的作用^［4～7］。為了避免城市公共交通對疫情蔓延發(fā)展的促進，各級政府部門不得不對城市公共交通的運營進行應急干預，如關閉、停運及調(diào)整部分公交線路的運營^［8］，以最大限度降低乘客在交通場站及車廂內(nèi)的聚集。這些果斷措施在疫情爆發(fā)初期切斷了疫情傳播途徑，取得了很好的抗疫效果，然而這些措施并不是一個長遠的可行措施。隨著各行業(yè)逐步復工復產(chǎn)，出行需求逐漸增加，迫切需要城市公交的運能恢復到常態(tài)，這就對疫情下的公交運營管理提出了挑戰(zhàn)^［9］。為了保證出行安全，常規(guī)公交如地鐵、公共汽車等運營依然要保持人流篩查和限流等管制措施。人流的篩查主要指利用大數(shù)據(jù)技術，將人群按照感染的風險程度分為高感染風險（紅碼）、中感染風險（黃碼）及低感染風險（綠碼）三類，只有低感染風險的乘客才允許進入公交設施，乘坐公共交通工具；而限流管制主要是指控制進入公交場站設施及車輛的乘客數(shù)量，以保證乘客之間具有一定空間，避免乘客之間的聚集和近距離接觸。人員篩查和限流管制降低了傳統(tǒng)公交（地鐵、公共汽車）的運能，使得一部分出行者不得不借助其他出行方式（如私家車、出租車及網(wǎng)約車等）來完成出行。雖然這種“一人一車”的出行方式具良好的安全性，但其也意味著較高的出行成本。因此，拼車出行似乎成為一種更好的選擇。相比傳統(tǒng)的公交，拼車出行不存在大規(guī)模的人群聚集，降低了出行風險；與私家車及出租車等相比，拼車可能又意味著更低的出行費用。然而，由于拼車過程不可避免仍會發(fā)生拼車者之間的接觸，特別當拼車者中有潛在可能的風險乘客時，拼車出行依然顯得不夠安全。那么是否可以對傳統(tǒng)的拼車調(diào)度模型進行改進，使之在疫情大背景下仍然能夠最大可能地保證出行者安全出行成為本文研究的核心問題。

1 相關研究

當前拼車優(yōu)化調(diào)度主要沿著匹配優(yōu)化、拼車路徑優(yōu)化及拼車匹配和路徑優(yōu)化相結合的統(tǒng)一優(yōu)化模型三個方向進行^{［10～12］}，拼車優(yōu)化的目標也主要為最大化拼車匹配成功率、最小化出行費用、節(jié)能減排等^{［13，14］}。拼車匹配優(yōu)化主要是指將有拼車需求的乘客與運營車輛進行合理配置，使拼車成功率及服務效率更高^{［15，16］}。例如Wang等人^［12］將拼車匹配穩(wěn)定的需求考慮到拼車匹配過程中，構建了拼車匹配的數(shù)學規(guī)劃模型，并用實證數(shù)據(jù)對模型的有效性進行了驗證，表明所構建的匹配模型可以顯著提高拼車匹配的成功率；Yang等人^［10］將匹配范圍與等待時間間隔引入到拼車匹配優(yōu)化模型中，構建了能夠顯著提高匹配成功率的拼車匹配優(yōu)化模型；Hou等人^［11］也提出了一種拼車的優(yōu)化模型，該模型首先將乘客按照出行需求與車輛進行最優(yōu)匹配，然后優(yōu)化匹配后的車輛路徑；Qian等人^［17］提出一種名為TGR（taxi group ride）的拼車模型，該模型將出行起點和目的地相似的乘客進行分類，分類后的乘客按照相互之間的距離優(yōu)化一個最佳的碰面地點，并以該碰面地點作為基點與進入平臺等待派單的出租車進行最優(yōu)匹配。在拼車問題中，如果確定了車輛與拼車乘客，接下來就只需要對拼車乘客的路徑進行優(yōu)化。實際上也就相當于將拼車問題轉換為了多個特殊的開放式的車輛路徑優(yōu)化問題（open vehicle routing problem，OVRP），即每個問題都只包含一輛車及多個服務節(jié)點（乘客上下車節(jié)點）的特殊OVRP^{［18，19］}。與OVRP相比，拼車問題的路徑優(yōu)化問題（ridesplitting vehicle routing problem，R-VRP）多了更多的強約束，如R-VRP約束了乘客的上下車位置的對應性，即任一乘客必須在其上車點上車，也必須在其對應的下車點下車；R-VRP還要求對車載容量進行約束，即在同一時間車輛的載客量不能超過車輛的最大載客量^［20］；在R-VRP可能服務的節(jié)點只能有一位乘客上車或者下車；此外還包括時間窗約束等。因此，R-VRP實際上是一個與OVRP類似但又比OVRP有著更多約束、求解也更復雜的NP問題^［21］。

將拼車問題轉換為拼車匹配與拼車路徑優(yōu)化的思路有利于降低拼車優(yōu)化調(diào)度模型構建及求解的難度，在實際中具有很好的應用前景^{［22，23］}，特別是當同類拼車乘客具有非常相似的起終點及出行路徑時，這種方法會顯得非常有效。然而在實際中，拼車乘客出行的路徑通常差異較大，此時將拼車匹配與路徑優(yōu)化分開進行優(yōu)化的解決思路就具有一定的局限性，因此就有了更多的將拼車匹配與路徑優(yōu)化同時進行優(yōu)化的研究。其中最經(jīng)典的模型就是DARP（dial a ride problem）和CPP（carpooling problem）模型。Bodin和Colorni等人^{［24，25］}較早提出DARP并構建了數(shù)學模型，隨后，Cordeau等人進一步完善了模型，并提出了求解該模型的經(jīng)典算法——分支割算法^{［26，27］}。近年來，隨著通信及互聯(lián)網(wǎng)技術的普及，拼車優(yōu)化調(diào)度問題成了學者們關注的一個熱點。結合具體的實踐及應用場景，學者們對DARP模型進行了各種各樣的拓展。如考慮到車輛異質(zhì)性，擴展出了H-DARP（heterogeneity-DARP）模型^［23］；考慮到多個起終站點，可以將DARP模型進一步拓展到MD-DARP（muti-depot DARP）模型^［28］；若在每一次調(diào)度中考慮到每輛車可以完成多次出行，則又演變出MT-DARP（muti-trip DARP）模型^［29］；此外還有考慮到車輛為電車時候的DARP-EV（DARP with electric vehicles）模型^［30］等。除了DARP模型，另外一個經(jīng)典的拼車模型就是CPP模型，經(jīng)典CPP模型的適用場景為在一個公司上下班的乘客進行的拼車，這些乘客或許具有同一出發(fā)地（下班時），或者具有同一目的地（上班時）。該模型集乘客分組、最優(yōu)駕駛員選擇（駕駛員為拼車乘客中的某一位）及路徑優(yōu)化為一體，對在同一區(qū)域上下班員工拼車具有較好的實用效果^{［31，32］}。

已有的相關研究雖然已經(jīng)構建了各種各樣的拼車模型，然而這些模型在構建過程中都將乘客視為具有同樣需求的同等類型，這種做法在常規(guī)情形下是合理的，然而在類似COVID-19這種疫情背景下就具有一定的局限性。因為在疫情背景下不同風險類型的乘客一起拼車會增加低風險乘客被感染的風險。所以，不同于以往的研究，本文將進一步考慮疫情背景的影響，將拼車安全的目標引入到拼車調(diào)度優(yōu)化過程中，構建疫情背景下的拼車應急管理調(diào)度優(yōu)化模型。

2 模型構建

2.1 問題描述

在常態(tài)條件下，平臺通過優(yōu)化所有車輛行駛的總費用（或總利潤）來優(yōu)化車輛—乘客的匹配以及車輛的行駛路徑。然而在疫情條件下，如果遇到低風險乘客和潛在風險乘客的拼車，會增加低風險乘客被感染的幾率，因此必須對拼車乘客進行分類調(diào)度管理，即允許低風險乘客相互拼車，潛在風險乘客之間及潛在風險乘客與低風險乘客之間都不可相互拼車，也就是說在一次出行中，使用拼車平臺的潛在風險乘客只可以獨立使用某輛車完成出行。其次，考慮到現(xiàn)實中新冠病毒極易傳播的特性，本文認為每次調(diào)度過程中必須針對運送過潛在風險乘客的車輛進行專門消毒，經(jīng)消毒后的車輛才允許再次進入平臺進行新的訂單分配，而運送過低風險乘客的車輛無須進行專門消毒就可以進入下一次的訂單分配。最后，與以往模型目標構建思路不同，本文認為拼車調(diào)度管理不應僅僅以平臺管理者的盈利為唯一目標，還應該更多兼顧到平臺所提供的服務質(zhì)量。特別是在疫情背景下，由于眾多常規(guī)公交都采取了人員篩查和限流管制措施，大大降低了傳統(tǒng)公交（地鐵、巴士）的運能，拼車這種新興的公交出行模式理應分擔更多的社會責任。本文嘗試在兼顧獲取最低利潤的基礎上，綜合考慮最低服務乘客比例及服務質(zhì)量，構建考慮疫情擴散傳播風險的多目標拼車應急管理優(yōu)化調(diào)度模型。模型具體場景為：假設在某一個時刻某空間內(nèi)有正在等待派單的網(wǎng)約車及等待拼車的乘客，假定這些乘客中有部分為低風險乘客（如可根據(jù)行程碼、健康碼等已有大數(shù)據(jù)分析方法認定），部分為潛在風險者（如根據(jù)是否途徑潛在風險地區(qū)，是否與潛在風險人群有可能接觸等大數(shù)據(jù)分析技術認定），每輛車及乘客都有其實時位置，每個乘客也都其目的地。當前等待派單的車輛和乘客的相關信息數(shù)據(jù)都會實時上傳至到拼車管理平臺，平臺將優(yōu)化后的車輛-乘客匹配結果及路徑優(yōu)化結果發(fā)布給每輛車。

2.2 符號說明

本文中：n_H表示車輛數(shù)；n_G表示低風險乘客數(shù)；n_Y表示潛在風險乘客數(shù)；n_P表示乘客的總數(shù)，n_P=n_G+n_Y；n_C表示消毒站點數(shù)；Q_h表示車輛h的最大載客量；H表示車輛集合，h∈H，H={1，2，…，h，…，n_H}；V_H表示車輛位置節(jié)點集合，V_H={1，2，…，i，…，n_H}；V^OG表示低風險乘客上車節(jié)點集合，V^OG={n_H+1，n_H+2，…，n_H+i，…，n_H+n_G}；V^OY表示潛在風險乘客上車節(jié)點集合，V^OY={n_H+n_G+1，n_H+n_G+2，…n_H+n_G+i，…，n_H+n_P}；V^DG表示低風險乘客目的地節(jié)點集合，V^DG={n_H+n_P+1，n_H+n_P+2，…，n_H+n_P+i，…，n_H+n_P+n_G}；V^DY表示潛在風險乘客目的地節(jié)點集合，V^DY={n_H+n_G+n_P+1，n_H+n_G+n_P+2，…，n_H+n_G+n_P+i，…，n_H+2n_P}；V_C表示消毒站點集合，V_C={n_H+2n_P+1，n_H+2n_P+2，…，n_H+2n_P+i，…，n_H+2n_P+n_C}；V₀表示虛擬起始節(jié)點，V₀={0}；V_T表示虛擬終止節(jié)點，V_T={n_H+2n_P+n_C+1}；V表示所有節(jié)點集合，V=V₀∪V_H∪V^OG∪V^DG∪V^OY∪V^DY∪V_C∪V_T；H表示車輛集合，h∈H；q_i表示節(jié)點i后的乘客需求量，在上車點q_i=1，在下車點q_i=-1；t_ij表示節(jié)點i到j的行程時間；T_h表示車輛行駛最長時間限制；d_ij表示節(jié)點i到j的距離；［e_i，l_i］表示節(jié)點i被訪問的時間窗；c表示單位距離車輛的運行成本；f₁表示低風險乘客拼車單位距離需要支付的費用；f₂表示潛在風險乘客拼車單位距離需要支付的費用；Q^hi表示車輛h訪問完節(jié)點i后的在車乘客數(shù)；B^hi表示車輛h到達節(jié)點i的時間；x^hi_j為0-1變量，若節(jié)點i到j被車輛h訪問則x^hi_j=1，否則為0；d⁺表示平臺獲取利潤的正偏差，d⁺gt;0；d^-表示平臺獲取利潤的負偏差，d^-gt;0；w⁺_i表示車輛到達節(jié)點i時間的正偏差，w⁺_igt;0；w^-_i表示車輛到達節(jié)點i時間的負偏差，w^-_igt;0；P_r表示基本額定利潤。

2.3 模型構建

1）拼車平臺的決策目標

拼車運營企業(yè)作為一般盈利型企業(yè)，其運營的目的首先就是保證有一定的利潤。拼車平臺的利潤為所有被服務乘客支付的拼車費用減去車輛行駛的總消耗。假設車輛行駛單位距離的費用不變，為常數(shù)c，則車輛消耗的總費用為

平臺獲得的總收入為所有乘客支付的乘車費用，包括低風險乘客及潛在風險乘客。低風險乘客支付的乘車費用可表達為

潛在風險乘客支付的乘車費用可表達為

考慮到拼車平臺的社會責任，在疫情背景下平臺不再追求利潤最大化，但是也要保證平臺最低的基本額定利潤。這里假定平臺每完成一次訂單需要獲取的最低額定利潤要求為P_r，引入利潤偏差d⁺及d^-，則利潤的目標約束可以表示為

平臺的第一目標為達到最低基本盈利，即盈利的負偏差最小：

在盡可能保證最低盈利的條件下，平臺還應該提供盡可能好的拼車服務。這里對拼車服務的評價可以量化為是否在乘客規(guī)定的時間窗范圍［e_i，l_i］內(nèi)提供相關服務。引入車輛到達節(jié)點i時間的正負偏差w⁺_i及w^-_i，則車輛到達節(jié)點i的時間的目標約束可以表示為

平臺的第二目標為盡可能保證所有乘客都能準時被提供服務，即最小化到達所有節(jié)點i的時間的正負偏差，可以寫為

綜上可以將平臺的目標寫為如下雙目標形式：

2）相關約束條件

為了保證服務品質(zhì)，平臺需要至少保證能夠滿足一定比例（η）乘客的服務要求：

車輛可能被分配訂單，也有可能不被分配訂單：

車輛的節(jié)點與車輛編號匹配約束：

車輛位置的前序節(jié)點只能是虛擬節(jié)點V₀：

車輛位置的后續(xù)節(jié)點只能是乘客的上下車點：

乘客有可能被提供服務，也有可能不被提供服務，且每位乘客最多只能被一輛車提供服務；而消毒站可能被使用也可能不被使用，每個消毒站可以為多輛車提供消毒服務：

低風險乘客只能與低風險乘客進行拼車，且在執(zhí)行下一次訂單之前無須到消毒站進行消毒。低風險乘客的路徑節(jié)點約束為

潛在風險乘客不得進行拼車，同時假定疫情背景下為了避免交叉感染，運送過潛在風險乘客的車輛在執(zhí)行下一個訂單前必須到一個固定的消毒站點進行消毒。潛在風險乘客的路徑節(jié)點約束為

所有的拼車乘客都必須在其對應的上車點上車，在其對應的下車點下車，相關約束可以寫為

車輛到達各個節(jié)點的時間為其離開上一個節(jié)點的時間加上其在上下兩節(jié)點之間的行程時間：

車輛載客量約束為

變量約束為

3）模型及拓展

考慮疫情擴散傳播風險的多目標拼車應急管理優(yōu)化調(diào)度模型（multi-objective ridesplitting emergency management optimization model，MREM），可以具體表達為以式（8）為目標函數(shù)，以式（4）（6）及（9）～（33）為約束的多目標優(yōu)化模型。若模型中不考慮將乘客按照風險等級分類服務及車輛的消毒動作，則模型退化為一般的多目標拼車優(yōu)化調(diào)度模型（general multi-objective ridesplitting optimization model，GMRM）。

3 求解算法

首先對目標P₁進行優(yōu)化，得到目標函數(shù)P₁的最優(yōu)解d^-*及d^+*；然后對目標P₂進行優(yōu)化，其目標保持不變，約束條件為在原約束的基礎上增加Z₁+Z₂-C+d^-*-d^+*=P_r。每求一個目標時都利用以下給出的組合模擬退火（hybrid simulated annealing，HSA）算法進行求解。

3.1 生成可行解

3.1.1 路徑約束檢驗

a）容量約束檢驗（capacity constraint test method，CM）。設當前路徑為R=（v_h，v₁，…，v_m），對應節(jié)點集為V_R，q_vi為節(jié)點i的需求量（q_vh=0），則車輛h各點處的載客量分別為Q^th=∑^ti=1q_vi（t=1，…，m），若所有的Q^th均小于車輛的最大容量Q_h，則當前路徑滿足容量約束，否則不滿足。

b）車輛路徑狀態(tài)檢驗（vehicle route status inspection，VRSI）。若當前車輛所在路徑為只有車輛一個節(jié)點，即R={v_h}，標記其為自由狀態(tài)，則其后續(xù)可以添加的節(jié)點類型為V^OG∪V^OY；若當前車輛所在路徑的首乘客節(jié)點為V^OG，則標記其為運送低風險乘客車輛路徑，該路徑只能添加V^OG∪V^DG類節(jié)點；若當前車輛所在路徑的首乘客節(jié)點為V^OY，則標記其為運送潛在風險乘客車輛路徑，該路徑只能添加V_C類節(jié)點；若當前車輛所在路徑的末節(jié)點為V_C，則標記其為成熟路徑，該路徑不再添加任何節(jié)點。

c）AT/WT/NOP計算。設車輛h的一個當前可行路徑為R=（v_h，v₁，…，v_m）是一條可行路徑，則可通過式（34）～（36）計算當前路徑各節(jié)點的到達時間和等待時間。已知B^hv_h=0，Q^hv_h=0。

AT（arrive time）：

其中：v_j^-表示節(jié)點v_j的前面節(jié)點。

3.1.2 最優(yōu)可行插入位置

由于是否滿足容量約束與節(jié)點的插入位置有關，所以在已有路徑中插入新節(jié)點時要依次判斷路徑中的每個試插位置，直至找到可行插入位置（feasible insertion position function，F(xiàn)IPF）為止。

a）從待選節(jié)點中隨機選取某一上下車節(jié)點p_i+和其對應的下車節(jié)點p_i-或V_C節(jié)點。

b）根據(jù)VRSI判定所取節(jié)點是否為可取節(jié)點，若是則繼續(xù)；否則丟棄該節(jié)點。

c）若該節(jié)點是V_C節(jié)點，則直接插入到當前路徑的最末端；否則初始化當前路徑中從起始點出發(fā)的第一條弧到最后一個節(jié)點之后為該p_i+節(jié)點試插入位置（圖1）；根據(jù)每一個試插位置，用CM檢驗是否為可行位置，根據(jù)Z₁+Z₂-C=P_r求出各可行位置插入該節(jié)點后的路徑凈利潤P_r，再由式（33）求得累積時間偏差∑（w^-_i+w⁺_i）。

d）FIPF1規(guī)則（P₁時使用）。將max P_r的弧作為該p_i+節(jié)點的插入位置，再從該節(jié)點之后，根據(jù)CM檢驗所有p_i-的可行插入位置，將max P_r的弧作為該p_i-節(jié)點的插入位置插入該節(jié)點；結束。

e）FIPF2規(guī)則（P₂時使用）。將min∑（w^-_i+w⁺_i）的弧作為該p_i+節(jié)點的插入位置，再從該節(jié)點之后，根據(jù)CM檢驗所有p_i-的可行插入位置，并將min∑（w^-_i+w⁺_i）的弧作為該p_i-節(jié)點的插入位置插入該節(jié)點；結束。

3.1.3 生成可行解（FSGA）

a）初始化，以等概率隨機選擇服務乘客數(shù)n_s，［ηn_P］≤n_s≤n_p，從n_p個乘客中隨機選擇n_s個乘客，其相關的上下車點集及V_C并入備選點集。

b）令k=0，針對每一輛車h∈H，產(chǎn)生一個初始路徑R^hk={V_h}，（R¹_k={V₁}，R²_k={V₂}，…，Rⁿ_Hk={V_nH}。

c）檢查當前各車輛的路徑狀態(tài)，若車輛h的路徑狀態(tài)為R^hk，ter，則不再對其分配節(jié)點；否則，從剩余節(jié)點中隨機選取某一上下車節(jié)點p_i+和其對應的下車節(jié)點p_i-或V_C節(jié)點。

d）根據(jù)FIPF規(guī)則（P₁時使用FIPF1、P₂時使用FIPF2），將該節(jié)點隨機插入某條路徑中，并對已有各路徑進行更新產(chǎn)生新路徑R^hk，ter。

e）檢查是否有剩余節(jié)點，若有進入下一步；否則令R^hk，ter=R^hk，進入步驟h）。

f）令k=k+1，針對所有R^hk，根據(jù)FIPF逐個檢查剩余節(jié)點是否可以插入R^hk中，若有則隨機選擇一個插入R^hk中，產(chǎn)生新路徑R^hk，ter，并令R^hk=R^hk，ter；若無，則令R^hk，ter=R^hk。

g）終止檢查。檢查是否所有R^hk都是R^hk，ter，若是則結束迭代；否則返回至b）。

h）根據(jù)R^hk，ter，利用AT、WT及NOP計算B^hi、Q^hi，生成一個可行解，記為X。

3.2 鄰域變換

在算法中需要不斷通過鄰域變換產(chǎn)生新解，本文通過節(jié)點交換、節(jié)點移植及車輛路徑交換三種機制實現(xiàn)鄰域向優(yōu)變換產(chǎn)生新解，具體分為NTNPR1和NTNPR2兩種機制，分別應用于P₁和P₂解鄰域變換過程，兩種機制的主要區(qū)別在于進行節(jié)點移植時所遵循的規(guī)則。

a）節(jié)點交換。從當前解各路徑中隨機找出一對乘客節(jié)點（上車點p_i+和下車點p_i-），兩兩交換這些節(jié)點，如式（37）所示。

其中：V_hi表示第i輛車的位置節(jié)點；V_p⁺_i和V_p^-_i表示第i個乘客上下車節(jié)點。交換兩條路徑中P₃和P₇位置得到新的路徑。

b）節(jié)點移植。節(jié)點移植僅在低風險乘客的路徑中進行。NTNPR1：根據(jù)當前解各路徑的利潤p^rh_i找出p^rh_i最小路徑，從中隨機找出一對節(jié)點，并隨機移植到剩余路徑中；NTNPR2：根據(jù)當前解各路徑的累積時間偏差∑_i∈r（w^-_i+w⁺_i）找出累積時間偏差最大的路徑，從中隨機找出一對節(jié)點，并隨機移植到剩余路徑中。如將經(jīng)過節(jié)點交換后的r_h1的P₆移植到r_h2中：

c）車輛路徑變換。經(jīng)節(jié)點交換和移植后的解可能破壞了車輛與初節(jié)點的最優(yōu)匹配，因此需要重新對車輛與路徑進行匹配。從車輛h₁開始對車輛逐次重新配對。計算車輛h_i距離各路徑起始節(jié)點的起始時間窗最近的節(jié)點min（e_vrjo-t_vhivrjo），e_vrjo表示第j條路徑的起始節(jié)點的起始時間，將車輛h_i與路徑r_j按照min（e_vrjo-t_vhivrjo）配對，當所有車輛配對完畢，形成一個新解。例如上例中，原路徑r_h1和r_h2重新匹配后的可能車輛路徑為

3.3 組合模擬退火算法（HSA）

結合以上初始可行解的產(chǎn)生及鄰域變換機制，利用模擬退火算法對模型進行求解。

首先對目標P₁進行求解：

a1）初始化。k=1，設置初始溫度T=T₀，每個溫度值T的迭代次數(shù)N_T，利用FSGA生成一個初始可行解X₀，令X_k=X₀。

b1）利用NTNPR1過程對X_k進行鄰域變換，產(chǎn)生一個新的可行解X_new。

c1）計算增量。目標P₁的增量ΔE=（Z₁（X_new）+Z₂（X_new）-C（X_new））-（Z₁（X_k）+Z₂（X_k）-C（X_k））。

d1）若ΔEgt;0，則接受X_new新的可行解，否則以概率p=epx（-ΔE/T_k）接受X_new為新可行解，更新后的當前解記為X_k，令k=k+1。

e1）若k≤N_T，進入下一步，否則轉入步驟g1）。

f1）若Tlt;0或d^-=0，則輸出當前解X^*。作為P₂的初始可行解，進入步驟h2）；否則返回步驟a1）。

g1）令T=T-ΔT，k=1，利用FSGA生成一個新的可行解X_new，返回步驟c1）。

目標P₂的求解是在滿足目標P₁的基礎上進行的，P₂的求解過程如下：

a2）將d^-*及d^+*代入式（9），與其他已有約束形成新的約束，以X^*為初始可行解，記為X^*₀。

b2）令k′=1，設置初始溫度T₀=T′₀，每個溫度值T值的迭代次數(shù)N′_T，令X^*_k=X^*₀。

c2）利用NTNPR2過程對X^*_k進行鄰域變換，產(chǎn)生一個新的可行解X^*_new。

e2）若ΔE₁lt;0，則保持當前解X^*_k為新的可行解，令k′=k′+1，轉入步驟g2）；否則進入下一步。

f2）若ΔE₂lt;0，則接受X^*_new為新的可行解；否則，若ΔE₂gt;0，則以概率p=exp（-ΔE₂/T′_k）接受X^*_new為新的可行解；令k′=k′+1。

g2）若k≤N_T，進入下一步，否則轉入步驟i2）。

h2）若Tlt;0或d^-=0，則輸出當前解作為最優(yōu)解，結束程序；否則進入下一步。

i2）令T=T-ΔT，k′=1，利用FSGA生成一個新的可行解X_new，返回步驟d2）。

3.4 算例分析

通過一個具體的算例對MREM模型的有效性進行驗證。算例均包含5輛車、15個低風險乘客、5個潛在風險乘客、3個消毒站；其中節(jié)點編號1～5表示車輛位置節(jié)點，6～20表示低風險乘客上車點，21～25表示潛在風險乘客上車點，26～40對應低風險乘客（6～20）下車點，41～45對應潛在風險乘客（21～25）下車點，46～48表示車輛消毒點。算例具體數(shù)據(jù)如表1所示。設定參數(shù)f₁=20，f₂=30，c=20，η=0.3，P_r=0。初始溫度均為200（T₀，T′₀），N_T均設定為100（N_T，N′_T），ΔT=10，對算例的求解結果如表2所示。

從表2算例的計算結果可以看出，h₁、h₂、h₄、h₅均只服務了一個乘客，這些乘客（23、25、22、24）正好屬于潛在風險乘客，而且在服務完每一個乘客后都會到專門的消毒站進行消毒，四輛車都進入47號消毒站進行消毒。h₃為第10、9、6的乘客實現(xiàn)了拼車服務，而10、9、6乘客都是低風險乘客。算例的乘客上下車站點的匹配和先后順序、車輛運送乘客數(shù)量等也均符合模型相關約束。這些都充分表明該算法計算結果符合模型的所表達的所有強約束，顯示出算法的有效性；同時還可以發(fā)現(xiàn)算例的第一個目標值為0，收斂到了最小。

為了進一步分析算法的收斂性及求解效率，依靠算例進一步對算法的斂散性進行分析。運用該算法對算例進行30次計算，并取目標函數(shù)的平均值對算法的收斂性進行分析。結果顯示算例中，P₁均很快就收斂了，這主要是因為本算例的特殊性，使得絕大多數(shù)初始可行解都可以滿足平臺盈利的目標d^-=0，使算法強制收斂。P₂的收斂速度相對較慢，收斂過程如圖2所示。

4 仿真實驗

通過以下仿真場景來進一步說明本文所構建的模型在抑制疫情傳播中的作用。假設在一個具有總人口數(shù)為N=10⁵的區(qū)域，根據(jù)已有信息可知這些人中低風險人數(shù)占到70%，潛在風險人群占到30%，所有人都可能是潛在的拼車出行的乘客。假設根據(jù)已有綜合推測及計算，知道總人數(shù)中真實的感染人數(shù)為n_I人，并知道這些人中有10%分布在低風險乘客中，有90%分布在潛在乘客中，但并不知道這些人具體是誰。也就是說任何一個低風險乘客和潛在風險乘客，其為真實感染者的概率分別為

每天進行調(diào)配的車輛總次數(shù)為120輛次，進入平臺待調(diào)度的低風險乘客人次為360人次，潛在風險乘客人次為120人次。對于每次進入平臺的低風險乘客，以概率P_l判定其是否為感染者，對于每次進入平臺的潛在風險乘客以概率P_p判定其是否為感染者。合乘感染率為100%，也就是說如果一個健康者和一個感染者合乘（包括在時空上進行過合乘以及車輛在未消毒前乘坐過同一輛車），健康者被感染的概率為100%，并且假定司機采取了很好的保護措施，不會被感染。凡是被專門運送的潛在風險乘客，其到達目的地后將自動隔離不再進行傳染。

為了評估MREM模型在抑制病毒傳播中的作用，本文將不采取乘客分類拼車及采取分類拼車的策略后，在經(jīng)過一段時間，場景中感染者數(shù)量的演化過程進行對比。基礎演化模型為SIR模型^{［33，34］}。基本參數(shù)設定為：f₁=20，f₂=30，c=2，η=0.3，P_r=0，δ=1，n_I=300，β分別為0.7×10^-5.6。演化步數(shù)設置為30次。具體如下：

a）依次在［0，100］²范圍內(nèi)生成n_H=120的車輛位置、n_I=360的低風險乘客上下車位置點及n_p=120的潛在風險乘客上下車位置點。根據(jù)P₁及P_p，按照輪盤賭確定進入平臺的每位乘客是否是感染者。

b）分別按照乘客分類拼車及不分類拼車的策略，利用MREM模型進行合乘派單優(yōu)化；確定實際進行了合乘的感染人數(shù)Δn_i，并分別分析合乘過程，得到合乘后新增感染人數(shù)Δn_j。

c）在初始值為（n_I-Δn_i）條件下，利用SIR模型進行一次感染人數(shù)演化，得到新的感染人數(shù)n^sI。

d）更新場景中的感染人數(shù)n_I=n^sI+Δn_i+Δn_j，作為下一步病毒演化分析的初始條件；返回步驟a）。

模擬結果分布如圖3所示。圖3（a）中R₁表示未對風險乘客進行區(qū)分條件下，采用一般拼車管理模型（GERM），在經(jīng)過一段時間后場景中感染的人數(shù)，R₂表示在區(qū)分潛在風險乘客條件下，采用分類拼車管理模型（MREM），在經(jīng)過一段時間后場景中的感染人數(shù)的演變過程，SIR是對比曲線，表示當環(huán)境中不存在拼車時感染人數(shù)的一般演化過程。圖3（b）中，δ₁表示未進行乘客分類拼車情形下病毒傳播人數(shù)與SIR模型病毒傳播人數(shù)之差，δ₂表示分類拼車情形下病毒傳播人數(shù)與SIR模型病毒傳播人數(shù)之差。從圖中可以看出，在疫情初期，當感染人數(shù)較少時（timelt;5），分類拼車和一般拼車對于病毒的擴散及抑制作用都不太明顯，然而，隨著感染人數(shù)的增加，分類拼車策略在抑制病毒擴散傳播方面就顯示出優(yōu)勢；而不采用分類拼車的管理，不僅不會對病毒傳播起到抑制作用，反而會對病毒傳播起到促進作用。

5 結束語

當前，新冠疫情仍然在肆虐。在大疫情公共衛(wèi)生危機背景下，提出一套如何應對疫情危機的公交應急管理策略成為當前的迫切需求。拼車作為互聯(lián)網(wǎng)條件下一種新興的出行模式，在一定條件下已經(jīng)體現(xiàn)出它的巨大優(yōu)勢，成為城市公共交通的有力補充。因此研究疫情下的拼車應急管理具有很大的現(xiàn)實意義和應用價值。本文首先從疫情大背景下拼車調(diào)度的目標分析出發(fā)，認為不同于常態(tài)下的拼車調(diào)度目標，疫情背景下的拼車調(diào)度目標應充分考慮到公共衛(wèi)生安全問題，同時在疫情背景下，拼車系統(tǒng)管理者的目標不應該是唯一追求利潤最大化的，而是應該在保證自己達到某一利潤的前提下，盡可能提高拼車服務質(zhì)量及服務水平。由此，本文構建了多目標拼車應急管理優(yōu)化模型MREM。模型將拼車乘客分為低風險乘客及潛在風險乘客兩類，通過構建相關約束，使得只有低風險乘客之間才可以進行拼車，而低風險乘客和潛在風險乘客以及潛在風險乘客之間無法進行拼車，達到疫情大背景下的安全拼車的目標。通過引入利潤目標約束以及到達時間目標約束以及最小服務乘客數(shù)量約束，既保證了疫情大背景下拼車調(diào)度管理應承擔的社會責任（不以利潤最大化為唯一目標，盡可滿足出行者的拼車需求，降低疫情大背景下低密度交通工具緊張的現(xiàn)實需要）。最后通過一個具體的仿真案例，對本文所構建模型對病毒傳播的的作用進行分析，結果顯示在疫情背景下本文所構建的模型能夠有效抑制病毒傳播速度。

參考文獻：

［1］Wang Wei，Miao Wei，Liu Yongdong，et al.The Impact of COVID-19 on the ride-sharing industry and its recovery：causal evidence from China［J］.Transportation Research Part A：Policy and Practice，2022，155（1）：128-141.

［2］Teixeira J F，Silva C，Moura E S F.The motivations for using bike sharing during the COVID-19 pandemic：insights from Lisbon［J］.Transportation Research Part F：Traffic Psychology and Behaviour，2021，82（10）：378-399.

［3］雷斌，劉星良，曹振 等.COVID-19在城市軌道交通系統(tǒng)內(nèi)的傳播建模與預測［J］.交通運輸工程學報，2020，20（3）：139-149.（Lei Bin，Liu Xingliang，Cao Zhen，et al.Modeling and forecasting of COVID-19 spread in urban rail transit system［J］.Journal of Traffic and Transportation Engineering，2020，20（3）：139-149.）

［4］Cooley P，Brown S，Cajka J，et al.The role of subway travel in an influenza epidemic：a New York City simulation［J］.Journal of Urban Health，2011，88（5）：982-995.

［5］Liu Qi，Lu Huan，Chen Rongchang.Effect of a bundle of intervention strategies for the control of COVID-19 in Henan，a neighboring province of Wuhan，China［J］.Wiener Klinische Wochenschrift，2020，132（13-14）：396-399.

［6］Hendrickson C，Rilett L R.The COVID-19 pandemic and transportation engineering［J］.Journal of Transportation Engineering Part A：Systems，2020，146（7）：01820001.

［7］Jia J S，Lu Xin，Yuan Yun，et al.Population flow drives spatio-temporal distribution of COVID-19 in China［J］.Nature，2020，582（7812）：389-394.

［8］馮旭杰，王洋，劉書浩 等.新冠肺炎疫情對城市軌道交通運營的影響［J］.交通運輸研究，2020，6（1）：45-49.（Feng Xujie，Wang Yang，Liu Shuhao，et al.Impacts of COVID-19 on urban rail transit operation［J］.Transport Research，2020，6（1）：45-49.）

［9］Morshed S A，Khan S S，Tanvir R B，et al.Impact of COVID-19 pandemic on ride-hailing services based on large-scale Twitter data analysis［J］.Journal of Urban Management，2021，10（2）：155-165.

［10］Yang Hai，Qin Xiaoran，Ke Jintao，et al.Optimizing matching time interval and matching radius in on-demand ride-sourcing markets［J］.Transportation Research Part B：Methodological，2020，131（1）：84-105.

［11］Hou Liwen，Li Dong，Zhang Dali.Ride-matching and routing optimisation：models and a large neighbourhood search heuristic［J］.Transportation Research Part E：Logistics and Transportation Review，2018，118（10）：143-162.

［12］Wang Xing，Agatz N，Erera A.Stable matching for dynamic ride-sharing systems［J］.Transportation Science，2018，52（4）：850-867.

［13］Ho S C，Szeto W Y，Kuo Y H，et al.A survey of dial-a-ride problems：literature review and recent developments［J］.Transportation Research Part B：Methodological，2018，111（5）：395-421.

［14］Molenbruch Y，Braekers K，Caris A.Typology and literature review for dial-a-ride problems［J］.Annals of Operations Research，2017，259（12）：295-325.

［15］Jiao Junfeng，Bischak C，Hyden S.The impact of shared mobility on trip generation behavior in the US：findings from the 2017 National Household Travel Survey［J］.Travel Behaviour and Society，2020，19（4）：1-7.

［16］Devaraj A，Ramakrishnan G A，Nair G S，et al.Joint model of application-based ride hailing adoption，intensity of use，and intermediate public transport consideration among workers in Chennai City［J］.Transportation Research Record，2020，2674（4）：152-164.

［17］Qian Xinwu，Zhang Wenbo，Ukkusuri S V，et al.Optimal assignment and incentive design in the taxi group ride problem［J］.Transportation Research Part B：Methodological，2017，103（9）：208-226.

［18］Ko?，Laporte G，Tükenmez I·.A review of vehicle routing with simultaneous pickup and delivery［J］.Computers amp; Operations Research，2020，122（10）：104987.

［19］Li Bo，Guo Chen，Ning Tao，et al.Solve VRPPD with improved bacteria optimization algorithm［C］//Proc of the 2nd International Confe-rence on Materials Science，Machinery and Energy Engineering.［S.l.］：Atlantis Press，2017：1732-1736.

［20］Parragh S，Doerner K，Hartl R.A survey on pickup and delivery pro-blems，part Ⅱ：transportation between pickup and delivery locations［J］.Journal für Betriebswirtschaft，2008，58（2）：81-117.

［21］Atasagun G C，Karaoglan I.A mathematical model for the time dependent vehicle routing problem with simultaneous pick-up and deli-very［J］.Journal of the Faculty of Engineering and Architecture of Gazi University，2019，34（4）：1743-1755.

［22］Ruiz E，Soto-Mendoza V，Barbosa A E R，et al.Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm［J］.Computers amp; Industrial Engineering，2019，133（7）：207-219.

［23］Riedler M，Raidl G.Solving a selective dial-a-ride problem with logic-based benders decomposition［J］.Computers amp; Operations Research，2018，96（8）：30-54.

［24］Masmoudi M A，Braekers K，Masmoudi M，et al.A hybrid genetic algorithm for the heterogeneous dial-a-ride problem［J］.Computers amp; Operations Research，2017，81（5）：1-13.

［25］Desrosiers J，Dumas Y，Soumis F.The multi-vehicle subscriber dial-a-ride problem［C］//Proc of the 4th International Workshop on Computer-Aided Scheduling of Public Transport.Berlin：Springer，1988：15-27.

［26］Colorni A，Righini G.Modeling and optimizing dynamic dial-a-ride problems［J］.International Transactions in Operational Research，2001，8（2）：155-166.

［27］Cordeau J F，Laporte G.The dial-a-ride problem：models and algorithms［J］.Annals of Operations Research，2007，153（9）：29-46.

［28］Cordeau J F.A branch-and-cut algorithm for the dial-a-ride problem［J］.Operations Research，2006，54（3）：573-586.

［29］Braekers K，Caris A，Janssens G K.Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots［J］.Transportation Research Part B：Methodological，2014，67（9）：166-186.

［30］Masmoudi M A，Hosny M，Braekers K，et al.Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem［J］.Transportation Research Part E：Logistics and Transportation Review，2016，96（12）：60-80.

［31］Liang Xiao，de Almeida Correia G H，An Kun，et al.Automated taxis’ dial-a-ride problem with ride-sharing considering congestion-based dynamic travel times［J］.Transportation Research Part C-Emerging Technologies，2020，112（3）：260-281.

［32］Baldacci R，Maniezzo V，Mingozzi A.An exact method for the car pooling problem based on Lagrangean column generation［J］.Operations Research，2004，52（3）：422-439.

［33］Tamannaei M，Irandoost I.Carpooling problem：a new mathematical model，branch-and-bound，and heuristic beam search algorithm［J］.Journal of Intelligent Transportation Systems，2019，23（3）：203-215.