李 敏，黃 敏，周 靜

(1.招商局重慶交通科研設(shè)計(jì)院有限公司， 重慶 400067； 2.中山大學(xué) 智能工程學(xué)院， 廣州 510006)

指路標(biāo)志作為一種指引工具，為出行者快速傳遞道路的方向、距離、地點(diǎn)等信息[1]。隨著城市路網(wǎng)建設(shè)進(jìn)程的不斷推進(jìn)，城市道路路網(wǎng)趨于多樣性與復(fù)雜性，從而使得出行者選擇路徑更趨于多元化，為此，出行者對(duì)指路標(biāo)志誘導(dǎo)系統(tǒng)的需求性逐漸增加[2]。指路標(biāo)志作為靜態(tài)誘導(dǎo)的重要組成單元，在交通流的誘導(dǎo)中起著重要的角色，科學(xué)合理地布設(shè)指路標(biāo)志不僅能為出行者提供有效的道路信息，同時(shí)也能夠平穩(wěn)過渡交通流，實(shí)現(xiàn)交通流的穩(wěn)靜化[3-4]。目前，國(guó)內(nèi)外學(xué)者對(duì)指路標(biāo)志的研究主要體現(xiàn)在指路標(biāo)志的版面尺寸設(shè)計(jì)、設(shè)置的具體位置等工程性應(yīng)用上，對(duì)指路標(biāo)志以路徑誘導(dǎo)為基礎(chǔ)，反向?qū)崿F(xiàn)指路標(biāo)志的智能化布設(shè)的研究較少[5-8]，且從整體路網(wǎng)的角度系統(tǒng)地考慮指路標(biāo)志設(shè)置的研究也較少。

交通指路標(biāo)志的版面內(nèi)容主要分為對(duì)道路的指引和地點(diǎn)的指引2大部分[9-10]，出行者一般已經(jīng)知道通過某條道路可以到達(dá)其目的地，其所需信息是怎樣才能到達(dá)該道路上。實(shí)際上，出行者最終想要到達(dá)的不是到達(dá)某條道路，而是通過哪些路徑能到到達(dá)其目的地。然而這些路徑中有些可能是時(shí)間上最短，有些可能是路程上最短，甚至有些路徑可能是風(fēng)光最好等等[11-12]。為此，本文根據(jù)出行者選擇出行路徑的多樣性，以出行者行駛路程權(quán)值最小的路徑作為最優(yōu)路徑，并以廣州大學(xué)城中山大學(xué)為例，采用動(dòng)態(tài)規(guī)劃的方法，找出在廣州大學(xué)城入口以及某些景點(diǎn)到中山大學(xué)的最優(yōu)路徑，再對(duì)其路徑著重布設(shè)指標(biāo)志，充分發(fā)揮指路標(biāo)志的誘導(dǎo)功能。

1 動(dòng)態(tài)規(guī)劃的基本概念

動(dòng)態(tài)規(guī)劃是在20世紀(jì)50年代由美國(guó)數(shù)學(xué)家貝爾曼(R.Bellman)等人提出的，它是解決多階段決策過程最優(yōu)化的一種方法[13-16]。此方法能較好地應(yīng)用于最優(yōu)路徑?jīng)Q策、生產(chǎn)計(jì)劃和庫存、資源分配、企業(yè)管理等方面。在諸多問題上，動(dòng)態(tài)規(guī)劃較線性與非線性規(guī)劃更有成效，特別在處理離散型問題上，由于解析數(shù)學(xué)較難處理，而動(dòng)態(tài)規(guī)劃就成為非常有用的方法。動(dòng)態(tài)規(guī)劃的核心思想在于將問題公式化，換而言之，動(dòng)態(tài)規(guī)劃是將多階段決策問題進(jìn)行公式化的一種手段。動(dòng)態(tài)規(guī)劃的基本流程分為階段、狀態(tài)、決策、策略、狀態(tài)轉(zhuǎn)移方程以及指標(biāo)函數(shù)和最優(yōu)值函數(shù)7大部分。在介紹動(dòng)態(tài)規(guī)劃的一些基本概念之前，先引入一個(gè)實(shí)例，然后結(jié)合實(shí)例來介紹基本概念，以易于理解。如圖1所示，在圖中要從A到F選擇一條行駛路徑，各點(diǎn)間連線上的數(shù)字表示距離權(quán)值，問應(yīng)怎么選擇使得路線距離最短？

圖1 線路網(wǎng)絡(luò)距離權(quán)值圖Fig.1 Weight map of line network distance

1.1 階段

動(dòng)態(tài)規(guī)劃方法是將問題的過程分解成多個(gè)相互聯(lián)系的階段，并按照一定的順序去求解，一般用k表示階段變量。階段的劃分常根據(jù)空間和時(shí)間特征來進(jìn)行劃分，例如圖1中的最短路徑問題可分為6個(gè)階段：A—B—C—D—E—F。

1.2 狀態(tài)

狀態(tài)表示每個(gè)階段在研究問題過程中所處的狀況，狀態(tài)就是某階段的出發(fā)位置，一般一個(gè)階段有多個(gè)狀態(tài)。在圖1中，第1階段有1個(gè)狀態(tài)即點(diǎn)A，第2階段有2個(gè)狀態(tài)，即點(diǎn)集合{B1,B2}，通常第k階段的狀態(tài)就是第k階段所有起始點(diǎn)的集合。一般用Sk表示第k階段的狀態(tài)變量，用Sk表示狀態(tài)變量的取值集合(狀態(tài)集合)。如例1中，第四階段的狀態(tài)集合S4={D1,D2,D3}。這里所說的狀態(tài)應(yīng)具有當(dāng)前的狀態(tài)是過去的一個(gè)完結(jié)，同時(shí)是未來過程的初始狀態(tài)的性質(zhì)，這個(gè)性質(zhì)被稱為無后效性，如圖1中，在第3階段(C階段)選擇什么路徑與之前的階段無關(guān)。

1.3 決策

決策表示在處于某一階段的某個(gè)狀態(tài)時(shí)，往下一階段做出的決定稱為決策。一般用uk(Sk)表示第k階段當(dāng)狀態(tài)處于Sk時(shí)的決策變量；Dk(Sk)表示第k階段從狀態(tài)Sk出發(fā)可以決策的集合。在例1中：D2(C2)={D1,D2,D3}，表示在第2階段從狀態(tài)C2出發(fā)允許決策有D1,D2,D3；u2(C2)=D1，表示第2階段在C2處選擇D1為下一目的地。

1.4 策略

策略可理解成按順序排列的決策組成的集合。由每階段的決策按順序排列組成的決策函數(shù)序列{uk(Sk),…,un(Sn)}稱為k子過程策略，簡(jiǎn)稱子策略，記為pk,n(Sk),其公式如式(1)：

pk,n(Sk)={uk(Sk),uk+1(Sk+1),…,un(Sn)}

(1)

當(dāng)k=1時(shí)，此決策函數(shù)序列稱為全過程的一個(gè)策略，簡(jiǎn)稱策略，記為p1,n(S1)，其公式如下：

p1,n(S1)={u1(S1),u2(S2),…,un(Sn)}

(2)

在例1中，p1,n(A)={A,B1,C1,D1,E1,F}就為一個(gè)策略。

1.5 狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程是確定過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的控制條件。若給定第k階段狀態(tài)變量Sk的值，如果該段的決策變量uk一經(jīng)確定，則第k+1階段的狀態(tài)變量Sk+1的值也就可以確定。即Sk+1的值隨Sk和uk值的變化而變化，這種確定的對(duì)應(yīng)關(guān)系，記為：Sk+1=Tk(Sk,uk)，此式描述了由k階段到k+1階段的狀態(tài)轉(zhuǎn)移方式，Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。例如圖1中，第2階段狀態(tài)及決策決定第3階段所處的狀態(tài)：S3=T2(S2，u2)；S2=B2，u2(B2)=C1, 則S3=T2(B2，C1)=C1。

1.6 指數(shù)函數(shù)

指數(shù)函數(shù)是一種數(shù)量指標(biāo)，用于衡量所實(shí)現(xiàn)過程的優(yōu)劣，常用Vk,n表示，其函數(shù)表達(dá)式為：Vk,n=Vk,n(Sk,uk,Sk+1,…,Sn+1),k=1,2,…,n。對(duì)于此指標(biāo)函數(shù)，應(yīng)具有可分離性，同時(shí)滿足遞推關(guān)系。即Vk,n可以表示為Sk、uk、Vk+1,n的函數(shù)。記為Vk,n(Sk,uk,Sk+1,…,Sn+1)=ψk[Sk,uk,Vk+1,n(Sk+1,n,…,Sn+1)]；常見的指標(biāo)函數(shù)形式如下。

1) 各階段的指標(biāo)的和，其公式為：

(3)

式中：vj(Sj,uj)為第j階段的階段指標(biāo)。這時(shí)，式(3)可寫成如下的公式：

Vk,n(Sk,uk,…,Sn+1)=vk(Sk,uk)+Vk+1,n(Sk+1,uk+1,…,Sn+1)

2) 各階段的指標(biāo)的乘積，其公式為：

(4)

這時(shí)也可寫成如下的公式：

Vk,n(Sk,uk,…,Sn+1)=vk(Sk,uk)+Vk+1,n(Sk+1,uk+1,…,Sn+1)

1.7 最優(yōu)值函數(shù)

最優(yōu)函數(shù)值為指標(biāo)函數(shù)的最優(yōu)值，記為fk(Sk)。它表示從第k階段狀態(tài)Sk采用最優(yōu)策略Pk,n到過程終止時(shí)的最優(yōu)值，其公式為：

(5)

當(dāng)k=1時(shí)，f1(S1)就是從初始狀態(tài)S1到全過程結(jié)束的整體最優(yōu)指標(biāo)函數(shù)。

2 應(yīng)用實(shí)例

本文以廣州大學(xué)城路網(wǎng)為實(shí)例，針對(duì)中山大學(xué)的指引，以各個(gè)進(jìn)入大學(xué)城的入口為起點(diǎn)O，以中山大學(xué)牌坊為終點(diǎn)D，如圖2所示。其中O1表示官洲隧道出口；O2表示小洲便橋出口；O3表示華南快速出口；O4表示赤坎橋出入口；O5表示新造渡口。在明確起終點(diǎn)的情況下，采用上述提到的動(dòng)態(tài)規(guī)劃的方法找到前往中山大學(xué)的最優(yōu)路徑，驗(yàn)證了動(dòng)態(tài)規(guī)劃算法的有效性。如圖2所示，廣州大學(xué)城是一個(gè)較為閉合的功能區(qū)域，路網(wǎng)結(jié)構(gòu)具有其獨(dú)特性。因此本節(jié)將先對(duì)廣州大學(xué)城的路網(wǎng)和功能特點(diǎn)進(jìn)行闡述，選取主要路網(wǎng)作為研究對(duì)象。

圖2 廣州大學(xué)城出入口示意Fig.2 Schematic diagram of the entrance and exit of Guangzhou University City

2.1 廣州大學(xué)城路網(wǎng)特點(diǎn)與道路等級(jí)

廣州大學(xué)城的內(nèi)部道路規(guī)劃結(jié)合自然形態(tài)，沿自然邊界走向由內(nèi)到外規(guī)劃了3條環(huán)線，形成“內(nèi)環(huán)、中環(huán)、外環(huán)”3大環(huán)的獨(dú)特路網(wǎng)。環(huán)線與環(huán)線之間采用放射性的道路進(jìn)行銜接，如圖2所示。根據(jù)廣州大學(xué)城的具體特征，按照車流量大小、道路功能，將大學(xué)城內(nèi)的道路分為3種等級(jí)。其中，具體道路指示等級(jí)劃分結(jié)果如表1所示。而本文主要采用一級(jí)道路和二級(jí)道路組成的路網(wǎng)，在此路網(wǎng)上找出最優(yōu)路徑，即圖3中粗線條組成的路網(wǎng)。

2.2 實(shí)例的具體運(yùn)算過程

用動(dòng)態(tài)規(guī)劃法求最短路徑問題可以用順序解法和逆序解法，只是行進(jìn)方向不同或?qū)κ级?、終端算法的顛倒，但動(dòng)態(tài)規(guī)劃求最優(yōu)解時(shí)，都是在行進(jìn)方向確定后，逆著這個(gè)既定方向行進(jìn)，從最后一段向前逆推計(jì)算，逐段找出最優(yōu)路徑。實(shí)例中介紹了5個(gè)起點(diǎn)O1、O2、O3、O4、O5，本節(jié)以起點(diǎn)O5為例，采用動(dòng)態(tài)規(guī)劃的方法，來計(jì)算O5到中山大學(xué)D的最短路徑。其中路網(wǎng)中各個(gè)路段的權(quán)值如圖4所示，黑色加粗?jǐn)?shù)字表示結(jié)點(diǎn)，黑色數(shù)字表示路段距離阻抗值。

表1 廣州大學(xué)城道路指示等級(jí)分類Table 1 Direction classification of Guangzhou University City road

圖3廣州大學(xué)城道路結(jié)構(gòu)示意
Fig.3 Schematic diagram of the road structure of Guangzhou University City

圖4 廣州大學(xué)城道路距離權(quán)值Fig.4 Weight map of Guangzhou University City road distance

首先根據(jù)動(dòng)態(tài)規(guī)劃的基本概念，顯然滿足無后效性，故可用動(dòng)態(tài)規(guī)劃求解。對(duì)于本實(shí)例，O5所在的結(jié)點(diǎn)為54，所以動(dòng)態(tài)規(guī)劃的起點(diǎn)從結(jié)點(diǎn)54開始，可將其分成11個(gè)階段從后往前推。

當(dāng)k=11時(shí)，其狀態(tài)集合為{55,44,28}，對(duì)于結(jié)點(diǎn)55，其最優(yōu)值為f11(55)=d(55,54)+0=572，最優(yōu)決策為55-54；結(jié)點(diǎn)44，其最優(yōu)值為f11(44)=d(44,54)+0=705，最優(yōu)決策為44-54；結(jié)點(diǎn)28其最優(yōu)值f11(28)=d(28,54)+0=1 502，最優(yōu)決策為28-54。

當(dāng)k=10時(shí)，其狀態(tài)集合為{56,53,45,34,27,18}，結(jié)點(diǎn)56，f10(56)=d(56,55)+f11(55)=2 605，最優(yōu)決策為56-55；結(jié)點(diǎn)53、45、34、27、18分別如下：

f10(53)=d(53,55)+f11(55)=1 376，最優(yōu)決策為53-55；

f10(45)=d(45,44)+f11(44)=978，最優(yōu)決策為45-44；

f10(34)=d(34,44)+f11(44)=1 118，最優(yōu)決策為34-44；

f10(18)=d(18,28)+f11(28)=2 267，最優(yōu)決策為18-28；

? ? ? ? ? ?

當(dāng)k=3時(shí)，f3(4)=2 974,f3(5)=2 975;f3(12)=3 669,f3(13)=3 327;

當(dāng)k=1時(shí)，其狀態(tài)集合為{1}

綜合得到最優(yōu)路徑為1-2-4-8-15-20-26-30-29-34-44-54。

O1、O2、O3、O4到D中大北門的最優(yōu)路徑可以類似于上述方法計(jì)算出來，最后總的最優(yōu)路線如圖5所示。找出各個(gè)起始點(diǎn)的最優(yōu)路徑后，再在其最優(yōu)路徑上著重布設(shè)指路標(biāo)志，最大限度地發(fā)揮好指路標(biāo)志誘導(dǎo)交通流的功能。

圖5 總的最優(yōu)指引路徑Fig.5 Diagram of overall optimal guidance path

3 結(jié)束語

本文采用動(dòng)態(tài)規(guī)劃的方法，在明確起終點(diǎn)條件下，找到了一定范圍路網(wǎng)內(nèi)的最優(yōu)路徑。通過在最優(yōu)路徑上設(shè)置指路標(biāo)志對(duì)目的地進(jìn)行指引，能充分發(fā)揮指路標(biāo)志的誘導(dǎo)功能，進(jìn)而體現(xiàn)指路標(biāo)志布設(shè)的科學(xué)性和合理性。本文提出的動(dòng)態(tài)規(guī)劃是在指路標(biāo)志指引上的應(yīng)用，只考慮了距離作為出行者的考慮因素，在后續(xù)的研究中將對(duì)出行者的路徑選擇進(jìn)行綜合分析，從綜合影響因素出發(fā)，系統(tǒng)地對(duì)指路標(biāo)志的指引路徑進(jìn)行研究，更好地完善與優(yōu)化指路標(biāo)志的誘導(dǎo)功能。