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

常馨玉

（交通運(yùn)輸部科學(xué)研究院，北京 100029）

0 引言

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

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

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

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

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

1.1 問題描述

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

1.2 模型構(gòu)建

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

目標(biāo)函數(shù)為求公路網(wǎng)總旅行時(shí)間最小：

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

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

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

2 隨機(jī)算例設(shè)計(jì)

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

（1）生成公路網(wǎng)中節(jié)點(diǎn)的位置坐標(biāo)和運(yùn)輸時(shí)間矩陣

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

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

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

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

3 兩階段啟發(fā)式算法設(shè)計(jì)

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

3.1 隨機(jī)游走算法

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

圖1 Dijkstra算法流程圖

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

圖2 隨機(jī)游走算法流程圖

3.2 模擬退火算法

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

模擬退火算法流程如下。

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

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

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

步驟4：將當(dāng)前解設(shè)為最優(yōu)解，計(jì)算終止。

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

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

圖3 模擬退火算法流程圖

4 算例求解與分析

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

表1 節(jié)點(diǎn)間時(shí)間矩陣tij 單位：h

表2 路段重要度矩陣Zij

表3 客貨運(yùn)輸OD流量矩陣rij 單位：kg

表3 （續(xù)）

表4 路段運(yùn)輸承載能力矩陣Cij 單位：kg

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

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

表5 （續(xù)）

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

圖4 節(jié)點(diǎn)連通動(dòng)態(tài)演示圖

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

5 結(jié)語

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