馬 龍，王春嬉，張正義，董 睿

西安航空學(xué)院 經(jīng)濟(jì)管理學(xué)院，西安710077

車輛路徑規(guī)劃問題是在時(shí)間窗約束下實(shí)現(xiàn)運(yùn)輸路徑和作業(yè)成本控制的組合優(yōu)化問題，該問題是由學(xué)者Dantzig與Ramser于1959年提出，并在物流運(yùn)籌學(xué)領(lǐng)域獲得廣泛深入的研究。目前對于車輛路徑規(guī)劃主要以最小運(yùn)輸總成本、最短運(yùn)輸距離和最少配送車輛數(shù)目為獨(dú)立研究目標(biāo)，或以這三個(gè)獨(dú)立研究目標(biāo)進(jìn)行兩兩組合，作為優(yōu)化計(jì)算的目標(biāo)，這樣會(huì)使解算目標(biāo)與實(shí)際問題脫節(jié)，且問題的求解結(jié)果差異較大，特別是針對規(guī)模較大的求解問題，傳統(tǒng)的運(yùn)籌學(xué)方法在求解車輛路徑規(guī)劃問題最優(yōu)解時(shí)耗時(shí)費(fèi)力[1-2]，因此，國內(nèi)外學(xué)者開始使用基本的人工智能算法或兩種基本算法的混合方法，包括下等雙向搜索算法[3]、禁忌搜索算法[4-5]、量子煙花進(jìn)化算法[6]、蟻群算法[7-15]、遺傳算法[16-21]、蝙蝠算法[22-23]、狼群算法[24]、混合進(jìn)化算法[25-27]等。但這些基本算法或混合算法主要以改進(jìn)基本算法的參數(shù)或兩種算法的混合形式，對帶時(shí)間窗的車輛路徑問題進(jìn)行求解。然而，改進(jìn)后的算法依然存在早熟或無法完全收斂到全局最優(yōu)解的問題。因此，探索使用互補(bǔ)性較強(qiáng)的兩種智能優(yōu)化算法，對兩種算法的性能進(jìn)行互補(bǔ)改進(jìn)，形成一種新型改進(jìn)算法是求解帶時(shí)間窗車輛路徑問題的熱點(diǎn)研究方向。

智能水滴算法（Intelligent Water Drops，IWD）是學(xué)者Hosseini在2007年提出的一種智能算法，該算法通過水滴算子和攜帶泥土量算子來模擬自然界的水系統(tǒng)與河道影響環(huán)境而形成的河水迭代流動(dòng)計(jì)算過程。該算法起初在旅行商（Traveling Salesman Problem，TSP）問題[28]、多維背包問題[29]等方面得到應(yīng)用，隨后，Kamkar等學(xué)者率先將該算法應(yīng)用于車輛路徑問題[30]，且部分學(xué)者對該算法進(jìn)一步改進(jìn)應(yīng)用[31-34]，然而，面對多目標(biāo)多時(shí)間窗車輛路徑問題，智能水滴算法及其改進(jìn)算法依然存在計(jì)算速度慢、全局收斂性能差等問題，因此，能否利用一種具備精準(zhǔn)搜索方向的智能優(yōu)化算法對智能水滴算法進(jìn)行徹底改善，形成一種具有優(yōu)勢互補(bǔ)的新型智能優(yōu)化算法解決車輛路徑問題還鮮有研究。

鴿群算法（Pigeon Inspired Optimization，PIO）是受到鴿子的歸巢行為啟發(fā)，由學(xué)者段海濱等于2014 年提出的新型精準(zhǔn)搜索算法，該算法是由兩個(gè)精準(zhǔn)搜索算子（地圖羅盤算子和地標(biāo)算子）分階段獨(dú)立運(yùn)行，彌補(bǔ)具有單一算子或復(fù)合算子的智能算法搜索不足問題，該算法具有明確的搜索方向和快速的搜索速度、計(jì)算精度，且在理論探索和實(shí)際應(yīng)用方面的成果較多。如背包問題[35]、無人機(jī)路徑規(guī)劃[36]、基本智能算法改進(jìn)與函數(shù)優(yōu)化求解[37]等。但將基本鴿群算法或單獨(dú)利用鴿群算子完全改進(jìn)智能水滴算法，解決帶有多目標(biāo)多時(shí)間窗的車輛路徑問題的成果還未見報(bào)道。

綜上可知，雖然現(xiàn)有的人工智能算法在改進(jìn)和車輛路徑問題應(yīng)用方面出現(xiàn)大量的成果，但能使算法在求解多時(shí)間窗車輛路徑問題時(shí)，能夠滿足收斂速度、計(jì)算精度、均衡開發(fā)和探索能力的還不夠完善。因此，綜合考慮具有硬時(shí)間窗約束的車輛路徑規(guī)劃問題的特點(diǎn)，構(gòu)建多目標(biāo)多時(shí)間窗車輛路徑規(guī)劃問題（Vehicle Routing Problem of Multiple-Objectives and Multiple Time Windows，VRPMOMTW）模型，并針對基本智能水滴算法的不足之處，提出求解VRPMOMTW 問題的鴿群-智能水滴互補(bǔ)改進(jìn)算法（Complementary Pigeon-Inspired optimization and Intelligent Water Drops，CPIIWD），并利用benchmark 函數(shù)對CPIIWD 算法進(jìn)行測試，且將仿真結(jié)果與人工免疫系統(tǒng)算法（Artificial Immune System，AIS）、粒子群算法（Particle Swarm Optimization，PSO）、遺傳算法（Genetic Algorithm，GA）的結(jié)果進(jìn)行比較，表明CPIIWD 算法收斂性能要比其他三種算法的性能更好，也是求解VRPMOMTW問題的最佳方法。同時(shí)，將VRPMOMTW模型求解結(jié)果與遺傳算法[38]、智能水滴算法[33]等結(jié)果進(jìn)行比較，有效彌補(bǔ)了智能水滴算法在多時(shí)間窗車輛路徑問題的應(yīng)用不足，從而強(qiáng)化了人工智能優(yōu)化算法在車輛路徑規(guī)劃方面的應(yīng)用效果。

1 多目標(biāo)多時(shí)間窗車輛路徑規(guī)劃模型

1.1 問題描述

多目標(biāo)多時(shí)間窗路徑規(guī)劃問題是通過給一個(gè)物流配送中心分配若干輛配送車，為多個(gè)服務(wù)點(diǎn)提供配送服務(wù)，根據(jù)不同服務(wù)點(diǎn)上的供貨需求量、車輛的最大載重量、服務(wù)點(diǎn)與配送中心之間的路徑長度等制約因素，所有服務(wù)點(diǎn)上均有相互獨(dú)立的服務(wù)時(shí)間窗。配送車輛為多個(gè)服務(wù)點(diǎn)提供貨物供應(yīng)服務(wù)，從配送中心出發(fā)再回到配送中心形成完整的閉合回路。假設(shè)一個(gè)服務(wù)點(diǎn)由一輛車在規(guī)定的時(shí)間窗內(nèi)完成配送服務(wù)，且為服務(wù)點(diǎn)提供裝卸貨服務(wù)的時(shí)間窗固定，使用每一輛配送車輛的成本和單位行駛距離成本均固定，單輛車的行駛總距離和行駛時(shí)間要求小于給定路線的最長距離和行駛時(shí)間。如何使配送總費(fèi)用最少、配送路徑最短和配送車輛數(shù)最少，從而使得車輛配送總成本達(dá)到整體最小。為了建模需要，作出如下假設(shè)：

（1）車輛由配送中心出發(fā)后返回到配送中心。

（2）采用相同型號的配送車輛，且車輛與服務(wù)點(diǎn)之間具有一對一和一對多的關(guān)系，其服務(wù)點(diǎn)需求量小于車輛最大載重量，服務(wù)時(shí)間恒定。

（3）運(yùn)輸?shù)缆窢顩r和車流量忽略不計(jì)。

（4）配送中心分配的車輛數(shù)小于車輛總數(shù)，不得重復(fù)調(diào)度。

（5）車輛到達(dá)服務(wù)點(diǎn)的時(shí)間應(yīng)在允許的時(shí)間窗范圍內(nèi)波動(dòng)。

（6）模型的適應(yīng)度值是以配送車輛的行駛距離和成本為衡量標(biāo)準(zhǔn)。

1.2 變量符號定義

為了準(zhǔn)確理解數(shù)學(xué)模型描述的抽象問題，需要對模型中涉及的變量符號進(jìn)行定義，并說明符號的含義，如表1所示。

1.3 模型建立

1.3.1 多目標(biāo)函數(shù)

多目標(biāo)多時(shí)間窗車輛路徑規(guī)劃問題以最小運(yùn)輸總成本、最短運(yùn)輸距離和最少配送車輛數(shù)目為優(yōu)化目標(biāo)，構(gòu)建的數(shù)學(xué)表達(dá)式為：

式中，z1中第一項(xiàng)和第二項(xiàng)表示m 輛車的固定運(yùn)輸成本和行駛距離的成本，第三項(xiàng)表示車輛為服務(wù)點(diǎn)提供服務(wù)的懲罰成本，即由服務(wù)點(diǎn)預(yù)訂時(shí)間段a 與開始服務(wù)時(shí)間sik之差構(gòu)成，M 表示車輛提前與滯后到達(dá)的懲罰系數(shù)；z2表示車輛k 從第i 服務(wù)點(diǎn)出發(fā)到達(dá)第j 個(gè)服務(wù)點(diǎn)提供服務(wù)的最短運(yùn)輸距離；z3表示車輛k 從第i 到第j個(gè)服務(wù)點(diǎn)配備的最少車輛數(shù)。

1.3.2 約束條件

（1）車輛出發(fā)地點(diǎn)。為了安排最少的車輛數(shù)配送貨物，要求每一輛貨車必須從物流配送中心出發(fā)，建立的數(shù)學(xué)表達(dá)式為：

（2）車輛返回配送中心。為了充分利用安排的配送車輛，要求完成配送任務(wù)的車輛必須返回配送中心，建立的數(shù)學(xué)表達(dá)式為：

（3）車輛出發(fā)的初始地點(diǎn)。配送車輛的出發(fā)地點(diǎn)從0點(diǎn)開始，且不作為車輛的返回地點(diǎn)，建立的數(shù)學(xué)表達(dá)式為：

（4）車輛返回地點(diǎn)。配送車輛的最終返回地點(diǎn)需要額外增加返回地點(diǎn)，而不能以原來的出發(fā)地點(diǎn)作為返回地點(diǎn)，建立的數(shù)學(xué)表達(dá)式為：

（5）車輛服務(wù)點(diǎn)。配送車輛中必須存在唯一車輛與之需求點(diǎn)提供對應(yīng)的服務(wù)，建立的數(shù)學(xué)表達(dá)式為：

（6）車輛到達(dá)服務(wù)點(diǎn)。如果恰好存在第k 輛到達(dá)第j 個(gè)服務(wù)點(diǎn)，則該車輛必須為該需求點(diǎn)提供服務(wù)，建立的數(shù)學(xué)表達(dá)式為：

表1 變量符號與含義說明

（7）車輛服務(wù)后離開服務(wù)點(diǎn)。如果為第i 個(gè)需求點(diǎn)配備了第k 輛車，則該車輛服務(wù)完成后必須離開第i 個(gè)需求點(diǎn)，建立的數(shù)學(xué)表達(dá)式為：

（8）需求總量低于最大裝載量。在物流配送過程中，任何需求點(diǎn)的需求總量必須小于其車輛的最大裝載量，建立的數(shù)學(xué)表達(dá)式為：

（9）車輛行駛距離限制。在物流配送過程中，任何服務(wù)車輛的總里程小于等于最大行駛里程，建立的數(shù)學(xué)表達(dá)式為：

（10）車輛出發(fā)時(shí)刻限制。在物流配送過程中，要求配送車輛從配送中心點(diǎn)出發(fā)的時(shí)刻為零，建立的數(shù)學(xué)表達(dá)式為：

（11）車輛到達(dá)服務(wù)點(diǎn)的時(shí)間關(guān)系。在物流配送路徑上，任何一輛配送車相繼到達(dá)兩個(gè)需求點(diǎn)的時(shí)刻存在一定的關(guān)聯(lián)關(guān)系，建立的數(shù)學(xué)表達(dá)式為：

（12）車輛服務(wù)時(shí)間窗限制。在物流配送過程中，為第i 個(gè)需求點(diǎn)在給定的時(shí)間窗α 內(nèi)配備了第k 輛車，則該車輛到達(dá)第i 個(gè)需求點(diǎn)的時(shí)刻需要在時(shí)間窗α 的范圍內(nèi)，建立的數(shù)學(xué)表達(dá)式為：

（13）車輛服務(wù)完成時(shí)間限制。在物流配送過程中，給定第i 個(gè)需求點(diǎn)的第k 輛車需要在給定的時(shí)間完成服務(wù)，建立的數(shù)學(xué)表達(dá)式為：

（14）車輛不到達(dá)服務(wù)點(diǎn)。如果第i 個(gè)需求點(diǎn)沒有安排第k 輛車為其提供服務(wù)，則該車輛無需到達(dá)第i 個(gè)需求點(diǎn)，建立的數(shù)學(xué)表達(dá)式為：

（15）決策變量的取值范圍為：

2 多目標(biāo)鴿群-水滴算法

鴿群算法作為一種典型的仿生進(jìn)化算法，通過使用兩類獨(dú)立搜索算子模擬鴿子的不同搜索方向。在地圖羅盤算子中，如果鴿群偏離目標(biāo)距離時(shí)，經(jīng)過地磁場形成的腦地圖感知目標(biāo)方向，靠近目的地后，地磁場與太陽系的作用減弱。如果鴿群臨近目標(biāo)距離時(shí)，熟悉地標(biāo)的鴿子主要依靠地標(biāo)算子指引飛行方向，其他鴿子跟隨飛行達(dá)到目標(biāo)地。關(guān)于基本鴿群算法的原理可參考文獻(xiàn)[39]。智能水滴算法是在2007 年，學(xué)者Hosseini 根據(jù)自然界河流中的水流形態(tài)和環(huán)境變化模擬而提出的智能優(yōu)化算法，該算法具有水流速度和攜帶泥土量兩類算子，關(guān)于水滴算法的原理可參考文獻(xiàn)[28-29]。下面只對利用鴿群算子改進(jìn)智能水滴算法中，涉及的最優(yōu)解選擇與存儲(chǔ)機(jī)制、適應(yīng)度函數(shù)、改進(jìn)的水滴流動(dòng)速度、流動(dòng)方向和攜帶泥土量以及改進(jìn)后的智能水滴算法的步驟等進(jìn)行詳細(xì)介紹。

2.1 最優(yōu)解選擇與存儲(chǔ)機(jī)制

利用鴿群-水滴算法求解多目標(biāo)車輛問題時(shí)，算法依然是局部和全局搜索的組合過程。因此，首要解決如何平衡局部與全局搜索獲得的Pareto非最優(yōu)解的關(guān)系，如圖1 所示。根據(jù)鴿群經(jīng)過地圖羅盤算子的方向?qū)б偷貥?biāo)算子的鴿群折半擇優(yōu)方法獲得每個(gè)鴿子的局部最優(yōu)搜索，搜索到的局部最優(yōu)解作為水滴流動(dòng)方向和攜帶泥土量的子代個(gè)體。利用存儲(chǔ)池結(jié)構(gòu)來存儲(chǔ)局部搜索到的Pareto非最優(yōu)解。通過比較存儲(chǔ)池內(nèi)的解集，如果算法在搜索過程中得到了新的Pareto非最優(yōu)解，則用其更新存儲(chǔ)池內(nèi)的一個(gè)劣勢解，局部搜索過程完成后，對于智能水滴算法和鴿群算法以及存儲(chǔ)池內(nèi)所有的解使用Pareto排序和擁擠度選擇機(jī)制[40]進(jìn)行選擇操作，獲得新的迭代搜索群體。

圖1 最優(yōu)解選擇與存儲(chǔ)機(jī)制示意圖

2.2 適應(yīng)度函數(shù)

根據(jù)鴿群-水滴互補(bǔ)優(yōu)化算法的局部和全局搜索機(jī)制的差異，在同時(shí)考慮三個(gè)目標(biāo)函數(shù)時(shí)，采用三種不同的適應(yīng)度函數(shù)，分別用于全局最優(yōu)解和局部搜索最優(yōu)解的選擇操作。

算法的選擇操作采用Pareto 排序和擁擠度的度量方法[40]，fiti( x )=( rank(x),Crowding-distnce(x) )，其中，rank(x)為Pareto 占優(yōu)的層級關(guān)系，rank(x)＜rank(y)為解x 占優(yōu)y 。Crowding-distnce(x)為擁擠度距離，距離越大越好。在選擇操作時(shí)，對于鴿子群體、水滴群體和存儲(chǔ)池中的所有解按照第一個(gè)關(guān)鍵字rank(x)升序、第二個(gè)關(guān)鍵字Crowding-distnce(x)降序排序，然后選擇前N 種群個(gè)體迭代進(jìn)入下一代計(jì)算。

在鴿群算法的地圖羅盤算子和地標(biāo)算子方向的導(dǎo)引下，進(jìn)行局部搜索，每次搜索均是從候選解的鄰域解列表中選擇一個(gè)最好解更新當(dāng)前解，然后繼續(xù)搜索其鄰域，因此可引入Pareto 強(qiáng)度來定義局部搜索的適應(yīng)度函數(shù)[41]：

式中，S( x )表示在存儲(chǔ)池中被x 占優(yōu)的解的個(gè)數(shù)，W( x)表示在存儲(chǔ)池中占優(yōu)x 的解的個(gè)數(shù)，局部適應(yīng)度函數(shù)反映了解x 在Pareto最優(yōu)解集中占優(yōu)強(qiáng)弱程度，如果解x強(qiáng)度大，則適應(yīng)度高，說明解x 在Pareto 最優(yōu)解集中處于優(yōu)勢地位，可在局部搜索過程中優(yōu)先搜索具有優(yōu)勢地位解的鄰域。

2.3 利用鴿群搜索算子改進(jìn)智能水滴算法

智能水滴算法中的水滴通常被抽象為離散化形式，這是因?yàn)槊恳坏嗡谶\(yùn)動(dòng)過程攜帶的泥土量不同，且會(huì)以攜帶的泥土量大小來選擇流動(dòng)的方向，這種狀態(tài)不利于河道內(nèi)的水滴快速向最優(yōu)解靠攏，也不利于攜帶泥土量多的水滴向最優(yōu)解位置聚集。然而，離散二進(jìn)制粒子群算法[42]以及利用改進(jìn)鴿群搜索算子優(yōu)化的粒子群算法[37]，對于求解種群個(gè)體的收斂速度和位置具有良好的效果，本文充分利用離散二進(jìn)制的位置變化概率和鴿群中的兩類導(dǎo)航算子對智能水滴算法中的水滴流動(dòng)速度、流動(dòng)方向和攜帶泥土量算子進(jìn)行改進(jìn)，下面分別對智能水滴算法的改進(jìn)過程進(jìn)行闡釋。

2.3.1 改進(jìn)的水滴流速算子

Kennedy與Eberhart提出的離散二進(jìn)制粒子群算法是對粒子個(gè)體進(jìn)行二進(jìn)制編碼后，將粒子飛行速度轉(zhuǎn)化為變換概率[43]，并取得了良好的收斂效果。為了表示水滴速度值為二進(jìn)制位取1的概率，本文將水滴流動(dòng)速度值映射到區(qū)間[0，1]，映射的方法一般利用Sigmoid 函數(shù)，其數(shù)學(xué)表達(dá)式為：

式中，S( velocityij(IWD) )為水滴移動(dòng)位置x( i,j )取1 的概率，水滴通過式（19）改變對應(yīng)位值：

式中，rand( )表示在[0 ,1] 區(qū)間內(nèi)產(chǎn)生的隨機(jī)數(shù)，為了避免S( velocityij(IWD) )過度趨近0 或1 的邊緣，使用參數(shù)velocitymax表達(dá)為水滴流動(dòng)的最大速度值，用于限制水滴流動(dòng)速度velocityij(IWD) 的取值范圍，即velocityij(IWD)∈[- velocitymax,velocitymax] ，水滴流動(dòng)速度最終限制了x( i,j )取0或1的概率。

智能水滴算法中的水滴經(jīng)過離散化處理后，水滴流速快慢與攜帶的泥土量多少直接相關(guān)，特別是水滴流動(dòng)過程中席卷的泥土量越大，則水滴的流速必會(huì)減慢，因此，利用鴿群算法中的地圖羅盤算子對水滴的流速進(jìn)行改進(jìn)，改進(jìn)后的數(shù)學(xué)表達(dá)式為：

2.3.2 改進(jìn)的水滴流動(dòng)方向

為了說明離散化水滴攜帶大量泥土而選擇最優(yōu)的流動(dòng)方向，水滴位置x( )i,j 變化概率是關(guān)鍵，根據(jù)文獻(xiàn)[43]中提出的位變化概率，對此進(jìn)行分析，根據(jù)式（19），水滴流動(dòng)軌跡是一種根據(jù)攜帶泥土重量交替選擇概率，設(shè)為水滴在第t 次從位置i 流動(dòng)到位置j 的速度，第t 次位為1的概率是，而且位為0的概率是1，此外，如果第t-1 次位值已成為0，則第t 次變化的概率為，同樣，如果第t-1 次位值已成為1，則第t 次變化的概率為，而第t-1 次位值是0 的概率為，第t-1 次位值是1 的概率為。則第t 次位的變化概率p( t )為：

根據(jù)式（18）的結(jié)果，可得到如下的數(shù)學(xué)表達(dá)式：

根據(jù)水滴攜帶泥土重量的大小，選擇流動(dòng)概率，但流動(dòng)方向還與地標(biāo)指引方向有關(guān)，因此，利用鴿群算法中的地標(biāo)算子改進(jìn)水滴流動(dòng)方向，其數(shù)學(xué)表達(dá)式為：

式中，xcenter為引導(dǎo)水滴流動(dòng)的中心位置；其余變量的符合含義與式（20）一致。

2.3.3 自適應(yīng)變鄰域擾動(dòng)攜帶泥土量算子

在以上改進(jìn)的IWD 算子中，只是對水滴流經(jīng)河道內(nèi)的水滴速度和方向進(jìn)行改進(jìn)，并未對整個(gè)河道內(nèi)的泥土量變化情況進(jìn)行考慮，為了提高算法開發(fā)和探索能力，提出自適應(yīng)變鄰域擾動(dòng)策略對水滴攜帶泥土量進(jìn)行干擾，增加算法的全局收斂能力。自適應(yīng)變鄰域擾過程，如圖2所示。

圖2 自適應(yīng)變鄰域擾動(dòng)過程

根據(jù)圖2可知，在IWD水滴算法中，水滴位置S1 和S2 向目的地匯聚過程中，河道中央的水滴會(huì)不斷對鄰域位置上的水滴進(jìn)行擾動(dòng)，且會(huì)根據(jù)河道中的泥土量Soil(IWD)取值實(shí)時(shí)更新，并根據(jù)河道鄰域內(nèi)的水滴位置k 與匯聚點(diǎn)D 的間距大小來更新，如果間距小，則無需更新河岸edge( )k,j 的泥土量，否則位置k 上的水滴將產(chǎn)生新攜帶的泥土量Soil(IWD′)，該水滴個(gè)體攜帶的泥土量Soil(IWD)初始值設(shè)定為0，水滴流速velocitykD(IWD′)的初始值設(shè)定為Initvelocity，其攜帶新泥土量的水滴速度和位置的更新表達(dá)式為：

由此可推算出河岸edge( k,j )上的泥土量Soil(IWD)參數(shù)變化表達(dá)式為：

2.4 改進(jìn)的智能水滴算法步驟

標(biāo)準(zhǔn)智能水滴算法的兩類算子在迭代計(jì)算時(shí)，通常根據(jù)水滴流動(dòng)過程中攜帶的泥土量來確定水流速度和移動(dòng)方向，且攜帶的泥土量也會(huì)隨著水流速度發(fā)生變化，這樣算法在局部空間搜索計(jì)算時(shí)，由于某段河道內(nèi)水滴攜帶泥土量較多，算法會(huì)陷入早熟收斂狀態(tài)，然而鴿群算法中的兩類獨(dú)立運(yùn)行算子能夠根據(jù)地圖羅盤和地標(biāo)的導(dǎo)引，可較好地指明個(gè)體鴿子的飛行方向和飛行速度，因此，本文利用鴿群算法中的地圖羅盤算子和地標(biāo)算子以及自適應(yīng)擾動(dòng)策略分別對智能水滴算法中的流動(dòng)速度、流動(dòng)方向以及水滴攜帶泥土量進(jìn)行改進(jìn)，設(shè)計(jì)出引入鴿群搜索算子的智能水滴算法，較好地克服標(biāo)準(zhǔn)智能水滴算法在車輛路徑問題求解方法的不足，算法的具體計(jì)算步驟如下：

步驟1 設(shè)置算法參數(shù)；最大迭代計(jì)算次數(shù)tmax；鴿子個(gè)數(shù)m；水滴個(gè)數(shù)N ；水滴流速參數(shù)av、bv、cv；泥土更新參數(shù)as、bs、cs；局部泥土更新系數(shù)ρ0、ρn；起止位置的初始泥土量

步驟2 初始化所有水滴的參數(shù)；設(shè)置算法的動(dòng)態(tài)參數(shù)；水滴初始狀態(tài)集合S( )IWD =?，水滴初始速度、水滴初始攜帶泥土量Soil(IWD)以及初始攜帶重量。

步驟3 選擇水滴局部更新信息；水滴根據(jù)流動(dòng)路徑上的泥土量大小，按照式（21）概率大小選擇流經(jīng)下一節(jié)點(diǎn)，根據(jù)被選擇節(jié)點(diǎn)更新水滴的局部信息，按照式（24）～式（26）更新水滴的局部信息。

步驟4 根據(jù)式（24）、式（26）分別對水滴的流動(dòng)速度和攜帶的泥土量進(jìn)行更新。

步驟5 條件判斷；如果河道內(nèi)所有的水滴都會(huì)收斂至同一路徑或達(dá)到最大迭代計(jì)算次數(shù)，轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟3。

步驟6 保存最優(yōu)解與最優(yōu)值，求解計(jì)算結(jié)束。

3 多目標(biāo)多時(shí)間窗車輛路徑模型處理方法

多目標(biāo)優(yōu)化問題通常采用懲罰函數(shù)與帕累托最優(yōu)解集進(jìn)行約束條件處理，且這兩種方法有著不同的特點(diǎn)。下面從懲罰函數(shù)和帕累托最優(yōu)解集兩個(gè)方面，對本文的多目標(biāo)車輛路徑模型的處理方法進(jìn)行探討分析，并提出多目標(biāo)優(yōu)化與懲罰函數(shù)的混合策略。

3.1 模型處理策略

多時(shí)間窗車輛路徑規(guī)劃問題可使用有向有環(huán)圖來表達(dá)，假設(shè)圖G=(V ,E )，V={0 ,1,2,…,n} 表示車輛配送中心0 與服務(wù)點(diǎn)i=1,2,…,n，E 表示車輛節(jié)點(diǎn)之間的路徑集合。同時(shí)，使用水滴抽象表示每一輛車，水滴多次經(jīng)過配送中心0，一次經(jīng)過服務(wù)點(diǎn)，形成完整的流動(dòng)路徑過程恰好為VRPMOMTW的解。求解一次迭代結(jié)束后，可在每個(gè)水滴流經(jīng)的完整路徑中搜索出最優(yōu)路徑，利用該最優(yōu)路徑不斷更新各個(gè)水滴節(jié)點(diǎn)之間的泥土量與全局最優(yōu)路徑，然后迭代到下一步迭代過程，直到達(dá)到算法的最大次數(shù)或期望的優(yōu)化路徑。

3.1.1 多目標(biāo)函數(shù)的懲罰處理策略

多目標(biāo)車輛路徑規(guī)劃問題涉及三個(gè)以上的目標(biāo)函數(shù)和多類復(fù)雜的約束條件，該類問題的求解較為復(fù)雜，為了簡化問題的求解難度，利用罰函數(shù)法[44-45]和理想點(diǎn)方法[46]分別對模型中的約束條件與多目標(biāo)函數(shù)進(jìn)行簡化處理。根據(jù)理想點(diǎn)法，將最小運(yùn)輸總成本、最短運(yùn)輸距離和最少配送車輛數(shù)目的多目標(biāo)轉(zhuǎn)化為單目標(biāo)問題，多目標(biāo)車輛路徑規(guī)劃模型可轉(zhuǎn)化為以下形式：

式中，Q1為A( x )的效用函數(shù)，取值為利用線性規(guī)劃方法求解該問題的上界值；Q2為B( x )的效用函數(shù)；Q3為C( x )的效用函數(shù)，由約束違反度函數(shù)的特性，且取值為零；λi為第i 目標(biāo)函數(shù)的權(quán)重，且∑λi=1，這種方法只能找到部分Pareto 最優(yōu)解，為了找到更多的Pareto 最優(yōu)解，可利用Pareto排序法確定各目標(biāo)函數(shù)的權(quán)重系數(shù)。

3.1.2 多目標(biāo)優(yōu)化與懲罰函數(shù)的混合策略

通常采用懲罰函數(shù)法和Pareto 最優(yōu)解集對多目標(biāo)函數(shù)問題進(jìn)行處理，但根據(jù)上述懲罰函數(shù)處理方法可知，雖然懲罰函數(shù)的選取具有一定的主觀性，但根據(jù)Pareto 優(yōu)超的定義和關(guān)系[47]，Pareto 最優(yōu)解集并非適用于所有個(gè)體，根據(jù)需要引入偏好程度才更為有效，如圖3所示，在Pareto 最優(yōu)解集中包含3 個(gè)依次排列的非劣個(gè)體A、B、C，假設(shè)只有個(gè)體A 距離可行域較近，而個(gè)體B與C 距離可行域較遠(yuǎn)，所以A 是需要提取的重要信息。另外，不可行解是無法超越Pareto 可行解，這是因?yàn)槿肿顑?yōu)點(diǎn)落在邊界點(diǎn)上，且算法進(jìn)入搜索后期會(huì)丟棄不可行解。因此，基于Pareto最優(yōu)解集的多目標(biāo)優(yōu)化方法往往忽視了偏好程度，且引入偏好的簡便方法是懲罰函數(shù)法。因此，本文提出多目標(biāo)優(yōu)化與懲罰函數(shù)混合方法，首先為了權(quán)衡目標(biāo)函數(shù)與約束條件方程G(x)的標(biāo)準(zhǔn)變化，將從Pareto 最優(yōu)解集中選擇個(gè)體的搜索偏好，找出群體中的最大和最小目標(biāo)函數(shù)值，然后對每個(gè)目標(biāo)函數(shù)值和約束條件的程度進(jìn)行歸一化處理，這樣處理的目標(biāo)函數(shù)具有降維特征，且可以比較Pareto最優(yōu)解集中的個(gè)體，根據(jù)偏好選擇個(gè)體。同時(shí)，在算法搜索初期存在少量可行解，通過引入懲罰函數(shù)，可以引導(dǎo)算法盡早進(jìn)入可行域。另外，優(yōu)化過程中，懲罰系數(shù)會(huì)依據(jù)群體狀態(tài)自動(dòng)調(diào)整，當(dāng)群體的可行解比例p ＞0.5 與懲罰系數(shù)ρ ＜1 時(shí)，可開發(fā)出目標(biāo)函數(shù)與約束程度較小的不可行解。

圖3 Pareto最優(yōu)解集中的非劣解示意圖

3.1.3 權(quán)重系數(shù)處理策略

在問題可行域上對各個(gè)目標(biāo)函數(shù)zi( x )進(jìn)行極小化處理，計(jì)算極小值點(diǎn)xi，得到：

利用算術(shù)平均法計(jì)算i 個(gè)分目標(biāo)函數(shù)的極小點(diǎn)的相對離差、為了避免各個(gè)分目標(biāo)函數(shù)值離差過大而影響權(quán)重系數(shù)的選取，對求解的相對離差做無量綱化處理。

同時(shí)，利用算術(shù)平均法計(jì)算出第i 個(gè)分目標(biāo)函數(shù)的極小點(diǎn)的平均相對離差，得到：

顯而易見，為了使權(quán)重系數(shù)規(guī)范化，當(dāng)Δi＞0 時(shí)，假設(shè)Δi1≥Δi2≥…≥Δis，且Δis∈{ Δ1,Δ2,…,Δm} ，選取如下式作為各分目標(biāo)對應(yīng)的權(quán)系數(shù)：

根據(jù)上述分目標(biāo)函數(shù)與權(quán)重系數(shù)的確定方法，構(gòu)建的多目標(biāo)車輛路徑規(guī)劃模型的數(shù)學(xué)表達(dá)式為：

式中，變量的含義與式（1）、式（27）的一致。

3.1.4 約束條件處理策略

多目標(biāo)窗車輛路徑規(guī)劃問題是帶有多種約束條件的復(fù)雜問題，采用罰函數(shù)法[44-45]將模型中的部分約束優(yōu)化問題處理為無約束優(yōu)化問題，由此對式（2）～式（15）中的約束條件處理如下：

式中，φi( x )為不等式約束條件；θi( x )為等式約束條件；σ 表示等式約束的懲罰因子；表明優(yōu)化后的車輛配送成本應(yīng)允許在[- σ,σ ]范圍內(nèi)波動(dòng)，通常σ 取很小的值。

3.2 模型求解步驟

步驟1 輸入初始靜態(tài)變量；服務(wù)點(diǎn)與配送中心集合D；服務(wù)點(diǎn)個(gè)數(shù)n；配送中心點(diǎn)0，服務(wù)點(diǎn)i 的需求量為qi,多時(shí)間窗t=1,2,…,p；服務(wù)時(shí)間sti,i=1,2,…,n；服務(wù)中心至服務(wù)點(diǎn)的距離矩陣為d；車輛的單位運(yùn)行成本c；車輛固定成本g；車輛行駛速度v；車輛的最大載重量Qmax；車輛在服務(wù)點(diǎn)與配送中心之間的行駛時(shí)間矩陣T ；最大迭代次數(shù)tmax；水滴數(shù)N ，水滴流動(dòng)更新速度參數(shù)av、bv、cv，泥土攜帶量更新參數(shù)as、bs、cs，局部泥土量更新權(quán)值a，全局泥土量更新權(quán)值β，服務(wù)點(diǎn)上的初始泥土量InitSoil,水滴的初始流動(dòng)速度InitVelocity,攜帶泥土量初始矩陣

步驟2 輸入初始動(dòng)態(tài)變量；初始化已訪問節(jié)點(diǎn)集Visitnode 為空集；未訪問節(jié)點(diǎn)集初始化為Novisitnode={0 ,1,2,…,n} ；水滴（車輛）從配送中心出發(fā)攜帶泥土量初始化為InitSoil=0；水滴（車輛）從配送中心出發(fā)的流動(dòng)速度初始化為InitVelocity=0；水滴（車輛）從配送中心出發(fā)的載重量初始化為Qmax=0；水滴從配送中心出發(fā)的開始時(shí)間為t=0。

步驟3 根據(jù)路徑規(guī)劃模型的約束條件，隨機(jī)選取水滴的初始訪問節(jié)點(diǎn)，以時(shí)間窗動(dòng)態(tài)更新水滴訪問節(jié)點(diǎn)列表Visitnode( IWD )和未訪問節(jié)點(diǎn)列表Novisitnode( IWD )。

步驟4 根據(jù)時(shí)間窗上未訪問節(jié)點(diǎn)Novisitnodei的需求量，確定水滴移動(dòng)訪問節(jié)點(diǎn)集合DV ；如果未訪問節(jié)點(diǎn)集合NDV 不符合容量和時(shí)間窗約束，水滴（車輛）返回配送中心0，初始化水滴對應(yīng)的動(dòng)態(tài)變量，形成一輛配送車輛的路徑；如果未訪問節(jié)點(diǎn)集合NDV=?，水滴（車輛）返回配送中心0，形成水滴（車輛）的完整訪問路徑，該路徑對應(yīng)VRPMOMTW問題的可行解TIWD。

步驟5 利用多種節(jié)點(diǎn)選擇方法，在水滴到達(dá)節(jié)點(diǎn)的服務(wù)概率與距離以及泥土量中加入重要度因子，計(jì)算水滴訪問列表的概率p( t )，確定從當(dāng)前節(jié)點(diǎn)i 到NDV 中的下一個(gè)服務(wù)點(diǎn)j 的概率，如下式：

εs為較小的整數(shù)，且εs=0.01。

步驟6 根據(jù)訪問節(jié)點(diǎn)集合DV 中每個(gè)節(jié)點(diǎn)對應(yīng)的概率，采用式（22）選擇下一個(gè)被訪問節(jié)點(diǎn)。并將被訪問服務(wù)點(diǎn)j 列入已訪問節(jié)點(diǎn)集合中，并修改當(dāng)前水滴對應(yīng)的已訪問節(jié)點(diǎn)集合、訪問順序和未訪問節(jié)點(diǎn)集合。

步驟7 根據(jù)式（24）、式（25）、式（26），分別對水滴（車輛）的流動(dòng)速度velocityij(IWD) 、攜帶泥土量Soil(IWD)和路徑滾動(dòng)泥土量進(jìn)行更新；其中，為了避免算法早熟問題，路徑泥土攜帶量需要在Soil( i,j )∈[min Soil( i,j ),max Soil( i,j )]之間變動(dòng)，且min Soil( i,j )與max Soil( i,j )的計(jì)算表達(dá)式如下[34]：

式中，Pbest=0.5，n 表示服務(wù)點(diǎn)數(shù)；表示當(dāng)前局部最優(yōu)解。

步驟8 根據(jù)步驟3 中計(jì)算的完整訪問路徑TIWD，并假設(shè)運(yùn)輸總成本cost(TIWD)，則搜索出目標(biāo)函數(shù)中最小平均可行解作為模型的最優(yōu)解TTB。

步驟9 根據(jù)當(dāng)前迭代計(jì)算得到的最優(yōu)解TTB，并將更新后的泥土量矩陣作為下次迭代計(jì)算的初始泥土量矩陣，其計(jì)算表達(dá)式為：

其中，nIB表示當(dāng)前迭代計(jì)算路徑上的服務(wù)節(jié)點(diǎn)數(shù)，表示最優(yōu)路徑上水滴（車輛）攜帶的泥土量。

步驟10 更新模型計(jì)算的全局最優(yōu)解：

步驟11 更新迭代計(jì)算次數(shù)ti=ti+1，若ti＜tmax，則轉(zhuǎn)入步驟2，否則，如果ti=tmax，則將最優(yōu)解fmin作為VRPMOMTW的最優(yōu)解，并輸出計(jì)算結(jié)果。

4 實(shí)例仿真與結(jié)果分析

4.1 算法性能測試函數(shù)

為了驗(yàn)證所提CPIIWD 算法的性能，以文獻(xiàn)[37]中的6 個(gè)經(jīng)典函數(shù)為例，對算法性能進(jìn)行仿真測試，其函數(shù)的具體形式如下：

（1）Sphere"s function

（2）Rosenbrock"s function

（3）Griewank"s function

（4）Ackley"s function

（5）Penalized function

（6）Shifted Griewank

4.2 實(shí)例數(shù)據(jù)來源

為了進(jìn)一步驗(yàn)證本文提出的VRPMOMTW 的穩(wěn)定性與算法的可行性，選用文獻(xiàn)[33，38]中的案例，利用CPIIWD 算法對VRPMOMTW 進(jìn)行優(yōu)化求解，并與文獻(xiàn)[33，38]中的求解結(jié)果進(jìn)行比較。

實(shí)例1 某物流配送中心在不同時(shí)間窗內(nèi)和服務(wù)時(shí)間長度，為10個(gè)需求量不同的客戶提供物流配送服務(wù)，其配送中心與需求服務(wù)點(diǎn)的距離和服務(wù)時(shí)間如表2、表3所示。

表2 配送中心與服務(wù)點(diǎn)之間的距離 km

表3 多時(shí)間窗的服務(wù)點(diǎn)需求量與服務(wù)時(shí)間

實(shí)例2 某配送中心的車型相同，配送服務(wù)需求點(diǎn)為20，配送中心位置為（0，0），每個(gè)需求點(diǎn)的位置坐標(biāo)、需求服務(wù)量和時(shí)間窗等信息如表4所示。

4.3 模型與算法參數(shù)設(shè)置

實(shí)驗(yàn)環(huán)境：Inter CoreTMi5-2450MCPU@ 3.2 GHz，內(nèi)存為4 GB，Window7 操作系統(tǒng)，MatlabR2015a 版本，四種算法經(jīng)過反復(fù)迭代計(jì)算后，選取如下參數(shù)后，計(jì)算結(jié)果較為理想。

表4 服務(wù)點(diǎn)位置、需求量、服務(wù)時(shí)間、時(shí)間窗數(shù)據(jù)

算法參數(shù)：（1）人工免疫系統(tǒng)算法[48]?？贵w數(shù)n=30,交叉概率pc=0.6，變異程度pm=0.3，淘汰率pe=0.3，濃度閾值Tc=0.3，抗體親和力閾值Tac1=0.75，記憶細(xì)胞親和力閾值Tac2=0.8，記憶細(xì)胞數(shù)量Nm=5，最大迭代次數(shù)tmax=500。

（2）粒子群算法[37]。種群規(guī)模S=300,K=3,維度D=100,最大迭代次數(shù)tmax=500。

（3）遺傳算法。種群規(guī)模N=300 ，交叉概率pc=0.7，變異概率pm=0.3，最大迭代次數(shù)tmax=500。

（4）鴿群-水滴算法。水滴數(shù)NIWD=100，水滴流動(dòng)更新速度av=1,bv=0.1,cv=1，泥土攜帶量更新參數(shù)as=1,bs=0.1,cs=1，局部泥土量更新參數(shù)a=1，全局泥土量更新參數(shù)β=1，服務(wù)點(diǎn)上的初始泥土量InitSoil=2 000，初始流動(dòng)速度InitVelocity=100，最大迭代次數(shù)tmax=500，水滴流動(dòng)方向的羅盤導(dǎo)航因子R=0.9，局部泥土更新系數(shù)ρ0=ρn=0.5。

模型參數(shù)：車輛最大載重量Qmax=90 t ，車輛固定成本g=50 元，車輛行駛單位成本ck=20 元，車輛的平均行駛速度v=50 km/h，車輛在配送中心與服務(wù)點(diǎn)之間的行駛時(shí)間tij=dij/50 h。

實(shí)例參數(shù)：實(shí)例1中，水滴數(shù)NIWD=100，水滴流動(dòng)更新速度av=1,bv=0.1,cv=1，泥土攜帶量更新參數(shù)as=1,bs=0.1,cs=1，局部泥土量更新參數(shù)a=1，全局泥土量更新參數(shù)β=1 ，服務(wù)點(diǎn)上的初始泥土量InitSoil=2 000 ，水滴的初始流動(dòng)速度InitVelocity=100，最大迭代次數(shù)tmax=100，水滴流動(dòng)方向的羅盤導(dǎo)航因子R=0.9，局部泥土量更新系數(shù)ρ0=ρn=0.5。

實(shí)例2 中，水滴數(shù)NIWD=200，水滴流動(dòng)更新速度av=1 000,bv=0.1,cv=1 ，泥土攜帶量更新參數(shù)as=1 000,bs=0.1,cs=1，局部泥土量更新參數(shù)a=0.9，全局泥土量更新參數(shù)β=0.9 ，服務(wù)點(diǎn)上的初始泥土量InitSoil=2 000 ，水滴的初始流動(dòng)速度InitVelocity=100，最大迭代次數(shù)tmax=800。

4.4 仿真結(jié)果與分析

4.4.1 算法性能測試結(jié)果與分析

根據(jù)表5 的仿真結(jié)果可知，四種算法分別經(jīng)過500次的迭代測試后，發(fā)現(xiàn)除了Rosebrock 函數(shù)和Penalized函數(shù)無法收斂到理想值，其余4種函數(shù)幾乎可收斂到理想的函數(shù)值。雖然AIS算法的收斂計(jì)算時(shí)間明顯減少，但AIS算法的收斂能力較弱，這是因?yàn)锳IS算法中保存在記憶庫中的抗體數(shù)較少時(shí)，降低了記憶細(xì)胞的搜索能力。另外，經(jīng)過Penalized 函數(shù)的仿真結(jié)果發(fā)現(xiàn)，雖然GA和CPIIWD收斂計(jì)算的結(jié)果幾乎接近理想值，但GA算法的求解速度慢于AIS算法的求解速度，這是因?yàn)樵摵瘮?shù)是分段函數(shù)，算法在收斂計(jì)算時(shí)的參數(shù)設(shè)置的不同而造成的差異。同時(shí)，使用PSO算法仿真測試的多維單峰和多峰函數(shù)收斂計(jì)算時(shí)間較長，而采用CPIIWD算法的收斂計(jì)算時(shí)間明顯減少，收斂效果要優(yōu)于其他3種不同的算法，這說明鴿群-水滴互補(bǔ)優(yōu)化算法在多維函數(shù)優(yōu)化方面的改進(jìn)效果要比單個(gè)人工智能算法的效果更好。

表5 四種算法的計(jì)算結(jié)果

圖4 四種算法的仿真收斂曲線

根據(jù)圖4的收斂曲線清晰看出，提出的鴿群-水滴互補(bǔ)優(yōu)化算法由于引入精準(zhǔn)的鴿群算子和多目標(biāo)種群初始化方法，使得智能水滴算法在計(jì)算復(fù)雜多維函數(shù)時(shí)，可逃逸局部最優(yōu)搜索空間，并在短時(shí)間內(nèi)快速向全局最優(yōu)解方向收斂。特別是AIS算法在6種不同函數(shù)上的收斂結(jié)果都不理想，且計(jì)算時(shí)間要比CPIIWD算法的計(jì)算時(shí)間長，但從部分函數(shù)也可看出，CPIIWD 算法在某些測試函數(shù)上也不能完全表現(xiàn)出最優(yōu)性能，這是因?yàn)閷λ嗡惴ǖ某跏紖?shù)選取和固有的弊端總會(huì)導(dǎo)致部分搜索計(jì)算效果較差，但從總體上來看，CPIIWD 算法要明顯優(yōu)于其他3種算法，這是因?yàn)槔螟澣核阉魉阕訉λ嗡惴ㄖ械乃阕踊パa(bǔ)改進(jìn)后產(chǎn)生的明顯效果。

4.4.2 模型求解結(jié)果與分析

通過算例1 中的數(shù)據(jù)源與處理后的約束條件（33）和目標(biāo)函數(shù)（1）的編程，利用CPIIWD 算法求解出本文最小運(yùn)輸總成本為6 705元、最少配送車輛數(shù)為3輛，最短配送路徑如圖5所示。

圖5 3輛車的最短配送路徑示意圖

根據(jù)圖5 的車輛配送路徑分布結(jié)果可知，實(shí)例1 中的車輛從物流配送中心出發(fā)，經(jīng)過不同時(shí)間點(diǎn)和服務(wù)點(diǎn)后，3輛配送車行經(jīng)最短運(yùn)輸距離，最終返回配送中心，符合物流車輛配送作業(yè)的基本要求。

為了進(jìn)一步驗(yàn)證本文CPIIWD算法求解VRPMOMTW問題的可行性，分別利用遺傳算法、基本智能水滴算法和CPIIWD算法對車輛路徑問題進(jìn)行解算，在實(shí)例1中，三種不同的人工智能算法經(jīng)過100次的迭代計(jì)算后，其收斂計(jì)算結(jié)果的曲線如圖6所示。

根據(jù)圖6中的收斂曲線可知，經(jīng)過三個(gè)不同的人工智能算法仿真計(jì)算后，遺傳算法經(jīng)過23 次迭代后獲得了問題的全局最優(yōu)解，基本智能水滴算法經(jīng)過19 次得到了全局最優(yōu)解，而CPIIWD算法經(jīng)過16次獲得了問題最優(yōu)解，這說明經(jīng)過鴿群搜索算子對水滴算法的互補(bǔ)改進(jìn)后，模型的求解效果要明顯優(yōu)于其他兩種算法，且使用該算法求解的最小運(yùn)輸總成本要比其他兩種算法少，為物流企業(yè)節(jié)約不少的運(yùn)輸費(fèi)用。

表6 三種不同算法的求解計(jì)算時(shí)間比較

圖6 三種算法的收斂計(jì)算過程

為了再次驗(yàn)證本文算法求解效果，通過對3種不同算法的尋優(yōu)次數(shù)、最少迭代次數(shù)和計(jì)算時(shí)間等進(jìn)行比較，如表6所示。

通過表6的計(jì)算結(jié)果可知，三種算法在相同的數(shù)據(jù)源和模型參數(shù)設(shè)置下，基本智能水滴算法的尋優(yōu)次數(shù)為96，遺傳算法的尋優(yōu)次數(shù)為30，而CPIIWD算法為28，這是因?yàn)轼澣核阕泳邆渚珳?zhǔn)的羅盤算子和地標(biāo)算子，使改進(jìn)后的水滴算法的計(jì)算時(shí)間和迭代次數(shù)明顯減少，但該算法得到的最差值要遜色于其他兩種算法，說明根據(jù)文獻(xiàn)[37]中的原理，任何算法不是萬能的，不可能在各個(gè)方面都能表現(xiàn)出良好的效果。

通過實(shí)例2 中的數(shù)據(jù)來源與模型參數(shù)設(shè)置，利用CPIIWD 算法對多目標(biāo)多時(shí)間窗車輛路徑問題進(jìn)行仿真計(jì)算，其20個(gè)服務(wù)點(diǎn)的最優(yōu)配送路徑示意圖如圖7所示，最小成本的收斂計(jì)算結(jié)果如圖8 所示，并對20 個(gè)服務(wù)點(diǎn)的車輛路徑距離進(jìn)行優(yōu)化計(jì)算，如圖9所示。

圖7 20個(gè)服務(wù)點(diǎn)的最優(yōu)配送路徑示意圖

根據(jù)圖7中的配送路徑分布結(jié)構(gòu)圖可知，物流服務(wù)車輛經(jīng)過不同的需求服務(wù)點(diǎn)后返回服務(wù)中心，且經(jīng)過CPIIWD算法的求解計(jì)算后，20個(gè)服務(wù)點(diǎn)上需要最少分配4輛相同型號的車輛。

圖8 鴿群-智能水滴算法的收斂計(jì)算過程

圖9 20個(gè)服務(wù)點(diǎn)的車輛路徑最優(yōu)化距離

通過表7的計(jì)算結(jié)果可知，經(jīng)過使用CPIIWD算法的優(yōu)化計(jì)算后，20 個(gè)需求服務(wù)點(diǎn)上，使用4 輛運(yùn)輸車輛的最小運(yùn)輸總成本為1 765.836元，這與文獻(xiàn)[38]中使用的基本智能水滴算法求解計(jì)算的最小運(yùn)輸總成本2 168.9元、最短運(yùn)輸距離353.804 km相比，每條運(yùn)輸路徑的拓?fù)浣Y(jié)構(gòu)不同，路徑距離分別減少20 km 左右，這說明使用精準(zhǔn)搜索的鴿群算法改進(jìn)水滴算法，求解VRPMOMTW問題的結(jié)果更為精確，優(yōu)化效果更為明顯。

表7 不同配送路徑上車輛的載重量

根據(jù)圖8 的收斂計(jì)算結(jié)果可知，為了增強(qiáng)CPIIWD算法求解VRPMOMTW問題的可信性，通過該算法800次迭代后，求解計(jì)算的最小運(yùn)輸成本達(dá)到最優(yōu)，且該算法經(jīng)過260 次的計(jì)算后，求解結(jié)果基本達(dá)到平穩(wěn)狀態(tài)，說明該算法能夠快速收斂到問題的最優(yōu)解。

由圖9 的計(jì)算結(jié)果可知，使用CPIIWD 算法求解VRPMOMTW 中的路徑距離后，車輛從配送中心出發(fā)后，經(jīng)過20個(gè)需求服務(wù)點(diǎn)形成不同運(yùn)輸路徑拓?fù)浣Y(jié)構(gòu)，最終返回配送中心，且計(jì)算獲得的車輛路徑最優(yōu)化距離為273.191 1 km，這與文獻(xiàn)[33]中使用基本智能水滴算法求解的車輛路徑距離減少80 km左右，降低了車輛運(yùn)輸總成本。

5 結(jié)語

（1）針對帶時(shí)間窗車輛路徑組合規(guī)劃目標(biāo)的差異化問題，提出多目標(biāo)多時(shí)間窗車輛路徑規(guī)劃模型，實(shí)現(xiàn)了物流車輛運(yùn)輸成本、運(yùn)輸距離和配置數(shù)量的抽象建模，拓展了物流車輛路徑規(guī)劃問題的研究范圍。

（2）針對基本智能水滴算法求解車輛路徑規(guī)劃模型速度慢、結(jié)果精度低等問題，利用地圖羅盤算子和地標(biāo)算子分別改進(jìn)了水滴的流動(dòng)速度和方向，同時(shí)，利用自適應(yīng)變鄰域擾動(dòng)策略干擾水滴攜帶的泥土量，提高水滴算法的搜索計(jì)算速度和求解精度。

（3）針對多目標(biāo)模型的求解難度大、處理過程復(fù)雜等問題，采用理想點(diǎn)法和多目標(biāo)優(yōu)化與罰函數(shù)混合方法，分別處理多目標(biāo)函數(shù)與復(fù)雜約束條件間的關(guān)系，簡化了人工智能算法求解模型處理能力。

（4）通過利用經(jīng)典標(biāo)準(zhǔn)測試函數(shù)與物流車輛路徑規(guī)劃問題作為仿真實(shí)例，測試了鴿群-水滴算法的優(yōu)化性能以及驗(yàn)證了模型求解的可行性，并從尋優(yōu)次數(shù)、收斂計(jì)算時(shí)間和平均值等指標(biāo)考核了4 種不同算法的計(jì)算結(jié)果，證明了CPIIWD 算法求解車輛路徑問題的優(yōu)越性，雖然改進(jìn)的智能水滴算法在車輛路徑規(guī)劃問題中獲得較好的求解結(jié)果，但該算法能否在不同工程優(yōu)化問題中表現(xiàn)出良好性能，這需要進(jìn)一步對本文算法的深入應(yīng)用展開研究。