許秋艷，馬 良，劉 勇

(1. 上海理工大學(xué)管理學(xué)院，上海 200093；2. 鹽城工學(xué)院信息工程學(xué)院，江蘇 鹽城224051)

1 引言

最小比率旅行商問(wèn)題(minimum ratio traveling salesman problem，MRTSP)是經(jīng)典旅行商問(wèn)題的一種擴(kuò)展形式：除考慮行程距離外，推銷(xiāo)員從一個(gè)城市到另一個(gè)城市將獲得一定的收益，該問(wèn)題的目標(biāo)就是選擇最佳旅行線路，最小化總路程和總收益的比值。該模型同時(shí)考慮距離和收益，和只考慮距離最小相比，該目標(biāo)函數(shù)等價(jià)于最小化費(fèi)用效益比，更符合實(shí)際情況。

旅行商問(wèn)題屬于NP難問(wèn)題，在其基礎(chǔ)上構(gòu)建的最小比率旅行商問(wèn)題MRTSP也屬于NP難問(wèn)題[1]。目前，用于求解MRTSP的算法主要有模擬退火算法、競(jìng)爭(zhēng)決策算法、大洪水算法、蝙蝠算法、蟻群優(yōu)化算法、引力搜索算法和中心引力優(yōu)化算法等[2，3]。這些方法為求解MRTSP提供了思路，但是計(jì)算效果需要進(jìn)一步優(yōu)化。為有效處理MRTSP問(wèn)題，本文將基于陰陽(yáng)平衡優(yōu)化(Yin-Yang-pair optimization，YYPO)算法[4]設(shè)計(jì)求解方法。

陰陽(yáng)平衡優(yōu)化算法是在2016年由Punnathanam等提出的，其優(yōu)化策略源于中國(guó)傳統(tǒng)文化——陰陽(yáng)學(xué)說(shuō)。在智能計(jì)算領(lǐng)域，算法的局部開(kāi)發(fā)與全局探索能力既對(duì)立又互補(bǔ)，如何實(shí)現(xiàn)兩者的平衡是算法設(shè)計(jì)的關(guān)鍵。YYPO算法將局部開(kāi)發(fā)與全局探索分別視為陰和陽(yáng)兩個(gè)方面，期望通過(guò)陰陽(yáng)平衡實(shí)現(xiàn)局部開(kāi)發(fā)與全局探索的均衡[5]。

因獨(dú)特的優(yōu)化機(jī)制，陰陽(yáng)平衡優(yōu)化算法備受關(guān)注。目前，該算法已經(jīng)成功用于發(fā)動(dòng)機(jī)系統(tǒng)設(shè)計(jì)[6]、光伏逆變器PID調(diào)節(jié)[7]、風(fēng)力渦輪機(jī)設(shè)計(jì)[8]和連續(xù)型選址[9]等?？傮w來(lái)看，陰陽(yáng)平衡優(yōu)化算法的研究處于起步階段，主要用于求解連續(xù)優(yōu)化問(wèn)題，還沒(méi)有涉及到組合優(yōu)化問(wèn)題。本文將陰陽(yáng)平衡優(yōu)化算法用于求解最小比率旅行商問(wèn)題，擴(kuò)大算法的應(yīng)用范圍，也為該問(wèn)題的求解提供可行有效的方法。為此，本文采用佳點(diǎn)集法產(chǎn)生初始群體，提高初始解質(zhì)量；基于超球體和歸檔集對(duì)解不斷進(jìn)行更新；并采用相對(duì)位置索引法直接產(chǎn)生可行解，避免多個(gè)約束條件的處理；基于綜卦變換引入反轉(zhuǎn)操作，提高算法的局部搜索性能。數(shù)值實(shí)驗(yàn)驗(yàn)證了算法求解最小比率旅行商問(wèn)題的可行性和有效性。

2 最小比率旅行商問(wèn)題MRTSP的數(shù)學(xué)模型

最小比率旅行商問(wèn)題的具體模型可描述如下[1-3]

本文考慮的網(wǎng)絡(luò)屬于完全圖G=(V，E) (否則，可通過(guò)計(jì)算任兩個(gè)點(diǎn)間最短路轉(zhuǎn)換成等價(jià)的完全圖)。令V={1，2，…，n} 代表頂點(diǎn)集，表示城市的位置；E={(i，j)：i≠j，i，j∈V}代表邊的集合；D=(dij)n×n代表距離矩陣，表示任兩個(gè)城市間的距離，其中?i，j∈V，dij=dji，dii=+∞，dij>0；P=(pij)n×n代表收入矩陣，表示旅行商(推銷(xiāo)員)完成從一個(gè)城市到另一個(gè)城市的銷(xiāo)售可得到的收入，其中?i，j∈V，pij=pji，pii=0，pij>0。設(shè)那么最小比率旅行商問(wèn)題的模型為

(1)

其中，式(1)表示目標(biāo)函數(shù)，在經(jīng)過(guò)所有點(diǎn)的回路中求總行程與總收入之比最??；式(2)和(3)要求在一次行程中每個(gè)城市只訪問(wèn)一次；式(4)要求沒(méi)有任何子回路生成；|S|代表子圖S中包含的圖G中頂點(diǎn)個(gè)數(shù)；式(5)表示決策變量取值范圍。同時(shí)滿足上述約束條件的解就形成了一條Hamilton 回路。

3 最小比率旅行商問(wèn)題的陰陽(yáng)平衡優(yōu)化算法

受到太極圖的啟示，陰陽(yáng)平衡優(yōu)化算法利用半徑為1的超球體表示其搜索空間。算法首先在超球體內(nèi)隨機(jī)生成兩個(gè)點(diǎn)，并比較這兩個(gè)點(diǎn)的適應(yīng)度值。令P1表示值較優(yōu)的點(diǎn)，而令P2表示值較差的點(diǎn)。然后分別以P1和P2為中心，δ1和δ2為步長(zhǎng)在超球體中進(jìn)行優(yōu)化搜索。在尋優(yōu)過(guò)程中，δ1會(huì)逐步減小而δ2會(huì)逐步變大。因此，點(diǎn)P1的搜索區(qū)域?qū)⒅饾u收縮而進(jìn)行小范圍尋優(yōu)，在算法中被稱為局部開(kāi)發(fā)，有收縮的含義，和陰對(duì)應(yīng)；點(diǎn)P2的搜索區(qū)域?qū)⒅饾u擴(kuò)展而進(jìn)行大范圍尋優(yōu)，在算法中被稱為全局探索，有擴(kuò)張的含義，和陽(yáng)對(duì)應(yīng)。利用P1和P2進(jìn)行的局部開(kāi)發(fā)和全局探索缺一不可，有陰陽(yáng)互根的含義。點(diǎn)P1的搜索范圍越來(lái)越小，而點(diǎn)P2的搜索范圍越來(lái)越大，有陰陽(yáng)對(duì)立的含義。在算法尋優(yōu)中，不斷增強(qiáng)基于點(diǎn)P1的局部搜索和點(diǎn)P2的全局搜索能力，有陰陽(yáng)皆長(zhǎng)的含義。算法期望通過(guò)基于點(diǎn)P1和點(diǎn)P2的兩種搜索以實(shí)現(xiàn)局部開(kāi)發(fā)和全局探索的權(quán)衡，有陰陽(yáng)平衡的含義。以下給出陰陽(yáng)平衡優(yōu)化算法求解最小比率旅行商問(wèn)題的具體實(shí)現(xiàn)過(guò)程。

3.1 基于佳點(diǎn)集的初始化

考慮到最小比率旅行商問(wèn)題NP-難的特征，設(shè)置合理的初始解，可改善算法的搜索效率。此外，雖然智能優(yōu)化算法不依賴于初始解，但是提高初始解質(zhì)量能夠加快優(yōu)化速度。而陰陽(yáng)平衡優(yōu)化算法僅通過(guò)P1和P2兩個(gè)點(diǎn)進(jìn)行優(yōu)化搜索，提高P1和P2對(duì)應(yīng)初始點(diǎn)質(zhì)量，可提高算法優(yōu)化效率。本文不再采用基本陰陽(yáng)平衡優(yōu)化算法對(duì)P1和P2隨機(jī)初始化的方法，而采用一種性能較好的初始化方法——佳點(diǎn)集法。在佳點(diǎn)集中選擇最好的兩個(gè)解賦值給P1和P2。

佳點(diǎn)集的概念由華羅庚等首先提出，具體方法如下[10]：

設(shè)Gn為n維空間的單位立方體，r=(r1，r2，…，rn) 為Gn內(nèi)的點(diǎn)。令Pm(k)是Gn內(nèi)的包含m個(gè)點(diǎn)的集合，如果形為Pm(k)={({r1k}，{r2k}，…，{rsk}，k=1，2，…，m}的偏差φ(m)滿足：φ(m)=C(r，ε)m-1+ε，那么就稱r為佳點(diǎn)，Pm(k)為佳點(diǎn)集。其中，ε代表無(wú)窮?。籆(r，ε)代表僅和r與ε有關(guān)的常量。

在具體應(yīng)用時(shí)，可以設(shè)置rk={2cos 2πk/q}，1≤k≤n，q為符合(q-3)/2≥n的最小素?cái)?shù)，那么r即為佳點(diǎn)。此外，也可以設(shè)置rk={ek}，1≤k≤n那么r也是佳點(diǎn)。其中，{t}代表t的小數(shù)部分。研究表明，相對(duì)隨機(jī)點(diǎn)集而言，佳點(diǎn)集分布更加均勻[2，11]。

3.2 基于超球體的解更新

算法分別采用P1和P2作中心點(diǎn)，δ1和δ2作步長(zhǎng)，并在超球體中進(jìn)行優(yōu)化搜索。因?yàn)镻1和P2兩點(diǎn)采用相同的更新方法，為方便起見(jiàn)，用P表示P1或P2，并用δ表示δ1或δ2。首先將P進(jìn)行復(fù)制，生成2D(D表示變量維數(shù))個(gè)同樣的點(diǎn)，并分別用NP1，NP2，…，NP2D進(jìn)行表示；然后對(duì)這些點(diǎn)進(jìn)行更新。在算法中，可以對(duì)點(diǎn)的一個(gè)分量或者所有分量進(jìn)行更新。對(duì)點(diǎn)的一個(gè)分量進(jìn)行更新時(shí)，具體方法如下：

(6)

(7)

在對(duì)點(diǎn)的所有分量進(jìn)行更新時(shí)，具體方法如下：

(8)

(9)

在算法中，通過(guò)等概率來(lái)選擇上述兩種方法的一種進(jìn)行點(diǎn)的更新。此外，在利用點(diǎn)P1生成的2D個(gè)新解中，挑選適應(yīng)度值最優(yōu)的點(diǎn)，直接替換P1。對(duì)P2生成的新解也進(jìn)行同樣的操作。

3.3 基于歸檔集的解更新

在計(jì)算過(guò)程中，算法采取精英保留策略，在進(jìn)行基于超球體的解更新前，會(huì)將P1與P2兩個(gè)點(diǎn)存儲(chǔ)到歸檔集內(nèi)。每隔I代將利用歸檔集中的2I個(gè)點(diǎn)對(duì)當(dāng)前的P1與P2兩點(diǎn)做更新操作。其中，I表示歸檔集的更新頻率，并且I是在Imin和Imax之間隨機(jī)產(chǎn)生的整數(shù)。

該階段的解更新方法如下：第一步，從歸檔集內(nèi)挑選適應(yīng)度值最優(yōu)的點(diǎn)并和P1進(jìn)行比較，如果該點(diǎn)優(yōu)于P1，則這兩個(gè)點(diǎn)進(jìn)行交換；第二步，再次從歸檔集內(nèi)中挑選適應(yīng)度值最優(yōu)的點(diǎn)并和P2進(jìn)行比較，如果該點(diǎn)優(yōu)于P2，則這兩個(gè)點(diǎn)也進(jìn)行交換；第三步，清空歸檔集，并生成的新的歸檔集更新頻率參數(shù)I。

此外，算法在該階段還對(duì)兩個(gè)搜索步長(zhǎng)δ1和δ2進(jìn)行更新，具體方法如下：

δ1=δ1-(δ1/α)

(10)

δ2=δ2+(δ2/α)

(11)

其中，α表示收縮/擴(kuò)張因子；δ1和δ2分別表示是點(diǎn)P1和P2的搜索步長(zhǎng)。

3.4 候選解的生成

為充分發(fā)揮陰陽(yáng)平衡優(yōu)化算法求解連續(xù)優(yōu)化問(wèn)題的優(yōu)勢(shì)，仍然采用連續(xù)空間表示算法的搜索空間。但最小比率旅行商問(wèn)題屬于組合優(yōu)化問(wèn)題，可行解表示城市的訪問(wèn)順序。如何實(shí)現(xiàn)算法搜索個(gè)體的位置到問(wèn)題解的轉(zhuǎn)換是必須要解決的問(wèn)題?？紤]到最小比率旅行商問(wèn)題的解是離散的特征，本文采用基于相對(duì)位置索引法的解生成方法[12]。

在相對(duì)位置索引法中，首先將最小實(shí)數(shù)轉(zhuǎn)換為最小整數(shù)1，然后將第二小的實(shí)數(shù)轉(zhuǎn)換為下一個(gè)高位整數(shù)2，以此類(lèi)推，可以對(duì)所有實(shí)數(shù)進(jìn)行編號(hào)。最后利用編號(hào)構(gòu)成城市的訪問(wèn)順序。該方法和隨機(jī)鍵編碼方法類(lèi)似，以下通過(guò)一個(gè)算例作進(jìn)一步說(shuō)明。例如，一個(gè)有四個(gè)城市的最小比率旅行商問(wèn)題，陰陽(yáng)平衡優(yōu)化算法的一個(gè)搜索個(gè)體位置為(0.52，0.68，0.15，0.97)，按照上述方法，得到的城市的訪問(wèn)順序?yàn)?2，3，1，4)。

此外，如果在轉(zhuǎn)換前向量中有多個(gè)相同的分量，這種方法可能會(huì)產(chǎn)生不可行解。本文設(shè)計(jì)一種修復(fù)機(jī)制，即根據(jù)向量位置的先后順序進(jìn)行編碼。以下以相對(duì)位置索引法舉例說(shuō)明，轉(zhuǎn)換前的向量(0.02，0.58，0.78，0.98，0.78)，第三個(gè)分量和第五個(gè)分量取值相同，根據(jù)上述修復(fù)機(jī)制，其編號(hào)分別為3和4，轉(zhuǎn)換后的向量為(1，2，3，5，4)。

因此，采用上述候選解的生成方法，可以直接產(chǎn)生可行解，每個(gè)城市只被訪問(wèn)一次，并且在任何一個(gè)子集中不會(huì)構(gòu)成完整的Hamilton 回路。在算法搜索過(guò)程中，可以直接計(jì)算目標(biāo)函數(shù)值，不再考慮模型中四個(gè)約束條件。

3.5 基于綜卦變換的局部搜索

基本陰陽(yáng)平衡優(yōu)化算法的全局搜索能力較強(qiáng)，而局部搜索能力較弱[13，14]。為求解最小比率旅行商問(wèn)題，需要提高算法的局部尋優(yōu)能力。和陰陽(yáng)學(xué)說(shuō)一樣，《易經(jīng)》也屬于中國(guó)傳統(tǒng)文化。從算法設(shè)計(jì)角度來(lái)看，卦的變化蘊(yùn)含了優(yōu)化思想。例如，綜卦是把本卦倒過(guò)來(lái)看，例如圖1所示，姤卦的綜卦是夬卦。綜卦的哲理是從另一個(gè)角度來(lái)看同一問(wèn)題[15，16]。

圖1 綜卦變化示意圖

受此啟發(fā)，將當(dāng)前解視為本卦，對(duì)其進(jìn)行綜卦變化，具體將采用反轉(zhuǎn)操作。在反轉(zhuǎn)操作中，旋轉(zhuǎn)變化的城市位置不再是起點(diǎn)和終點(diǎn)，而是隨機(jī)選擇兩個(gè)城市位置作為起點(diǎn)和終點(diǎn)，然后將隨機(jī)選出的兩個(gè)城市之間的訪問(wèn)順序顛倒過(guò)來(lái)。圖2給出一個(gè)示例，其中T表示反轉(zhuǎn)操作前的解，T′ 表示反轉(zhuǎn)操作后的解。

圖2 反轉(zhuǎn)操作示意圖

3.6 算法主要計(jì)算步驟

綜上所述，求解最小比率旅行商問(wèn)題的陰陽(yáng)平衡優(yōu)化算法具體步驟如下：

步驟1：根據(jù)佳點(diǎn)集法產(chǎn)生初始點(diǎn)，并選擇最好的兩個(gè)點(diǎn)分別賦值給P1和P2

步驟2：在基于超球體的解更新階段，按等概率原則分別利用P1與P2進(jìn)行優(yōu)化搜索；

步驟3：每間隔I次迭代，則進(jìn)入基于歸檔集的解更新階段，否則，轉(zhuǎn)步驟4；

步驟4：若迭代次數(shù)達(dá)到預(yù)設(shè)最大值，轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟5。

步驟5：若點(diǎn)P2適應(yīng)度值優(yōu)于點(diǎn)P1適應(yīng)度值，則交換這兩個(gè)點(diǎn)的取值與搜索步長(zhǎng)，轉(zhuǎn)步驟2；

步驟6：對(duì)當(dāng)前最好解進(jìn)行基于綜卦的反轉(zhuǎn)操作，算法停止，輸出最好結(jié)果。

4 數(shù)值實(shí)驗(yàn)

實(shí)驗(yàn)共分為三個(gè)部分：首先采用并行程序設(shè)計(jì)陰陽(yáng)平衡優(yōu)化算法；然后比較陰陽(yáng)平衡優(yōu)化算法和微粒群優(yōu)化算法、引力搜索算法、生物地理學(xué)優(yōu)化算法以及最有價(jià)值球員算法的求解性能；最后對(duì)距離矩陣和收益矩陣的元素進(jìn)行參數(shù)靈敏度分析。在本文中，采用最小比率旅行商問(wèn)題的3個(gè)典型問(wèn)題進(jìn)行仿真。這些算例定義如下[1-3]：

算例1： 設(shè)給定對(duì)稱賦權(quán)完全圖G={V，E}，距離矩陣D和收益矩陣P定義如下

算例2： 設(shè)給定對(duì)稱賦權(quán)完全圖G={V，E}，距離矩陣D和收益矩陣P定義如下

算例3： 設(shè)給定對(duì)稱賦權(quán)完全圖G={V，E}，距離矩陣D和收益矩陣P定義如下：

4.1 算法并行程序設(shè)計(jì)

迄今為止，在智能優(yōu)化算法領(lǐng)域，使用并行程序設(shè)計(jì)算法是一個(gè)重要方向，現(xiàn)有工作主要是將計(jì)算任務(wù)分配給多臺(tái)計(jì)算機(jī)完成，而在一臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并行智能優(yōu)化算法的研究工作極其罕見(jiàn)。當(dāng)前計(jì)算機(jī)至少配置了雙核或者四核的CPU，在體系結(jié)構(gòu)上具有實(shí)現(xiàn)并行計(jì)算的硬件條件。此外，還有許多支持并行計(jì)算的軟件環(huán)境，例如，Windows多線程編程、MPI并行編程和Matlab并行計(jì)算工具箱等[17]。

為充分利用計(jì)算資源，設(shè)計(jì)者需要認(rèn)識(shí)到底層多核的存在，采用并行程序設(shè)計(jì)智能優(yōu)化算法，提高算法性能。在陰陽(yáng)平衡優(yōu)化算法中，所有個(gè)體基于超球體的解更新操作具有相互獨(dú)立性，具有天然的并行特征。此外，和其它智能優(yōu)化算法一樣，陰陽(yáng)平衡優(yōu)化算法采用群體搜索策略，具有隱含并行性，例如各個(gè)體適應(yīng)度函數(shù)值的評(píng)價(jià)可以并行化等。在本文中，采用Matlab的并行計(jì)算工具箱(Parallel Computing Toolbox)對(duì)陰陽(yáng)平衡優(yōu)化算法進(jìn)行并行程序設(shè)計(jì)。

以算例1為例進(jìn)行實(shí)驗(yàn)，對(duì)比算法并行和串行的計(jì)算時(shí)間。在Windows10操作系統(tǒng)下，CPU：Intel(R) Xeon(R) E-2186M、32G內(nèi)存、2.90GHz主頻的計(jì)算機(jī)上運(yùn)行，調(diào)用六核進(jìn)行并行計(jì)算。算法參數(shù)設(shè)置為：Imin=5，Imax=10，α=25，a=2。此外，δ1與δ2初始值都設(shè)為0.5；為防止步長(zhǎng)δ2無(wú)限制的增大，超出算法的搜索區(qū)域，將其最大值設(shè)為0.75；最大迭代次數(shù)T=500。

和大多數(shù)智能優(yōu)化方法一樣，陰陽(yáng)平衡優(yōu)化算法屬于隨機(jī)方法，需要多次運(yùn)行同一算法，統(tǒng)計(jì)其優(yōu)化性能。在實(shí)驗(yàn)中，循環(huán)次數(shù)分別為1，100，200，300，400，500，比較并行和串行計(jì)算的耗時(shí)，結(jié)果如圖3所示。

圖3 算法并行和串行計(jì)算時(shí)間對(duì)比

此外，還計(jì)算了這5次的加速比(串行算法的執(zhí)行時(shí)間除以并行算法的執(zhí)行時(shí)間)，最大加速比為4.5231。采用并行程序設(shè)計(jì)算法，能夠充分利用空閑的CPU內(nèi)核，能夠減少運(yùn)行時(shí)間。因此，本文所有算法均采用并行程序設(shè)計(jì)，以提高算法運(yùn)行速度。

4.2 算法優(yōu)化性能測(cè)試

為測(cè)試陰陽(yáng)平衡優(yōu)化算法YYPO性能，采用微粒群優(yōu)化算法(particle swarm optimization，PSO)[18]、引力搜索算法(gravitational search algorithm，GSA)[19]、生物地理學(xué)優(yōu)化算法(biogeography-based optimization，BBO)[20]和最有價(jià)值球員算法(most valuable player algorithm，MVPA)[21]進(jìn)行比較。

為保證實(shí)驗(yàn)公平性，這5種算法設(shè)置相同的函數(shù)評(píng)價(jià)次數(shù)，即2000n，其中n為問(wèn)題規(guī)模。YYPO算法其它參數(shù)設(shè)置保持不變，其它算法根據(jù)文獻(xiàn)[18-21]進(jìn)行參數(shù)設(shè)置。為避免算法單次運(yùn)行結(jié)果的偶然性對(duì)分析優(yōu)化性能的影響，每種算法各自獨(dú)立運(yùn)行30次，分別統(tǒng)計(jì)最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差等指標(biāo)。此外，統(tǒng)計(jì)結(jié)果還考慮每個(gè)算法在30次實(shí)驗(yàn)中達(dá)到已知最優(yōu)解的成功次數(shù)，并進(jìn)行排序。具體計(jì)算結(jié)果如表1所示。

表1 不同算法計(jì)算結(jié)果比較

圖4 算法優(yōu)化過(guò)程對(duì)比

通過(guò)分析表1中的結(jié)果不難發(fā)現(xiàn)：對(duì)于最小規(guī)模的算例1，在相同的函數(shù)評(píng)價(jià)次數(shù)下，這5種算法都能收斂到已知最優(yōu)解。但是對(duì)更大規(guī)模的算例2和3，雖然微粒群優(yōu)化算法PSO、引力搜索算法GSA、生物地理學(xué)優(yōu)化算法BBO和最有價(jià)值球員算法MVPA都可以找到已知最優(yōu)值，但是在最差值、平均值、標(biāo)準(zhǔn)差、成功次數(shù)和排序這五個(gè)指標(biāo)上，這些算法都明顯劣于陰陽(yáng)平衡優(yōu)化算法YYPO。此外，陰陽(yáng)平衡優(yōu)化算法YYPO所獲得的標(biāo)準(zhǔn)差明顯優(yōu)于其它4種算法，說(shuō)明本文算法的優(yōu)化性能更加穩(wěn)定。上述結(jié)果說(shuō)明陰陽(yáng)平衡優(yōu)化算法YYPO在計(jì)算精度方面明顯優(yōu)于其它4種優(yōu)化算法。

為進(jìn)一步分析算法優(yōu)化性能，圖4給出了這5種算法優(yōu)化速度對(duì)比示意圖。從圖中可以發(fā)現(xiàn)，陰陽(yáng)平衡優(yōu)化算法YYPO不僅具有更高的計(jì)算精度，而且具有更快的收斂速度。該算法為最小比率旅行商問(wèn)題的求解提供一個(gè)可行有效的算法。

4.3 靈敏度分析

在最小比率旅行商問(wèn)題中，兩個(gè)城市間的距離和旅行商的收入直接影響總行程和總收益之比。這里，分析距離矩陣D和收益矩陣P發(fā)生變化時(shí)對(duì)結(jié)果的影響。為方便起見(jiàn)，考慮距離矩陣和收益矩陣中元素同時(shí)增加或同時(shí)減少的情況。當(dāng)這兩個(gè)矩陣元素取值反向變化時(shí)，總行程和總收益之比容易判斷變化趨勢(shì)。例如，當(dāng)距離矩陣元素取值都變大而收益矩陣元素取值都變小時(shí)，總行程和總收益之比變大。

這里，以算例1為例，分析這兩個(gè)矩陣元素取值同向變化時(shí)，總行程和總收益之比變化情況。原總行程為199，總收益為234，總行程和總收益之比為0.8504。

當(dāng)距離矩陣元素值都增加5，收益矩陣元素都增加1時(shí)，總行程變?yōu)?24，總收益為239，兩者比值為0.9372。此時(shí)，目標(biāo)函數(shù)值變差。當(dāng)距離矩陣元素值都增加10，收益矩陣元素都增加20時(shí)，總行程變?yōu)?49，總收益為334，兩者比值為0.7455。此時(shí)，目標(biāo)函數(shù)值變好。

當(dāng)距離矩陣元素值都減少6，收益矩陣元素都減少2時(shí)，總行程變?yōu)?69，總收益為219，兩者比值為0.7717。此時(shí)，目標(biāo)函數(shù)值變好。當(dāng)距離矩陣元素值都減少8，收益矩陣元素都減少16時(shí)，總行程變?yōu)?59，總收益為154，兩者比值為1.0325。此時(shí)，目標(biāo)函數(shù)值變差。

距離矩陣元素值都增加相當(dāng)于旅行商通勤距離變大，服務(wù)對(duì)象擴(kuò)展到郊區(qū)。此時(shí)，旅行商的收益也會(huì)增加，但不表示費(fèi)用效益比也會(huì)增加，即總行程和總收益之比可能變大也可能變小。與此類(lèi)似，距離矩陣元素值都減小相當(dāng)于交通條件的改善，通勤距離變短。此時(shí)，旅行商的收益會(huì)減少，但不表示費(fèi)用效益比也會(huì)減少，即總行程和總收益之比可能變小也可能變大。

最小比率旅行商問(wèn)題的目標(biāo)是考慮總行程和總收益之比，類(lèi)似于經(jīng)濟(jì)學(xué)中費(fèi)用效益比，與僅關(guān)注總距離相比，既考慮總行程，又考慮旅行商的收益，更具有現(xiàn)實(shí)意義。在滿足約束的情況下，如何兼顧成本和旅行商收益需要根據(jù)具體問(wèn)題進(jìn)行定量計(jì)算，以實(shí)現(xiàn)最佳的調(diào)度方案。

5 結(jié)論

為有效求解最小比率旅行商問(wèn)題，構(gòu)建了陰陽(yáng)平衡優(yōu)化算法。首先，引入佳點(diǎn)集法來(lái)初始化搜索群體，改善算法初始解的性能；其次，采用基于超球體和歸檔集的兩種策略對(duì)不同階段的解進(jìn)行更新，并根據(jù)相對(duì)位置索引法進(jìn)行解的編碼來(lái)產(chǎn)生可行解，以滿足模型中所有的約束條件；最后，根據(jù)綜卦變換采用反轉(zhuǎn)操作，避免算法早熟收斂。此外，算法采用并行程序設(shè)計(jì)，以充分利用多核處理器計(jì)算資源。與其它四種算法相比，在計(jì)算精度和優(yōu)化速度兩方面，所設(shè)計(jì)的算法均排名第一。通過(guò)距離矩陣和收益矩陣的靈敏度分析發(fā)現(xiàn)，配送距離和收益同時(shí)增加或者減小時(shí)，需要根據(jù)具體問(wèn)題進(jìn)行定量計(jì)算，才可以確定最小比率(費(fèi)用效益比)的變化情況。將算法用于車(chē)輛路徑問(wèn)題是進(jìn)一步的研究工作。