一種改進人工魚群算法求解冷鏈中車輛路徑問題

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

(聊城大學 計算機學院，山東 聊城 252059)

0 引言

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

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

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

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

1 問題描述

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

1.1 問題建模

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

(3) 決策變量.

1.2 成本分析

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

(1)

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

(2)

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

(3)

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

(4)

因此，運輸過程中的碳排放量表示如

(5)

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

(6)

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

(7)

1.3 問題模型

在本文中對冷鏈中帶時間窗與顧客滿意度的研究建立了以下多目標優(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)保證客戶點只被訪問一次.約束條件(12)每輛車必須離開車場.約束條件(13)保證車輛在服務完后前往下一個客戶點.約束條件(14)和(15)表示物品的流動關系.約束條件(16)保證在每條路線上h型車輛總的裝載量不超過Qh.約束條件(17)保證車輛不違反客戶的時間窗.約束條件(18)和(19)表示客戶點的時間關系.約束條件(20)和(21)限定了變量取值范圍.

2 人工魚群算法

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

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

2.1 初始解的產生

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

xv=x+Visual·Rand(),

(22)

(23)

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

2.2 覓食行為

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

(24)

2.3 聚群行為

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

(25)

2.4 追尾行為

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

(26)

2.5 隨機行為

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

3 改進人工魚群算法設計

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

3.1 問題編碼

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

3.2 問題解碼

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

3.3 改進的覓食行為

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

3.4 改進的追尾行為

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

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

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

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

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

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

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

3.5 算法框架

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

4 試驗分析

4.1 算例描述

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

表1 算例說明

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

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

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

4.2 實驗參數(shù)

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

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

表3 參數(shù)水平表

4.3 與其他算法的比較

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

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

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

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

表4 IAFS算法與其他算法的對比結果

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

5 結論

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