一種解決專用道設置問題的分布式蟻群算法實現

曹明

（北京航空航天大學經濟管理學院，北京100191）

1 背景

隨著中國社會經濟的發展，各種大型活動，如大型體育賽事、大型會展活動等經常在大城市舉辦。這樣一方面使大城市的交通壓力增大，另一方面因為大型活動對時間有嚴格的要求（比如2008 年北京奧運會就嚴格要求從運動員駐地到比賽場館的行車時間要限制在30 分鐘內），場館到運動員駐地的交通必須保持暢通。要同時解決這兩方面的問題，在城市交通基礎設施不能短期內得到明顯提升的前提下，實行必要的交通管制是一種行之有效的手段。為保證這類大型活動對時間的要求，交通管制一般的做法是在有多條車道的城市道路上劃定專用車道，在某個時間范圍內供大型活動的車輛使用，這種做法類似于城市的公交專用道[1,2]，如圖1 所示。本文的研究目標就是這種專用道的設置問題。

圖1 城市的公交專用道示例

LRP（Lane Reservation Problem）即專用道設置問題[3-6]，是交通運輸領域的熱點研究問題之一。LRP 著眼于解決在哪些道路上設置專用道，可以滿足諸如從運動員駐地到比賽場館的最長時間要求的限制，同時盡量保證城市交通不受太大影響。LRP是組合優化問題，這類問題的算法復雜度通常都是NP-Hard的，需要綜合交通、運籌學、計算機科學等多學科知識加以解決。由于LRP 的復雜性，對大規模問題，運籌學軟件可能無能為力，即不可能在有限時間內找到最優解。這就需要采用啟發式算法，在可以接受的計算時間內求得一個能夠滿足要求的次優解。

本文探討在分布式計算框架Spark 下實現一個蟻群算法[7-11]，用于求解LRP 問題。首先描述了LPR 的數學模型，隨后給出了分布式蟻群算法的實現方法。將該方法應用于現有的LRP，給出了實驗結果。

2 數學模型

采用文獻[3]中的LRP 的數學模型作為本文求解的模型。該模型是以2010 年廣州亞運會的道路網絡圖為基礎構建的，如圖2 所示。圖2 包括一個表示運動員駐地的頂點（起點），多個表示比賽場館的頂點（終點），多個表示途中各個岔路口的頂點（中間節點），以及表示這些點之間道路的弧。從圖2 可以看出，從運動員駐地到任何比賽場館都存在至少一條可通達的路徑。圖3 中用到的式（14）定義：

圖2 運動員駐地到比賽場館的道路網絡圖

3 分布式蟻群算法的實現

從上述LRP 模型可以知道，求解該模型的關鍵是找到從起始頂點到目標終點的一條無回路的行駛路徑。可以利用蟻群算法的生物特性，假定有一只螞蟻從起始頂點走到目標終點且不產生回路（無環），那么這只螞蟻走過的路徑可以作為一條備選路徑，再繼續考察是否要在這條路徑上設置專用道即可，問題就簡化成了一個背包問題。

根據蟻群算法的信息素更新來指導每次迭代中每只螞蟻的道路選擇。因為算法使用Spark 計算框架實現，故這里直接給出在Spark 框架下蟻群算法的工作流程，見圖3 中的偽代碼。

圖3 蟻群算法在Spark 框架下的偽代碼

表1 交通網絡圖中弧(i,j)上信息示例：ω ij (λ i j ,T C ij ,T Sij , μij)

4 實驗結果

實驗結果在Intel Core I9 的電腦上以Spark 中的本地運行local[8]的方式運行獲得，即默認使用8 線程并行計算。

采用上述蟻群算法，本文在迭代3 次、每次使用3 只螞蟻的條件下，求出了該LRP 模型在時間約束C=30 分鐘下的一個次優解，如表2 所示。

表2 時間約束C=30 分鐘下的一個次優解

又隨機做了10 次迭代，每次使用10 只螞蟻，得到了另一個次優解,如表3 所示。

表3 時間約束C=30 分鐘下的第二個次優解

從兩個次優解可以看出，在約束C=30 分鐘的情況下，可以求出不需要設置專用道的、符合賽會行程時間限制的次優解，也就是從運動員駐地到比賽場館，若按照可選擇的路徑行駛，就沒有必要設置專用道，正常通行即可，不會對城市交通帶來影響。

為考察算法對大規模問題的求解效率，本文將網絡圖的頂點個數調大，由Spark 的Graphx 自生成圖的方式，生成不同頂點個數的網絡圖，然后采用蟻群算法計算，得到的頂點個數和算法運算時間的關系如圖4 所示。從圖中可以觀察到，頂點個數和運算時間的曲線呈現多項式關系。

圖4 頂點個數和運算時間的關系圖

5 結論

本文闡述了LRP 的研究背景和數學模型。LRP 是一個復雜度為NP-Hard 的問題，用傳統算法無法在多項式時間內求出精確解，因此需使用啟發式算法對LRP 問題求得滿足約束條件的次優解。為此，本文在Spark 計算框架下設計了一種分布式的蟻群算法。通過實驗發現，該算法可以有效求得模型的次優解。對于大規模LRP 的求解，本文用設計的蟻群算法計算并比較了不同的網絡頂點個數對應的運算時間。從結果可以看出，網絡頂點個數和運算時間呈多項式關系。