基于網絡層次拓撲結構的公路網多目標最優路徑算法

龍威棟

摘要：公路網多目標最優路徑問題（Multi-objective Optimal Path Problem of Highway Net-work，MOPPHN）是一個活躍的研究領域，因為它應用于大量系統。在路網系統中，有必要找到從一個節點到指定節點或所有其他節點的最佳路徑。在最壞的情況下，用于計算從指定源節點到MOPPHN中所有其他節點的所有多目標最優路徑的計算復雜度是指數級的。文章提出了一種算法，用于在網絡層次拓撲結構內找到一組多目標最優路徑的值，而不是在指數時間內生成多目標最優路徑的所有值，這在許多情況下都是非常重要的。應用文章提出的算法，可以找到網絡中任何MOPPHN的一組多目標最優路徑，即使它包含負循環。通過實驗分析，驗證了該算法在實際和理論上都表現良好。

關鍵詞：網絡;多重目標;多目標最優路徑

中圖分類號：U491 文獻標識碼：A DOI：10.13282/j.cnki.wccst.2019.10.048

文章編號：1673-4874（2019）10-0174-05

0引言

網絡優化問題是運籌學和管理科學中研究最多的課題之一。網絡模型可以從大量應用領域獲得，例如運輸系統、通信系統、電力傳輸系統及水、血液、氣體和排水的管道分配系統，神經決策系統、生產計劃和項目規劃等。這種網絡中涉及的目標數量可以是一個或多個。這里的基本問題是找到從特定起始節點到所有其他節點的最佳路徑或帕累托最優路徑。在單目標最短路徑問題（SOSPP）中，只考慮一個目標，而公路網多目標最優路徑問題（MOPPHN）由多個目標組成。對于SOSPP，文獻中存在許多有效的算法以找到從一個節點到另一個節點或從一個節點到所有其他節點的最短路徑。萬瑩等對運輸網絡的多目標設計和42個選定參考文獻的注釋書目進行分類，提交了一份關于MOPPHN的調查報告。一個特定的網絡證明了在最壞情況下生成所有Pareto最優解使兩個目標最短路徑問題變得難以處理，因為公路網多目標最優路徑的數量隨著節點數量呈指數增長。網絡中任何MOPPHN的公路網多目標最優路徑的最大數量，在最壞的情況下，是1+（n-2）+（n-2）（n-3）+…+（n-2）！+（n-2）！它位于2[（n-2）！]和3[（n-2）！]之間。有研究提出了MOPPHN的標記算法并修改了Hansen網絡，表明標記算法還可以確定指數數量的主導標簽來計算單個最優解，給出了一種使用動態規劃方法解決MOPPHN的算法，這在理論上也不是一個好的算法。

因此，用于生成從源節點到MOPPHN中的所有其他節點的多目標最優路徑的所有值的現有算法都是指數時間算法。這促使本文研究網絡層次拓撲結構以多目標最優路徑的值集的子集來改善時間復雜度。本文提出了一種顧及網絡層次拓撲結構的公路網多目標最優路徑算法，該算法通過確定相應SOSPP的第一個多目標最優路徑，生成網絡中MOPPHN的多目標最優路徑的所有值集合的子集。首先使用算術平均技術確定對應于網絡的給定MOPPHN的SOSPP。如果網絡的MOPPHN具有負循環，則所有現有算法僅指示負循環的存在，即指數操作之后也是如此。但是，應用本文提出的算法，可以找到網絡中任何MOPPHN的一組多目標最優路徑，即使它包含負循環。

1基本知識

1.1 符號

1.2 相關知識

1.2.1 網絡

1.2.2 路徑和無環路徑

V的節點i和j之間的路徑是連接節點i和j的連續邊緣序列，本文還可以通過其節點的序列（v，…，v）來表示路徑。如果路徑的節點序列是有限的，那么該路徑被認為是有限的。如果網絡的所有節點都是不同的，則稱其為無環路徑。

1.2.3 路徑的值

1.2.4 多目標最優路徑問題

2 多目標最優路徑算法

本文提出的算法需要計算多目標最優路徑。基本標簽校正算法用于找到多目標最優路徑。基本標簽校正算法僅生成不包含負循環的網絡的多目標最優路徑的值。生成的值對應的多目標最優路徑可以包含循環。本文已經包含了一個額外的步驟，它跟蹤無環路徑并生成非減少k最短無環路徑和路徑本身的值。由于算法生成無環路徑，因此它可以應用于任何網絡，即使它包含負循環。為了確定無環路徑，該算法需要額外的O（nk）基本操作。因此，確定k-最短無環路徑的最壞情況計算復雜度是。（nkIogn+nk），該算法將給定的網絡MOPPHN轉換為SOSPP。通過用相應邊緣的矢量權重的分量的算術平均值替換網絡的每個邊緣的矢量權重來完成變換。它確定SOSPP的第一個多目標最優路徑，并且從這些路徑確定給定MOPPHN的多目標最優路徑的子集。

步驟2：將任何多目標最優路徑算法應用于簡化的SOSPP，以找到從給定源節點到網絡的每個其他節點的第一個多目標最優路徑P（i=1到k）。

步驟3：對于每個路徑P，通過添加構成路徑P的邊的矢量權重來確定網絡的MOPPHN的值MP。

步驟4：求MP=Pmin{MP，MP，…，MP}，其中MP（i=1至k）是第j個最短路徑P的矢量權重。

為了找到第一個k-最短無環路徑，所提算法的步驟2需要O（nklogn+nk）基本運算，其中n是節點數，k是所需的最短路徑數。為了確定k組值的Poreto最小值，步驟4需要O（k）個基本運算。該算法所需的基本運算總數為O（nklogn+nk）+O（k）=O（nklogn+nk）。

由于多目標最優路徑的值是通過對位于路徑上的邊的所有矢量權重求和而獲得的，因此不能應用所有其他平均值，如幾何和調和平均值。考慮路徑（v，v，v），其邊緣（v，v）和（v，v）的矢量權重分別為（a、，a，…，a）和（b，b，…，b）。現在，邊緣（v，v）和（v，v）的矢量權重分量的幾何平均值是（a×a× …×a）和（b×b×…×b），路徑的值是：

（a×a×…×a）+（b×b×…×b）

（1）

路徑的矢量權重是[（a+b），（a+b），…，（a+b）]。

路徑的值等于路徑的矢量權重的分量的幾何平均值

[（a+b），（a+b），…，（a+b）] （2）

考慮以下網絡的MOPPHN來說明上述說法，如圖1所示。

第一個最短路徑（1，2，3，8）的值是11.2;第二個最短路徑（1，4，5，6，7，8>的值是12。但第二個最短路徑的矢量權重是路徑（16，10）支配第一最短路徑（17，10）的矢量權重。因此，使用幾何平均值將MOPPHN減少為SOSPP后確定的最短路徑不是帕累托最小值。

3 實驗與結果分析

解決方案：應用所提出的算法，從步驟2到步驟3，本文得到以下前四個最短無環路徑（k=2）及其矢量權重，從起始節點1到所有其他節點（見表1）。

在算法結束時，本文從起始節點1到所有其他節點獲得以下多目標最優路徑集（見表2）。

圖4為采用普通目標最優路徑算法的最優值變化曲線，圖5為采用遺傳算法得到的目標函數最優路徑最優解及最優路徑均值變化曲線，圖6為采用MOPPHN算法的評價函數最優值的變化曲線。圖6中橫坐標為最優次數，縱坐標為評價函數的全局最優值。

從圖6中可以看出基于公路網多目標最優路徑優化進行路徑規劃的全局最優值在300次最優時已經達到6.79x 10，且單調遞減，收斂速度快且精度高。而采用普通公路網多目標最優路徑優化和遺傳算法仿真得到的結果，從圖4中可看出普通目標最優路徑算法全局最優值在600次最優時僅為4.178x10，甚至包括一段幾手不變的區域，這表明普通公路網多目標最優路徑優化仿真速度慢且容易陷入局部最優。遺傳算法目標函數最優路徑最優解及最優路徑均值變化曲線進化300代得到目標函數最優值為0.013987。仿真結果充分顯示了MOPPHN算法強大的搜索最優參數的能力。

4 結語

在最壞情況復雜度下，生成從指定源節點到網絡MOPPHN中所有其他節點的所有多目標最優路徑的現有算法是指數級的。這里提出的算法是在網絡層次拓撲結構內多目標最優路徑的值的子集。所提出的算法使用算術平均技術將給定的網絡MOPPHN減少為SOSPP，已證明相關定理支持該算法。使用所提出的算法，本文可以解決任何具有正或負或兩者權重的循環和非循環網絡的MOPPHN。本文甚至可以將等級分配給MOPPHN的多目標最優路徑的值。如果網絡的MOPPHN具有負循環，則所有現有算法僅指示負循環的存在，即指數操作之后也是如此。但是，應用本文提出的算法，本文可以找到網絡中任何MOPPHN的一組多目標最優路徑，即使它包含負循環。該算法在實際和理論上都表現良好。