基于覆蓋控制的城市多應(yīng)急救援車輛分布規(guī)劃策略

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

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

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

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

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

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

覆蓋控制理論是面向任務(wù)需求的多智能體協(xié)同控制方法,綜合考慮了智能體的運動模型和目標(biāo)區(qū)域內(nèi)的信息分布狀態(tài)。利用覆蓋控制方法,可根據(jù)目標(biāo)區(qū)域內(nèi)的信息分布情況,合理分布多智能體的位置,使得目標(biāo)區(qū)域內(nèi)的關(guān)鍵節(jié)點受到更多智能體的關(guān)注。近年來,隨著對機(jī)器-信息交互需求的加深,覆蓋控制理論也應(yīng)用于環(huán)境監(jiān)測、智能巡邏、火災(zāi)巡檢和應(yīng)急救援等多個領(lǐng)域[21-23]。

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

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

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

1 問題描述

考慮n輛應(yīng)急救援車隨機(jī)分布在目標(biāo)區(qū)域Q中,每輛車的運動學(xué)模型為

(1)

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

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

根據(jù)上述場景描述,本文主要研究城市路網(wǎng)在不同交通擁堵狀態(tài)下,多輛應(yīng)急救援車在目標(biāo)區(qū)域內(nèi)的最優(yōu)分布問題。引入交通擁堵函數(shù)來描述目標(biāo)區(qū)域內(nèi)的交通擁堵狀況,以車輛救援時間為評價函數(shù),構(gòu)建面向整個區(qū)域的救援時間消耗目標(biāo)函數(shù)。利用覆蓋控制的相關(guān)理論,調(diào)整應(yīng)急救援車輛的分布位置,優(yōu)化目標(biāo)函數(shù),使得目標(biāo)區(qū)域內(nèi)任意一點發(fā)生的交通事故都能得到最快響應(yīng)。

注1:本文考慮到交通擁堵狀態(tài)是分層級的,在某一特定時間段內(nèi),可以認(rèn)為不變。因此,可以利用特定時間段內(nèi)的固定交通擁堵狀態(tài)計算多應(yīng)急車輛分布。當(dāng)目標(biāo)區(qū)域內(nèi)的交通擁堵狀態(tài)發(fā)生變化時,可以根據(jù)新的交通擁堵狀態(tài)重新計算多應(yīng)急救援車輛分布,調(diào)整應(yīng)急車輛位置與負(fù)責(zé)區(qū)域。

2 城市路網(wǎng)下的多應(yīng)急救援車輛分布模型

2.1 多應(yīng)急救援車輛分布建模

應(yīng)急救援車輛分布規(guī)劃的關(guān)鍵點在于減少應(yīng)急救援車輛到達(dá)交通事故發(fā)生點的救援時間。假設(shè)事故點附近有多輛應(yīng)急救援車,在考慮交通擁堵狀況下,確定每輛應(yīng)急救援車的負(fù)責(zé)區(qū)域,是建立應(yīng)急救援車輛分布模型的關(guān)鍵。

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

考慮更大的路網(wǎng)中存在更多的交通事故與應(yīng)急救援車輛。首先需要按照時間最優(yōu)的原則,確定每輛應(yīng)急救援車的負(fù)責(zé)區(qū)域與最優(yōu)分布位置。當(dāng)目標(biāo)區(qū)域中某個位置發(fā)生交通事故后,判斷該點屬于哪一輛車輛的負(fù)責(zé)區(qū)域,并派遣相應(yīng)的車輛前往事故發(fā)生點救援。

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

從更嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)角度來說,假設(shè)所構(gòu)建的城市路網(wǎng)(目標(biāo)區(qū)域)是由n×n條道路組成的方格形結(jié)構(gòu)。在路網(wǎng)中,n輛應(yīng)急救援車輛初始時刻隨機(jī)分布在路網(wǎng)上。根據(jù)道路上不同位置的交通擁堵狀態(tài)φ(q),規(guī)劃每輛應(yīng)急救援車的負(fù)責(zé)區(qū)域Wi,并計算每輛應(yīng)急救援車的最優(yōu)位置pi,使得車輛對目標(biāo)區(qū)域內(nèi)任意一點的交通位置都能夠?qū)崿F(xiàn)快速的救援響應(yīng),進(jìn)而縮小多應(yīng)急救援車對整個目標(biāo)區(qū)域內(nèi)所有事故的救援時間。

為了定量地描述車輛的救援時間,定義多應(yīng)急救援車在目標(biāo)區(qū)域內(nèi)的救援時間目標(biāo)函數(shù)為

(2)

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

由(2)式可知,應(yīng)急救援車輛的救援時間由車輛的位置信息P、負(fù)責(zé)區(qū)域Wi以及交通擁堵函數(shù)φ(q)共同決定。由于φ(q)已經(jīng)固定,當(dāng)目標(biāo)函數(shù)H(P,W)達(dá)到最小時,所有車輛的負(fù)責(zé)區(qū)域及其位置均處于最優(yōu)。

因此,要實現(xiàn)目標(biāo)區(qū)域內(nèi)多應(yīng)急救援車輛的最優(yōu)分布規(guī)劃,不僅需要解決目標(biāo)區(qū)域的最優(yōu)分配問題,還要計算車輛在其負(fù)責(zé)區(qū)域內(nèi)的最優(yōu)位置。

注2:本文提出的應(yīng)急救援車輛分布模型旨在尋找多輛應(yīng)急救援車輛在目標(biāo)區(qū)域內(nèi)負(fù)責(zé)的子區(qū)域以及最優(yōu)位置,是在交通事故發(fā)生前就進(jìn)行的分配,以便真實的交通事故發(fā)生后,能夠得到最快救援。

注3:針對應(yīng)急車輛數(shù)量限制這一問題,首先應(yīng)分析目標(biāo)區(qū)域的范圍大小,結(jié)合每輛應(yīng)急救援車輛的范圍能力,進(jìn)一步確定應(yīng)急救援車輛的數(shù)量。本文聚焦于考慮擁堵路況下應(yīng)急救援車輛的分布,重點建立了城市多應(yīng)急救援車覆蓋網(wǎng)絡(luò)的評價模型。對不同范圍的路網(wǎng),應(yīng)急車輛的數(shù)量不同。同一路網(wǎng)中,每個應(yīng)急車輛的負(fù)責(zé)區(qū)域會隨應(yīng)急車輛數(shù)量的增加而變小,反之亦然。

2.2 多應(yīng)急救援車的負(fù)責(zé)區(qū)域分配方法

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

在此基礎(chǔ)上,考慮n輛應(yīng)急救援車隨機(jī)分布在目標(biāo)區(qū)域Q內(nèi),其位置為P。則多應(yīng)急救援車輛的區(qū)域分配原則可表示為

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

(3)

式中:f(pi,q)為第i輛車到達(dá)目標(biāo)點q的評價指標(biāo);Vi為第i輛車的負(fù)責(zé)區(qū)域。

多應(yīng)急救援車的應(yīng)急救援時間目標(biāo)函數(shù)可進(jìn)一步改寫為

(4)

式中,V={V1,…,Vn}表示所有應(yīng)急救援車的負(fù)責(zé)區(qū)域集合。

以應(yīng)急救援車輛到達(dá)事故點的時間為目標(biāo)函數(shù)。令(4)式中的評價指標(biāo)f(pi,q)為車輛到達(dá)目標(biāo)點q的時間,即

f(pi,q)=tiq

(5)

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

在此基礎(chǔ)上,多應(yīng)急救援車輛的Voronoi區(qū)域分配表示為

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

(6)

由(6)式可知,應(yīng)急救援車輛到達(dá)其負(fù)責(zé)區(qū)域內(nèi)任意一點的時間均小于其他車輛。即交通事故的發(fā)生地點在哪輛車的負(fù)責(zé)區(qū)域,就由相應(yīng)的應(yīng)急救援車進(jìn)行救援。

在進(jìn)一步確定車輛的負(fù)責(zé)區(qū)域過程中,需具體計算車輛到點q的行駛時間tiq。然而影響tiq的參量不僅包括車輛的行駛軌跡,還與當(dāng)前路網(wǎng)下的交通擁堵狀態(tài)φ(q)相關(guān)。后續(xù)將詳細(xì)介紹tiq的計算方法。

2.3 城市路網(wǎng)下應(yīng)急救援車的救援時間

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

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

圖3 車輛位置移動情形一

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

圖4 車輛位置移動情形二

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

圖5 車輛位置移動情形三

在明確應(yīng)急救援車的行駛路徑后,車輛到達(dá)目標(biāo)區(qū)域內(nèi)任意一點的行駛時間可通過如下過程計算。

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

圖6 路段柵格化

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

(7)

式中,qa=[xa,ya]為目標(biāo)區(qū)域Q內(nèi)路網(wǎng)上點a的坐標(biāo)。

(8)

假設(shè)應(yīng)急救援車輛的當(dāng)前位置pi距離事故點q的行駛距離為Liq,則該行駛距離包含上述離散化網(wǎng)格的數(shù)量Niq為

(9)

則應(yīng)急救援車輛到達(dá)事故點q的時間tiq可表示為

(10)

在此基礎(chǔ)上,多應(yīng)急救援車的救援時間目標(biāo)函數(shù)H(P,V)可進(jìn)一步表述為

(11)

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

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

圖7為基于覆蓋控制的多應(yīng)急救援車輛分布規(guī)劃控制系統(tǒng)框圖。通過該控制系統(tǒng),能夠使得隨機(jī)分布在城市路網(wǎng)中的應(yīng)急救援車輛,逐漸收斂到最優(yōu)分布狀態(tài)。

圖7 基于覆蓋控制的多應(yīng)急救援車分布規(guī)劃控制框圖

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

需要注意的是多應(yīng)急救援車輛的負(fù)責(zé)區(qū)域與最優(yōu)位置是交互影響的。由于Voronoi區(qū)域分配原則是根據(jù)2輛相鄰車輛的當(dāng)前位置進(jìn)行劃分的,當(dāng)利用優(yōu)化方法減少目標(biāo)函數(shù)H(P,V)時,會產(chǎn)生新的車輛位置,進(jìn)而導(dǎo)致相鄰車輛的Voronoi區(qū)域產(chǎn)生變化。而新的Voronoi區(qū)域會進(jìn)一步影響H(P,V)的結(jié)構(gòu),使得H(P,V)衍化出新的最優(yōu)解。這一更新迭代過程會一直持續(xù)到H(P,V)的優(yōu)化結(jié)果與更新后的Voronoi區(qū)域結(jié)果一致為止。

在上述控制系統(tǒng)的基礎(chǔ)上,給出如圖8所示的計算流程圖。通過該計算流程,可使得隨機(jī)分布的應(yīng)急救援車輛逐步趨向于當(dāng)前擁堵狀態(tài)下的最優(yōu)分布。

圖8 多應(yīng)急救援車分布規(guī)劃算法流程圖

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

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

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

step3 建立目標(biāo)區(qū)域內(nèi)所有路段的交通擁堵函數(shù)φ(q)。

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

(12)

step5 重復(fù)執(zhí)行step4,計算其余n-1輛車位于其Voronoi區(qū)域內(nèi)的消耗總時間{T(p1(t0)),…,T(pn(t0))},得到整個應(yīng)急救援車輛網(wǎng)絡(luò)在目標(biāo)區(qū)域內(nèi)的位于P(t0)處消耗時間目標(biāo)函數(shù)和H(P(t0))

(13)

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

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

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

4 仿真實驗

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

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

(14)

式中,q=[x,y]為目標(biāo)區(qū)域Q內(nèi)路網(wǎng)上的任意一點的坐標(biāo)。

圖9為交通擁堵狀態(tài)分布函數(shù)在目標(biāo)區(qū)域Q內(nèi)的變化規(guī)律。由該圖可知,目標(biāo)區(qū)域在右上角的區(qū)域擁堵系數(shù)最高。

圖9 交通擁堵狀態(tài)分布函數(shù) 圖10 應(yīng)急救援車的初始位置及其Voronoi區(qū)域 圖11 多應(yīng)急救援車最優(yōu)位置及其Voronoi區(qū)域

圖10和圖11分別為多應(yīng)急救援車網(wǎng)絡(luò)在目標(biāo)區(qū)域內(nèi)的初始位置和最優(yōu)位置,其中星號代表車輛的初始位置,三角代表車輛的最優(yōu)分布。每輛應(yīng)急救援車輛的負(fù)責(zé)區(qū)域由不同顏色進(jìn)行區(qū)分。

由圖10仿真結(jié)果可知,在考慮交通擁堵情況下,每輛應(yīng)急救援車的負(fù)責(zé)區(qū)域均有所不同。例如6號車所在位置的周圍交通擁堵系數(shù)較高,則6號車負(fù)責(zé)的區(qū)域較小,進(jìn)而有效保障該區(qū)域內(nèi)的交通事故能夠得到及時處理。4號車的負(fù)責(zé)區(qū)域也明顯大于6號車。這是因為4號車的負(fù)責(zé)區(qū)域內(nèi)交通擁堵狀態(tài)優(yōu)于6號車的負(fù)責(zé)區(qū)域。

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

圖12 多應(yīng)急救援車網(wǎng)絡(luò)的目標(biāo)函數(shù)

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

因此,上述仿真結(jié)果表明多應(yīng)急救援車輛網(wǎng)絡(luò)能夠?qū)崿F(xiàn)對目標(biāo)區(qū)域的最優(yōu)覆蓋,驗證了本文提出多應(yīng)急救援車最優(yōu)分布規(guī)劃算法的有效性與可行性。

5 結(jié) 論

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

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

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

后續(xù)的研究將進(jìn)一步在更復(fù)雜的交通路網(wǎng)上,進(jìn)行未知路況的估計,分析未知路況下的城市多應(yīng)急救援車輛分布規(guī)劃方法。