基于網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)的公路網(wǎng)多目標(biāo)最優(yōu)路徑算法

龍威棟

摘要：公路網(wǎng)多目標(biāo)最優(yōu)路徑問(wèn)題（Multi-objective Optimal Path Problem of Highway Net-work，MOPPHN）是一個(gè)活躍的研究領(lǐng)域，因?yàn)樗鼞?yīng)用于大量系統(tǒng)。在路網(wǎng)系統(tǒng)中，有必要找到從一個(gè)節(jié)點(diǎn)到指定節(jié)點(diǎn)或所有其他節(jié)點(diǎn)的最佳路徑。在最壞的情況下，用于計(jì)算從指定源節(jié)點(diǎn)到MOPPHN中所有其他節(jié)點(diǎn)的所有多目標(biāo)最優(yōu)路徑的計(jì)算復(fù)雜度是指數(shù)級(jí)的。文章提出了一種算法，用于在網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)內(nèi)找到一組多目標(biāo)最優(yōu)路徑的值，而不是在指數(shù)時(shí)間內(nèi)生成多目標(biāo)最優(yōu)路徑的所有值，這在許多情況下都是非常重要的。應(yīng)用文章提出的算法，可以找到網(wǎng)絡(luò)中任何MOPPHN的一組多目標(biāo)最優(yōu)路徑，即使它包含負(fù)循環(huán)。通過(guò)實(shí)驗(yàn)分析，驗(yàn)證了該算法在實(shí)際和理論上都表現(xiàn)良好。

關(guān)鍵詞：網(wǎng)絡(luò);多重目標(biāo);多目標(biāo)最優(yōu)路徑

中圖分類號(hào)：U491 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.13282/j.cnki.wccst.2019.10.048

文章編號(hào)：1673-4874（2019）10-0174-05

0引言

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

因此，用于生成從源節(jié)點(diǎn)到MOPPHN中的所有其他節(jié)點(diǎn)的多目標(biāo)最優(yōu)路徑的所有值的現(xiàn)有算法都是指數(shù)時(shí)間算法。這促使本文研究網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)以多目標(biāo)最優(yōu)路徑的值集的子集來(lái)改善時(shí)間復(fù)雜度。本文提出了一種顧及網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)的公路網(wǎng)多目標(biāo)最優(yōu)路徑算法，該算法通過(guò)確定相應(yīng)SOSPP的第一個(gè)多目標(biāo)最優(yōu)路徑，生成網(wǎng)絡(luò)中MOPPHN的多目標(biāo)最優(yōu)路徑的所有值集合的子集。首先使用算術(shù)平均技術(shù)確定對(duì)應(yīng)于網(wǎng)絡(luò)的給定MOPPHN的SOSPP。如果網(wǎng)絡(luò)的MOPPHN具有負(fù)循環(huán)，則所有現(xiàn)有算法僅指示負(fù)循環(huán)的存在，即指數(shù)操作之后也是如此。但是，應(yīng)用本文提出的算法，可以找到網(wǎng)絡(luò)中任何MOPPHN的一組多目標(biāo)最優(yōu)路徑，即使它包含負(fù)循環(huán)。

1基本知識(shí)

1.1 符號(hào)

1.2 相關(guān)知識(shí)

1.2.1 網(wǎng)絡(luò)

1.2.2 路徑和無(wú)環(huán)路徑

V的節(jié)點(diǎn)i和j之間的路徑是連接節(jié)點(diǎn)i和j的連續(xù)邊緣序列，本文還可以通過(guò)其節(jié)點(diǎn)的序列（v，…，v）來(lái)表示路徑。如果路徑的節(jié)點(diǎn)序列是有限的，那么該路徑被認(rèn)為是有限的。如果網(wǎng)絡(luò)的所有節(jié)點(diǎn)都是不同的，則稱其為無(wú)環(huán)路徑。

1.2.3 路徑的值

1.2.4 多目標(biāo)最優(yōu)路徑問(wèn)題

2 多目標(biāo)最優(yōu)路徑算法

本文提出的算法需要計(jì)算多目標(biāo)最優(yōu)路徑。基本標(biāo)簽校正算法用于找到多目標(biāo)最優(yōu)路徑?；緲?biāo)簽校正算法僅生成不包含負(fù)循環(huán)的網(wǎng)絡(luò)的多目標(biāo)最優(yōu)路徑的值。生成的值對(duì)應(yīng)的多目標(biāo)最優(yōu)路徑可以包含循環(huán)。本文已經(jīng)包含了一個(gè)額外的步驟，它跟蹤無(wú)環(huán)路徑并生成非減少k最短無(wú)環(huán)路徑和路徑本身的值。由于算法生成無(wú)環(huán)路徑，因此它可以應(yīng)用于任何網(wǎng)絡(luò)，即使它包含負(fù)循環(huán)。為了確定無(wú)環(huán)路徑，該算法需要額外的O（nk）基本操作。因此，確定k-最短無(wú)環(huán)路徑的最壞情況計(jì)算復(fù)雜度是。（nkIogn+nk），該算法將給定的網(wǎng)絡(luò)MOPPHN轉(zhuǎn)換為SOSPP。通過(guò)用相應(yīng)邊緣的矢量權(quán)重的分量的算術(shù)平均值替換網(wǎng)絡(luò)的每個(gè)邊緣的矢量權(quán)重來(lái)完成變換。它確定SOSPP的第一個(gè)多目標(biāo)最優(yōu)路徑，并且從這些路徑確定給定MOPPHN的多目標(biāo)最優(yōu)路徑的子集。

步驟2：將任何多目標(biāo)最優(yōu)路徑算法應(yīng)用于簡(jiǎn)化的SOSPP，以找到從給定源節(jié)點(diǎn)到網(wǎng)絡(luò)的每個(gè)其他節(jié)點(diǎn)的第一個(gè)多目標(biāo)最優(yōu)路徑P（i=1到k）。

步驟3：對(duì)于每個(gè)路徑P，通過(guò)添加構(gòu)成路徑P的邊的矢量權(quán)重來(lái)確定網(wǎng)絡(luò)的MOPPHN的值MP。

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

為了找到第一個(gè)k-最短無(wú)環(huán)路徑，所提算法的步驟2需要O（nklogn+nk）基本運(yùn)算，其中n是節(jié)點(diǎn)數(shù)，k是所需的最短路徑數(shù)。為了確定k組值的Poreto最小值，步驟4需要O（k）個(gè)基本運(yùn)算。該算法所需的基本運(yùn)算總數(shù)為O（nklogn+nk）+O（k）=O（nklogn+nk）。

由于多目標(biāo)最優(yōu)路徑的值是通過(guò)對(duì)位于路徑上的邊的所有矢量權(quán)重求和而獲得的，因此不能應(yīng)用所有其他平均值，如幾何和調(diào)和平均值。考慮路徑（v，v，v），其邊緣（v，v）和（v，v）的矢量權(quán)重分別為（a、，a，…，a）和（b，b，…，b）?，F(xiàn)在，邊緣（v，v）和（v，v）的矢量權(quán)重分量的幾何平均值是（a×a× …×a）和（b×b×…×b），路徑的值是：

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

（1）

路徑的矢量權(quán)重是[（a+b），（a+b），…，（a+b）]。

路徑的值等于路徑的矢量權(quán)重的分量的幾何平均值

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

考慮以下網(wǎng)絡(luò)的MOPPHN來(lái)說(shuō)明上述說(shuō)法，如圖1所示。

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

3 實(shí)驗(yàn)與結(jié)果分析

解決方案：應(yīng)用所提出的算法，從步驟2到步驟3，本文得到以下前四個(gè)最短無(wú)環(huán)路徑（k=2）及其矢量權(quán)重，從起始節(jié)點(diǎn)1到所有其他節(jié)點(diǎn)（見表1）。

在算法結(jié)束時(shí)，本文從起始節(jié)點(diǎn)1到所有其他節(jié)點(diǎn)獲得以下多目標(biāo)最優(yōu)路徑集（見表2）。

圖4為采用普通目標(biāo)最優(yōu)路徑算法的最優(yōu)值變化曲線，圖5為采用遺傳算法得到的目標(biāo)函數(shù)最優(yōu)路徑最優(yōu)解及最優(yōu)路徑均值變化曲線，圖6為采用MOPPHN算法的評(píng)價(jià)函數(shù)最優(yōu)值的變化曲線。圖6中橫坐標(biāo)為最優(yōu)次數(shù)，縱坐標(biāo)為評(píng)價(jià)函數(shù)的全局最優(yōu)值。

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

4 結(jié)語(yǔ)

在最壞情況復(fù)雜度下，生成從指定源節(jié)點(diǎn)到網(wǎng)絡(luò)MOPPHN中所有其他節(jié)點(diǎn)的所有多目標(biāo)最優(yōu)路徑的現(xiàn)有算法是指數(shù)級(jí)的。這里提出的算法是在網(wǎng)絡(luò)層次拓?fù)浣Y(jié)構(gòu)內(nèi)多目標(biāo)最優(yōu)路徑的值的子集。所提出的算法使用算術(shù)平均技術(shù)將給定的網(wǎng)絡(luò)MOPPHN減少為SOSPP，已證明相關(guān)定理支持該算法。使用所提出的算法，本文可以解決任何具有正或負(fù)或兩者權(quán)重的循環(huán)和非循環(huán)網(wǎng)絡(luò)的MOPPHN。本文甚至可以將等級(jí)分配給MOPPHN的多目標(biāo)最優(yōu)路徑的值。如果網(wǎng)絡(luò)的MOPPHN具有負(fù)循環(huán)，則所有現(xiàn)有算法僅指示負(fù)循環(huán)的存在，即指數(shù)操作之后也是如此。但是，應(yīng)用本文提出的算法，本文可以找到網(wǎng)絡(luò)中任何MOPPHN的一組多目標(biāo)最優(yōu)路徑，即使它包含負(fù)循環(huán)。該算法在實(shí)際和理論上都表現(xiàn)良好。