李俊青 黃體浩 宋美嫻 韓玉艷

(聊城大學(xué) 計(jì)算機(jī)學(xué)院，山東 聊城 252059)

0 引言

車輛路徑問題(Vehicle Routing Problem，VRP)是現(xiàn)實(shí)生活中最重要的問題之一，現(xiàn)已成為運(yùn)輸、供應(yīng)鏈管理和物流領(lǐng)域的核心問題.它有眾多的實(shí)際應(yīng)用其中包括公交路線規(guī)劃、郵政、包裹運(yùn)送、餐飲配送、銀行和ATM終端的現(xiàn)金配送、工業(yè)垃圾收集等.在為給定的配送問題構(gòu)建規(guī)劃路徑時(shí)，需要考慮大量的實(shí)際問題，例如可用的車隊(duì)規(guī)模、容量、地理上分散的客戶之間的行程成本，可能拜訪客戶的時(shí)間間隔，以及許多其他意外情況，這些因素都有可能影響路徑規(guī)劃的可行性.

隨著時(shí)間窗和其他時(shí)間數(shù)據(jù)的進(jìn)一步復(fù)雜化，帶時(shí)間窗的車輛路徑問題(Vehicle Routing Problem with Time Windows，VRPTW)應(yīng)運(yùn)而生.Solomon等人對(duì)VRPTW進(jìn)行了較早的研究，并于1992年提出了一種新的優(yōu)化算法，通過列生成策略解決了VRPTW集劃分公式的LP松弛問題[1].近年來(lái)，多種元啟發(fā)式算法被成功應(yīng)用于求解VRPTW問題中，典型的包括：粒子群算法[2]、細(xì)菌覓食優(yōu)化算法[3]、人工蜂群算法[4]等.

隨著人們對(duì)冷藏食品需求的不斷增加，冷鏈物流作為新興的物流方式逐漸受到人們的重視.在一些文獻(xiàn)中將冷鏈配送問題與VRPTW問題結(jié)合起來(lái)，其中懲罰成本是反映冷鏈時(shí)間敏感性的主要因素.2007年，Hsu等人考慮了在易腐食品運(yùn)送過程中設(shè)備能耗以及時(shí)間窗約束對(duì)配送的影響[5].2014年，Hsu和Chen進(jìn)一步研究了根據(jù)不同溫度區(qū)域的要求優(yōu)化多溫度食品制備的車輛大小和配送調(diào)度[6].2015年，Ji等人針對(duì)冷鏈物流中同時(shí)取貨配送(Vehicle Routing Problem with Simultaneous Pickup and Delivery，VRPSPD)的車輛路徑問題，分析了冷鏈物流配送過程中車輛固定成本、運(yùn)行成本、冷藏成本和冷鏈貨物變質(zhì)成本等成本結(jié)構(gòu)，建立了VRPSPD問題優(yōu)化模型[7].2019年，Li等人從溫室氣體排放的角度出發(fā)，研究了冷鏈物流綠色車輛路徑問題，建立了冷鏈物流的綠色車輛路徑優(yōu)化模型[8].2019年，Zhang等人將低碳經(jīng)濟(jì)引入冷鏈物流，建立了包含碳排放成本的冷鏈物流路徑優(yōu)化模型，使用核糖核酸計(jì)算與蟻群算法相結(jié)合的方法進(jìn)行求解，并將其應(yīng)用到雄安某冷鏈物流企業(yè)的路徑優(yōu)化問題中，得到了較好的結(jié)果[9].Qin和Tao等人考慮了成本、客戶滿意度和碳排放等影響因素，建立了以單位滿意顧客成本最小為目標(biāo)函數(shù)的綜合冷鏈車輛路徑優(yōu)化問題模型[10].

綜上所述，車輛路徑問題及其變體在國(guó)內(nèi)外都有著廣泛的研究，不僅對(duì)問題本身的研究特別是基本的VRP問題及其符合現(xiàn)實(shí)情況的變體進(jìn)行了研究，也對(duì)該類問題的求解算法進(jìn)行了研究與優(yōu)化.隨著時(shí)代發(fā)展，所考慮的問題不僅是單一需求，而需要將更多的因素納入考慮范圍，如配送車型的多樣化、時(shí)間窗的選擇等.但是關(guān)于冷鏈運(yùn)輸同時(shí)考慮顧客滿意度、能量消耗和碳排放三個(gè)因素的研究還較少.因此，在激烈的市場(chǎng)競(jìng)爭(zhēng)和低碳經(jīng)濟(jì)的需求下，冷鏈物流為了更好的發(fā)展，配送網(wǎng)絡(luò)不僅要考慮項(xiàng)目的總成本，還要必須關(guān)注客戶滿意度和碳排放，不斷優(yōu)化問題模型，在為客戶提供更好更快服務(wù)的同時(shí)獲得利益的最大化，這不僅是現(xiàn)代企業(yè)的要求也符合社會(huì)發(fā)展的趨勢(shì).

1 問題描述

在傳統(tǒng)VRP問題中，所有車輛的類型都是相同的，即每輛車都有同樣的能源消耗，裝載能力與運(yùn)送裝置.然而在現(xiàn)實(shí)的物流系統(tǒng)中，許多配送車輛的類型、裝載能力、能耗指標(biāo)和運(yùn)送裝置都是不同的.因此本文研究的問題可以描述為：有一個(gè)配送中心可以為客戶提供常溫貨物與冷凍貨物，有一定數(shù)量的運(yùn)輸車輛，車型也有常溫與冷藏兩種，服務(wù)于一組客戶.配送中心和客戶的具體信息都是確定不變的，如客戶的位置、所需數(shù)量、需求車型等.另外，每個(gè)客戶點(diǎn)都有兩種時(shí)間窗：最優(yōu)時(shí)間窗和松弛時(shí)間窗，如果服務(wù)車輛在客戶點(diǎn)的最優(yōu)時(shí)間窗口內(nèi)到達(dá)，客戶將完全滿意；如果在客戶規(guī)定的松弛時(shí)間窗內(nèi)到達(dá)，則需要根據(jù)車輛到達(dá)的時(shí)間計(jì)算客戶滿意度.因此，本文的主要目的是在考慮成本、客戶滿意度和環(huán)境因素的情況下找到最優(yōu)的解決方案.具體約束條件如(1) 車輛分為常溫車型與冷藏車型，每條路線的總負(fù)荷不得超過車輛的額定負(fù)荷，(2) 配送中心和客戶點(diǎn)的具體位置已知，(3) 每個(gè)客戶的需求貨物種類與數(shù)量已知，(4) 完成配送任務(wù)后，所有貨車必須返回配送中心，(5) 每個(gè)客戶只服務(wù)一次，(6) 服務(wù)車輛的車型要與客戶要求的車型一致，(7) 運(yùn)輸過程不考慮道路擁堵、天氣原因等狀況.

1.1 問題建模

(1) 集合.H={1,…,k}：可用車輛類型的集合，V={0,1,…,n}：節(jié)點(diǎn)集合，節(jié)點(diǎn)0代表配送中心，[1,…,n]代表客戶點(diǎn)，V'=V{0}.

(3) 決策變量.

1.2 成本分析

(1) 固定成本C1.當(dāng)使用車輛時(shí)，需要支付一些固定的費(fèi)用，包括司機(jī)的工資、卡車的損耗、道路維護(hù)費(fèi)用等等，由于每種車型的固定成本是不同的.因此在該模型中車輛的固定成本C1可以表示為

(1)

(2) 運(yùn)輸成本C2.車輛的運(yùn)輸成本主要與燃油消耗、維護(hù)保養(yǎng)等因素相關(guān)，與車輛行駛距離成正比

(2)

(3) 制冷成本C3.制冷成本公式可以表示為

(3)

(4) 碳排放成本C4.在運(yùn)輸和配送過程中，碳排放主要產(chǎn)生來(lái)源有兩個(gè)：運(yùn)輸途中燃料的排放和設(shè)備制冷產(chǎn)生的氣體排放.在本文中，燃料消耗在每單位距離的線性函數(shù)公式ρ(X)計(jì)算公式如

(4)

因此，運(yùn)輸過程中的碳排放量表示如

(5)

HVRPTW模型的碳排放成本公式為

(6)

(5) 貨損成本C5.公式D(t)=D0e-?t可以計(jì)算貨物的損失成本

(7)

1.3 問題模型

在本文中對(duì)冷鏈中帶時(shí)間窗與顧客滿意度的研究建立了以下多目標(biāo)優(yōu)化模型

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

EEti≤ti

(17)

(18)

t0=0,

(19)

(20)

(21)

約束條件(9)表示每種類型使用數(shù)量不能超出該車型的最大數(shù)量.約束條件(10)和(11)保證客戶點(diǎn)只被訪問一次.約束條件(12)每輛車必須離開車場(chǎng).約束條件(13)保證車輛在服務(wù)完后前往下一個(gè)客戶點(diǎn).約束條件(14)和(15)表示物品的流動(dòng)關(guān)系.約束條件(16)保證在每條路線上h型車輛總的裝載量不超過Qh.約束條件(17)保證車輛不違反客戶的時(shí)間窗.約束條件(18)和(19)表示客戶點(diǎn)的時(shí)間關(guān)系.約束條件(20)和(21)限定了變量取值范圍.

2 人工魚群算法

人工魚群(Artificial Fish Swarm，AFS)算法是李曉磊于2002年在其博士論文中提出的，是一種基于簡(jiǎn)化的魚群自然社會(huì)行為的模擬和群集理論[11].人工魚群算法有很多優(yōu)點(diǎn)：算法結(jié)構(gòu)簡(jiǎn)單，只使用目標(biāo)的函數(shù)值作為決策數(shù)據(jù)；計(jì)算速度快，即使有隨機(jī)因素的存在，算法也能快速計(jì)算出最佳位置.

人工魚群算法的優(yōu)化過程是通過多種基本行為來(lái)實(shí)現(xiàn)的，主要包括3個(gè)步驟：(1) 生成一組初始人工魚群，構(gòu)造初始種群解；(2) 每條人工魚都會(huì)經(jīng)歷以下四種行為：覓食、聚群、追尾和隨機(jī)行為，以獲得更好的位置與較高的食物濃度；(3) 使用公告板解決方案記錄到目前為止找到的最佳解決方案.

2.1 初始解的產(chǎn)生

在經(jīng)典的AFS算法中，可以初始化m個(gè)點(diǎn)，即m條人工魚X=(x1,x2,…,xm)用來(lái)識(shí)別有希望尋找全局解決方案的區(qū)域，其中xi為當(dāng)前魚狀態(tài).Yi=f(xi)為所在位置的食物濃度.人工魚個(gè)體i與j之間的距離用dij=‖xi-xj‖表示.AFS算法的關(guān)鍵問題是每條人工魚的感知距離，也被稱為“可視范圍”，用Visual進(jìn)行表示.Step表示人工魚移動(dòng)的最大步長(zhǎng).δ為擁擠度因子，δ∈(0,1).Try_number為人工魚的最大試探次數(shù)

xv=x+Visual·Rand(),

(22)

(23)

Rand()函數(shù)用于生成0到1之間的隨機(jī)數(shù).

2.2 覓食行為

在經(jīng)典AFS算法中，覓食行為用于生成當(dāng)前人工魚“可視范圍”內(nèi)的鄰域解.假設(shè)xi為當(dāng)前人工魚狀態(tài)，如果鄰域內(nèi)存在另一條人工魚，其狀態(tài)為xj，同時(shí)食物濃度Yi

(24)

2.3 聚群行為

假設(shè)為當(dāng)前人工魚xi，在其“視野范圍”內(nèi)的伙伴數(shù)目nf和中心位置xc，若Yc/nf>δYi，則表明中心位置有足夠的食物且不擁擠，同時(shí)Yi

(25)

2.4 追尾行為

人工魚xi可以在“可視范圍”內(nèi)選擇其他人工魚如最優(yōu)位置的人工魚，然后利用Ybest=f(xbest)計(jì)算最大食物濃度.在追尾行為中，xi位置狀態(tài)更新公式如

(26)

2.5 隨機(jī)行為

當(dāng)人工魚xi的“可視范圍”為空(沒有其他的人工魚可以追隨)或其他行為未執(zhí)行時(shí)，人工魚xi會(huì)隨機(jī)尋找另一個(gè)有食物的區(qū)域.

3 改進(jìn)人工魚群算法設(shè)計(jì)

在本節(jié)中，提出了一種改進(jìn)的人工魚群算法(Improved Artificial Fish Swarm，IAFS)來(lái)解決冷鏈物流中的HVRPTW問題.為了設(shè)計(jì)AFS算法的離散維數(shù)，將算法的所有步驟都進(jìn)行了離散化，包括編碼和解碼方法、初始化方法和經(jīng)典AFS算法的改進(jìn)行為.

3.1 問題編碼

本算法考慮了問題的特點(diǎn)和目標(biāo)，采用二維數(shù)組的方式編碼一個(gè)解，二維數(shù)組的第一維表示每一輛車，第二維表示每輛車服務(wù)客戶的序號(hào)和順序.例如，車隊(duì)包含8個(gè)客戶，兩種車輛類型，每種車型都有25輛車.第一類是沒有任何特殊裝置的常溫車型，第二類是裝有冷藏裝置的車型，圖1給出了一個(gè)編碼示例.每輛車都由一個(gè)數(shù)組表示，數(shù)組中包含該車輛服務(wù)的客戶序列，客戶序號(hào)的先后順序表示這些客戶點(diǎn)的服務(wù)次序.對(duì)于給定的8個(gè)客戶，將5個(gè)客戶{2,5,6,7,8}分給第一類車輛(常溫車)，將{1,3,4}分配給第二類車輛(冷藏車).然后按照順序?qū)2,7,6}分配到同一輛車上，將{5,8}分配到相同類型的另一輛車上.

3.2 問題解碼

對(duì)于3.1小節(jié)中的編碼，解碼如甘特圖2所示，將所有客戶點(diǎn)逐一分配到相應(yīng)的車輛上.同時(shí)，在解碼過程中需要考慮兩對(duì)客戶之間的距離、每個(gè)客戶接受服務(wù)的最早和最晚時(shí)間，客戶的滿意程度，每個(gè)客戶的服務(wù)時(shí)長(zhǎng)、車輛容量、以及每輛車的最大裝載能力.同時(shí)，在解碼過程中，最重要的任務(wù)之一是計(jì)算客戶滿意度，并將其加入到問題目標(biāo)函數(shù)中.

3.3 改進(jìn)的覓食行為

在經(jīng)典的AFS算法中，覓食行為用于為每個(gè)選擇的解生成鄰近解.然而，AFS算法中的覓食行為僅適用于連續(xù)優(yōu)化問題，為了使其適用于求解離散優(yōu)化問題，提出了一種改進(jìn)的覓食行為，具體如：Step 1：循環(huán)初始解集的每一個(gè)解xi，根據(jù)“可視范圍”確定解的鄰域解集.Step 2：如果當(dāng)前解xi在“可視范圍”內(nèi)隨機(jī)選擇一個(gè)解xj，xj如果的目標(biāo)值比xi優(yōu)秀，則xi向xj方向移動(dòng)，即xi與xj進(jìn)行交叉操作.Step 3：在公告板更新最好解.Step 4：更新xi的嘗試次數(shù)Try_number.在改進(jìn)的覓食行為中，對(duì)現(xiàn)有的人工魚xi采取兩種策略：(1) 策略I. Step 1：為了生成鄰域解，隨機(jī)選擇一種車型，對(duì)所選車型隨機(jī)選擇一輛車，然后從中隨機(jī)選擇一個(gè)客戶，并將其在所選車輛中刪除.Step 2：將所選客戶插入到同類型的另一輛車中.在策略I中，將客戶插入到當(dāng)前解決方案的時(shí)間復(fù)雜度為O(n2)，假設(shè)要重新插入的客戶數(shù)量為(1/r)×n，其中r為選擇的速率，則該策略的時(shí)間復(fù)雜度為O(n3).(2) 策略Ⅱ. Step 1：為了生成鄰域解，與策略I相同，隨機(jī)選擇一輛車，然后從所選車輛中隨機(jī)選擇一定數(shù)量的客戶并將這些客戶從當(dāng)前車輛中刪除.Step 2：將選擇的客戶隨機(jī)插入到相同車型的其他車輛中.策略Ⅱ中的改進(jìn)的覓食行為過程如圖3.兩種覓食啟發(fā)式在該改進(jìn)算法中是隨機(jī)選擇使用的.

3.4 改進(jìn)的追尾行為

在經(jīng)典的AFS算法中，追尾行為是使當(dāng)前的解決方案從相鄰的解決方案中學(xué)習(xí)以增強(qiáng)算法收斂的快速性和全局性.在經(jīng)典的追尾行為中，如果“可視范圍”內(nèi)不擁擠，且中心點(diǎn)在“可視范圍”中具有最佳的目標(biāo)函數(shù)值，則趨向于中心點(diǎn)移動(dòng).然而，典型的AFS算法是針對(duì)連續(xù)優(yōu)化問題的，為了使AFS算法更適應(yīng)于求解離散的優(yōu)化問題，提出了離散追尾行為.在改進(jìn)的追尾行為中有以下兩種交叉方式.

第一種改進(jìn)交叉：主要思想是刪除其他父代個(gè)體中路線上出現(xiàn)的客戶，然后將它們插入到當(dāng)前父代個(gè)體最佳位置形成新的解決方案.具體步驟：(1) 隨機(jī)選擇兩個(gè)父代解p1、p2；(2) 從p2中選擇一定數(shù)量的車輛，并將這些車輛上的客戶存儲(chǔ)到集合D中；(3) 將D中的所有客戶從p1中刪除，利用PFIH啟發(fā)式將這些被刪除的客戶插入到最優(yōu)位置.

圖4顯示了p1和p2交叉的過程.首先，從p2中按一定比例選擇了一些客戶，一共10個(gè)客戶，被選擇的客戶數(shù)量為1/m(m=2)，即5個(gè)客戶.將這5個(gè)客戶從p1的路徑中移除，然后重新計(jì)算最佳插入位置，將客戶插入到p1中.交叉的時(shí)間復(fù)雜度為O(n).

第二種交叉的步驟：(1) 隨機(jī)選擇兩個(gè)父代解p1、p2；(2) 子代解的第一種車輛向其中一個(gè)父代解學(xué)習(xí)，另一種車輛向另一種父代解學(xué)習(xí).圖5為交叉的具體步驟，給出了兩個(gè)父代解，然后從p1取常溫車輛，從p2取出冷藏車輛，從而得到相鄰解.在本文中，交叉算子不需要進(jìn)行任何修復(fù)過程就可以生成一個(gè)可行解.

在該算法中，這兩種交叉算子都是隨機(jī)選擇的，然后當(dāng)前的人工魚以概率Pc向“可視范圍”內(nèi)的魚群中心(最佳點(diǎn))移動(dòng)，或以1-Pc概率隨機(jī)向鄰近解移動(dòng).改進(jìn)后的追尾行為可以在一定概率范圍內(nèi)學(xué)習(xí)最優(yōu)解，從而具有跳出局部最優(yōu)解的能力.

第二種交叉算法框架：Step 1：選擇當(dāng)前解xi的普通車輛部分，選擇“可視范圍”內(nèi)最優(yōu)解xbest的冷鏈車部分，將兩部分組合起來(lái)；Step 2：如果xi的冷鏈車數(shù)量大于xbest的冷藏車數(shù)量，則全部復(fù)制，刪去多余車輛；Step 3：選擇當(dāng)前解xi的冷藏車輛，選擇“可視范圍”內(nèi)最優(yōu)解xbest的常溫車部分，將兩部分組合起來(lái)；Step 4：如果xbest的冷藏車數(shù)量大于xi的冷鏈車數(shù)量，則全部復(fù)制，刪去多余車輛；Step 5：原有目標(biāo)值與重組后目標(biāo)值進(jìn)行比較，將最好解更新至公告板.

綜上，改進(jìn)的追尾行為算法框架.Step 1：循環(huán)初始解集的每一個(gè)解xi，根據(jù)“可視范圍”確定解的鄰域解集；Step 2：如果“可視范圍”內(nèi)存在最優(yōu)解xbest，當(dāng)xi周圍不是很擁擠，且xbest的目標(biāo)值比xi優(yōu)秀，則xi向xbest移動(dòng)，即xi與xbest進(jìn)行交叉操作；Step 3：在公告板更新最好解；Step 4：如果移動(dòng)不成功，則執(zhí)行覓食行為.

3.5 算法框架

改進(jìn)的人工魚群算法框架.Step 1：設(shè)置系統(tǒng)參數(shù)；Step 2：使用初始解生成策略初始化一個(gè)解決方案，對(duì)每個(gè)可行解進(jìn)行評(píng)估；Step 3：采用車輛等待策略以提高客戶滿意度；Step 4：不滿足停止條件時(shí)，執(zhí)行下一步；Step 5：對(duì)于當(dāng)前種群中的每個(gè)解進(jìn)行局部搜索：Step 5.1：執(zhí)行改進(jìn)的覓食行為；Step 5.2：如果新生成的解決方案比前一個(gè)好，則替換成當(dāng)前找到的最佳解決方案.Step 6：對(duì)于種群中的每個(gè)解，執(zhí)行以下全局搜索：Step 6.1：執(zhí)行改進(jìn)的追尾行為；Step 6.2：如果新生成的解決方案比前一個(gè)更好，則替換到目前為止找到的最佳解決方案.

4 試驗(yàn)分析

4.1 算例描述

SOLOMON算例是一種經(jīng)典的VRPTW算例，它由56個(gè)算例組成，每個(gè)算例中又包含了100個(gè)客戶點(diǎn)的詳細(xì)信息.其中，算例中客戶點(diǎn)的布局分為三類，分別是：具有高聚集度的Clustering系列17個(gè)，簡(jiǎn)稱C系列算例；具有分散聚集度的Random系列算例23個(gè)，簡(jiǎn)稱R系列算例；以及，中等聚集度的RC系列算例16個(gè).表1給出了算例說(shuō)明.

表1 算例說(shuō)明

圖6顯示了 SOLOMON經(jīng)典算例C101與R101的客戶點(diǎn)分布圖的特點(diǎn).在多車型的冷鏈物流中，需要將冷藏貨物與常溫貨物進(jìn)行區(qū)別，這是與SOLOMON經(jīng)典算例的一個(gè)很大的區(qū)別.因此，本文在SOLOMON經(jīng)典算例的基礎(chǔ)之上改進(jìn)了客戶的需求，增加了貨物需求標(biāo)志，其中需求普通貨物的客戶設(shè)置標(biāo)志0，需求冷藏貨物的客戶設(shè)置標(biāo)志1.同時(shí)，在擴(kuò)展的經(jīng)典SOLOMON算例中，將普通客戶與冷藏客戶的數(shù)量采用1:1到1:5之間隨機(jī)生成的方法.擴(kuò)展的55個(gè)SOLOMON算例將重新命名為“cc101”到“crc207”.但cc系列、cr系列和rcr系列這三類算例的主要特點(diǎn)與原有算例的特點(diǎn)保持一致，沒有發(fā)生改變.

經(jīng)典SOLOMON算例與擴(kuò)展算例的主要區(qū)別如下：(1) 所有車輛分為兩類：常溫車輛和冷藏車輛；(2) 所有的客戶也分為兩類：只需要常溫車輛運(yùn)輸常溫產(chǎn)品的普通客戶和需要用冷藏車輛運(yùn)輸冷凍貨物的特殊客戶；(3) 兩類車型的容量和能耗能不同.

表2 車輛數(shù)據(jù)示例

4.2 實(shí)驗(yàn)參數(shù)

在本實(shí)驗(yàn)中，主要參數(shù)有三個(gè)，包括Ra：鄰域的半徑，即人工魚的“可視范圍”visual.如果Ra=0.2，則表示一條人工魚的“可視范圍”是整個(gè)魚群大小的20%.Ra越大，所涉及的鄰域越大，當(dāng)Ra=1時(shí)表示整個(gè)種群屬于單個(gè)鄰域范圍.(2)Cr：擁擠參數(shù)；(3)Pc：跟隨概率.根據(jù)詳細(xì)的實(shí)驗(yàn)和已發(fā)表文獻(xiàn)的參數(shù)對(duì)各個(gè)參數(shù)進(jìn)行賦值，各參數(shù)的參數(shù)級(jí)別均設(shè)置為{0.2,0.4,0.6,0.9}.表3給出了參數(shù)水平表.

采用實(shí)驗(yàn)設(shè)計(jì)DOE Taguchi方法構(gòu)造了一套正交陣列L16對(duì)參數(shù)進(jìn)行組合，對(duì)于每個(gè)參數(shù)組合，使用IAFS算法獨(dú)立運(yùn)行30次并收集算法獲得的平均適應(yīng)度值作為響應(yīng)變量(Response Variable，RV).圖7給出了因子水平和交點(diǎn).經(jīng)過計(jì)算，IAFS算法表現(xiàn)最優(yōu)的參數(shù)組合為Ra=0.2、Cr=0.6、Pc=0.2.同時(shí)，設(shè)置目標(biāo)權(quán)重α=0.2.

表3 參數(shù)水平表

4.3 與其他算法的比較

為了檢驗(yàn)IAFS算法的性能，本文選擇了三種經(jīng)典的比較算法：混合進(jìn)化算法(Hybrid Evolutionary Algorithm，HEA)[12]、禁忌搜索算法(Tabu Search，TS)[13]和自適應(yīng)大鄰域搜索啟發(fā)式算法(Adaptive Large Neighborhood Search Heuristic, ALNS)[14].選擇這三個(gè)算法作為比較算法的主要原因是針對(duì)異構(gòu)車隊(duì)約束條件下的VRPTW問題，HEA、TS以及ALNS是求解VRPTW問題常用算法.由于本文考慮的HVRPTW問題是VRPTW問題的一個(gè)擴(kuò)展版本，只需這三種比較算法進(jìn)行簡(jiǎn)單地?cái)U(kuò)展即可解決所考慮的問題.因此，在本研究中，將HEA、ALNS和TS算法在文獻(xiàn)中提出的主要組件進(jìn)行了重新編碼，并對(duì)其進(jìn)行了修改，以適應(yīng)于求解HVRPTW問題.為了進(jìn)行更公平的對(duì)比，對(duì)所有比較的算法進(jìn)行了重新編碼，并對(duì)其文獻(xiàn)中的主要成分和參數(shù)進(jìn)行了調(diào)整.此外，為了獲得一個(gè)公允的結(jié)果，在相同的設(shè)備下，將四種比較算法進(jìn)行了30次獨(dú)立運(yùn)行，并收集每個(gè)算例的最優(yōu)值進(jìn)行詳細(xì)地比較.

表4顯示了四種算法的比較結(jié)果，其中第三列到第六列分別為HEA、TS、ALNS算法和IAFS算法這四種比較算法對(duì)應(yīng)每個(gè)算例的結(jié)果，并將同一算例中的最優(yōu)值記錄在表中的第二列.最后四列顯示了這四種比較算法的結(jié)果與最優(yōu)值之間的dev偏差.由表4中數(shù)據(jù)顯示：在給定的55個(gè)算例中，所提出的IAFS算法獲得了41個(gè)最優(yōu)值，找到最優(yōu)值的數(shù)量占總算例的74.5%，而排名第二的TS算法只得到8個(gè)最優(yōu)值；表中最后一行為各個(gè)算法的平均性能，其中IAFS算法的dev偏差僅為1.55，而次優(yōu)算法TS的dev偏差卻為12.59；同時(shí)，與最近發(fā)表ALNS算法比較，可以從數(shù)據(jù)中得到ALNS算法的dev偏差為16.02，約為IAFS算法的10倍，充分證明了IAFS算法的求解能力.最后，將這四種算法進(jìn)行多重比較，并通過方差分析得到了ANOVA分析圖(圖8)，進(jìn)一步驗(yàn)證了IAFS求解問題的性能明顯優(yōu)于其他三種算法.

此外，為了證明IAFS算法的收斂能力，進(jìn)行詳細(xì)的對(duì)比實(shí)驗(yàn).針對(duì)ALNS與IAFS算法，選取crc103算例，對(duì)解決方案進(jìn)行數(shù)據(jù)收斂實(shí)驗(yàn)，圖9顯示出兩種算法的收斂性能.通過比較可以直觀地看出，IAFS算法對(duì)求解HVRPTW問題具突出的收斂能力.

在圖10的甘特圖中，顯示了算例“cc101”的求解結(jié)果，其中兩種不同的顏色矩形代表了兩種需要不同車型進(jìn)行服務(wù)的客戶點(diǎn)，客戶點(diǎn)下面的數(shù)字是車輛完成該客戶點(diǎn)服務(wù)的時(shí)間.例如，最上面一行中的客戶點(diǎn)81則是使用冷藏車.因此，圖10可證明IAFS算法對(duì)求解“cc101”算例是可行的.

表4 IAFS算法與其他算法的對(duì)比結(jié)果

續(xù)表4 IAFS算法與其他算法的對(duì)比結(jié)果

5 結(jié)論

針對(duì)冷鏈物流中VRPTW問題，采用改進(jìn)人工魚群算法進(jìn)行求解.分析了該算法的主要四個(gè)行為，并對(duì)算法進(jìn)行了改進(jìn)用于求解所提出的多車型冷鏈車輛路徑問題.在IAFS算法中，首先設(shè)計(jì)了一種特殊的編碼方法來(lái)考慮不同類型車輛的問題特征，接著通過改進(jìn)的覓食行為和改進(jìn)的追尾行為使算法更適用于求解離散優(yōu)化問題.同時(shí)，通過改進(jìn)的追尾行為在一定的概率范圍內(nèi)學(xué)習(xí)最優(yōu)解，具備了跳出局部最優(yōu)解的能力.為了驗(yàn)證改進(jìn)后算法的性能，采用擴(kuò)展的SOLOMON算例進(jìn)行了驗(yàn)證，選擇了三種經(jīng)典的算法與IAFS算法進(jìn)行了充分的對(duì)比實(shí)驗(yàn)，豐富的實(shí)驗(yàn)證明了所提出的IAFS算法對(duì)于求解多車型的冷鏈車輛路徑問題具有良好的性能.未來(lái)的研究工作主要集中于進(jìn)一步提升算法全局搜索和局部搜索能力方面.