基于兩階段啟發(fā)式算法的公路網(wǎng)布局研究

常馨玉

（交通運輸部科學研究院，北京 100029）

0 引言

公路運輸作為綜合運輸體系的重要組成部分，對社會發(fā)展和客貨流通具有非常重要的作用。隨著公路網(wǎng)規(guī)模的不斷擴大、等級結(jié)構(gòu)的不斷提升，部分區(qū)域路網(wǎng)布局不夠合理等問題日益凸顯。例如，某些路段交通量過飽和，造成通而不暢；有些節(jié)點間缺乏多路聯(lián)通，路網(wǎng)的韌性和安全性有待提升，這些問題都影響了公路網(wǎng)整體效益的發(fā)揮。為此，需對公路網(wǎng)布局方法進行研究，通過完善已有的公路網(wǎng)布局方法為規(guī)劃實踐提供理論指導。

在公路網(wǎng)布局方法方面，國外主要使用專家論證法、數(shù)理解析法、系統(tǒng)分析法和四階段法[1]。隨著計算機技術(shù)的廣泛應用和交通規(guī)劃的不斷發(fā)展，一些研究逐漸將公路網(wǎng)布局問題看成網(wǎng)絡優(yōu)化問題來分析[2-3]，即在一定的約束條件下以目標函數(shù)最優(yōu)為目的，通過求解決策變量來獲得最優(yōu)解。國內(nèi)對交通規(guī)劃的研究起步相對較晚，最初采用專家論證法和數(shù)理解析法，后又采用四階段法等交通規(guī)劃理論和模型。隨著我國交通規(guī)劃的發(fā)展，國內(nèi)學者結(jié)合我國國情對公路網(wǎng)布局做了進一步探索。目前，我國公路網(wǎng)布局方法主要有以下4 種：總量控制法、節(jié)點重要度法、四階段法、交通區(qū)位線法，這幾種方法在實踐中得到了廣泛應用。在此基礎上，一系列研究工作也相繼開展，主要分為4 類：①通過定性分析與定量分析相結(jié)合來改進現(xiàn)有布局方法，如節(jié)點重要度結(jié)合交通區(qū)位線法的聯(lián)合布局法[4-6]、改進的線路重要度模型[7-8]、改進的節(jié)點重要度法[9]等；②分析路網(wǎng)布局的影響因素，對各相關因素進行量化并引入模型，構(gòu)建多因素布局優(yōu)化模型[10-12]；③基于圖論，考慮運輸需求、節(jié)點重要度、區(qū)域經(jīng)濟聯(lián)系度等建立多目標混合整數(shù)規(guī)劃模型[13-15]優(yōu)化公路網(wǎng)布局，通過對抽象網(wǎng)絡的布局來指導實踐規(guī)劃；④基于GIS 技術(shù)，實現(xiàn)規(guī)劃過程的可視化，構(gòu)建基于ArcGIS 軟件平臺的路網(wǎng)規(guī)劃模型[16-18]。

在算法求解方面，已有研究通過構(gòu)建啟發(fā)式算法對復雜的網(wǎng)絡布局問題進行求解。Du 等[19]運用衰退可靠性模型和求解算法，對交通需求和路段流量變化進行分析預測；Solomon[20]應用節(jié)約算法、掃描法等啟發(fā)式算法求解路徑優(yōu)化問題；余健[21]基于遺傳算法，針對具有兩個約束條件的情況，提出線路的最優(yōu)或次優(yōu)解決方案；趙會艷等[22]構(gòu)建了高速公路物流網(wǎng)絡規(guī)劃模型，并運用改進遺傳算法求解，提高了計算效率；吳群琪等[23]提出添加虛擬節(jié)點的方法對公路網(wǎng)布局進行優(yōu)化，并引入粒子群算法對模型求解；蔡錦德等[24]綜合考慮建設費用、路網(wǎng)可靠性和對環(huán)境的影響3 個因素構(gòu)建了多目標路網(wǎng)規(guī)劃模型，并設計混合粒子群優(yōu)化算法求解模型；楊明等[25]構(gòu)建了隨機OD 需求下的雙層交通網(wǎng)絡規(guī)劃模型，設計了基于Frank-Wolfe算法等的遺傳算法求解。

可以看出，既有研究針對公路網(wǎng)的布局方法較為單一，多集中于對既有方法（如節(jié)點重要度法、四階段法）和模型的優(yōu)化改進，且求解算法多采用單一階段的路徑優(yōu)化算法，缺少對初始解二次優(yōu)化的過程。本文將基于既有研究，結(jié)合節(jié)點重要度法，綜合考慮節(jié)點的運輸需求、路段重要度等因素構(gòu)建混合整數(shù)規(guī)劃模型，并采用隨機游走算法和模擬退火算法相結(jié)合的兩階段啟發(fā)式算法對模型進行求解，以期使公路網(wǎng)布局方案更合理。

1 路網(wǎng)布局模型構(gòu)建

1.1 問題描述

在進行公路網(wǎng)布局研究時，會將實際的公路網(wǎng)抽象為節(jié)點間的連線，節(jié)點間的需求是有向的，但本文重點解決在滿足需求的基礎上實現(xiàn)抽象網(wǎng)絡中節(jié)點間的連通問題，而非確定交通流向。因此本研究將問題定義在無向圖中，求解在多種約束條件下滿足節(jié)點連通節(jié)點間客貨流雙向聯(lián)系的公路網(wǎng)布局方案。既有的公路網(wǎng)布局多從旅行時間、建設費用、運輸成本等角度來建立模型并對網(wǎng)絡進行優(yōu)化，本文以公路網(wǎng)總旅行時間最小作為目標，以帶權(quán)鄰接矩陣作為目標函數(shù)路網(wǎng)總旅行時間的決策變量，通過目標函數(shù)和約束條件之間相互影響、相互反饋對帶權(quán)鄰接矩陣（0-1變量）不斷進行優(yōu)化，最終獲得最優(yōu)目標函數(shù)下的帶權(quán)鄰接矩陣，以此得到相應的公路網(wǎng)布局方案。

1.2 模型構(gòu)建

將問題定義在無向圖G=(V,S)上，V表示n個節(jié)點的集合，V={1,…,n} ；S表示路徑集合，s表示路徑，s∈S。

目標函數(shù)為求公路網(wǎng)總旅行時間最?。?/p>

式（1）中：z為公路網(wǎng)總旅行時間；xij為0-1 變量，當節(jié)點i,j（i,j∈V）間有直線連通時取1，否則取0；tij為節(jié)點i,j間的旅行時間；rij為由i點到j點的公路客貨運輸需求量；Cij為路段運輸承載能力；α,β為模型參數(shù)，在美國聯(lián)邦公路局的交通分配程序中，取α=0.15,β=4。

目標函數(shù)的約束條件如下：

約束（2）表示公路網(wǎng)的里程規(guī)模不超過里程規(guī)模上限，實際規(guī)劃過程中可結(jié)合當?shù)亟ㄔO需求以及數(shù)理模型預測來確定，其中Lmax表示交通網(wǎng)絡的里程規(guī)模限制，dij表示從節(jié)點i到節(jié)點j的直線距離；約束（3）表示所有節(jié)點的客貨運輸需求均被滿足，其中M表示一個能使不等式恒成立的較大的數(shù)；約束（4）表示由i點到j點的多條路徑客貨運輸需求之和為i點到j點的客貨運輸需求，其中表示由i點到j點的通過路徑s的公路客貨流量；約束（5）和（6）表示若i點到j點是直線連通，則i點到j點的公路客貨運輸需求總量等于由i點到j點通過路徑S的公路客貨流量；約束（7）表示當節(jié)點i與節(jié)點j間的路段重要度大于節(jié)點i與節(jié)點k間的路段重要度，那么xij=1,xik=0，反之，xij=0,xik=1，其中Zij表示節(jié)點i,j間的路段重要度；約束（8）表示每個節(jié)點都被連接且每個節(jié)點多路連通；約束（9）表示xij是0-1變量；約束（10）表示當節(jié)點i=j時，xij=0。

2 隨機算例設計

為驗證模型和算法的有效性，本文利用MATLAB 生成隨機算例，算例的編號為RANDn，表示節(jié)點個數(shù)為n的隨機算例。

（1）生成公路網(wǎng)中節(jié)點的位置坐標和運輸時間矩陣

首先，建立笛卡爾坐標系，將抽象網(wǎng)絡中的節(jié)點位置表示在坐標系中。將本次公路網(wǎng)的覆蓋范圍設定為100km×100km，以（50,50）為圓心，50 為半徑生成圓，在該圓內(nèi)隨機生成n個客戶點坐標，利用各節(jié)點的坐標計算兩節(jié)點間的歐氏距離dij，除以牽引車的旅行速度v即可得到兩節(jié)點間的旅行時間tij，計算公式為：

式（11）中：(xi,yi),(xj,yj)分別為兩節(jié)點的空間位置坐標。

（3）生成節(jié)點i,j間的路段重要度Zij矩陣以及路段運輸承載能力Cij矩陣

在MATLAB 中生成一個n階的零矩陣，生成(n2-4)/2 個隨機數(shù)，并將隨機數(shù)賦值于[Z12,…,Z1n],[Z23,…,Z2n],…,，生成矩陣，將矩陣轉(zhuǎn)置后得到矩陣，將矩陣和矩陣相加后得到路段重要度矩陣Zij。在MATLAB 中生成n×n的隨機數(shù)矩陣作為路段運輸承載能力矩陣Cij。

3 兩階段啟發(fā)式算法設計

網(wǎng)絡布局問題屬于NP-hard 問題，通常采用啟發(fā)式算法求解，啟發(fā)式算法是一種仿自然體算法，針對很多難以求解的復雜問題可給出相對滿意的可行解。常見的啟發(fā)式算法主要有節(jié)約算法、鄰域搜索、蟻群搜索、遺傳算法、隨機游走算法等，既有針對網(wǎng)絡布局問題的研究多采用鄰域搜索、蟻群算法、遺傳算法等，采用隨機游走算法求解網(wǎng)絡布局問題的較少。隨機游走算法是一種局部搜索算法，其基本策略是每次從當前候選解的鄰域中選擇一個更優(yōu)的進行轉(zhuǎn)移，相較于鄰域搜索、遺傳算法等能在全局優(yōu)化的過程中避免陷入局部極小值。本研究構(gòu)建的初始路網(wǎng)具有無規(guī)則性，若采用隨機游走算法求解，隨著迭代次數(shù)的增加，可能會陷入局部最優(yōu)點，因此本文在用隨機游走算法求得初始解的基礎上結(jié)合模擬退火算法，對初始解進行再次優(yōu)化，允許在迭代過程中以一定的概率接受較差的解，擺脫局部最優(yōu)情況。采取隨機游走算法和模擬退火算法相結(jié)合的兩階段啟發(fā)式算法能增強算法的全局搜索能力，提高獲得最優(yōu)解的概率。

3.1 隨機游走算法

由于模型中要計算節(jié)點間的旅行時間，因此在優(yōu)化過程中，實際改變的決策變量是各節(jié)點間的帶權(quán)鄰接矩陣，而計算兩節(jié)點間的最短距離可采用Dijkstra 算法。該算法使用貪心算法策略，用于計算一個節(jié)點到達另一個節(jié)點的最短路徑，在本文兩階段啟發(fā)式算法中屬于內(nèi)層嵌套算法。Dijkstra 算法流程如圖1 所示，其中w(k,j) 表示從k到j的路徑長度。

圖1 Dijkstra算法流程圖

外層的隨機游走算法用來優(yōu)化帶權(quán)鄰接矩陣xij。首先，根據(jù)公路運輸需求矩陣生成鄰接矩陣xij_b來表示節(jié)點間的連通情況，該鄰接矩陣不唯一，節(jié)點間有多種連接情況來滿足運輸需求，相應得到多個鄰接矩陣xij_b下的目標函數(shù)值object_b。在鄰接矩陣xij_b的基礎上做隨機擾動，如隨機改變節(jié)點i,j的連接（若i和j連通，那么斷開，反之建立連接），通過隨機操作后能得到一個新的鄰接矩陣xij_n，計算當前鄰接矩陣xij_n下的目標函數(shù)值object_n，若object_n＜object_b，則接受新的鄰接矩陣xij_n，若object_n≥object_b，則不接受該次擾動，重新進行下一次尋優(yōu)。由于鄰接矩陣xij_b的生成具有一定的隨機性，因此，在此基礎上的隨機擾動大概率會使得當前解優(yōu)于初始解，當達到初始設定的迭代次數(shù)后，輸出當前的目標函數(shù)值T即為最大迭代次數(shù)下的最優(yōu)解。隨機游走算法流程如圖2所示。

圖2 隨機游走算法流程圖

3.2 模擬退火算法

模擬退火（Simulated Annealing,SA）算法利用組合優(yōu)化問題與物理退火過程間的相似性，使優(yōu)化過程從某一較高初溫（即初始解）開始，迭代過程伴隨溫度（即目標值）的不斷下降，并結(jié)合溫度在短期內(nèi)小幅度上升（即隨機接受較差解）的特點，能跳出局部最優(yōu)解，在解空間中隨機尋求全局最優(yōu)解。本研究采用模擬退火算法對隨機游走算法生成的初始解進行優(yōu)化，使其在迭代過程中能以一定的概率接受較差解，從而使算法能跳出局部最優(yōu)，改進計算效果。接受較差解的概率P可以隨著迭代次數(shù)的增多而降低，P=(1-i/Iter) × Rand2，其中，i表示當前迭代次數(shù)，Iter表示最大迭代次數(shù)，Rand2為生成的隨機數(shù)。

模擬退火算法流程如下。

步驟1：設置最大迭代次數(shù)Iter，以隨機游走算法獲得的解為初始解，開始迭代。

步驟2：若i＜Iter，則返回隨機游走算法重新求解初始解，并得到目標函數(shù)值T，進行步驟3。否則，轉(zhuǎn)到步驟4。

步驟3：設當前解的目標值為CUR，若T＞CUR，則將初始解T設為當前解；若T≤CUR，生成隨機數(shù)Rand1，Rand1為[ ]0,1 的隨機數(shù)。當Rand1＜P時，T為當前解；否則當前解不變，迭代次數(shù)加1，返回步驟2。

步驟4：將當前解設為最優(yōu)解，計算終止。

歷史最優(yōu)解不受模擬退火的影響，只有尋優(yōu)到新的最優(yōu)解時才會覆蓋原有解，當出現(xiàn)新的最優(yōu)解時更新節(jié)點連接網(wǎng)絡。在達到最大迭代次數(shù)后算法停止并輸出最優(yōu)解。

模擬退火算法流程如圖3所示。

圖3 模擬退火算法流程圖

4 算例求解與分析

本文運用兩階段啟發(fā)式算法對生成的隨機算例進行求解，以區(qū)域內(nèi)10個節(jié)點的算例為例進行連線布局，節(jié)點間的時間矩陣、路段重要度矩陣、客貨運輸OD 流量矩陣和路段運輸承載能力矩陣分別如表1～表4所示。

表1 節(jié)點間時間矩陣tij 單位：h

表2 路段重要度矩陣Zij

表3 客貨運輸OD流量矩陣rij 單位：kg

表3 （續(xù)）

表4 路段運輸承載能力矩陣Cij 單位：kg

通過MATLAB 編程計算，循環(huán)次數(shù)設置為5 000，每次循環(huán)中在生成初始解的基礎上按照一定的概率接受較差的解，直至所有節(jié)點均被連通，由此得到目標函數(shù)值z=54.45h，計算時間為15s。各節(jié)點的布局連接情況如表5所示。

表5 節(jié)點間布局連接情況

表5 （續(xù)）

通過對隨機算例的求解得到圖4節(jié)點連通圖，節(jié)點的空間位置由橫縱坐標確定，圖4 反映了兩個節(jié)點間的連通情況，可代表一條線路，也可代表多條線路之和。由圖4 可以看出，當?shù)螖?shù)較少時，優(yōu)先連通重要度較大的節(jié)點，部分重要度較低的節(jié)點尚未被連通（如圖4（a）所示），隨著迭代次數(shù)的增加，網(wǎng)絡中的所有節(jié)點均被連通（如圖4（b）所示）。當給一定的隨機擾動后，節(jié)點間的連接情況發(fā)生改變，重要度較低的節(jié)點可能被多路連通，若目標函數(shù)值未被優(yōu)化，那么重新改變連通方式（如圖4（c）～4（f）所示），直至在最大迭代次數(shù)下獲得目標函數(shù)值最優(yōu)的公路網(wǎng)布局方案（如圖4（g）所示）。圖中存在節(jié)點4 到節(jié)點7、節(jié)點5 到節(jié)點7 的連線接近重合的情況，原因為該圖是抽象網(wǎng)絡圖，圖中兩條連線僅反映節(jié)點間的連通情況，連線接近并不代表實際路線接近。

圖4 節(jié)點連通動態(tài)演示圖

計算結(jié)果表明，兩階段啟發(fā)式算法能在較短時間內(nèi)給出較為滿意的解，可為規(guī)劃實踐中大規(guī)模網(wǎng)絡優(yōu)化問題的求解提供一定的方法借鑒。在公路網(wǎng)布局規(guī)劃實踐中，也可通過該方法獲得初始路網(wǎng)，在此基礎上，綜合考慮自然地形、建設資金、區(qū)域發(fā)展規(guī)劃等因素，再結(jié)合單因素法、交通區(qū)位線法等進行優(yōu)化調(diào)整。

5 結(jié)語

交通網(wǎng)絡布局是需求到網(wǎng)絡形態(tài)的映射，而網(wǎng)絡的布局形態(tài)由節(jié)點的連接決定，本文將公路網(wǎng)布局抽象為一定約束條件下節(jié)點的連通問題，以路網(wǎng)總旅行時間最小為目標，綜合考慮路段重要度和運輸需求，構(gòu)建了公路網(wǎng)布局的混合整數(shù)規(guī)劃模型，以路段重要度和運輸需求為啟發(fā)式條件設計了隨機游走算法與模擬退火算法相結(jié)合的兩階段啟發(fā)式算法，通過該兩階段啟發(fā)式算法可有效求解路網(wǎng)布局問題，獲得公路網(wǎng)布局方案。由于在規(guī)劃實踐中影響路網(wǎng)布局的因素較多，本文構(gòu)建的模型雖能在一定程度上反映路網(wǎng)布局的目標和要求，但未能全面考慮所有相關因素對節(jié)點連通的影響，下一階段可將區(qū)域、國家政策等因素量化并納入模型中，使模型更貼合規(guī)劃實際；同時，可從保證節(jié)點間的多路連通等方面進一步優(yōu)化設計兩階段啟發(fā)式算法，增強路網(wǎng)韌性。