基于螢火蟲算法的動態(tài)車輛路徑規(guī)劃

董 海，雷鳳達(dá)

(沈陽大學(xué) 1.應(yīng)用技術(shù)學(xué)院；2.機(jī)械工程學(xué)院，遼寧 沈陽 110044)

信息技術(shù)的進(jìn)步促進(jìn)了智慧交通系統(tǒng)(intelligent transport system,ITS) 的發(fā)展。目前很多城市開始朝著智慧城市方向發(fā)展。作為智慧城市重要組成部分的智慧交通成了研究熱點(diǎn)。而動態(tài)車輛路徑問題(dynamic vehicle routing problem,DVRP) 作為車輛路徑問題的變體之一，是智慧交通研究中不可或缺的組成部分。通過動態(tài)獲取實(shí)時(shí)交通信息和客戶需求變更信息，根據(jù)城市實(shí)時(shí)交通情況和客戶需求的變更進(jìn)行車輛路徑規(guī)劃，為客戶提供更加快速的服務(wù)，以解決由于城市基建滯后、交通結(jié)構(gòu)單一、客戶需求變更等原因?qū)е碌某鞘袚矶聠栴}和成本浪費(fèi)，實(shí)現(xiàn)智慧交通讓城市更美好的愿景。

目前，大多數(shù)關(guān)于VRP的研究都假設(shè)在路徑規(guī)劃之前，信息不隨時(shí)間變化而變化。基于這樣的假設(shè)，路徑的安排相對固定，該種VRP被稱為靜態(tài)VRP。然而，客觀世界存在很多不確定性，需要動態(tài)地改變車輛的運(yùn)行路線并及時(shí)調(diào)整原來的行車路線。此時(shí)，靜態(tài)VRP 的理論和方法對這些問題不再適用。因此，對于動態(tài)車輛路徑問題的求解，需要研究一套全新的理論和方法。1988 年，Psaraftis[1]首次將車輛調(diào)度問題定義為“安排車輛路徑以滿足實(shí)時(shí)出行的顧客需求”。從線性規(guī)劃(linear programning,LP) 到啟發(fā)式算法，有許多方案可以解決DVRP及其變體。Yang 等[2]在以車隊(duì)必須為動態(tài)請求提供服務(wù)的基礎(chǔ)上提出一種基于線性規(guī)劃的滾動時(shí)域方法用以解決卡車動態(tài)交付問題。Montemanni 等[3]利用時(shí)間片策略開發(fā)了一個求解DVRP問題的蟻群算法(ant colony optimization，ACO)，并在每個時(shí)間節(jié)點(diǎn)上都檢查并處理請求。Chen等[4]提出一種用于DVRPTW的動態(tài)列生成器方案，在適應(yīng)度函數(shù)方面取得了較好的結(jié)果。吳斌等[5]提出基于狀態(tài)分類更新的粒子群算法(particle swarm optimization,PSO)用以求解開放式動態(tài)網(wǎng)絡(luò)車輛路徑。Pillac 等[6]提出帶有多場景方法(mutliple scane analysis,MSA) 的事件驅(qū)動框架，通過將請求的子集分配給車輛來完成路徑規(guī)劃。寧濤等[7]將車輛鏈和貨物鏈的雙鏈量子編碼，提出改進(jìn)的多相量子粒子群算法用以求解多目標(biāo)DVRP。Briseida 等[8]提出可變鄰域搜索算法(variable neighborhood search,VNS)，通過對隨機(jī)場景進(jìn)行采樣來擴(kuò)展解的空間，更加精確求解DVRP。Alchami 等[9]提出一種帶有人類調(diào)度員的遺傳算法(genetic algorithm,GA) 來解決DVRP問題，使GA在整個范圍內(nèi)一直運(yùn)行并不斷更新路徑。閆凱等[10]在此基礎(chǔ)上將GA與ACO結(jié)合，更快地求解單配送中心路徑優(yōu)化問題模型。孫俊成等[11]基于貪婪思想的隨機(jī)鄰域搜索策略提出一種新改進(jìn)的螢火蟲算法(firefly algorithm,FA)，解決軟時(shí)間窗的多配送中心開放式車輛路徑問題。Maroua 等[12]針對CDVRP需求與決策支持系統(tǒng)的性能差異，提出一種新的基于圖形處理單元(graphics processing unit,GPU) 的分布式蜂群算法。辜羽潔等[13]基于嵌套分割算法，設(shè)計(jì)了鄰近救援策略、最佳離庫策略、增派車輛策略對DVRP模型進(jìn)行求解。范雙南等[14]采用智能水滴算法對車輛路徑優(yōu)化模型進(jìn)行求解，使用灰狼優(yōu)化算法改善智能水滴算法的搜索能力，獲取最優(yōu)路徑。Orivalde 等[15]在多蟻群系統(tǒng)的基礎(chǔ)上，引入隨機(jī)變量鄰域下降策略求解帶時(shí)間窗的DVRP。Resmi 等[16]利用帶學(xué)習(xí)能力的尖峰神經(jīng)P系統(tǒng)與FA進(jìn)行結(jié)合，利用尖峰神經(jīng)系統(tǒng)的并行性優(yōu)化FA，以解決綠色動態(tài)車輛路徑問題。

綜上所述，現(xiàn)有解決策略大多基于優(yōu)先分配原則，這樣會延遲客戶對車輛的請求分配。因此，一些客戶可能會進(jìn)入一個較長的等待期，進(jìn)而影響系統(tǒng)的整體性能。本文提出一種改進(jìn)的螢火蟲優(yōu)化方案，引入螢火蟲的運(yùn)動和吸引概念來表達(dá)模型動態(tài)性，用改進(jìn)后的算法對解空間進(jìn)行智能化探索和開發(fā)，解決CDVRPTW問題。

1 問題描述

CDVRPTW是VRP的一個變體，是由于最近通信方面的改進(jìn)而出現(xiàn)的。DVRP在開始設(shè)置路徑時(shí)，并不是所有的信息都是可用的；即使在路徑被構(gòu)建之后，信息也可能發(fā)生變化。圖1列出了CDVRPTW的路徑規(guī)劃圖。該圖中有4個頂點(diǎn)(A、B、C和D)，其對應(yīng)已知請求的4個不同客戶。連接客戶的邊緣表示不同的參數(shù)，如旅行成本、旅行距離等。為滿足已知請求而進(jìn)行的初始路線為車場→A→B→C→D→車場，當(dāng)車輛沿著AB路線行駛時(shí)，出現(xiàn)一個動態(tài)請求E。此時(shí)，如果車輛的總?cè)萘啃∮诨虻扔诼肪€中每個客戶的所有容量之和，則車輛路徑規(guī)劃為車場→A→B→C→D→E→車場；反之則需要在滿載前更改路徑以滿足客戶需求。

圖1 動態(tài)環(huán)境下的線路規(guī)劃Figure 1 Route planning in dynamic environment

2 帶時(shí)間窗和容量受限的動態(tài)車輛路徑模型(CDVRPTW)

CDVRPTW可以看作是一個完全的圖論問題。其中，頂點(diǎn)集A={A0···AB}；邊緣集E={(Ai,Aj):Ai,Aj∈A,i≠j}。頂點(diǎn)A0車場，每個頂點(diǎn)AK∈A都有參數(shù)，定義請求Pk、到達(dá)時(shí)間Tak、等待時(shí)間Twk、服務(wù)時(shí)間Tsk和時(shí)間窗口[Tek,Tlk,]，C′kj是客戶j到客戶k在時(shí)間段t內(nèi)的運(yùn)輸成本。每輛車k有一個非負(fù)的容量Wk。總時(shí)段數(shù)用T表示，fc和tc分別是車輛的固定成本和每單位時(shí)間的行駛成本。

總成本是車輛固定成本和路線成本的總和，車輛總成本最小問題表達(dá)式為

受以下約束。

1) 將客戶分配到車輛：每個客戶在給定時(shí)間僅分配給一輛車。

2) 車場容量：車場出發(fā)的車輛數(shù)量不超過車場的車輛總數(shù)(N) 。

3) 同一車輛服務(wù)于同一個集群上的客戶。

其中，M是一個非常大的數(shù)，定義為第k個客戶的最晚時(shí)間與第j個(連續(xù)) 客戶的最早時(shí)間之間的最大差值，?k,j,k≠j。

4) 每個客戶節(jié)點(diǎn)都必須由一輛車提供服務(wù)。

5) 車輛容量(Wk) ：車輛交付給客戶的負(fù)載不應(yīng)超過客戶需求Pk的車輛容量。

6) 排除備用路徑：如果車輛從客戶k在t處為客戶j服務(wù)，則不應(yīng)存在任何路徑。此處|A|是路徑中的客戶總數(shù)。

7) 時(shí)間窗口約束：為客戶提供服務(wù)的時(shí)間限制不應(yīng)超過時(shí)間窗口。

3 求解方法

本文采用改進(jìn)螢火蟲算法求解模型，并利用DVRP求解器來處理新的動態(tài)請求。與其他生物啟發(fā)算法相比，F(xiàn)A被選擇作為所提出解決方案方法的基礎(chǔ)有以下優(yōu)勢。

1) FA整個群被細(xì)分為多個子群，并且每個子群位于一個局部最優(yōu)的周圍，促進(jìn)FA的靈活性。

2) 光吸收系數(shù)γ作為一個比例因子，調(diào)節(jié)FA的多溫能力，并連續(xù)調(diào)節(jié)種群的多樣性。

因?yàn)榻?jīng)典FA在實(shí)域中是連續(xù)的，而VRP的解空間是離散整數(shù)，F(xiàn)A不能直接用于求解VRP問題，因此本文提出基于坐標(biāo)的螢火蟲算法，利用CR編碼/解碼方法，使VRP的離散解映射到連續(xù)域，從而求解模型。

3.1 DVRP求解器

根據(jù)本文對DVRP的定義可知，可以將DVRP模型的求解劃分為兩個階段：工作開始前基于已知顧客信息的車輛初始路徑的求解階段與每次接收到新需求后車輛路徑的調(diào)整階段。

在車輛開始工作之前，只能將當(dāng)前已知所有的顧客信息進(jìn)行整合并規(guī)劃路線，也就是說此時(shí)面對的規(guī)劃問題中需求是完全確定的。在第1個階段的車輛路徑規(guī)劃相當(dāng)于對CVRPTW模型進(jìn)行求解。當(dāng)每次接收到新顧客需求時(shí)，將結(jié)合新顧客與原規(guī)劃路線中關(guān)鍵節(jié)點(diǎn)以后的未服務(wù)顧客的需求信息和位置信息，調(diào)整關(guān)鍵節(jié)點(diǎn)以后的車輛行駛路線，并執(zhí)行新路線。此時(shí)，每輛車處于不同的位置，剩余的容量也不同，可將車輛當(dāng)前位置虛擬為新的起點(diǎn)。從本質(zhì)上來看，與第1階段規(guī)劃車輛路徑相比，出現(xiàn)動態(tài)需求后對路徑規(guī)劃在車的容量和車輛位置上有差異。因此如果在一個工作日內(nèi)出現(xiàn)了N次動態(tài)信息，則對整個過程的CDVRPTW模型就分解成了求解一個車輛在同一位置出發(fā)的CVRPTW模型和N個車輛在不同位置出發(fā)的CVRPTW模型，分別對應(yīng)了對車輛初始行駛路徑的求解和N次接收到新顧客需求后新路徑的求解。

針對模型的求解算法，本文將采用坐標(biāo)螢火蟲算法求得模型的初始解。為解決該初始算法求解質(zhì)量不高的問題，利用局部搜索對其進(jìn)行改進(jìn)。本文DVRP模型的求解策略如圖2所示。

圖2 DVRP求解策略Figure 2 DVRP solution strategy

3.2 螢火蟲算法

螢火蟲算法的靈感來自生物發(fā)光的過程，在自然界中，螢火蟲利用生物發(fā)光來吸引潛在的伙伴和獵物，或者作為一種警告機(jī)制。用每只螢火蟲的光強(qiáng)來模擬解的質(zhì)量，即螢火蟲在三維空間中的目標(biāo)函數(shù)和運(yùn)動機(jī)制。一般來說，一只明亮的螢火蟲會吸引一只不太亮的螢火蟲向其靠近，但光強(qiáng)不是該機(jī)制的唯一因素。隨著兩個螢火蟲之間的距離增加，光強(qiáng)根據(jù)平方反比定律減小，螢火蟲間的吸引力減小。本文建立3個規(guī)則來模擬所描述的行為。

1) 所有的螢火蟲都是不分性別的，都能夠相互吸引。

2) 螢火蟲的吸引力與其亮度成正比。因此，對于任何兩個閃爍的螢火蟲來說，不太亮的一個會移向較亮的一個。隨著任意兩只螢火蟲之間距離的增加，吸引力和亮度都會降低，如果兩只螢火蟲亮度相同將會隨機(jī)移動。

3) 螢火蟲的亮度受目標(biāo)函數(shù)影響。

每只螢火蟲都有兩個重要的特征，光強(qiáng)度I和吸引力β。關(guān)于優(yōu)化問題，螢火蟲在H位置的光強(qiáng)與目標(biāo)函數(shù)f(x)的值(在最大化的情況下) 或其倒數(shù)(在最小化的情況下) 直接相關(guān)。吸引力與相鄰螢火蟲看到的光線強(qiáng)度成正比，并遵從笛卡爾距離方程，隨著rij(螢火蟲i和螢火蟲j距離) 的變化而變化。其中，γ表示固定光吸收系數(shù)，β0表示在r=0時(shí)的吸引力。距離公式為

螢火蟲i在時(shí)間t朝吸引力更大的螢火蟲j運(yùn)動表示為

式(13) 中最后一項(xiàng)包括隨機(jī)化參數(shù)和在時(shí)間t從高斯或均勻分布中提取的隨機(jī)數(shù)向量。參數(shù)設(shè)置是為了控制解的多樣性，文獻(xiàn)[17]建議

其中，L為平均問題比例。

算法1為最初的螢火蟲算法，偽代碼如下。

3.3 基于相關(guān)坐標(biāo)的螢火蟲算法(CR-FA)

3.3.1 相關(guān)坐標(biāo)方法的描述

本文提出的相關(guān)坐標(biāo)編碼/解碼過程是為利用標(biāo)準(zhǔn)的FA方案及其方程來求解VRP變體而設(shè)計(jì)的。CR的主要功能是將離散編碼的解轉(zhuǎn)換為連續(xù)值，以便可以直接應(yīng)用FA方程。

目前廣泛使用的VRP解的表示是向量或數(shù)組列表。每條路徑的起點(diǎn)和終點(diǎn)是節(jié)點(diǎn)“0”，其余可用節(jié)點(diǎn)的訪問序列由其所在解向量中的索引表示。但由于問題的復(fù)雜性和可選擇性，不應(yīng)訪問可用集合中的每個節(jié)點(diǎn)，無法在CDVRPTW的解決方案中直接實(shí)現(xiàn)這些機(jī)制。因此本文提出了CR編碼/解碼方法，利用每個節(jié)點(diǎn)的笛卡爾坐標(biāo)(二維空間中的位置) 和節(jié)點(diǎn)之間的歐幾里德距離。按照CR編碼方案，每個解決方案向量由兩個新的向量表示，其分別對應(yīng)于解決方案中每個節(jié)點(diǎn)的X和Y坐標(biāo)，如表1所示。

表1 CR變換向量示例Table 1 Example of CR transform vector

表2表示車場的節(jié)點(diǎn)“0”位于(0，0)，遵循FA的算法框架，每個螢火蟲都由一個解向量表示，并被吸引到一個更亮的，即一個解將向一個更好的方向移動，運(yùn)動和距離由方程控制。

表2 相關(guān)解向量Table 2 Correlation solution vector

在目前的研究中，認(rèn)為兩個給定解的距離可以計(jì)算為在兩個不同向量中相同位置的每對節(jié)點(diǎn)的最小歐幾里德距離，不包括公共節(jié)點(diǎn)和節(jié)點(diǎn)“0”。此時(shí)，可以計(jì)算吸引力。假設(shè)解向量1的光強(qiáng)大于解向量2的光強(qiáng)，則應(yīng)更新向量2。在實(shí)踐中，每個維度(X和Y) 通過計(jì)算，產(chǎn)生一個新的坐標(biāo)集作為解向量2的更新版本，如表3所示。

表3 更新解向量2示例Table 3 Example of updated solution vector 2

解碼過程遵循索引過程，并且相關(guān)性遵循以下原則。

1) 可用節(jié)點(diǎn)集中的所有節(jié)點(diǎn)都應(yīng)是“對應(yīng)節(jié)點(diǎn)”的候選節(jié)點(diǎn)，并應(yīng)通過可行性控制決定，具體取決于CDVRPTW公式施加的路徑約束。

2) 搜索的方向，即X軸或Y軸，是從均勻分布的隨機(jī)數(shù)中隨機(jī)選擇的，其增強(qiáng)了該過程的探索強(qiáng)度。

3) 如果上述候選數(shù)中有最初被列入被審查的數(shù)，則應(yīng)選擇其他，以增加過程的多樣化。

4) 初始節(jié)點(diǎn)和最終節(jié)點(diǎn)“0”可以是相應(yīng)的節(jié)點(diǎn)，也可以由進(jìn)程強(qiáng)制實(shí)施，以符合問題的可行性限制。

3.3.2 CR-FA算法

所提出的基于坐標(biāo)的螢火蟲算法包括運(yùn)用啟發(fā)式方法來創(chuàng)建初始解種群，以確保更新解的可行性，并改進(jìn)更新解。因此，CR-FA的框架包含初始群、坐標(biāo)化(解碼/編碼)、增強(qiáng)路徑、移除節(jié)點(diǎn)和交換節(jié)點(diǎn)。算法2偽代碼如下。

對于初始種群的構(gòu)造，采用了初始種群啟發(fā)式方法。第1步是制定M條初始路線，其中只包括車輛段和一個其他節(jié)點(diǎn)。這些路徑被組合成一個初始解向量，未包含的節(jié)點(diǎn)根據(jù)它們的亮度值進(jìn)行排序。

最有效的插入位置(節(jié)點(diǎn)I、j之間)Sij為

整個解決方案達(dá)到的總需求Qlow為

解決方案的每條路徑都由節(jié)點(diǎn)擴(kuò)充，達(dá)到預(yù)定義的容量限制應(yīng)不超過Qlow。算法3偽代碼如下。

隨后，F(xiàn)A方案被初始化，定義了光吸收系數(shù)γ，并計(jì)算對于所創(chuàng)建的群體中的每個成員的適應(yīng)值fi與相應(yīng)的光強(qiáng)度Li。由于CDVRPTW是一個最小化問題，所以光強(qiáng)被分別定義為每個解的適應(yīng)值的倒數(shù)。然后，對群體中的每一對解進(jìn)行比較，光強(qiáng)值較低的解應(yīng)該向另一個解移動。為此，首先應(yīng)測量它們相應(yīng)的距離，然后再應(yīng)用坐標(biāo)化編碼/解碼過程。為了提高算法解的質(zhì)量，使用局部搜索技術(shù)，包含增強(qiáng)路徑、移除節(jié)點(diǎn)和交換節(jié)點(diǎn)技術(shù)。在增強(qiáng)路徑過程中，考慮到所有上述約束，使用節(jié)省方法用于填充每個路徑節(jié)點(diǎn)。將解決方案中的節(jié)點(diǎn)添加到它們各自的最佳位置。隨后，另外兩種局部搜索技術(shù)被用于改善迭代次數(shù)。首先，在移除節(jié)點(diǎn)過程中，算法在移除節(jié)點(diǎn)后重構(gòu)，并且連續(xù)地，在不違反最小需求約束的情況下構(gòu)建更高質(zhì)量的解決方案。所采用的原則是，當(dāng)具有低強(qiáng)度的節(jié)點(diǎn)從解中移除時(shí)，剩余的解與新的弧連接，并且如果新的方案在成本(距離) 方面是可行的，則可以出現(xiàn)更好的解(具有更低的目標(biāo)函數(shù)值) 。算法4偽代碼如下。

交換節(jié)點(diǎn)是一個重復(fù)的交換過程，在一個解決方案中的隨機(jī)路徑之間進(jìn)行指定次數(shù)的迭代。隨機(jī)選擇兩條路線，并且還隨機(jī)選擇所選路線之一的位置。交換所需的第2位置，即來自第2路徑的節(jié)點(diǎn)，是使用距離向量計(jì)算的。所描述的節(jié)點(diǎn)交換旨在通過省略無效的節(jié)點(diǎn)序列并創(chuàng)建更有效的連接來創(chuàng)建具有更少行駛距離(更低成本) 的解決方案。算法5偽代碼如下。

4 算例測試與分析

本節(jié)評估解決CDVRPTW的CR-FA算法的性能。由于目前還沒有形成CDVRPTW的基準(zhǔn)數(shù)據(jù)集，因此，本文將動態(tài)模型看作很多靜態(tài)車輛路徑模型的集合，在開放數(shù)據(jù)集上的 CVRPTW實(shí)例對CR-FA進(jìn)行了測試，并對結(jié)果進(jìn)行了分析。本文采用Intel Xenon2.93ghz處理器、12gbram、Windows10操作系統(tǒng)，用Matlab對實(shí)驗(yàn)進(jìn)行了仿真。

4.1 參數(shù)設(shè)置

本文提出的CR-FA的優(yōu)勢在于其需要與標(biāo)準(zhǔn)FA相同的參數(shù)化。Yang 等[18]考慮到問題規(guī)模與解空間中可用節(jié)點(diǎn)的數(shù)量N有關(guān)，對于每個測試實(shí)例，初始隨機(jī)性比例因子分別計(jì)算為a0=0.01N，光吸收系數(shù)計(jì)算為。人口規(guī)模w和冷卻系數(shù)δ的設(shè)為w=40，δ=0.96。

4.2 CVRPTW數(shù)據(jù)集測試

CR-FA在所羅門數(shù)據(jù)集上進(jìn)行了平均40次測試，本文算法有兩個停止標(biāo)準(zhǔn)。當(dāng)它到達(dá)最優(yōu)解或最大迭代次數(shù)，設(shè)為500次迭代。將CR-FA的最佳值和平均值與蟻群算法(ACO)、粒子群算法(PSO)、遺傳算法(GA) 和差分進(jìn)化算法(DE) 進(jìn)行比較，并對結(jié)果進(jìn)行分析。

表4給出了5種方法的解質(zhì)量的最佳值和平均值，其中最好的結(jié)果用黑體表示。與其他4種算法相比，本文所提出的CR-FA實(shí)現(xiàn)了20個最佳值中的15個和20個平均值中的14個高于其他算法，并在20個實(shí)例中取得平均最佳。為了清楚地區(qū)分這些方案的優(yōu)劣性，以解的最小值、最大值、中位數(shù)、上四分位數(shù)以及下四分位數(shù)為原始數(shù)據(jù)，見表4。

表4 各種算法解的平均值與最佳值Table 4 The average value and best value of various algorithm solutions

選擇ACO作為基準(zhǔn)繪制算法對比箱線圖，用于分析各種方案的改進(jìn)百分比，如圖3。通過對箱線圖的分析可以看出，就總體而言，CR-FA的改善百分比明顯優(yōu)于其他方案。

由于ACO算法對解決此類車輛路徑問題效果較差，所以在下面分析R101實(shí)例結(jié)果中不作分析。具體運(yùn)行結(jié)果如表5所示。其中，Pk代表客戶的需求；Ve表示車輛數(shù)；R表示車輛所行駛的距離；F表示車輛的成本；T表示算法的運(yùn)行時(shí)間。結(jié)果表明CR-FA除了迭代速度較其他算法比稍顯不足，在成本以及行駛距離上明顯優(yōu)于其他算法，圖3在算法迭代速度上進(jìn)行進(jìn)一步分析。

表5 算法比較-R101實(shí)例Table 5 Algorithm comparison-R101 instance

圖3 改進(jìn)質(zhì)量百分比比較Figure 3 Comparison of improved quality percentage

圖4顯示了最優(yōu)路徑的收斂性，將本文提出的CR-FA算法的收斂性與其他算法作出對比分析。結(jié)果表明CR-FA在初期就具有優(yōu)于其他算法的收斂能力，并在最終收斂結(jié)束的目標(biāo)值優(yōu)于其他算法。在迭代次數(shù)為250次時(shí)得到最優(yōu)路徑，算法持續(xù)探索解的空間追求更高質(zhì)量的解。

圖4 最優(yōu)路徑收斂曲線Figure 4 Optimal path convergence curve

圖5通過大型實(shí)例C150，展示了CR-FA到達(dá)最優(yōu)解或最優(yōu)解附近的收斂行為和CR-FA解決C150實(shí)例的結(jié)果。該圖描述了運(yùn)行期間獲得的最佳解和平均解，并顯示了CR-FA的收斂行為。算法在280次迭代后求出最優(yōu)解。在初始階段，CR-FA具有很高的收斂速度。在搜索過程中，CR-FA實(shí)現(xiàn)了最優(yōu)解和搜索速度之間的良好平衡。這種平衡有助于CRFA有效地探索搜索空間并避免陷入局部最優(yōu)。此外，在搜索過程中沒有出現(xiàn)停滯。

圖5 C150實(shí)例下的迭代行為Figure 5 Iterative behavior in C150 instance

4.3 實(shí)例驗(yàn)證

為了驗(yàn)證所提CR-FA的實(shí)用性，將其應(yīng)用于沈陽市新鮮果蔬物流一個實(shí)際實(shí)例中。將果蔬從倉庫(水果蔬菜配送中心) 送到13個配送點(diǎn)(沈陽市13家果蔬超市)，每兩點(diǎn)之間的距離詳見表6。

當(dāng)貨物從配送中心運(yùn)送至各配送點(diǎn)時(shí)，運(yùn)輸車輛為同一類型的普通卡車。該卡車的最大承載能力為40 t，平均速度為60 km/h。每輛車的固定運(yùn)輸費(fèi)為600 元/km，運(yùn)輸費(fèi)為5 元/km。表6根據(jù)標(biāo)記順序給出了配送中心和超市的具體情況。本文的研究并沒有考慮到交通擁堵，車輛可以在超市規(guī)定的時(shí)間窗口內(nèi)送貨。

表6 任意兩個超市間距Table 6 Distance between any two supermarketsm

實(shí)際問題的具體目標(biāo)是盡量減少車輛數(shù)量、減少車輛總行駛距離和配送中心的總成本。因此，應(yīng)用FA和CR-FA來解決VRPTW實(shí)例。通過比較這兩種算法的結(jié)果，分析并驗(yàn)證該CR-FA的實(shí)用性和有效性，其結(jié)果見表7。

從表7可以看出，使用FA解決CVRPTW實(shí)例需要6輛車，但這6輛車并未得到充分利用。根據(jù)最后一行，總距離為57 158.92 m，車隊(duì)需花費(fèi)3 890.02元才能完成全部交付。然而，當(dāng)使用CR-FA來解決CVRPTW實(shí)例時(shí)，需要5輛車，并且與FA方案中的6輛車相比，這5輛車幾乎被充分使用?？偩嚯x為54 395.47 m，比CR-FA解決方案中的總距離小2 763.45 m。車隊(duì)完成所有交付的成本為3 276.88元，節(jié)約613.14元。因此，通過對實(shí)例的應(yīng)用和分析表明，所提出的CR-FA是有效的，具有實(shí)際意義。

表7 CR-FA與FA解決方案對比Table 7 Comparison of CR-FA and FA solutions

5 結(jié)論

本文提出一種改進(jìn)螢火蟲算法解決帶時(shí)間窗和容量約束的動態(tài)車輛路徑問題，主要結(jié)論如下。

1) 在動態(tài)車輛路徑模型的基礎(chǔ)上加入時(shí)間窗和容量約束，以總成本最小化為目標(biāo)構(gòu)建CDVRPTW模型。

2) 提出基于CR編碼/解碼方法使螢火蟲算法的解坐標(biāo)化，將離散解映射到連續(xù)域，其在解決車輛路徑問題時(shí)，不需要在標(biāo)準(zhǔn)算法框架中應(yīng)用雜交或離散化技術(shù)；同時(shí)根據(jù)CR過程的解碼部分，使每對新坐標(biāo)對應(yīng)一個節(jié)點(diǎn)，可以根據(jù)特定VRP公式施加的約束進(jìn)行可行性控制；采用局部搜索技術(shù)優(yōu)化運(yùn)算過程，避免其陷入局部最優(yōu)。

3) 在實(shí)例驗(yàn)證中，將CR-FA在解的質(zhì)量、車輛利用率以及收斂性等方面與蟻群算法、粒子群算法、遺傳算法和差分進(jìn)化算法進(jìn)行比較，統(tǒng)計(jì)分析驗(yàn)證了本文所提的算法解決CDVRPTW的有效性。