求解帶時(shí)間窗車輛路徑問題的改進(jìn)FPA

叢揚(yáng)瀟，袁志高，李 素，姜緣平，王祖榮

(北京工商大學(xué) 計(jì)算機(jī)學(xué)院，北京 100048)

0 引 言

車輛路徑問題[1](VRP)是典型的組合優(yōu)化問題。旨在為客戶安排合理的行車路線，在滿足約束的前提下，得到配送方案的最優(yōu)解。帶時(shí)間窗車輛路徑問題[2](VRPTW)是車輛路徑問題的另一擴(kuò)展問題。由于VRPTW模型采用精確算法對(duì)其求解的效率很低，國(guó)內(nèi)外學(xué)者將重點(diǎn)轉(zhuǎn)移到各種啟發(fā)式算法上。Jacobsen-Grocott J等[3]采用遺傳編程求解VRPTW。Asadi-Gangraj E等[4]提出了一種混合遺傳算法求解VRPTW；馬龍等[5]利用鴿群與水滴算法結(jié)合求解多目標(biāo)多時(shí)間窗車輛路徑問題。張瑾等[6]利用改進(jìn)的蝙蝠算法求解帶容量和時(shí)間窗約束的車輛路徑問題。李珺等[7]利用改進(jìn)的細(xì)菌覓食算法求解VRPTW。Belhaiza S等[8]提出了混合遺傳變量鄰域啟發(fā)式搜索算法求解VRPTW。上述算法雖然在解決VRPTW方面取得了一定效果，但還有較大的提升空間。

FPA(flower pollination algorithm)是一種啟發(fā)式群智能算法[9]，是受自然界中顯花植物花朵授粉過程的啟發(fā)而提出的，具有全局搜索能力強(qiáng)、選用參數(shù)少、搜索路徑優(yōu)及多目標(biāo)問題求解能力強(qiáng)等特點(diǎn)，已成功應(yīng)用于蛋白質(zhì)分子對(duì)接[10]、視頻跟蹤[11]、車間調(diào)度[12]、機(jī)器人導(dǎo)航路徑優(yōu)化[13]和圖像色彩量化[14]等方面。因此本文深入研究FPA，發(fā)現(xiàn)其不足之處，并用遺傳算法(genetic algorithms，GA)對(duì)其改進(jìn)，提出了一種改進(jìn)FPA(GA-FPA)，并將其用于VRPTW求解。

1 問題描述與數(shù)學(xué)模型

VRPTW問題描述為：一組車輛從配送中心出發(fā)，根據(jù)客戶的需求量和時(shí)間窗的限制制定配送路線，最終返回配送中心，使配送總成本達(dá)到最小。

帶時(shí)間窗的車輛路徑問題主要分為硬時(shí)間窗和軟時(shí)間窗硬時(shí)間窗要求車輛必須在客戶的規(guī)定時(shí)間內(nèi)完成配送任務(wù)；軟時(shí)間窗允許客戶在規(guī)定時(shí)間外完成任務(wù)，但要支付額外的懲罰費(fèi)用。由于硬時(shí)間窗在執(zhí)行中很難找到合適可行的調(diào)度方案，同時(shí)與實(shí)際彈性時(shí)間情況不符，而軟時(shí)間窗具有一定應(yīng)用性，更符合實(shí)際情況。因此在本研究中采用軟時(shí)間窗作為約束條件。

配送車輛應(yīng)該滿足的約束條件請(qǐng)參見文獻(xiàn)[15]。

符號(hào)定義與數(shù)學(xué)模型如下：

配送中心為C0；客戶集為C={1，2，…，n}；每個(gè)客戶的需求量為qi(i∈C)；配送車輛數(shù)量為k，車輛集為V={1，2，…，k}；每輛配送車的載重量為Q；客戶i與j之間的距離為dij；配送車輛在i與j配送點(diǎn)之間所需的行駛時(shí)間tij；配送車輛到達(dá)Ci客戶的時(shí)間為Si；配送車輛在Ci客戶點(diǎn)的服務(wù)時(shí)間為Ti；配送車輛在Ci客戶點(diǎn)的等待時(shí)間為Wi；如果配送車輛k從第i個(gè)客戶前往到第j個(gè)客戶，則xijk=1，否則，xijk=0；如果客戶i的配送任務(wù)由配送車輛k完成xijk，則yik=1，否則yik=0；[ETi，LTi]表示客戶i的服務(wù)時(shí)間窗，ETi為開始服務(wù)時(shí)間，LTi為結(jié)束服務(wù)時(shí)間；

目標(biāo)函數(shù)如式(1)所示

(1)

約束條件如式(2)～式(11)所示

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Si+Wi+Ti+tij=Sj，i，j(1，2，…，n)，i≠j

(9)

ETi≤Si≤LTi，i(1，2，…，n)

(10)

Wi=max{ETi-Si，0}，i(1，2，…，n)

(11)

式(1)為目標(biāo)函數(shù)，表示完成配送服務(wù)的最短距離；式(2)為配送車輛的裝載量限制；式(3)表示配送車輛均從配送中心出發(fā)；式(4)表示配送車輛完成服務(wù)后，返回配送中心；式(5)和式(6)表示每個(gè)客戶被車輛訪問一次；式(7)表示配送車輛在服務(wù)完節(jié)點(diǎn)i后服務(wù)節(jié)點(diǎn)j；式(8)表示車輛在服務(wù)節(jié)點(diǎn)j之前服務(wù)節(jié)點(diǎn)i；式(9)、式(10)和式(11)表示時(shí)間約束，確保配送車輛在時(shí)間窗限制內(nèi)完成服務(wù)。

2 FPA的基本原理

花朵授粉算法定義請(qǐng)參見文獻(xiàn)[13]。

在理想條件下的花朵授粉可以用數(shù)學(xué)公式表示，全局授粉的位置變化公式為

(12)

(13)

式中：Г(λ) 是標(biāo)準(zhǔn)的伽馬函數(shù)。

全局授粉的位置變化公式為

(14)

3 求解帶時(shí)間窗車輛路徑問題的GA-FPA

3.1 算法思想

GA-FPA的基本思想是使用FPA和GA結(jié)合，設(shè)計(jì)一種求解VRPTW問題的混合算法。首先，針對(duì)原始FPA是用來求解連續(xù)優(yōu)化問題的情況，重新定義了FPA中的全局授粉和局部授粉操作；其次，在FPA中加入GA的交叉算子和變異算子。通過交叉算子的加入，使花朵種群中的優(yōu)良個(gè)體在種群中頻繁出現(xiàn)，提高了FPA的尋優(yōu)精度。通過變異算子的加入可以增加花朵種群的多樣性，避免FPA過早陷入局部最優(yōu)；然后，針對(duì)原始FPA中控制局部授粉和全局授粉的轉(zhuǎn)換概率p為常數(shù)，不能夠根據(jù)算法執(zhí)行情況控制全局授粉和局部首份操作的次數(shù)，進(jìn)而使算法不易于收斂和容易陷入局部最優(yōu)解等問題，對(duì)FPA中的轉(zhuǎn)換概率p進(jìn)行改進(jìn)，使其可以根據(jù)算法執(zhí)行情況，進(jìn)行自適應(yīng)調(diào)整。

3.2 全局授粉操作

在本文中，每一朵花代表群體中的一個(gè)個(gè)體，用一種排列形式表示，排列的先后順序是車輛運(yùn)輸貨物的先后順序，每朵花被認(rèn)為是一種解決方案。例如，在車輛路徑問題當(dāng)中，每朵花代表一種配送方案，排列中的節(jié)點(diǎn)表示客戶的編號(hào)，排列順序即為配送順序。在車輛路徑問題中，配送中心和客戶的位置是固定不變的，不能修改其坐標(biāo)值，所以全局授粉操作應(yīng)該是按照某種規(guī)定方式基于配送順序的改變，然后從已有的方案中得到新的配送方案。本文采用的方法是針對(duì)每種配送方案的排列順序，每次隨機(jī)選取兩個(gè)不相鄰的客戶節(jié)點(diǎn)，交換這兩個(gè)客戶節(jié)點(diǎn)的位置，判斷是否滿足約束條件，滿足則視為新的配送方案，否則視為無(wú)效解。以10個(gè)客戶節(jié)點(diǎn)為例，隨機(jī)選擇3號(hào)客戶節(jié)點(diǎn)和7號(hào)客戶節(jié)點(diǎn)，然后交換位置，從而產(chǎn)生一種配送方案，如圖1所示。

圖1 交換配送方案中兩個(gè)客戶節(jié)點(diǎn)

3.3 局部授粉操作

原始FPA中的局部授粉是隨機(jī)選取出種群中兩朵花，然后根據(jù)兩朵花的差異程度決定更新下一代花朵的位置。然而在車輛路徑問題中，要進(jìn)行局部搜索就必須小量地改變相鄰單位，從而得到新的結(jié)果，搜索步長(zhǎng)應(yīng)該較全局搜索小。所以，本文采用的方法是隨機(jī)選取種群中的兩種配送方案，隨機(jī)選擇相同下標(biāo)指定的客戶節(jié)點(diǎn)，然后對(duì)調(diào)位置，從而產(chǎn)生兩種新的配送方案。然后判斷是否滿足約束條件，如果滿足則視為新的配送方案，否則視為無(wú)效解。以10個(gè)客戶節(jié)點(diǎn)為例，隨機(jī)選擇3號(hào)客戶節(jié)點(diǎn)和c號(hào)客戶節(jié)點(diǎn)，然后交換位置，從而產(chǎn)生兩種新的配送方案，如圖2所示。

圖2 交換兩種配送方案中兩個(gè)客戶節(jié)點(diǎn)

3.4 轉(zhuǎn)換概率p的自適應(yīng)調(diào)整

在FPA中，全局授粉和局部授粉操作通過轉(zhuǎn)換概率p∈[0，1]進(jìn)行調(diào)節(jié)。在算法的執(zhí)行過程中，如果全局授粉的操作過多，那么算法易得到全局最優(yōu)解，但是不容易收斂。如果局部授粉的操作過多，那么容易陷入局部最優(yōu)解。因此需要轉(zhuǎn)化概率p對(duì)授粉操作進(jìn)行調(diào)整，如式(15)所示

p=0.8+0.2×rand

(15)

式中：rand是[0，1]之間的隨機(jī)數(shù)。在標(biāo)準(zhǔn)FPA算法中表明，p=0.8更為有效，算法性能最好，因此自轉(zhuǎn)化概率p設(shè)定在0.8附近浮動(dòng)。

通過式(15)對(duì)轉(zhuǎn)化概率p值進(jìn)行改進(jìn)后，每次迭代會(huì)更新一次p值，使每一次迭代都能夠自適應(yīng)地調(diào)節(jié)執(zhí)行概率，有效地解決了算法在全局和局部之間的平衡問題，提高了算法收斂速度。

3.5 基于精英父代的多點(diǎn)交叉算子

本文采用保留精英解的策略。首先選取當(dāng)前方案的最優(yōu)解，記為精英單親父代。隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，將交叉點(diǎn)之間的片段記為精英交叉段。隨機(jī)在群體中選取一條單親父代個(gè)體，將精英交叉段插入到該父代個(gè)體的尾部，從而得到一條新的配送方案。保持交叉片段不變，將新的配送方案中與交叉段重復(fù)的節(jié)點(diǎn)刪除，最終得到新的子代。

以客戶標(biāo)號(hào)為1-10的配送方案舉例，首先選取精英父代，然后隨機(jī)選擇精英父代中3號(hào)客戶節(jié)點(diǎn)和7號(hào)客戶節(jié)點(diǎn)為交叉位，將3號(hào)客戶節(jié)點(diǎn)到7號(hào)客戶節(jié)點(diǎn)之間作為交叉段，然后隨機(jī)選取一條客戶標(biāo)號(hào)為1-10的單親父代個(gè)體，最后將交叉段的基因插入到該個(gè)體尾部，保留交叉段不變，將新的配送方案中與交叉段重復(fù)的客戶節(jié)點(diǎn)刪除，從而產(chǎn)生一種新的配送方案。基于精英父代的多點(diǎn)交叉過程如圖3所示。

圖3 基于精英父代的多點(diǎn)交叉過程

3.6 單親多點(diǎn)基因變異換位算子

本文選取多點(diǎn)基因算子進(jìn)行變異換位操作。在一條染色體中，隨機(jī)生成多個(gè)交換節(jié)點(diǎn)，兩兩交換彼此的節(jié)點(diǎn)，其余片段保持不變，最終得到新的子代。

以客戶標(biāo)號(hào)為1-10的配送方案舉例，首先隨機(jī)選取一條客戶標(biāo)號(hào)為1-10的父代個(gè)體，然后隨機(jī)選取3號(hào)客戶節(jié)點(diǎn)和7號(hào)客戶節(jié)點(diǎn)為一對(duì)交換位對(duì)，5號(hào)客戶節(jié)點(diǎn)和9號(hào)客戶節(jié)點(diǎn)為一對(duì)交換位對(duì)，最后同時(shí)交換3號(hào)客戶節(jié)點(diǎn)和7號(hào)客戶節(jié)點(diǎn)，5號(hào)客戶節(jié)點(diǎn)和9號(hào)客戶節(jié)點(diǎn)，從而產(chǎn)生一種新的配送方案。單親多點(diǎn)基因變異換位過程如圖4所示。

圖4 單親多點(diǎn)基因變異換位過程

4 GA-FPA算法實(shí)現(xiàn)步驟

步驟1 輸入測(cè)試實(shí)例數(shù)據(jù)

數(shù)據(jù)包括客戶數(shù)目和位置、貨物需求量、時(shí)間窗、車輛載重量限制等；

步驟2 花朵種群初始化

步驟3 計(jì)算花朵目標(biāo)函數(shù)值

根據(jù)目標(biāo)函數(shù)對(duì)每個(gè)花朵位置進(jìn)行測(cè)試，得出每個(gè)花朵的目標(biāo)函數(shù)值，同時(shí)記錄當(dāng)前最優(yōu)配送路線及最少配送成本；

步驟4 按規(guī)則更新花朵位置

首先按照式(15)對(duì)轉(zhuǎn)換概率p值進(jìn)行計(jì)算，然后隨機(jī)產(chǎn)生rand∈[0，1]，如果rand>p，則按照3.2節(jié)中重新定義的全局授粉規(guī)則進(jìn)行異花授粉；否則按照3.3節(jié)中的局部授粉規(guī)則進(jìn)行自花授粉。計(jì)算更新后花朵位置的目標(biāo)函數(shù)值，與步驟3得到的最優(yōu)值相比較，選出當(dāng)前最優(yōu)位置(最優(yōu)配送路線)及最優(yōu)值(最少配送成本)；

步驟5 執(zhí)行遺傳操作

對(duì)執(zhí)行步驟4后的花朵種群中的每個(gè)花朵位置進(jìn)行遺傳操作。首先按照花朵位置的目標(biāo)函數(shù)值進(jìn)行從低到高排序，選擇出目標(biāo)函數(shù)值較低的M個(gè)個(gè)體作為重新繁殖的下一代群體。產(chǎn)生一個(gè)隨機(jī)數(shù)rand∈[0，1]。若rand≤0.5，則對(duì)花朵種群中的花朵位置按照3.5節(jié)中提出的基于父代的多點(diǎn)交叉算子進(jìn)行運(yùn)算，然后計(jì)算更新后花朵位置的目標(biāo)函數(shù)值；若rand>0.5，則對(duì)花朵種群中的花朵按照3.6節(jié)中提出的單親多點(diǎn)基因變異換位算子進(jìn)行運(yùn)算，計(jì)算更新后花朵位置的目標(biāo)函數(shù)值。將步驟4得到的最優(yōu)值與遺傳操作后的花朵位置的目標(biāo)函數(shù)值進(jìn)行比較，選出當(dāng)前的最優(yōu)位置及最優(yōu)值；

步驟6 終止條件

令t=t+1，若t≤T，則轉(zhuǎn)步驟3；否則輸出當(dāng)前最優(yōu)值(總的最少配送成本)和相對(duì)應(yīng)的最優(yōu)位置(最優(yōu)配送路線)；

5 實(shí)驗(yàn)分析

為了測(cè)試算法的有效性及求解性能，使用著名的Solomon算例為實(shí)驗(yàn)測(cè)試數(shù)據(jù)(數(shù)據(jù)來源：http：//www.ber-nabe.dorronsoro.es/vrp/)，并使用GA-FPA算法對(duì)其求解。算法使用Python編程實(shí)現(xiàn)，在操作系統(tǒng)：OS X EI Capitan，CPU：2.7 GHz Intel Core i5，內(nèi)存：8.00 GB的MacBook Pro主機(jī)上運(yùn)行所得。

取該測(cè)試算例里C104、R208、RC107中規(guī)模為25個(gè)客戶和C104、R101中規(guī)模為50個(gè)客戶的情形進(jìn)行測(cè)試，求解次數(shù)均為20次，求解結(jié)果見表1。對(duì)于客戶數(shù)為25的算例，種群規(guī)模indSize=50，進(jìn)化代數(shù)max_gen=50；對(duì)于客戶數(shù)為50的算例，種群規(guī)模indSize=100，進(jìn)化代數(shù)max_gen=50。配送路徑的單位配送成本unitCost=8，車輛的租賃費(fèi)為initCost=100，車輛早到的等待成本waitCost=1，車輛遲到的懲罰成本delayCost=1.5。

表1 標(biāo)準(zhǔn)測(cè)試算例運(yùn)算結(jié)果

表1為準(zhǔn)測(cè)試算例運(yùn)算結(jié)果，給出了在標(biāo)準(zhǔn)遺傳算法、粒子群算法、FPA算法、粒子群改進(jìn)算法、狼群算法以及本文提出的GA-FPA算法在算例中的表現(xiàn)，并給出GA-FPA算法最優(yōu)解與已知最優(yōu)解的gap值 (gap=((GA-FPA算法求解結(jié)果-已知最優(yōu)路徑長(zhǎng)/已知最優(yōu)路徑長(zhǎng))*100%))。

表1采用文獻(xiàn)[15]的算例，設(shè)置相同的參數(shù)進(jìn)行對(duì)比。結(jié)果發(fā)現(xiàn)，在25個(gè)客戶數(shù)的情況下，GA-FPA在C104、R208數(shù)據(jù)集的結(jié)果優(yōu)于粒子群改進(jìn)算法，以及改進(jìn)的狼群算法。但是在RC107數(shù)據(jù)集中，GA-FPA算法的效果則低于上述兩種算法。在50個(gè)客戶數(shù)的情況下，GA-FPA在C104數(shù)據(jù)集的效果優(yōu)于狼群算法。盡管GA-FPA在小部分?jǐn)?shù)據(jù)集上不如其它改進(jìn)算法，但在大部分?jǐn)?shù)據(jù)集上結(jié)果優(yōu)于其它改進(jìn)算法，總體來看GA-FPA算法能優(yōu)于其它算法，本實(shí)驗(yàn)具有可比性。

由表1可知，GA-FPA算法求得的最優(yōu)解與已知最優(yōu)解中使用的車輛數(shù)基本相同，結(jié)果如表2～表6所示。但是在R101算例中，GA-FPA算法求解結(jié)果使用的車輛數(shù)較最優(yōu)解少，結(jié)果見表5，有50個(gè)客戶(編號(hào)1-50)和1個(gè)配送中心(編號(hào)0)。盡管其總路程較最優(yōu)解大一些，但其gap值大部分不超過5%。GA-FPA算法在解決多客戶的VRPTW問題上，與GA、粒子群算法、原始FPA、粒子群改進(jìn)算法以及狼群算法相比具有一定優(yōu)勢(shì)?？傮w來看，GA-FPA算法能夠在較小的迭代次數(shù)和較小種群規(guī)模的實(shí)驗(yàn)中取得較好的結(jié)果，并且算例結(jié)果十分接近最優(yōu)解。

表2 GA-FPA求解C104(25個(gè)客戶)算例

表3 GA-FPA求解R208(25個(gè)客戶)算例

表4 GA-FPA求解RC107(25個(gè)客戶)算例

表5 GA-FPA求解C104(50個(gè)客戶)算例

表6 GA-FPA求解R101(50個(gè)客戶)算例

對(duì)GA-FPA中控制全局授粉和局部授粉的轉(zhuǎn)換概率p的取值進(jìn)行實(shí)驗(yàn)測(cè)試。取測(cè)試算例里C104、R208、RC107、R101中規(guī)模為25個(gè)客戶和50個(gè)客戶的情形進(jìn)行測(cè)試，首先令p=0.8，分別求解次數(shù)均為20次，記錄下車輛運(yùn)輸費(fèi)用。然后按照式(15)對(duì)p值進(jìn)行賦值，使其可以根據(jù)程序執(zhí)行情況，進(jìn)行自適應(yīng)調(diào)整，然后記錄下車輛運(yùn)輸費(fèi)用，進(jìn)行對(duì)比，結(jié)果見表7。由表7可知，對(duì)轉(zhuǎn)換概率p值進(jìn)行改進(jìn)后，每迭代一次，更新一次p值，自適應(yīng)地調(diào)節(jié)搜索執(zhí)行概率，對(duì)求解到的目標(biāo)值(車輛的運(yùn)輸費(fèi)用)有所下降。有效解決了算法的全局搜索和局部搜索之間的平衡問題，避免了FPA陷入局部最優(yōu)。

表7 轉(zhuǎn)換概率p取值的運(yùn)算結(jié)果

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

本文設(shè)計(jì)了一種求解VRPTW的GA-FPA算法，算法通過加入基于精英父代的多點(diǎn)交叉算子，提高了FPA的尋優(yōu)精度。通過加入單親多點(diǎn)基因變異換位算子和對(duì)轉(zhuǎn)換概率p值進(jìn)行改進(jìn)，自適應(yīng)地調(diào)節(jié)全局搜索和局部搜索的執(zhí)行概率兩種策略避免了FPA過早陷入局部最優(yōu)。算法求解結(jié)果與已知最優(yōu)解和GA、粒子群算法、原始FPA、粒子群改進(jìn)算法以及狼群算法進(jìn)行對(duì)比，結(jié)果表明GA-FPA具有更優(yōu)的求解精度與收斂性，是一種行之有效的求解VRPTW的算法。今后在此基礎(chǔ)上，進(jìn)一步研究改進(jìn)FPA及其它新的群智能算法在低碳約束下的物流配送車輛路徑問題上的應(yīng)用。