考慮接駁費用的車輛共享調(diào)度算法研究*

鄒 兵 余 志▲ 黃 敏 何兆成 陳金邕

（1.中山大學(xué)智能工程學(xué)院 廣州510006；2.中山大學(xué)廣東省智能交通系統(tǒng)重點實驗室 廣州510006）

0 引 言

隨著城市機動車保有量的不斷增加，城市交通面臨的擁堵、環(huán)保等問題日益嚴重。同時，泛在感知、即時通信和大數(shù)據(jù)等技術(shù)的發(fā)展為交通系統(tǒng)的變革提供了機遇?？萍歼M步不斷催生出新的出行模式和服務(wù)模式，助力交通運行效率的改善和居民出行體驗的提升。其中，無人駕駛汽車[1]、網(wǎng)聯(lián)汽車[2]和“共享經(jīng)濟”的不斷發(fā)展和普及，為城市中的出行運輸提供了新的思路。未來的交通系統(tǒng)中傳統(tǒng)的有人駕駛出租車、私家車等交通方式將逐步被無人的自動駕駛汽車所取代。自動駕駛車輛共享的普及和應(yīng)用在交通擁堵問題的緩解、環(huán)境問題的改善[3]等方面具有較大的意義。

近些年，在共享車輛方面的研究日趨豐富，主要集中于行程共享和車輛共享2個方面。行程共享指的是乘客進行拼車、順風(fēng)車共同使用一輛車，車輛共享指車輛被統(tǒng)一調(diào)度用于不同出行趟次的運輸[4]。在前者的研究上，Paolo Santi等[5]基于紐約出租車出行數(shù)據(jù)進行“拼車”系統(tǒng)的方案驗證，結(jié)果顯示車輛累計出行里程可以減少至少40%。同樣，利用出租車數(shù)據(jù)，Javier Alonso-Mora等[6]設(shè)計了一種大規(guī)模實時拼車算法，實驗結(jié)果明，98%的出租車需求能被約總量15%的2 000輛車輛共享滿足。Ma Shuo等[7]則基于北京出租車數(shù)據(jù)研究，顯示一定車輛承載力和候車時間等約束條件下的共享方案可以減少13%的總出行距離。Li Ruimin等[8]通過車牌識別數(shù)據(jù)構(gòu)建軌跡時空匹配及合乘模型，采用帶花樹算法求解最大匹配，并探究了行程共享對道路運行速度的影響。車輛共享的研究方面，為了解決車輛與出行需求的匹配問題，通常采用車輛與需求之間的時空關(guān)系尋找最佳車輛，如隨機遍歷策略[9]、基于多智能體的模型分配[10]。此外，一些研究提出優(yōu)化模型進行系統(tǒng)共享車輛的調(diào)度分配。M.M.Vazifeh 等[11]設(shè)計車輛共享網(wǎng)絡(luò)對出租車出行需求建模，轉(zhuǎn)化為二分圖最大匹配問題并基于Hopcroft-Karp 算法求解最小車輛規(guī)模，紐約數(shù)據(jù)集分析表示當(dāng)不同出行需求連接時間為15 min 時，出租車數(shù)量可減少40%左右。王冠[12]、姚曉銳等[13]則利用分時租賃電動汽車數(shù)據(jù)、手機數(shù)據(jù)進行上海市最小車隊規(guī)模的研究，轉(zhuǎn)化為多旅行商問題、圖論模型進行求解并分析不同因素對車輛規(guī)模的影響。Michael W.Levin[14]將路網(wǎng)擁擠考慮在內(nèi)進行車輛分配及路徑調(diào)度，表明共享車輛調(diào)度會造成平均旅行時間增加。

具體的調(diào)度模型及優(yōu)化算法方面，可分為2類：對出行需求的匹配和車輛的調(diào)度進行建模，以最大交通流量、減少最多車輛數(shù)[8]、總運營里程減少[15-16]、調(diào)度運營成本降低[17]、最大社會效益[18]為目標進行建模，進而轉(zhuǎn)化為整數(shù)規(guī)劃問題，采用遺傳算法[12，15]、貪婪分配[19]、調(diào)度池[20]等方法進行求解；將出行抽象為節(jié)點構(gòu)建圖[5，11，13，21]，進而轉(zhuǎn)化為圖論中的最小不相交路徑覆蓋問題求解到更優(yōu)調(diào)度分配方案，同一共享車輛可連續(xù)調(diào)度服務(wù)多個出行，所需車輛規(guī)模即會降低。

在進行車輛共享調(diào)度時，一方面期望減少車輛降低成本，緩解交通擁堵；另一方面也應(yīng)該考慮由于車輛的減少帶來的負面影響，如車輛空駛造成的環(huán)境污染、油耗代價等。系統(tǒng)角度下，車輛規(guī)模降低的同時，車輛共享由于調(diào)度接駁及其他出行需求，必然會產(chǎn)生多余的出行費用。上述的研究在問題的描述上局限于某個場景,求解出最小車隊規(guī)?；蜃钚】偝鲂欣锍痰葐我蛔顑?yōu)目標，導(dǎo)致求得的最小車輛規(guī)模往往不是最少接駁費用的調(diào)度方案。

筆者將針對現(xiàn)有的車輛共享調(diào)度算法未充分考慮車輛共享調(diào)度同時造成的接駁費用影響問題，建立最小車輛規(guī)模、最少接駁費用雙目標優(yōu)化模型。在模型的求解上，基于圖論相關(guān)理論，將車輛共享調(diào)度雙目標最優(yōu)問題轉(zhuǎn)化為二分圖的最大匹配且權(quán)重最優(yōu)問題，提出Kuhn-Munkres（KM）算法求解最大匹配與權(quán)重最優(yōu)匹配的條件并進行證明，進而結(jié)合Hopcroft-Karp（HK）算法與KM 算法進行模型求解。以安徽宣城市為例，基于高度密集布局的車牌識別數(shù)據(jù)獲取車輛出行需求信息，進行車輛共享調(diào)度算法案例分析。

1 最小車輛規(guī)模最少接駁費用車輛共享調(diào)度模型

1.1 問題描述

給定車輛的出行需求后，車輛共享的問題可以描述為調(diào)度若干自動駕駛車輛完成交通系統(tǒng)中所有出行需求的運輸。如圖1 所示，給定出行需求集合代表車輛的每個出行需求，分別對應(yīng)著車輛出行的起點以及出發(fā)時間，對應(yīng)著車輛出行的終點及到達時間。車輛共享的任務(wù)為：在一定時間內(nèi)，自動駕駛汽車在完成一個運輸任務(wù)之后從上一個出行的終點在下一個出行的出發(fā)時間之前調(diào)度至其出發(fā)起點繼續(xù)運輸出行需求。2 個出行需求若能被有向地接駁，則可用同一共享車輛進行運輸，匹配的越多，車輛規(guī)模減少的越多。例如，圖1中完成T1出行之后，同一車輛可以繼續(xù)完成出行T3，也可以在時空條件允許的情況下先接駁T2或者T4，再接駁T3。所要解決的問題是確定哪些出行需求由共享車輛以什么行駛路徑進行指揮接駁，以達到最小車輛規(guī)模同時接駁費用最少的優(yōu)化問題。

圖1 車輛共享接駁示意Fig.1 Vehicle sharing diagram

以往的模型及算法往往只單一地以最小車輛規(guī)?；蛘咦钌倏偝杀緸槟繕耍矣捎谒惴ㄇ蠼怆y度較大，難以獲得真正的最小車輛規(guī)模最少接駁費用最優(yōu)解。因此，本文的研究同時將接駁費用考慮在內(nèi)進行模型的建立。

1.2 模型假設(shè)條件

考慮到在車輛共享調(diào)度過程中，變量和影響因素較多，從車輛運營過程中的實際情況出發(fā)作出以下假設(shè)以便更好地抽象為數(shù)學(xué)模型。

1）共享車輛統(tǒng)一由調(diào)度中心算法指揮調(diào)度，車輛型號、服務(wù)水平、核載人數(shù)相等且有足夠多的車輛滿足路網(wǎng)中所有的出行需求。共享車輛在調(diào)度過程中由于突發(fā)事件等因素造成的影響本模型暫不考慮。

2）每個出行需求只能被共享車輛接駁1 次，即共享車輛最多經(jīng)過該出行需求1次。實際運營過程中，每個出行需求被運輸1 次即可，符合真實物理場景。

3）共享車輛進行出行需求接駁時滿足一定的調(diào)度時間間隔或距離約束，且不發(fā)生乘客出行延誤的情況。車輛在結(jié)束1個出行運輸之后調(diào)度至其他出行起點時，為避免產(chǎn)生過長時間或距離的不合實際的調(diào)度，須進行一定條件的約束。同時，需在不降低乘客出行服務(wù)水平下進行服務(wù)。

4）共享車輛能連續(xù)進行多個出行需求的接駁，每個車輛調(diào)度只執(zhí)行1 次共享任務(wù)，根據(jù)調(diào)度路徑調(diào)度后不再重復(fù)進行運輸服務(wù)。真實運營場景下，共享車輛可進行多趟運輸，研究模型主要為驗證最優(yōu)化算法，暫不將車輛身份屬性考慮在內(nèi)。

5）車輛共享過程中不考慮行程共享即拼車情況。模型暫不考慮車輛共享與行程共享2種混合情況下最優(yōu)。

1.3 車輛共享調(diào)度最小車輛規(guī)模最少接駁費用模型

1.3.1 最小車輛規(guī)模目標

對于車輛共享調(diào)度最小車輛規(guī)模問題，指在給定出行需求T={T1，T2，…，Tk}時，在出行需求接駁的時空條件限制下，所有的出行需求能被最少車輛規(guī)模vmin滿足。構(gòu)建出以出行需求匹配的數(shù)量最大為目標的車輛共享調(diào)度模型。

式（1）為模型的目標函數(shù)，表示出行需求匹配數(shù)量Z1最大，由于每匹配2 個出行需求，便會減少1個車輛，匹配越多，實際需要車輛規(guī)模越小。因此，以最大需求匹配數(shù)量為目標求最小車輛規(guī)模。其中，rij為2 個出行進行銜接的約束條件變量，若2 個出行能夠滿足有向時空條件進行接駁則為1，否則為0。

式（2）為每2個出行需求之間的匹配決策變量，如果求解過程中選擇出行Ti與Tj進行匹配，則matchij值為1，否則為0。

式（3）～（4）表示每個出行需求的匹配約束，只能與另外1 個出行需求匹配或者不匹配，也只能被匹配1次或者不被匹配。

式（5）的rij表示2個出行進行銜接的約束條件，設(shè)置原則根據(jù)車輛調(diào)度實際情況可分為以下2個部分。

1）為避免過長的連接時間造成不切實際的車輛調(diào)度，2 次出行調(diào)度時間不宜過長，即上1 次出行之后至多在α min之內(nèi)能接駁到下1次出行進行下1次運輸，滿足2次出行調(diào)度間隔時間約束。

2）上次出行Ti結(jié)束之后，車輛共享通過路網(wǎng)此時段最短旅行時間的路徑進行空駛調(diào)度，在下1 次出行Tj出發(fā)之前從到達其出發(fā)起點，且調(diào)度到達的時間在之前，即

式中：tij為不同地點之間同一時段的最短旅行時間，從路網(wǎng)車輛出行信息重構(gòu)獲得的分時段的路徑及旅行時間先驗集中獲取。

1.3.2 最少接駁費用目標

對于車輛共享調(diào)度最小車輛規(guī)模最少接駁費用的目標，指在給定出行需求T={T1，T2，…，Tk}，求出最小車輛規(guī)模vmin后，仍然一對多地存在多種車輛共享調(diào)度方案，不同車輛接駁方案造成的費用不同，需求解最少費用的調(diào)度方案，從而減少多余出行造成的影響。因此，獲得最大出行需求匹配數(shù)量后，需在保持最小車輛規(guī)模的基礎(chǔ)上，繼續(xù)求解最少費用調(diào)度方案。見式（8）。

式（8）表示最小接駁費用的目標函數(shù)，cos tij為出行Ti與Tj接駁的費用權(quán)重；為以最小費用為目標下的決策變量。

式（9）表示如果出行需求Ti能與Tj進行車輛共享，其出行費用cos tij為wij，本研究中根據(jù)接駁出行是否產(chǎn)生無效空駛的空間移動分別設(shè)置wij為1 和0。如果不能進行車輛接駁，出行費用設(shè)置為L。rij同樣符合式（5）的銜接約束。

式（10）表示最少費用調(diào)度方案與最大匹配相等，為控制最小車輛規(guī)模始終不變的條件，在此約束下，求解的最少接駁費用即為最小車輛規(guī)模的基礎(chǔ)上的最少接駁費用。

在以往的模型建立過程中，往往忽略式（8）最小接駁費用這一目標，由于車輛規(guī)模最優(yōu)的同時仍然可能存在多個接駁方案，未考慮接駁費用時無法進一步得到費用也最優(yōu)的最終方案。所提出的模型將最少接駁費用也加入目標，求解更優(yōu)的調(diào)度方案，符合實際調(diào)度的應(yīng)用情況。

2 基于二分圖的最小車輛規(guī)模最少費用調(diào)度模型求解算法

以往研究證明，圖論模型無論在出行銜接矩陣的構(gòu)建還是算法的求解速度和和質(zhì)量方面都表現(xiàn)出更優(yōu)的效果。考慮到本文模型的特點，將問題轉(zhuǎn)化為二分圖匹配問題，并改進二分圖匹配算法進行求解。

2.1 基于有向無環(huán)圖的車輛共享調(diào)度問題轉(zhuǎn)化

有向無環(huán)圖是一種從某個頂點出發(fā)但是無法經(jīng)過若干個邊再回到該點的有向圖[22]。將每個出行需求抽象為1 個節(jié)點nk，圖1中車輛共享任務(wù)可以轉(zhuǎn)化為圖2（a）所示的車輛共享的有向無環(huán)圖V=(N，E)[11]，出行需求之間的時空可銜接的條件轉(zhuǎn)化為節(jié)點與節(jié)點之間的邊ek，如果2 個出行需求在一定約束條件下可以進行調(diào)度連接，則可以構(gòu)建節(jié)點與節(jié)點之間的邊為2個可連接的節(jié)點。車輛出行需求及限制條件輸入后構(gòu)建的有向無環(huán)圖建模了不同的車輛調(diào)度的分配方案。例如，圖2（a）所示的車輛分配方案包括：T1→T3，T1→T2→T3，T1→T4→T3，T5→T4→T6，T5→T6。

圖1的最小車隊規(guī)模問題則轉(zhuǎn)化為求解有向無環(huán)圖的最少不相交路徑覆蓋問題。如圖2（b）所示，T1→T2→T3，T5→T4→T6為圖2（a）有向無環(huán)圖的最小不相交路徑覆蓋，路徑數(shù)量為2，表示滿足圖1車輛出行需求的車輛共享最小規(guī)模為2。

圖2 車輛有向無環(huán)圖Fig.2 Directed acyclic graph of vehicle sharing

2.2 二分圖的最大匹配與帶權(quán)最大匹配

2.2.1 二分圖匹配

對于上述構(gòu)建的車輛共享有向無環(huán)圖，其最小路徑覆蓋問題可以應(yīng)用二分圖的最大匹配算法進行求解。二分圖是一種經(jīng)典的圖論模型，最早用于婚戀匹配的問題中，目前已形成比較成熟的理論。二分圖一般用G=(X，Y，E)表示，X，Y 表示頂點集分割的不相交的2個子集，E 為連接2個集合的邊集，其連接的2個頂點分別在X，Y 這2個子集中。

在本研究當(dāng)中，把圖2 有向無環(huán)圖描述的車輛出行需求T={T1，T2，…，Tk}中的每個點Tk拆分成Tkx和Tky這2個點，見圖3（a）。對于V=(N，E)，如果2 個出行需求Tx和Ty能夠連接，則加1 條邊從X 集合中的Tx指向Y集合中的Ty，即可得到V 所對應(yīng)的二分圖。二分圖有以下3個核心概念。

1）最大匹配。在二分圖G=(X，Y，E)中，若存在1個子圖M ?G，且M 中的任意的邊集均不同時連接到同一頂點，則稱M 為G 的1個匹配，見圖3（b）實線連接。最大匹配為子圖M 匹配邊數(shù)最大時的匹配，最大匹配數(shù)為k，見圖3（c）。

2）增廣路。增廣操作是求解二分圖最大匹配的一個重要環(huán)節(jié)。在二分圖G=(X，Y，E)中，M 是1 個已匹配的集合，M ?G，若P 是1 條連接2 個分別位于X，Y 子集的未匹配頂點的路徑，匹配的邊與未匹配的邊交替出現(xiàn)且未匹配邊中比已匹配的邊多，則稱P 為M 的1 條增廣路。如圖3（b）中的即為1 條增廣路。增廣操作是將P 中原匹配的邊從M 中刪除，未匹配的邊添加到M ，從而實現(xiàn)匹配邊的數(shù)量的增加的過程，如P1中刪除邊T1xT3y，增加邊T2xT3y和T1xT2y。

圖3 車輛共享二分圖Fig.3 Bipartite graph of vehicle sharing

3）帶權(quán)最大匹配。在二分圖G=(X，Y，E)中，當(dāng)連接X，Y 這2 個子集的邊集E 被賦予權(quán)重{li}時，（見圖4（a）），這樣的二分圖稱為帶權(quán)二分圖。對于帶權(quán)二分圖，其帶權(quán)最大匹配為尋找到G 的1 組匹配M ，使得所獲得的權(quán)重總和最大。若求解最小權(quán)重匹配，只需將存在原權(quán)重取反即可，（見圖4（b）），取反后最大權(quán)重為-3，原圖最小權(quán)重則為3。

圖4 二分圖帶權(quán)匹配示意Fig.4 Weighted matching of bipartite graphs

2.2.2 Hopcroft-Karp（HK）算 法 與Kuhn-Munkres（KM）算法

車輛共享接駁場景下，二分圖的最大匹配和帶權(quán)最大匹配可分別用于求解最小車輛規(guī)模與最少接駁費用的共享調(diào)度方案。

二分圖最優(yōu)匹配的求解算法包括匈牙利算法、Hopcroft-Karp（HK）算法、Kuhn-Munkres（KM）算法等。匈牙利算法的主要思想是通過深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜素（BFS）不斷地尋找增廣路，直至初始匹配M 不能繼續(xù)增廣，最終的M 即為二分圖最大匹配。HK 算法是對匈牙利算法的進一步優(yōu)化，時間復(fù)雜度為不同于匈牙利算法每次只能尋找到1 條增廣路，HK 算法能夠一次尋找到多條增廣路徑，繼而同時增加多個匹配。由Kuhn 提出，經(jīng)Munkres 改進的Kuhn-Munkres 算法為一種求解二分圖權(quán)重最大匹配的方法，在完備匹配（所有頂點均能被匹配）情況下，求得最大權(quán)值，見圖4，原圖不存在邊權(quán)重的可通過補邊實現(xiàn)完備匹配。

HK 算法和KM 算法可分別用于求解最大匹配和最優(yōu)權(quán)重匹配，但無法同時求解雙目標下的最優(yōu)解。HK 算法求解最小車輛規(guī)模的調(diào)度方案往往不是費用最少，而KM 算法求解費用最少的調(diào)度方案往往不是最小車輛規(guī)模的方案。因此，需對2 種算法進行改進以滿足雙目標求解的目的。

2.3 最小車輛規(guī)模最少接駁費用求解算法

本研究的目標是求解最小車輛規(guī)模最少接駁費用調(diào)度模型，期望在最小車輛規(guī)模的基礎(chǔ)上，繼續(xù)求解最少費用的調(diào)度方案，即需要保持二分圖最大匹配不變繼續(xù)求解二分圖帶權(quán)最優(yōu)匹配。然而現(xiàn)有的HK 算法與KM 算法無法滿足求解的目標，因此，基于匈牙利算法原理對KM 算法進行改進，提出KM算法求解最大匹配最小權(quán)重匹配的條件并進行證明，進而提出HK-KM算法框架。

2.3.1 KM算法求解最大匹配最小權(quán)重匹配條件證明

KM 算法可用來求解權(quán)重最優(yōu)匹配，然而無法控制求出的權(quán)重最優(yōu)匹配同時也是最大匹配。因此，需根據(jù)最大匹配的原理對KM 算法對權(quán)重設(shè)置條件進行修改以達到本研究求解最大匹配下的最小權(quán)重匹配的目標。

記二分圖存在接駁費用的邊的權(quán)重為{li} ，為求解最小權(quán)重匹配，現(xiàn)將二分圖中存在的權(quán)重取反，即為{- li} 。再將其他不存在邊權(quán)重的補邊并且設(shè)置權(quán)重為-L，見圖4（a），T1xT1y，T1xT5y，T1xT6y等為補充邊，轉(zhuǎn)換為費用矩陣后見圖5（a）。僅將L 取值范圍設(shè)置為L ＞klmax，即可實現(xiàn)KM 算法求出最小權(quán)重匹配的同時也是最大匹配。其中，k 為二分圖的最大匹配數(shù)量，lmax為原二分圖存在的權(quán)重{li} 中的最大值。

圖5 二分圖費用矩陣與匹配矩陣示例Fig.5 Examples of cost matrix（left）and complete matching matrix（right）of bipartite graphs

證明：當(dāng)L 取值范圍為L ＞klmax，KM 算法求解的最小權(quán)重匹配即為最大匹配下的最小權(quán)重匹配。

KM 算法的完備匹配指N 個頂點均有匹配邊，見圖4（b）、圖5（b），每個頂點TNx均有1 個頂點TNy連接，標記為1。記KM算法求得的最大權(quán)重匹配為M′。對于匹配M′，記權(quán)重為-lp的匹配邊的數(shù)量為，此時二分圖的完備匹配中有權(quán)重的匹配邊總數(shù)為權(quán)重為-L 的補充邊數(shù)量為N-k'，完備匹配下二分圖匹配邊的總權(quán)重和為

將KM算法與HK算法的權(quán)重總和在N 個頂點均有匹配的情況下進行比較。對于HK算法求得的任意原最大匹配M ，新增N-k 個權(quán)重為-L 的匹配邊使成為完備匹配。記權(quán)重為-lq的匹配邊的數(shù)量為，此時二分圖的最大匹配等于有權(quán)重的邊匹配總和即，此種匹配下二分圖N 個匹配邊的總權(quán)重和為

1）首先證明L 取值范圍為L ＞klmax時，k′=k。因為k 是最大匹配數(shù)量，所以k′≤k 。假設(shè)k′＜k ，則匹配M′與任意最大匹配的權(quán)重和之差為

這與M′是最大權(quán)匹配矛盾，故k′=k。

2）證明k′=k 時，求解的匹配M′為最大匹配下的最小權(quán)重匹配。因為KM算法求得的最大權(quán)重匹配權(quán)重和大于任意其他匹配，所以有

整理得

當(dāng)k′=k 時，式（13）即為

可得，此時匹配M′求得的最小權(quán)重匹配小于任意匹配的權(quán)重和。

綜上，當(dāng)L 取值范圍為L ＞klmax，KM 算法求解的最小權(quán)重匹配即為二分圖最大匹配下的最小權(quán)重匹配。

2.3.2 HK-KM算法流程

獲得KM 算法改進條件后，提出求解最大匹配情況下最小權(quán)重匹配的HK-KM算法流程。算法在給定出行需求后，將出行需求轉(zhuǎn)化為有向無環(huán)圖，進一步轉(zhuǎn)化為二分圖，根據(jù)出行的時空信息構(gòu)建二分圖的銜接矩陣和費用權(quán)重矩陣。最小車輛規(guī)模目標模型輸入二分圖銜接矩陣，通過HK 算法求解二分圖最大匹配k ，同時，最少費用目標模型輸入原始接駁費用權(quán)重和最大匹配數(shù)k ，補充邊的權(quán)重調(diào)整為L ＞klmax，通過調(diào)整后的KM 算法求解最小權(quán)重匹配，即可求得最大匹配情況下最小權(quán)重匹配方案。具體算法流程見圖6。

圖6 最小車輛規(guī)模最少費用求解算法流程圖Fig.6 Algorithm flow chart

3 案例研究

3.1 出行數(shù)據(jù)獲取

案例分析選取安徽省宣城市中心城區(qū)某年某月卡口系統(tǒng)的車牌識別數(shù)據(jù)進行先驗信息庫的構(gòu)建與案例分析，數(shù)據(jù)內(nèi)容見表1。宣城市位于安徽省東南部，身份檢測設(shè)備布局高度密集，中心城區(qū)卡口覆蓋信控路口108個，高達76%，卡口布局見圖7。

表1 車牌識別數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)Tab.1 Data structure of automatic vehicle identification data

圖7 宣城市卡口點位布局圖Fig.7 Diagram of Xuancheng city road network

基于陳開穎[23]的研究方法進行車輛出行信息重構(gòu)，包括基礎(chǔ)數(shù)據(jù)清洗、車輛出行子鏈提取、出行路徑修復(fù)等步驟（見表1），獲得宣城市研究范圍該月所有車輛個體的出行信息存入數(shù)據(jù)庫中供模型輸入，數(shù)據(jù)處理和存儲分別采用C#和Oracle 完成。宣城市日均卡口檢測次數(shù)約230萬次，出行約8萬輛車，車輛日均總出行28萬次。

3.2 模型與算法案例分析

選取宣城市該月某1 d 的出行數(shù)據(jù)，裁剪10 個交通小區(qū)之間組成的90個OD對之間的車輛出行需求數(shù)據(jù)進行車輛共享自動駕駛調(diào)度問題算法驗證研究。基于Python 語言和環(huán)境，輸入相應(yīng)時段所有出行需求，分別進行調(diào)度模型的構(gòu)建，包括出行銜接矩陣的獲取、接駁費用矩陣、二分圖的構(gòu)建。其中，出行銜接時間閾值α 設(shè)置為30 min。tij從該月車輛出行先驗信息集獲得，共享車輛按照OD對之間最短旅行時間路徑及時間進行調(diào)度。因此，設(shè)置可銜接邊的權(quán)重為tij（單位：min），90個OD對間的接駁費用見表2。

表2 OD 對之間接駁費用Tab.2 The scheduling cost betweem OD pairs

3.2.1 HK-KM算法求解

實驗路網(wǎng)90 個OD 對之間全天出行總數(shù)13 575 次，出行分布見圖8。調(diào)度時間α 設(shè)置為30 min時，二分圖可銜接匹配13 532個邊。首先進行HK 算法進行最大匹配，求得k 為13 096，由表2可得lmax=18，得到KM 算法中原來不存在權(quán)重的邊及完備匹配補充邊的權(quán)重設(shè)置條件為L ＞klmax=235 728，本案例設(shè)置L=1 000 000。本文求解目標為最小費用和，將費用矩陣中的權(quán)重取反，利用KM算法進行求解。

圖8 實驗路網(wǎng)分時段出行需求分布Fig.8 Trip distribution of experimental road network

算法計算結(jié)果見表3，將HK-KM 算法與HK 算法單獨匹配的結(jié)果進行對比以分析提出算法的優(yōu)勢。表中的二分圖實際匹配指的是匹配結(jié)果中匹配成功的原來存在邊權(quán)重的邊，即采用表2 的接駁費用進行接駁的匹配。HK 算法求得的二分圖最大匹配為13 096，匹配率96.5%，車輛規(guī)模減少至479，調(diào)度總費用83 118 min。

表3 最小車輛規(guī)模最少費用算法結(jié)果Tab.3 Results of algorithm

HK-KM算法求得的實際匹配同樣為13 096，車輛規(guī)模降至最低479，表明13 575 個出行需求如果由算法調(diào)度共享車輛滿足，只需要3.5%（1/28）的車輛規(guī)模即可滿足。而研究提出的HK-KM算法求解的總費用為49 211 min，相對于HK 算法接駁費用降低了40.8%。HK-KM 算法求解的共享車輛的部分調(diào)度路徑見表4?？梢?，雖然求得的最終匹配數(shù)與單一的HK 算法相同，但是算法求解的是另一種接駁費用更少的調(diào)度分配方案，即最小車輛規(guī)模下最少的接駁費用。算法復(fù)雜度o（n3），可在多項式時間內(nèi)可求得最優(yōu)解。

表4 算法調(diào)度部分路徑及替代車輛規(guī)模Tab.4 Scheduling route of algorithm results andalternative fleet size

3.2.2 共享車輛使用特征分析

最小車輛規(guī)模最少接駁費用調(diào)度方案下，13 575個出行需求由算法統(tǒng)一調(diào)度，可進一步分析479 個共享車輛在接駁調(diào)度的過程中的使用特征。算法調(diào)度下車輛服務(wù)相關(guān)指標見表5。

表5 算法調(diào)度與原始出行車輛運行指標對比Tab.5 Index comparison between scheduling algorithm and original vehicle operation

共享車輛在使用過程中分為：①在網(wǎng)調(diào)度運行狀態(tài)，包括載客出行和前往接駁調(diào)度2種情況；②等待指揮中心調(diào)度狀態(tài)，共享車輛在完成1 個運輸或者多個運輸任務(wù)之后，由于在時空約束下暫無匹配的下1個出行，停駛等待調(diào)度。圖9為實驗路網(wǎng)出行需求服務(wù)車輛組成。在深夜時段00：00—5：00，由于出行需求較少，依靠00：00 時新增的共享車輛基本可以滿足所有出行需求，出行需求曲線與“共享車輛接駁出行”曲線貼合度較高。早高峰時段左右05：00—9：00，隨著出行需求的持續(xù)增加，路網(wǎng)現(xiàn)存的共享車輛無法滿足出行接駁需求，約14%的出行需求需新增共享車輛服務(wù)出行，這一階段出行需求曲線與“共享車輛接駁出行”曲線出現(xiàn)間隙，出行車輛供給小于出行需求情況。09：00—24：00，路網(wǎng)積累的共享車輛基本可以滿足所有的出行需求，出行需求曲線與“共享車輛接駁出行”曲線基本保持重合。其中，由于出行需求在13：00時大幅度較少，而15：00時突變增加，部分共享車輛無法在調(diào)度時間約束下進行接駁，導(dǎo)致15：00 需新增小部分車輛滿足路網(wǎng)瞬時出行需求。

圖9 分時段出行需求服務(wù)組成Fig.9 Composition of vehicles'service in different periods

路網(wǎng)的累計車輛及運行狀態(tài)見圖10。與圖9 對出行需求服務(wù)規(guī)律分析一致，路網(wǎng)累計車輛在05：00—09：00及15：00經(jīng)歷2個增加，在15：00之后達到路網(wǎng)車輛規(guī)模最大水平479。路網(wǎng)在網(wǎng)運行車輛在經(jīng)過共享車輛一段新增后在08：00之后達到較高水平，于15：00 時達到最高440 左右。而后，隨著出行需求的降低，在網(wǎng)車輛逐漸降低，等待調(diào)度車輛不斷增加，出行車輛供給大于出行需求。

圖10 分時段共享車輛運行狀態(tài)Fig.10 Usage distribution of SAV in different periods

4 結(jié)束語

針對現(xiàn)有的車輛共享調(diào)度模型與算法在求解最小車輛規(guī)模的調(diào)度方案時，忽略車輛共享調(diào)度時產(chǎn)生的接駁費用影響問題，提出一種最小車輛規(guī)模最少接駁費用雙目標最優(yōu)模型。對出行需求進行圖論建模，將模型的求解轉(zhuǎn)化為二分圖的最大匹配且最小權(quán)重匹配問題，基于HK 和KM 算法的原理，提出KM算法求解最大匹配最小權(quán)重匹配的條件并進行了推導(dǎo)證明，設(shè)計出求解模型的算法流程。最后，基于安徽宣城的數(shù)據(jù)集進行了算法的驗證和共享車輛使用分析，結(jié)果顯示，提出的模型和HK-KM算法能較好地求解車輛共享調(diào)度時最小車輛規(guī)模最少接駁費用的方案。同時，本文提出的模型及求解算法同樣適用于其他類似的優(yōu)化場景。

本文在建立模型過程中以降低車輛規(guī)模和接駁費用進行優(yōu)化，未從交通系統(tǒng)整體視角進行車輛規(guī)模與接駁費用之間的權(quán)衡評價，此外，尚未進行共享車輛調(diào)度造成擁堵對車輛規(guī)模的影響分析，在未來的工作中可在這2 個方面進一步開展研究，提高模型的適用性。