李 珺，郝麗艷，何奕濤，段鈺蓉

（蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 730070）

0 概述

車輛路徑問題（Vehicle Routing Problem，VRP）一直是物流配送活動中的基本問題，受到國內(nèi)外學(xué)者的廣泛關(guān)注。隨著電子商務(wù)的發(fā)展以及客戶需求的提高，企業(yè)在設(shè)計物流系統(tǒng)時需要在規(guī)定時間窗內(nèi)完成服務(wù)，從而提高服務(wù)水平。帶時間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）是經(jīng)典VRP 問題的一個重要擴(kuò)展，每個顧客有預(yù)先設(shè)定的時間窗，車輛不能早于顧客允許的最早服務(wù)時間提供服務(wù)，也不能晚于顧客允許的最晚服務(wù)時間提供服務(wù)。

求解VRPTW 問題的算法大致可以分為精確算法和啟發(fā)式算法兩類。精確算法在理論上可以找到問題的最優(yōu)解，但由于在實際應(yīng)用中消耗的空間和時間成本較大，因此計算機(jī)內(nèi)存要求較高，僅適用于求解較小規(guī)模的路徑優(yōu)化問題。啟發(fā)式算法不管是求解小規(guī)模的問題還是大規(guī)模的問題，都能夠在一定范圍和較短的時間內(nèi)給出滿意解或最優(yōu)解。因此，目前相關(guān)領(lǐng)域的學(xué)者專注于設(shè)計不同的啟發(fā)式算法尋找該問題的近似最優(yōu)解，特別是對現(xiàn)代啟發(fā)式算法的研究。文獻(xiàn)［1］利用分布式多agent系統(tǒng)實現(xiàn)分布式求解VRPTW問題。文獻(xiàn)［2］介紹基于量子蟻群算法的VRPTW 問題。文獻(xiàn)［3］介紹一種求解VRPTW 問題的離散粒子群算法。文獻(xiàn)［4］介紹改進(jìn)的蟻群算法求解帶時間窗的車輛路徑問題。文獻(xiàn)［5］介紹一種新的求解帶時間窗車輛路徑問題的遺傳算法。文獻(xiàn)［6］介紹考慮載荷約束的求解時間窗車輛路徑問題的遺傳算法。

目前，還有一些學(xué)者采用深度強(qiáng)化學(xué)習(xí)方法求解車輛路徑問題。文獻(xiàn)［7］提出一個基于深度強(qiáng)化學(xué)習(xí)框架的改進(jìn)啟發(fā)式規(guī)劃方法來求解車輛路徑問題。通過設(shè)計基于自我關(guān)注的深層架構(gòu)策略網(wǎng)絡(luò)，指導(dǎo)下一步解決方案的選擇。學(xué)習(xí)到的策略能很好地概括不同的初始解和問題規(guī)模，并在實際數(shù)據(jù)集上給出了較好的解決方案。文獻(xiàn)［8］提出一種基于緊急程度的插入啟發(fā)式算法來構(gòu)造初始解，在局部搜索改進(jìn)階段使用強(qiáng)化學(xué)習(xí)來指導(dǎo)搜索。實驗結(jié)果表明，基于單個解的算法中的抽樣方案并沒有顯著提高解的質(zhì)量，但是可以大幅降低搜索過程中發(fā)現(xiàn)的不可行解的比例，在大規(guī)模搜索空間內(nèi)具有很強(qiáng)的搜索能力。文獻(xiàn)［9］提出一種具有動態(tài)編譯碼結(jié)構(gòu)的動態(tài)關(guān)注模型，該模型能夠在不同的構(gòu)建步驟中動態(tài)探索節(jié)點特征并有效挖掘隱藏的結(jié)構(gòu)信息，但是訓(xùn)練階段比較耗時，僅可針對中小規(guī)模問題實例進(jìn)行訓(xùn)練。文獻(xiàn)［10］使用基于蒙特卡羅預(yù)測及深度策略梯度學(xué)習(xí)的智能車輛路徑規(guī)劃方法，設(shè)計一種基于環(huán)境感知預(yù)測、行為決策和控制序列生成的深度強(qiáng)化學(xué)習(xí)框架，并將多個單一的強(qiáng)化學(xué)習(xí)算法應(yīng)用到智能車路徑規(guī)劃系統(tǒng)的不同子任務(wù)中。實驗結(jié)果驗證了車輛具有的預(yù)估風(fēng)險能力，并以盡量大的安全距離調(diào)整車輛狀態(tài)，行駛時有更加連續(xù)的轉(zhuǎn)角控制序列，實現(xiàn)快速、安全、平穩(wěn)的路徑規(guī)劃。文獻(xiàn)［11］提出一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)式算法，設(shè)計算法的高層啟發(fā)式策略，包括選擇策略和解的接收準(zhǔn)則，算法在實驗求解過程中整體性能較好，但在客戶規(guī)模較大的車輛路徑問題上仍具有改進(jìn)空間。目前，關(guān)于使用深度強(qiáng)化學(xué)習(xí)方法求解VRPTW 問題的研究相對較少，可進(jìn)行更深入的探討。

細(xì)菌覓食算法（Bacterial Foraging Algorithm，BFA）作為現(xiàn)代啟發(fā)式算法之一，是由PASSINO［12］于2002 年提出的一種仿生隨機(jī)搜索算法，具有局部搜索能力強(qiáng)、并行搜索、實現(xiàn)簡單等優(yōu)點，目前已在優(yōu)化計算、圖像處理、模式識別、系統(tǒng)仿真、人臉識別等領(lǐng)域得到廣泛應(yīng)用［13-15］。本文提出一種改進(jìn)的細(xì)菌覓食算法來求解VRPTW 問題，使用K-means 算法根據(jù)地理位置對待配送點進(jìn)行聚類，依據(jù)聚類結(jié)果采用貪婪插入法生成初始解。將細(xì)菌覓食的趨化操作與大鄰域搜索相結(jié)合，設(shè)計4 種removal 算子進(jìn)行尋優(yōu)，擴(kuò)大搜素范圍，在不增加時間復(fù)雜度的情況下，提高收斂精度。

1 考慮時間窗的車輛路徑優(yōu)化問題

VRPTW 問題描述：有一定數(shù)量的相同型號的車輛，從中心倉庫出發(fā)，對若干個客戶節(jié)點進(jìn)行服務(wù)，要求滿足約束條件，合理安排配送路徑，使總配送成本最小。基本假設(shè)如下：

式（1）表示最小化車輛總行程；式（2）表示每個客戶僅被一輛車服務(wù)一次；式（3）表示每輛車的行駛距離都不得超過最大行駛距離；式（4）表示每個客戶只被同一輛車服務(wù)；式（5）表示車輛從配送中心出發(fā)最終必須再回到配送中心；式（6）表示每輛車配送的客戶總需求量不得超過車輛最大載重；式（7）表示客戶i的開始服務(wù)時間必須滿足給定的時間窗；式（8）表示消除子回環(huán)。

2 改進(jìn)的細(xì)菌覓食算法

改進(jìn)的細(xì)菌覓食算法（Improved Bacterial Foraging Algorithm，IBFA）是在細(xì)菌覓食算法的基礎(chǔ)上結(jié)合大鄰域搜索（Large Neighborhood Search，LNS）的優(yōu)化算法［16-18］。該算法主要通過趨化操作、復(fù)制操作和遷徙操作的迭代計算來搜索問題的最優(yōu)解。趨化操作是算法的核心操作，因此本文在趨化操作中結(jié)合了大鄰域搜索算法中的removal 算子，運用4 種removal 算子進(jìn)行尋優(yōu)，擴(kuò)大細(xì)菌的搜索范圍。大鄰域搜索算法由SHAW［19］于1998年提出，克服局部搜索的缺陷，提高BFA優(yōu)化能力，能夠更快地找到最優(yōu)解，對于求解VRPTW問題十分有效。

2.1 編碼

本文采用非負(fù)整數(shù)編碼方式表示解空間，配送中心編號為0，客戶節(jié)點編號為1，2，…，N，令S=［S1，S2，…，SK］（K為車輛數(shù)目）為VRPTW 問題的一組可行解，假設(shè)車輛路徑規(guī)劃為S=［S1，S2］=［｛0，3，2，8，7，6，0｝，｛0，1，4，5，9，0｝］，第1 條路徑從配送中心出發(fā)，服務(wù)客戶3、2、8、7、6 后回到配送中心，第2 條路徑從配送中心出發(fā)，服務(wù)客戶節(jié)點1、4、5、9 后回到配送中心，如圖1 所示。

圖1 配送示意圖Fig.1 Schematic diagram of distribution

2.2 初始解構(gòu)造

本文采用基于K-means 算法的貪婪插入法構(gòu)造VRPTW 問題的初始解。在運用貪婪插入法構(gòu)造初始解時，由于前期客戶的插入次序?qū)獾臉?gòu)造有較大影響，因此使用K-means 算法對客戶節(jié)點進(jìn)行預(yù)處理，其中V為配送中心所擁有的最大車輛數(shù)目，k為隨機(jī)選取該范圍中的一個整數(shù)，利用客戶節(jié)點的位置信息對客戶節(jié)點聚類，根據(jù)聚類結(jié)果產(chǎn)生客戶的插入序列，使用貪婪插入法生成路徑。貪婪插入法首先構(gòu)建一條從配送中心出發(fā)再返回配送中心的路徑，即［0，0］，然后運用K-means 算法排列好的客戶節(jié)點依次插入路徑中的最佳位置，當(dāng)路徑中無法再插入新客戶時，重新構(gòu)建一條［0，0］的路徑，重復(fù)上述操作，直到所有客戶都插入為止。

為驗證采用K-means 構(gòu)造初始解對算法的影響，本文選取Solomon 測試集中的R211 算例進(jìn)行驗證。測試集共100 個客戶節(jié)點，車輛載重為1 000，使用K-means 算法聚類后的客戶排列順序和原始客戶集中的客戶排列順序分別生成初始解，共進(jìn)行10 次實驗，采用K-means 聚類后得到的最終解平均值為782.43，使用初始客戶集生成最終解的平均值為791.08。圖2 給出了使用K-means 算法得到的最優(yōu)解構(gòu)造的初始路徑。圖3 給出了使用原始序列得到的最優(yōu)解構(gòu)造的初始路徑。實驗結(jié)果表明，使用K-means算法對客戶集進(jìn)行預(yù)處理得到的解更優(yōu)。

圖2 基于K-means 算法最優(yōu)解的初始路徑Fig.2 Initial path based on the optimal solution obtained by the K-means algorithm

圖3 基于原始序列最優(yōu)解的初始路徑Fig.3 Initial path based on the optimal solution obtained by the original sequence

2.3 趨化操作改進(jìn)

在細(xì)菌覓食優(yōu)化算法中，對問題的解空間進(jìn)行尋優(yōu)的核心操作是趨化操作，包括旋轉(zhuǎn)和游動。細(xì)菌向任意方向移動單位步長定義為旋轉(zhuǎn)。旋轉(zhuǎn)后計算適應(yīng)度值，若得到的路徑適應(yīng)度值更小則繼續(xù)沿著該方向游動，直到達(dá)到最大步長或者適應(yīng)度值不發(fā)生改變，此過程稱為游動。由于細(xì)菌的步長和方向會影響到尋優(yōu)效果，因此本文結(jié)合VRPTW 問題的特性，將大鄰域搜索中的removal 算子結(jié)合到趨化操作中。為達(dá)到更好的搜索效果，共設(shè)計4 種removal算子，分別為Random removal算子、Least profit removal 算 子、Route removal 算子和Relatedness removal 算子。這4 種算子作為細(xì)菌游動的方向，游動步長設(shè)置為m。用輪盤賭方法選擇一種removal算子，用來模擬細(xì)菌在旋轉(zhuǎn)過程中任意選擇的方向，確定方向后進(jìn)行移除插入操作。如果該算子取得的適應(yīng)度值變好，則繼續(xù)采用，直到達(dá)到細(xì)菌的最大游動次數(shù)，此過程模擬了細(xì)菌在該方向上的游動。若旋轉(zhuǎn)后適應(yīng)度值沒有改善，則選擇另一個removal 算子，即另一個方向，繼續(xù)進(jìn)行游動。每個細(xì)菌都從旋轉(zhuǎn)操作開始，在達(dá)到趨化算子次數(shù)前不斷反復(fù)交替執(zhí)行旋轉(zhuǎn)和游動操作，更新路徑。將removal 算子應(yīng)用到趨化操作中，擴(kuò)大搜索范圍，有利于局部搜索。在移除了m個客戶節(jié)點后，運用之前的貪婪插入法重新將移除的客戶進(jìn)行插入。

下面以一個Solomom 數(shù)據(jù)集中的實例說明利用removal 算子尋優(yōu)。假設(shè)VRPTW 的配送中心和客戶節(jié)點信息如表1 所示，編號0 表示配送中心，編號1～9表示客戶節(jié)點，每輛車的載重為100。采用貪心策略插入法生成的細(xì)菌個體為S=［｛0，8，3，9，5，0｝，｛0，1，7，2，4，0｝，｛0，6，0｝］，即由三輛車配送，適應(yīng)度值為328.883 0。removal 算子的移除個數(shù)m=3，最大游動次數(shù)為4。

表1 配送中心及客戶節(jié)點信息Table 1 Information of distribution center and customer nodes

假設(shè)選定Random removal算子第一次游動移除的客戶節(jié)點為7、2、8，在之前生成的解S中找到7、2、8 并將其移除，移除后的路徑Snew=［｛0，3，9，5，0｝，｛0，1，4，0｝，｛0，6，0｝］。首先，插入客戶節(jié)點7，在滿足約束條件后，在每條路徑中插入的具有最小配送成本的最佳位置如圖4 所示。客戶節(jié)點7 插入3 條路徑最佳位置的適應(yīng)度值分別為354.033 4、301.987 5、273.882 6，通過比較得出最小適應(yīng)度值為273.882 6，因此將客戶節(jié)點插入路徑3，此時Snew=［｛0，3，9，5，0｝，｛0，1，4，0｝，｛0，7，6，0｝］。然后，插入客戶節(jié)點2，在滿足約束條件后，在每條路徑中插入的具有最小配送成本的最佳位置如圖5所示?？蛻艄?jié)點2 插入3 條路徑最佳位置的適應(yīng)度值分別355.298 4、293.456 7、374.964 9，通過比較得出最小適應(yīng)度值為293.456 7，因此將客戶節(jié)點2插入路徑2，此時Snew=［｛0，3，9，5，0｝，｛0，1，2，4，0｝，｛0，7，6，0｝］。最后，插入客戶節(jié)點8，在滿足約束條件后，在每條路徑中插入的具有最小配送成本的最佳位置如圖6 所示。客戶節(jié)點8 插入3 條路徑最佳位置的適應(yīng)度值分別296.257 3、319.856 7、326.907 1，通過比較得出最小適應(yīng)度值為296.257 3，因此將客戶節(jié)點8 插入路徑1，此時Snew=［｛0，8，3，9，5，0｝，｛0，1，2，4，0｝，｛0，7，6，0｝］。Snew的適應(yīng)度值為296.257 3，S的適應(yīng)度值為328.883 0，經(jīng)過比較，Snew的適應(yīng)度值較小，則用Snew的位置更新S，繼續(xù)采用removal算子進(jìn)行局部尋優(yōu)，直到達(dá)到最大游動次數(shù)。如果該removal算子沒有改善適應(yīng)度值，則維持S的位置不變，結(jié)束此次游動，細(xì)菌進(jìn)行翻轉(zhuǎn)，用另一個removal 算子進(jìn)行第二次游動，重復(fù)以上操作，直到適應(yīng)度值不再發(fā)生改變。

圖4 客戶節(jié)點7 插入每條路徑的最佳位置Fig.4 The best position for inserting client node 7 into each path

圖5 客戶節(jié)點2 插入每條路徑的最佳位置Fig.5 The best position for inserting client node 2 into each path

圖6 客戶節(jié)點8 插入每條路徑的最佳位置Fig.6 The best position for inserting client node 8 into each path

圖7 和圖8 分別給出了初始路徑和經(jīng)過趨化操作的改進(jìn)路徑。

圖7 初始路徑Fig.7 Initial path

圖8 經(jīng)過趨化操作的改進(jìn)路徑Fig.8 Improved path after chemotaxis

4 種removal 算子的具體描述如下：

1）Random removal 算子。該算子是隨機(jī)選擇q個客戶節(jié)點進(jìn)行移除，再將其進(jìn)行插入。該算子的隨機(jī)性增加了搜索的多樣性。

2）Least profit removal 算子。該算子主要移除成本較高的客戶，給定一個客戶i和一個解s，定義客戶節(jié)點i的成本為Ci(s)=f(s)-f-i(s)，其中f-i(s)表示移除客戶節(jié)點i之后的適應(yīng)度值，對C(s)值進(jìn)行降序排列，選擇成本較高的q個客戶節(jié)點進(jìn)行移除。

3）Route removal 算子。該算子主要是減少尋優(yōu)過程中車輛的使用數(shù)目，選取配送客戶節(jié)點較少的車輛中的客戶節(jié)點進(jìn)行移除。在采用Route removal算子進(jìn)行局部搜索過程中，可以發(fā)現(xiàn)某些車輛所服務(wù)的客戶節(jié)點數(shù)量非常少，這樣對車輛資源造成較大的浪費，也不利于總配送路徑的減少。因此，在Route removal 算子中應(yīng)該優(yōu)先移除這些車輛配送數(shù)目較少的客戶節(jié)點，再將移除的客戶節(jié)點用貪婪插入策略重新插入路徑中。

4）Relatedness removal 算子。該算子移除相關(guān)性較高的客戶節(jié)點，根據(jù)兩個客戶節(jié)點i和j的距離Cij、送貨需求的差異|Di-Dj|以及兩個客戶的最早開始時間|Ei-Ej|的差異來衡量兩個客戶節(jié)點i和j的相關(guān)性。每個局部相關(guān)性度量分別使用α、β、γ進(jìn)行加權(quán)，并對問題實例給出的所有客戶S集合的各個極值進(jìn)行歸一化。因此，兩個客戶節(jié)點i和j的相關(guān)性度量Rij表示如下：

其中：max（Cij）是任意兩個客戶之間的最大距離；max（Di）是交付的最大需求值；min（Di）是交付的最小需求值；max（Ei）是客戶開始服務(wù)時間的最大值，min（Ei）是客戶開始服務(wù)時間的最小值。對任意兩個客戶節(jié)點間的相關(guān)性進(jìn)行排序，移除相關(guān)性較大的q個客戶節(jié)點，重新將它們插入到路徑中，從而得到新的解決方案。

2.4 算法流程

改進(jìn)的細(xì)菌覓食算法步驟具體如下：

1）初始化參數(shù)。初始化細(xì)菌種群數(shù)目N、趨化操作次數(shù)Nc、最大游動次數(shù)Ns、復(fù)制次數(shù)Nre、遷徙次數(shù)Ned、遷徙概率Ped、removal 算子中的移除個數(shù)q，根據(jù)基于K-means 的貪婪插入法構(gòu)造初始解。

2）對種群中的所有細(xì)菌個體進(jìn)行趨化操作。

3）對細(xì)菌的適應(yīng)度值進(jìn)行評價并按照升序排列。將前面N/2 個細(xì)菌個體的位置復(fù)制給排列在后面的N/2 個細(xì)菌個體。

4）為每個細(xì)菌個體隨機(jī)生成一個概率rand。如果rand 小于Ped，則隨機(jī)生成Nnum到2 的全排列數(shù)據(jù)，將生成的數(shù)據(jù)按照貪心策略插入法生成細(xì)菌個體；如果rand大于等于Ped，則維持原細(xì)菌個體位置不變。

5）重復(fù)步驟2～步驟4，直至達(dá)到最大遷徙次數(shù)Ned。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境

實驗中使用的計算機(jī)配置為2 GHz CPU、8 GB RAM、64 位操作系統(tǒng)。編程語言使用Matlab 語言，版本為Matlab r2017b。

3.2 算例測試與比較

為評價改進(jìn)算法的性能，使用Solomon 數(shù)據(jù)集進(jìn)行實驗，將所得最短配送距離與對比算法進(jìn)行比較。Solomon 數(shù)據(jù)集的VRPTW 共分為C1、C2、R1、R2、RC1、RC2 等6 類。C1 和C2 類的客戶呈 現(xiàn)分塊聚集分布；R1 和R2 類的客戶是隨機(jī)分布的；RC1 和RC2 類的客戶既有隨機(jī)分布，又有分塊聚集分布。R1、C1、RC1 數(shù)據(jù)集的車輛容量小、時間窗口窄，每條路線只允許少數(shù)客戶；R2、C2 和RC2 數(shù)據(jù)集的車輛容量大，且在較長的計劃周期內(nèi)允許許多客戶使用同一輛車進(jìn)行服務(wù)。本文算法在每個算例上獨立運行10 次。將實驗結(jié)果與文獻(xiàn)［20］中的具有交叉操作的人工蜂群（Artificial Bee Colony with Crossover operation，ABC-C）算法、具有掃描策略的人工蜂群（Artificial Bee Colony with Scanning strategy，ABC-S）算法和改進(jìn)人工蜂群（Improved Artificial Bee Colony，IABC）算法所給出的算例進(jìn)行比較，將全部算例分別與文獻(xiàn)［21］中的混合遺傳算法（Hybrid Genetic Algorithm，HGA）和文獻(xiàn)［22］中的自適應(yīng)記憶算法（Adaptive Memetic Algorithm，AMA）進(jìn)行比較。具體比較情況如表2～表4 所示，其中“—”部分表示對比算法未計算相應(yīng)數(shù)據(jù)。改進(jìn)的細(xì)菌覓食算法中的參數(shù)設(shè)置為：細(xì)菌種群數(shù)目N=30，趨化操作次數(shù)Nc=50，最大游動次數(shù)Ns=3，復(fù)制次數(shù)Nre=5，遷徙次數(shù)Ned=2，鄰域搜索長度W=10。

表2 C 類算例測試結(jié)果比較Table 2 Comparison of test results in C class example

表3 R 類算例測試結(jié)果比較Table 3 Comparison of test results in R class example

表4 RC 類算例測試結(jié)果比較Table 4 Comparison of test results in RC class example

在與ABC-C、ABC-S 和IABC 算法的比較中：由表2 可以看出，對于C1 類算例，IBFA 算法除了C101求解性能較弱，其他算例均優(yōu)于對比算法；由表3 可以看出，對于R1 類算例，IBFA 算法除了R101、R102、R103、R109、R110 和R112 的求解性能較弱以外，其他算例都優(yōu)于對比算法；由表4 可以看出，對于RC類算例，IBFA 算法除了RC201 算例求解性能較弱以外，其他算例都優(yōu)于對比算法。以上結(jié)論說明IBFA算法是有效的。

在與HGA 算法的比較中：由表2 可以看出，IBFA 算法對于C 類算例的求解性能均優(yōu)于對比算法；由表3 可以看出，IBFA 算法對于R 類算例的求解效果也優(yōu)于對比算法；由表4 可以看出，在RC 類算例 中，IBFA 算法除 了RC103、RC104 和RC107 求 解性能弱于對比算法以外，其他算例均優(yōu)于對比算法。整體而言，IBFA 算法的改進(jìn)效果較好。

在與AMA 算法的比較中：由表2 可以看出，在C 類算例中，IBFA 算法與對比算法取得了相同的效果；由表3 可以看出，在R 類算例中，IBFA 算法僅有R106 的求解性能劣于對比算法，其他算例均優(yōu)于對比算法；由表4 可以看出，在RC 類算例中，IBFA 算法僅有RC103、RC104、RC107 和RC108 的求解性能劣于對比算法，其他算例均優(yōu)于對比算法。整體而言，IBFA 算法的尋優(yōu)效果較好。

為進(jìn)一步驗證IBFA 算法的有效性，同樣使用Solomon 數(shù)據(jù)集進(jìn)行測試，將其與已知最優(yōu)的啟發(fā)式結(jié)果進(jìn)行比較，已知最優(yōu)啟發(fā)式結(jié)果中的數(shù)據(jù)從http：//w.cba.neu.edu/～msolomon/heuristi.htm 中選取。在表5～表7 中，TD 為已知啟發(fā)式最優(yōu)解，IBFA 為本文算法得到的最優(yōu)解，GAP 表示本文算法最優(yōu)解與已知啟發(fā)式最優(yōu)解之間的百分比偏差，用于評估算法的質(zhì)量。

表5 C 類算例中IBFA 與已知最優(yōu)解的比較Table 5 Comparison of IBFA and known optimal solutions in C class example

表6 R 類算例中IBFA 與已知最優(yōu)解的比較Table 6 Comparison of IBFA and known optimal solutions in R class example

表7 RC 類算例中IBFA 與已知最優(yōu)解的比較Table 7 Comparison of IBFA and known optimal solutions in RC class example

由表5 可以看出，對于C1 和C2 類算例，IBFA算法與已知啟發(fā)式最優(yōu)解之間沒有百分比偏差。由表6 可以看出，對于R 類算例，IBFA 算法除了R106 的百分比偏差是正值以外，其余均是負(fù)值，范圍為-15.03% 到-0.18%，證明求解質(zhì)量較好。由表7 可以看出，對于RC 類算例，IBFA 算法中RC103、RC104、RC107 和RC108 的百分比偏差為正值，其余均是負(fù)值，范圍為-19.59%到-0.43%，證明求解效果較好。

圖9 給出了IBFA 算法與其他算法在不同算例上的最短配送距離比較結(jié)果。由圖9（a）和圖9（b）可以看出，在C 類算例上，IBFA 算法基本取得了最佳效果。由圖9（c）和圖9（d）可以看出，改進(jìn)細(xì)菌覓食算法整體上優(yōu)于其他算法。由圖9（e）和圖9（f）可以看出，RC1 類算例RC103、RC104、RC107 和RC108 效果比較差，其他算例效果整體較好。以上結(jié)論證明了IBFA 算法改進(jìn)效果較好。圖10 給出了IBFA 算法的部分算例的路徑規(guī)劃結(jié)果。

圖9 6 類算例上的算法最短配送距離比較Fig.9 Comparison of the shortest distribution distances of algorithms on six class examples

圖10 部分算例的IBFA 路徑規(guī)劃結(jié)果Fig.10 IBFA path planning results of some examples

3.3 算法運行時間比較

為驗證算法性能，將本文IBFA 算法與ABC-C、ABC-S 和IABC 算法進(jìn)行運行時間對比，依據(jù)文獻(xiàn)［14］中的數(shù)據(jù)經(jīng)過計算得到：IBFA 算法在C 類、R 類以及RC 類算例的平均運行時間分別為61.33 s、119.42 s 和114.63 s；ABC-C 算法在C 類、R 類以及RC 類算例的平均運行時間分別為77.67 s、218.33 s和185.75 s；ABC-S 算法在C 類、R 類 以及RC 類算例的平均運行時間分別為74.11 s、213.5 s 和178.13 s；IABC 算法在C 類、R 類以及RC 類算例的平均運行時間分別為68.44 s、199.92 s 和168.75 s。從平均運行時間上看，IBFA 算法在各類算例上的平均運行時間均優(yōu)于ABC-C、ABC-S 和IABC 算法，證明IBFA算法運行效率較高。

4 結(jié)束語

本文提出一種改進(jìn)的細(xì)菌覓食算法，用于求解帶時間窗的車輛路徑優(yōu)化問題。將大鄰域搜索方法與趨化操作相結(jié)合，設(shè)計4 種removal 算子，擴(kuò)大搜索范圍，提高求解質(zhì)量。實驗結(jié)果證明，改進(jìn)算法具有較強(qiáng)的尋優(yōu)能力，在不增加時間復(fù)雜度的基礎(chǔ)上，能夠得到更優(yōu)的配送路徑。下一步將從環(huán)境保護(hù)角度出發(fā)，設(shè)計減少碳排放、提升客戶滿意度、降低配送成本的多目標(biāo)函數(shù)，研究低碳環(huán)保的帶時間窗車輛路徑規(guī)劃問題。