求解帶時(shí)間窗車(chē)輛路徑優(yōu)化問(wèn)題的改進(jìn)細(xì)菌覓食算法

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

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

0 概述

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

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

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

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

1 考慮時(shí)間窗的車(chē)輛路徑優(yōu)化問(wèn)題

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

式（1）表示最小化車(chē)輛總行程；式（2）表示每個(gè)客戶(hù)僅被一輛車(chē)服務(wù)一次；式（3）表示每輛車(chē)的行駛距離都不得超過(guò)最大行駛距離；式（4）表示每個(gè)客戶(hù)只被同一輛車(chē)服務(wù)；式（5）表示車(chē)輛從配送中心出發(fā)最終必須再回到配送中心；式（6）表示每輛車(chē)配送的客戶(hù)總需求量不得超過(guò)車(chē)輛最大載重；式（7）表示客戶(hù)i的開(kāi)始服務(wù)時(shí)間必須滿(mǎn)足給定的時(shí)間窗；式（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］。該算法主要通過(guò)趨化操作、復(fù)制操作和遷徙操作的迭代計(jì)算來(lái)搜索問(wèn)題的最優(yōu)解。趨化操作是算法的核心操作，因此本文在趨化操作中結(jié)合了大鄰域搜索算法中的removal 算子，運(yùn)用4 種removal 算子進(jìn)行尋優(yōu)，擴(kuò)大細(xì)菌的搜索范圍。大鄰域搜索算法由SHAW［19］于1998年提出，克服局部搜索的缺陷，提高BFA優(yōu)化能力，能夠更快地找到最優(yōu)解，對(duì)于求解VRPTW問(wèn)題十分有效。

2.1 編碼

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

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

2.2 初始解構(gòu)造

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

為驗(yàn)證采用K-means 構(gòu)造初始解對(duì)算法的影響，本文選取Solomon 測(cè)試集中的R211 算例進(jìn)行驗(yàn)證。測(cè)試集共100 個(gè)客戶(hù)節(jié)點(diǎn)，車(chē)輛載重為1 000，使用K-means 算法聚類(lèi)后的客戶(hù)排列順序和原始客戶(hù)集中的客戶(hù)排列順序分別生成初始解，共進(jìn)行10 次實(shí)驗(yàn)，采用K-means 聚類(lèi)后得到的最終解平均值為782.43，使用初始客戶(hù)集生成最終解的平均值為791.08。圖2 給出了使用K-means 算法得到的最優(yōu)解構(gòu)造的初始路徑。圖3 給出了使用原始序列得到的最優(yōu)解構(gòu)造的初始路徑。實(shí)驗(yàn)結(jié)果表明，使用K-means算法對(duì)客戶(hù)集進(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)化算法中，對(duì)問(wèn)題的解空間進(jìn)行尋優(yōu)的核心操作是趨化操作，包括旋轉(zhuǎn)和游動(dòng)。細(xì)菌向任意方向移動(dòng)單位步長(zhǎng)定義為旋轉(zhuǎn)。旋轉(zhuǎn)后計(jì)算適應(yīng)度值，若得到的路徑適應(yīng)度值更小則繼續(xù)沿著該方向游動(dòng)，直到達(dá)到最大步長(zhǎng)或者適應(yīng)度值不發(fā)生改變，此過(guò)程稱(chēng)為游動(dòng)。由于細(xì)菌的步長(zhǎng)和方向會(huì)影響到尋優(yōu)效果，因此本文結(jié)合VRPTW 問(wèn)題的特性，將大鄰域搜索中的removal 算子結(jié)合到趨化操作中。為達(dá)到更好的搜索效果，共設(shè)計(jì)4 種removal算子，分別為Random removal算子、Least profit removal 算 子、Route removal 算子和Relatedness removal 算子。這4 種算子作為細(xì)菌游動(dòng)的方向，游動(dòng)步長(zhǎng)設(shè)置為m。用輪盤(pán)賭方法選擇一種removal算子，用來(lái)模擬細(xì)菌在旋轉(zhuǎn)過(guò)程中任意選擇的方向，確定方向后進(jìn)行移除插入操作。如果該算子取得的適應(yīng)度值變好，則繼續(xù)采用，直到達(dá)到細(xì)菌的最大游動(dòng)次數(shù)，此過(guò)程模擬了細(xì)菌在該方向上的游動(dòng)。若旋轉(zhuǎn)后適應(yīng)度值沒(méi)有改善，則選擇另一個(gè)removal 算子，即另一個(gè)方向，繼續(xù)進(jìn)行游動(dòng)。每個(gè)細(xì)菌都從旋轉(zhuǎn)操作開(kāi)始，在達(dá)到趨化算子次數(shù)前不斷反復(fù)交替執(zhí)行旋轉(zhuǎn)和游動(dòng)操作，更新路徑。將removal 算子應(yīng)用到趨化操作中，擴(kuò)大搜索范圍，有利于局部搜索。在移除了m個(gè)客戶(hù)節(jié)點(diǎn)后，運(yùn)用之前的貪婪插入法重新將移除的客戶(hù)進(jìn)行插入。

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

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

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

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

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

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

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

圖7 初始路徑Fig.7 Initial path

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

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

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

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

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

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

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

2.4 算法流程

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 算例測(cè)試與比較

為評(píng)價(jià)改進(jìn)算法的性能，使用Solomon 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，將所得最短配送距離與對(duì)比算法進(jìn)行比較。Solomon 數(shù)據(jù)集的VRPTW 共分為C1、C2、R1、R2、RC1、RC2 等6 類(lèi)。C1 和C2 類(lèi)的客戶(hù)呈 現(xiàn)分塊聚集分布；R1 和R2 類(lèi)的客戶(hù)是隨機(jī)分布的；RC1 和RC2 類(lèi)的客戶(hù)既有隨機(jī)分布，又有分塊聚集分布。R1、C1、RC1 數(shù)據(jù)集的車(chē)輛容量小、時(shí)間窗口窄，每條路線(xiàn)只允許少數(shù)客戶(hù)；R2、C2 和RC2 數(shù)據(jù)集的車(chē)輛容量大，且在較長(zhǎng)的計(jì)劃周期內(nèi)允許許多客戶(hù)使用同一輛車(chē)進(jìn)行服務(wù)。本文算法在每個(gè)算例上獨(dú)立運(yùn)行10 次。將實(shí)驗(yàn)結(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 所示，其中“—”部分表示對(duì)比算法未計(jì)算相應(yīng)數(shù)據(jù)。改進(jìn)的細(xì)菌覓食算法中的參數(shù)設(shè)置為：細(xì)菌種群數(shù)目N=30，趨化操作次數(shù)Nc=50，最大游動(dòng)次數(shù)Ns=3，復(fù)制次數(shù)Nre=5，遷徙次數(shù)Ned=2，鄰域搜索長(zhǎng)度W=10。

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

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

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

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

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

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

為進(jìn)一步驗(yàn)證IBFA 算法的有效性，同樣使用Solomon 數(shù)據(jù)集進(jìn)行測(cè)試，將其與已知最優(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)解之間的百分比偏差，用于評(píng)估算法的質(zhì)量。

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

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

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

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

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

圖9 6 類(lèi)算例上的算法最短配送距離比較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 算法運(yùn)行時(shí)間比較

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

4 結(jié)束語(yǔ)

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