動態規劃在指路標志指引上的應用

李 敏，黃 敏，周 靜

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

指路標志作為一種指引工具，為出行者快速傳遞道路的方向、距離、地點等信息[1]。隨著城市路網建設進程的不斷推進，城市道路路網趨于多樣性與復雜性，從而使得出行者選擇路徑更趨于多元化，為此，出行者對指路標志誘導系統的需求性逐漸增加[2]。指路標志作為靜態誘導的重要組成單元，在交通流的誘導中起著重要的角色，科學合理地布設指路標志不僅能為出行者提供有效的道路信息，同時也能夠平穩過渡交通流，實現交通流的穩靜化[3-4]。目前，國內外學者對指路標志的研究主要體現在指路標志的版面尺寸設計、設置的具體位置等工程性應用上，對指路標志以路徑誘導為基礎，反向實現指路標志的智能化布設的研究較少[5-8]，且從整體路網的角度系統地考慮指路標志設置的研究也較少。

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

1 動態規劃的基本概念

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

圖1 線路網絡距離權值圖Fig.1 Weight map of line network distance

1.1 階段

動態規劃方法是將問題的過程分解成多個相互聯系的階段，并按照一定的順序去求解，一般用k表示階段變量。階段的劃分常根據空間和時間特征來進行劃分，例如圖1中的最短路徑問題可分為6個階段：A—B—C—D—E—F。

1.2 狀態

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

1.3 決策

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

1.4 策略

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

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

(1)

當k=1時，此決策函數序列稱為全過程的一個策略，簡稱策略，記為p1,n(S1)，其公式如下：

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

(2)

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

1.5 狀態轉移方程

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

1.6 指數函數

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

1) 各階段的指標的和，其公式為：

(3)

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

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

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

(4)

這時也可寫成如下的公式：

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

1.7 最優值函數

最優函數值為指標函數的最優值，記為fk(Sk)。它表示從第k階段狀態Sk采用最優策略Pk,n到過程終止時的最優值，其公式為：

(5)

當k=1時，f1(S1)就是從初始狀態S1到全過程結束的整體最優指標函數。

2 應用實例

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

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

2.1 廣州大學城路網特點與道路等級

廣州大學城的內部道路規劃結合自然形態，沿自然邊界走向由內到外規劃了3條環線，形成“內環、中環、外環”3大環的獨特路網。環線與環線之間采用放射性的道路進行銜接，如圖2所示。根據廣州大學城的具體特征，按照車流量大小、道路功能，將大學城內的道路分為3種等級。其中，具體道路指示等級劃分結果如表1所示。而本文主要采用一級道路和二級道路組成的路網，在此路網上找出最優路徑，即圖3中粗線條組成的路網。

2.2 實例的具體運算過程

用動態規劃法求最短路徑問題可以用順序解法和逆序解法，只是行進方向不同或對始端、終端算法的顛倒，但動態規劃求最優解時，都是在行進方向確定后，逆著這個既定方向行進，從最后一段向前逆推計算，逐段找出最優路徑。實例中介紹了5個起點O1、O2、O3、O4、O5，本節以起點O5為例，采用動態規劃的方法，來計算O5到中山大學D的最短路徑。其中路網中各個路段的權值如圖4所示，黑色加粗數字表示結點，黑色數字表示路段距離阻抗值。

表1 廣州大學城道路指示等級分類Table 1 Direction classification of Guangzhou University City road

圖3廣州大學城道路結構示意
Fig.3 Schematic diagram of the road structure of Guangzhou University City

圖4 廣州大學城道路距離權值Fig.4 Weight map of Guangzhou University City road distance

首先根據動態規劃的基本概念，顯然滿足無后效性，故可用動態規劃求解。對于本實例，O5所在的結點為54，所以動態規劃的起點從結點54開始，可將其分成11個階段從后往前推。

當k=11時，其狀態集合為{55,44,28}，對于結點55，其最優值為f11(55)=d(55,54)+0=572，最優決策為55-54；結點44，其最優值為f11(44)=d(44,54)+0=705，最優決策為44-54；結點28其最優值f11(28)=d(28,54)+0=1 502，最優決策為28-54。

當k=10時，其狀態集合為{56,53,45,34,27,18}，結點56，f10(56)=d(56,55)+f11(55)=2 605，最優決策為56-55；結點53、45、34、27、18分別如下：

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

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

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

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

? ? ? ? ? ?

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

當k=1時，其狀態集合為{1}

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

O1、O2、O3、O4到D中大北門的最優路徑可以類似于上述方法計算出來，最后總的最優路線如圖5所示。找出各個起始點的最優路徑后，再在其最優路徑上著重布設指路標志，最大限度地發揮好指路標志誘導交通流的功能。

圖5 總的最優指引路徑Fig.5 Diagram of overall optimal guidance path

3 結束語

本文采用動態規劃的方法，在明確起終點條件下，找到了一定范圍路網內的最優路徑。通過在最優路徑上設置指路標志對目的地進行指引，能充分發揮指路標志的誘導功能，進而體現指路標志布設的科學性和合理性。本文提出的動態規劃是在指路標志指引上的應用，只考慮了距離作為出行者的考慮因素，在后續的研究中將對出行者的路徑選擇進行綜合分析，從綜合影響因素出發，系統地對指路標志的指引路徑進行研究，更好地完善與優化指路標志的誘導功能。