基于覆蓋控制的城市多應急救援車輛分布規劃策略

左磊, 孟鐸, 閆茂德, 張守旭

1.長安大學 電子與控制工程學院,陜西 西安 710064; 2.西北工業大學 航海學院, 陜西 西安 710072

近年來,隨著機動車保有量快速增加與人們出行需求日益增長,城市交通安全問題愈發嚴峻。對于城市內頻發的交通事故,交通管理部門與應急救援部門需及時處理交通事故,盡量避免通行效率降低,甚至人員傷亡的情況[1]。城市道路應急救援車輛作為處理交通事故的主要工具,其合理的分布規劃能夠有效縮短交通事故的影響范圍,提高救援效率,減少社會經濟損失[2]。

城市應急救援車輛分布規劃的核心問題是應急救援車輛的負責區域劃分與分布位置優化。目前國內外在這方面已取得了一定的研究成果[3-7]。國外在應急救援車輛分布規劃方面的研究起步較早,針對不同的路網模型以及目標需求,提出了不同的分布模型,包括P-中心模型[8]、P-中位模型[9]、集合覆蓋模型[10]、最大覆蓋模型[11]和多目標優化模型[12]。Huang等[13]研究了P-中心問題中整個城市大部分設施失去功能的大規模緊急情況,對路徑網絡上的設施位置使用動態規劃方法,并進一步開發了一種有效的算法來優化位置分布。Kocatepe等[14]在分配避難所空間時,考慮特殊人群需求,提出了一個容量化的P中值優化模型,最大限度地提高了現有避難所的可達性和容量。Shiah等[15]利用地址數據來衡量需求容量以及最短路徑的組合,將救護車的服務能力引入集合覆蓋模型,使對目標區域的覆蓋率得到了大幅度提升。Murali等[16]考慮了基于距離的覆蓋函數和需求不確定性,提出了面向最大覆蓋范圍的選址模型,并通過解決定位設施的案例證明了該模型的可行性。Moghaddam[17]設計了一個多目標數學模型以識別和排序候選供應商,并能夠有效獲取識別模型的最優解。

相比之下,國內針對應急救援車輛分布問題的研究主要側重于理論模型的改進與優化。方磊等[18]在考慮應急系統時間緊迫性的基礎上,提出了基于系統最小費用的數學模型,并設計了相應的求解算法。楊金順等[19]考慮公路自然災害應急救援點的功能需求,建立了基于多目標的公路網應急救援點選址模型,并將選址模型應用于浙江桐廬公路網。姜濤等[20]基于應急設施到各個事故點的最小距離,設計了考慮不確定性的應急設施選址模型,并給出了模型的求解算法。

然而,上述關于應急救援車輛的分布規劃大多是從管理規劃的角度出發,在具體量化分析與數值理論研究方面尚顯不足。因此,本文引入覆蓋控制理論,綜合考慮應急救援車輛的運動學模型與城市道路的擁堵狀況,通過建立面向最小救援時間的應急救援車輛分布規劃模型,設計不同擁堵路況下城市多應急救援車輛的分布規劃策略。

覆蓋控制理論是面向任務需求的多智能體協同控制方法,綜合考慮了智能體的運動模型和目標區域內的信息分布狀態。利用覆蓋控制方法,可根據目標區域內的信息分布情況,合理分布多智能體的位置,使得目標區域內的關鍵節點受到更多智能體的關注。近年來,隨著對機器-信息交互需求的加深,覆蓋控制理論也應用于環境監測、智能巡邏、火災巡檢和應急救援等多個領域[21-23]。

根據目標區域內信息分布狀態的變化特性,覆蓋控制可分為靜態覆蓋和動態覆蓋兩大類[24]。傳統的覆蓋控制大多是靜態覆蓋,在靜態覆蓋下信息分布狀態不會隨時間發生變化。Cortes等[25]基于Voronoi分區原則,提出了面向連續和離散系統的多智能體覆蓋控制算法,并驗證了相應算法的可行性與收斂性。相比之下,動態覆蓋更符合實際問題,由于待覆蓋信息的分布規律不斷變化,多智能體系統為了獲得最優的覆蓋效果,必須隨時調整多智能體位置,持續對任務環境進行監測。Zuo等[26]針對動態信息分布區域內的最短時間覆蓋控制問題,設計了基于時間最優的Voronoi區域劃分方法,并為多智能體網絡提供了一種分布式覆蓋控制律,使得智能體能夠從目標區域內的任意位置逐漸收斂到目標區域內的最優覆蓋位置。此外,從目標區域的空間維度出發,覆蓋控制在三維覆蓋(3D覆蓋)、二維覆蓋(平面覆蓋)和一維覆蓋(直線覆蓋)領域內均有研究[27-29]。

受此啟發,本文擬應用覆蓋控制理論優化解決城市多應急救援車輛的分布規劃問題,研究范疇及所用方法屬于靜態覆蓋問題。在現有的覆蓋控制研究成果中,智能體在目標區域內可以任意移動,其行駛軌跡不受任何約束限制,然而應急救援車輛在城市中的運動軌跡受路網的約束。兩者結合會產生一個新的科學問題,即二維平面內交叉型區域的多智能體覆蓋控制問題。而這一問題在覆蓋控制中相關成果較少,仍需開展大量的研究工作。因此,應用覆蓋控制理論解決城市多應急救援車輛的分布規劃問題,具有豐富的理論意義與應用價值。

有鑒于此,本文研究基于覆蓋控制的城市應急救援車輛分布策略,主要創新點在于:①針對城市應急救援車輛的分布規劃問題,綜合考慮城市交通的擁堵狀態,利用覆蓋控制理論,建立面向最短救援時間的多應急救援車輛分布規劃模型,量化評價多應急救援車輛在目標區域內救援時間成本;②綜合考慮應急救援車輛在城市路網的軌跡約束與交通擁堵阻尼,利用梯度下降法計算多應急救援車輛在目標區域內的最優分布位置與救援負責區域,并通過仿真實驗的方式驗證所提算法的有效性與可行性。

1 問題描述

考慮n輛應急救援車隨機分布在目標區域Q中,每輛車的運動學模型為

(1)

式中:pi為第i輛應急救援車的位置信息;ui為它的控制輸入。

針對多應急救援車的最優分布規劃問題,假設每輛車具有通訊、計算、采樣和定位功能,且它們的最大速度相同。由于城市路網在不同路段和不同時間段上的交通流量差別較大,其交通擁堵狀況也存在差異,會對車輛的救援時間產生不同的影響,因此,本文使用函數φ(q):Q→R+來描述目標區域內交通擁堵狀態,其中q∈Q表示路網Q內任意一點。同一路段在不同的交通擁堵狀態下,應急救援車的救援時間必然有所不同。

根據上述場景描述,本文主要研究城市路網在不同交通擁堵狀態下,多輛應急救援車在目標區域內的最優分布問題。引入交通擁堵函數來描述目標區域內的交通擁堵狀況,以車輛救援時間為評價函數,構建面向整個區域的救援時間消耗目標函數。利用覆蓋控制的相關理論,調整應急救援車輛的分布位置,優化目標函數,使得目標區域內任意一點發生的交通事故都能得到最快響應。

注1:本文考慮到交通擁堵狀態是分層級的,在某一特定時間段內,可以認為不變。因此,可以利用特定時間段內的固定交通擁堵狀態計算多應急車輛分布。當目標區域內的交通擁堵狀態發生變化時,可以根據新的交通擁堵狀態重新計算多應急救援車輛分布,調整應急車輛位置與負責區域。

2 城市路網下的多應急救援車輛分布模型

2.1 多應急救援車輛分布建模

應急救援車輛分布規劃的關鍵點在于減少應急救援車輛到達交通事故發生點的救援時間。假設事故點附近有多輛應急救援車,在考慮交通擁堵狀況下,確定每輛應急救援車的負責區域,是建立應急救援車輛分布模型的關鍵。

有鑒于此,考慮某一交通事故的周圍存在2輛應急救援車,如圖1所示,其中q點處發生交通事故,車輛i和j均在事故點附近,其位置分別為pi與pj。當前路網的交通擁堵狀態函數為φ(q)。分別計算車輛i和車輛j到q的時間tiq與tjq。比較tiq和tjq的大小,并選擇耗時最短的車輛前往事故點救援。

考慮更大的路網中存在更多的交通事故與應急救援車輛。首先需要按照時間最優的原則,確定每輛應急救援車的負責區域與最優分布位置。當目標區域中某個位置發生交通事故后,判斷該點屬于哪一輛車輛的負責區域,并派遣相應的車輛前往事故發生點救援。

圖2展示了大范圍路網內多應急救援車輛分布場景,其中圖2a)為多應急車輛初始分布場景,圖中分布了4輛應急救援車輛,不同顏色的直線表示不同應急救援車輛的負責區域,假設圖中任意位置發生了交通事故,則派遣事故點所屬區域的應急救援車輛進行救援。圖2b)為多應急救援車輛優化分布場景,此時每個應急救援車輛更靠近交通擁堵程度高的區域。例如車輛4此時位于交通擁堵程度高的路段,若在其負責的區域內發生了交通事故,相比于圖2a)中初始分布的位置,車輛4可更快速地前往事故地點進行處理,進而有效減少救援響應的時間。

從更嚴謹的數學角度來說,假設所構建的城市路網(目標區域)是由n×n條道路組成的方格形結構。在路網中,n輛應急救援車輛初始時刻隨機分布在路網上。根據道路上不同位置的交通擁堵狀態φ(q),規劃每輛應急救援車的負責區域Wi,并計算每輛應急救援車的最優位置pi,使得車輛對目標區域內任意一點的交通位置都能夠實現快速的救援響應,進而縮小多應急救援車對整個目標區域內所有事故的救援時間。

為了定量地描述車輛的救援時間,定義多應急救援車在目標區域內的救援時間目標函數為

(2)

式中:P={p1,…,pn}為所有車輛的位置信息集合;W={W1,…,Wn}為所有車輛的負責區域;f(pi,q,φ(q))用來表示第i輛車到其分配區域Wi內任意一點q的救援時間函數。

由(2)式可知,應急救援車輛的救援時間由車輛的位置信息P、負責區域Wi以及交通擁堵函數φ(q)共同決定。由于φ(q)已經固定,當目標函數H(P,W)達到最小時,所有車輛的負責區域及其位置均處于最優。

因此,要實現目標區域內多應急救援車輛的最優分布規劃,不僅需要解決目標區域的最優分配問題,還要計算車輛在其負責區域內的最優位置。

注2:本文提出的應急救援車輛分布模型旨在尋找多輛應急救援車輛在目標區域內負責的子區域以及最優位置,是在交通事故發生前就進行的分配,以便真實的交通事故發生后,能夠得到最快救援。

注3:針對應急車輛數量限制這一問題,首先應分析目標區域的范圍大小,結合每輛應急救援車輛的范圍能力,進一步確定應急救援車輛的數量。本文聚焦于考慮擁堵路況下應急救援車輛的分布,重點建立了城市多應急救援車覆蓋網絡的評價模型。對不同范圍的路網,應急車輛的數量不同。同一路網中,每個應急車輛的負責區域會隨應急車輛數量的增加而變小,反之亦然。

2.2 多應急救援車的負責區域分配方法

應急救援車的區域分配方法是基于Voronoi區域分配原理。Voronoi區域分配原理是指利用特定的評價指標,根據多智能體的位置信息,將目標區域分割成多個互不重疊的子區域。在這些子區域所包含的智能體擁有優于其他智能體的特性優勢[30]。例如當以距離為評價指標時,每個智能體到其子區域內任意一點的距離都小于其他智能體到該點的距離。

在此基礎上,考慮n輛應急救援車隨機分布在目標區域Q內,其位置為P。則多應急救援車輛的區域分配原則可表示為

Vi={q∈Q|f(pi,q)≤f(pj,q),?i≠j,?i,j∈n}

(3)

式中:f(pi,q)為第i輛車到達目標點q的評價指標;Vi為第i輛車的負責區域。

多應急救援車的應急救援時間目標函數可進一步改寫為

(4)

式中,V={V1,…,Vn}表示所有應急救援車的負責區域集合。

以應急救援車輛到達事故點的時間為目標函數。令(4)式中的評價指標f(pi,q)為車輛到達目標點q的時間,即

f(pi,q)=tiq

(5)

式中,tiq為第i個車到點q的時間。

在此基礎上,多應急救援車輛的Voronoi區域分配表示為

Vi={q∈Q|tiq≤tjq,?i≠j,?i,j∈n}

(6)

由(6)式可知,應急救援車輛到達其負責區域內任意一點的時間均小于其他車輛。即交通事故的發生地點在哪輛車的負責區域,就由相應的應急救援車進行救援。

在進一步確定車輛的負責區域過程中,需具體計算車輛到點q的行駛時間tiq。然而影響tiq的參量不僅包括車輛的行駛軌跡,還與當前路網下的交通擁堵狀態φ(q)相關。后續將詳細介紹tiq的計算方法。

2.3 城市路網下應急救援車的救援時間

針對應急救援車輛在城市路網的行駛軌跡,本文分析了應急救援車輛在城市路網中的3種典型情形:直線路段、T字形交叉口和十字形交叉口。具體的行駛場景如下:

情形一:當車輛位于直線路段上時,車輛在此路段內僅能朝2個方向移動。假設車輛每個單位時間內行駛距離相同,單位時間后車輛的位置會出現圖3中所示的情況。

圖3 車輛位置移動情形一

情形二:當車輛位于T字形交叉口時,車輛可在此路口朝3個方向移動。假設車輛每個單位時間內行駛距離相同,單位時間后車輛的位置會出現圖4中所示的情況。

圖4 車輛位置移動情形二

情形三:當車輛位于十字形交叉口時,車輛可在此路口朝4個方向移動。假設車輛每個單位時間內行駛距離相同,單位時間后車輛的位置會出現圖5中所示的情況。

圖5 車輛位置移動情形三

在明確應急救援車的行駛路徑后,車輛到達目標區域內任意一點的行駛時間可通過如下過程計算。

首先將城市路網進行柵格化處理。假設柵格化后相鄰兩點之間的長度均為l,由于單個柵格區間的長度較短,可以認為同一柵格區間內各點的交通擁堵函數φ(q)的大小相同,圖6所示為路段柵格化后的狀態。

圖6 路段柵格化

在此引入自由流車速,自由流車速是指密度為零時交通流的理論速度,定義路段的自由流車速為vf,假設各路段的自由流車速相同。同一柵格區間內各點的交通擁堵函數φ(q)大小相同,以相鄰2個柵格點a與b為例,a與b之間的交通擁堵函數大小即為a點處的交通擁堵函數大小φ(qa)。則相應的實際車速vr的數學表述為

(7)

式中,qa=[xa,ya]為目標區域Q內路網上點a的坐標。

(8)

假設應急救援車輛的當前位置pi距離事故點q的行駛距離為Liq,則該行駛距離包含上述離散化網格的數量Niq為

(9)

則應急救援車輛到達事故點q的時間tiq可表示為

(10)

在此基礎上,多應急救援車的救援時間目標函數H(P,V)可進一步表述為

(11)

3 基于覆蓋控制的車輛分布規劃策略

根據上述多應急救援車在城市路網的分布模型,基于覆蓋控制的車輛分布規劃方法重點在于:通過調整多應急救援車的位置,使得救援時間目標函數H(P,V)的值逐漸達到最小。根據(11)式中H(P,V)的具體形式,通過梯度優化的方法,逐步求解多應急救援車輛在城市交通路網中的最優分布。

圖7為基于覆蓋控制的多應急救援車輛分布規劃控制系統框圖。通過該控制系統,能夠使得隨機分布在城市路網中的應急救援車輛,逐漸收斂到最優分布狀態。

圖7 基于覆蓋控制的多應急救援車分布規劃控制框圖

在該控制系統中,多應急救援車輛網絡包括n個分布式協同控制器、車輛運動學模型和位置信息。車輛的位置信息P、交通擁堵函數φ(q)以及城市路網模型均為已知信息。在控制過程中,首先利用Voronoi區域分配原則對目標城市路網進行劃分,得到n輛車的負責區域。其次,形成以車輛位置為變量的時間目標函數。最后,通過梯度下降法,調整每輛應急救援車的位置與負責區域,使得目標函數H(P,V)逐漸趨向最小值。

需要注意的是多應急救援車輛的負責區域與最優位置是交互影響的。由于Voronoi區域分配原則是根據2輛相鄰車輛的當前位置進行劃分的,當利用優化方法減少目標函數H(P,V)時,會產生新的車輛位置,進而導致相鄰車輛的Voronoi區域產生變化。而新的Voronoi區域會進一步影響H(P,V)的結構,使得H(P,V)衍化出新的最優解。這一更新迭代過程會一直持續到H(P,V)的優化結果與更新后的Voronoi區域結果一致為止。

在上述控制系統的基礎上,給出如圖8所示的計算流程圖。通過該計算流程,可使得隨機分布的應急救援車輛逐步趨向于當前擁堵狀態下的最優分布。

圖8 多應急救援車分布規劃算法流程圖

根據圖8中的算法流程,基于覆蓋控制的車輛分布規劃算法步驟如下:

step1 考慮n輛應急車初始時刻位置P(t0)={p1(t0),…,pn(t0)}。

step2 初始化n輛應急車位于初始位置時的Voronoi區域,得到每輛應急救援車的Voronoi區域{V(p1(t0)),…,V(pn(t0))}。

step3 建立目標區域內所有路段的交通擁堵函數φ(q)。

step4 計算第i輛應急車位于P(t0)處時分別到達其分配區域內任意一點q的時間tiq(pi(t0))。在此基礎上,求得總時間T(pi(t0))

(12)

step5 重復執行step4,計算其余n-1輛車位于其Voronoi區域內的消耗總時間{T(p1(t0)),…,T(pn(t0))},得到整個應急救援車輛網絡在目標區域內的位于P(t0)處消耗時間目標函數和H(P(t0))

(13)

step6 根據車輛位置移動的3種情形,以初始時刻位置為起點,采用梯度下降法計算每輛應急車下一步的位置,并更新每輛車的Voronoi區域。

step7 交替迭代step6,使得H(P,V)逐漸趨向于最小值。此時區域分配即為最優區域分配,車輛的位置即為最優位置。

需要注意的是,本文提出的車輛分布規劃方式屬于優化問題中的一種,得到的最優分布位置可能是目標函數H(P,V)的局部最優解。產生這一結果的原因是無法確定目標函數H(P,V)的凹凸性。然而這一結果并不影響實際應用。因為在工程應用中,大部分結果的全局最優解是不存在的。只要能夠通過該方法,有效提升應急救援車輛對目標城市區域內的救援效率,就具有一定的應用價值。

4 仿真實驗

考慮6輛應急救援車隨機分布在由12條交叉直線組成的5 km×5 km的目標區域Q中。該目標區域Q為標準的橫縱型路網模型。每輛車的運動模型由(1)式描述。令路網中每條路長度為L=5 km,柵格化后相鄰兩點之間的長度l=0.1 km,各路段的自由流車速vf=40 km/h,目標區域內的交通擁堵狀態分布函數φ(q)表示為

φ(q)=1+9exp(-0.1(x-5)2-0.1(y-5)2)

(14)

式中,q=[x,y]為目標區域Q內路網上的任意一點的坐標。

圖9為交通擁堵狀態分布函數在目標區域Q內的變化規律。由該圖可知,目標區域在右上角的區域擁堵系數最高。

圖9 交通擁堵狀態分布函數 圖10 應急救援車的初始位置及其Voronoi區域 圖11 多應急救援車最優位置及其Voronoi區域

圖10和圖11分別為多應急救援車網絡在目標區域內的初始位置和最優位置,其中星號代表車輛的初始位置,三角代表車輛的最優分布。每輛應急救援車輛的負責區域由不同顏色進行區分。

由圖10仿真結果可知,在考慮交通擁堵情況下,每輛應急救援車的負責區域均有所不同。例如6號車所在位置的周圍交通擁堵系數較高,則6號車負責的區域較小,進而有效保障該區域內的交通事故能夠得到及時處理。4號車的負責區域也明顯大于6號車。這是因為4號車的負責區域內交通擁堵狀態優于6號車的負責區域。

圖11為多應急救援車在目標區域內的最優分布規劃,其中應急救援車輛的負責區域是根據當前車輛的優化位置(即三角標號位置)進行劃分的。對比圖10與圖11可知,利用本文提出的分布規劃算法,多應急救援車的分布位置以及負責區域都產生了不同程度變化。這一變化驗證了應急救援車輛與負責區域之間的交替影響規律。更進一步地,關于該分布規劃優化算法的量化分析可通過圖12進行說明。

圖12 多應急救援車網絡的目標函數

圖12為多應急救援車在目標區域內的救援時間目標函數變化曲線,其中縱坐標為應急救援車到達目標區域內任意一點的整體時間,橫坐標為應急救援車輛從初始位置收斂到最優分布所用的時間。由該結果可知,隨著分布優化算法的實施,多應急救援車不斷調整其最優分布位置,使其對目標區域的整體救援時間逐漸減少。此外,本文還在圖12中將所提算法與傳統的平均分布算法進行了對比,其中H1為平均分布規劃算法,H2為本文所提的基于覆蓋控制的分布規劃算法。由該對比結果可知,本文所提算法充分考慮目標區域內的交通擁堵狀態,使得應急救援車輛能夠在更短的時間內對目標區域內任意一點的交通事故進行處理,整體救援時間縮短了15%。

因此,上述仿真結果表明多應急救援車輛網絡能夠實現對目標區域的最優覆蓋,驗證了本文提出多應急救援車最優分布規劃算法的有效性與可行性。

5 結 論

本文基于覆蓋控制理論,考慮交通擁堵狀況對城市應急救援車輛分布的影響,構建了面向最優應急救援時間的分布規劃模型,并提出了多應急救援車在多事故發生情況下的分布規劃策略。

針對多個應急救援車在目標區域內的區域分配問題,利用Voronoi區域分配原則,以每輛車到任意一點的行駛時間為評價指標,提出了基于Voronoi區域分配原則的區域劃分策略,使得目標區域內任意一點的交通事故,都能夠在最短的時間內得到響應。

相對于傳統的車輛平均分配原則,本文所提的分配規劃方法充分考慮了交通擁堵路況對分布規劃策略的影響,可有效提高應急救援車輛對目標區域的覆蓋效率,縮短救援時間。

后續的研究將進一步在更復雜的交通路網上,進行未知路況的估計,分析未知路況下的城市多應急救援車輛分布規劃方法。