王 君

（天津財(cái)經(jīng)大學(xué)商學(xué)院，天津300222）

1 引言

隨著顧客對(duì)物流配送要求的提高，帶時(shí)間窗的車輛路徑問題VRPTW（Vehicle Routing Problem with Time Windows）一直是物流與供應(yīng)鏈管理的熱點(diǎn)問題。VRPTW是典型的組合優(yōu)化問題，主要采用啟發(fā)式優(yōu)化算法進(jìn)行求解。啟發(fā)式算法分為以禁忌搜索TS（Tabu Search）［1］為代表的局部搜索和以遺傳算法GA（Genetic Algorithm）［2］為代表的種群搜索兩大類。現(xiàn)在更加趨向于多種搜索機(jī)制的結(jié)合，以彌補(bǔ)單一啟發(fā)式算法的不足。

文化基因算法MA（Memetic Algorithm）是以文化進(jìn)化思想為指導(dǎo)的智能優(yōu)化算法，用局部搜索來模擬文化進(jìn)化過程，既具有群體算法搜索范圍大的優(yōu)點(diǎn)，又具有局部算法搜索的深度優(yōu)勢(shì)［3］，目前已經(jīng)出現(xiàn)了用MA求解車輛路徑問題的研究［4］。多目標(biāo)文化基因算法MOMA（Multi－Objective MA）是采用多目標(biāo)優(yōu)化機(jī)制的MA算法，已經(jīng)成功應(yīng)用到車間調(diào)度［5］、物流網(wǎng)絡(luò)設(shè)計(jì)［6］、飛機(jī)航線調(diào)度［7］等多目標(biāo)優(yōu)化問題中。

VRPTW需要同時(shí)考慮車輛的使用數(shù)和車輛行駛距離兩個(gè)目標(biāo)，因此它也是一個(gè)多目標(biāo)優(yōu)化問題，現(xiàn)有研究大部分采用多目標(biāo)進(jìn)化算法求Pareto最優(yōu)解集［8，9］，然而用MOMA解決VRPTW的研究十分罕見。本文基于以上研究成果，提出求解VRPTW的一種MOMA算法，運(yùn)用不同的適應(yīng)度函數(shù)分別支持種群和局部精英解的選擇。對(duì)國際通用的benchmark數(shù)據(jù)進(jìn)行仿真對(duì)比實(shí)驗(yàn)，表明本文提出的MOMA算法是求解VRPTW問題的有效方法。

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

一個(gè)VRPTW描述為：設(shè)G＝｛I，E｝為一個(gè)完備的無向圖，其中，I＝｛0，1，2，…，n｝為節(jié)點(diǎn)集；E＝｛i，j｝為邊集，i，j∈I且i≠j。0代表車庫點(diǎn)，其余為顧客點(diǎn)，一隊(duì)具有相同裝載能力的車輛從車庫點(diǎn)出發(fā)，實(shí)現(xiàn)對(duì)所有顧客點(diǎn)的配送服務(wù)，最終回到車庫。每個(gè)顧客點(diǎn)有一個(gè)固定的需求和固定的服務(wù)時(shí)間，并且只能由一輛車服務(wù)。車輛必須在時(shí)間窗內(nèi)到達(dá)顧客點(diǎn)，且不能晚于結(jié)束時(shí)間；如果車輛到達(dá)時(shí)間早于顧客規(guī)定的時(shí)間窗開始時(shí)間，那么車輛需要等待。優(yōu)化目標(biāo)是確定車輛的行駛路線，在滿足顧客要求的前提下，使得總費(fèi)用最小。

為描述方便，定義如下的標(biāo)號(hào)和參數(shù)變量：

cij：表示節(jié)點(diǎn)i和節(jié)點(diǎn)j間的距離；

V：表示車輛集合；

tij、ati、wti、sti：分別表示車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間、到達(dá)節(jié)點(diǎn)i的時(shí)間、在服務(wù)節(jié)點(diǎn)i前的等待時(shí)間和服務(wù)節(jié)點(diǎn)i的持續(xù)服務(wù)時(shí)間；

［Ei，Li］：節(jié)點(diǎn)i的時(shí)間窗，最早和最遲開始服務(wù)時(shí)間；

di：表示第i個(gè)顧客的配送貨物量；

Qv：車輛v的載重量；

xijv：是0－1類型的決策變量，即：

那么，VRPTW的數(shù)學(xué)模型為：

滿足以下條件：

其中，式（1）表示目標(biāo)函數(shù)，同時(shí)最小化使用車輛數(shù)和車輛行駛總路徑長(zhǎng)度兩個(gè)目標(biāo)。式（2）和式（3）表示每輛車都要從車庫出發(fā)，最終回到車庫。式（4）和式（5）表示每個(gè)顧客有且僅有一輛車為其服務(wù)。式（6）表示運(yùn)貨量不能超過車輛的載重量。式（7）、式（8）分別是車輛在節(jié)點(diǎn)i的等待時(shí)間、到達(dá)節(jié)點(diǎn)j的時(shí)間的計(jì)算公式，其中wt0＝0，at0＝0，st0＝0。式（9）是時(shí)間窗約束，即顧客到達(dá)節(jié)點(diǎn)i的時(shí)間需在時(shí)間窗關(guān)閉之前。式（10）指決策變量是0－1變量。

3 多目標(biāo)文化基因算法

3.1 精英解的存儲(chǔ)和選擇機(jī)制

MOMA算法是基于種群的全局搜索和基于個(gè)體的局部搜索的結(jié)合，因此首先要解決的是如何協(xié)調(diào)種群搜索和局部搜索得到的Pareto非占優(yōu)解的相互關(guān)系。如圖1所示，對(duì)父代種群經(jīng)過交叉操作得到的每個(gè)新個(gè)體進(jìn)行局部搜索，搜索得到的局部最優(yōu)解作為子代的個(gè)體。采用一個(gè)容量足夠大的存儲(chǔ)池結(jié)構(gòu)來存儲(chǔ)局部搜索得到的Pareto非占優(yōu)解。比較存儲(chǔ)池中的解集，如果在局部搜索過程中得到了新的Pareto非占優(yōu)解，那么就用其更新存儲(chǔ)池中的一個(gè)劣解。局部搜索完成后，對(duì)父代種群、子代種群和存儲(chǔ)池中的所有解采用基于Pareto排序和擁擠度的選擇機(jī)制［10］進(jìn)行選擇操作，得到新的父代種群，然后進(jìn)行新的一次迭代過程。

3.2 適應(yīng)度函數(shù)

因?yàn)榉N群搜索和局部搜索的機(jī)制不同，所以在同時(shí)考慮個(gè)體的兩個(gè)目標(biāo)函數(shù)時(shí)，采用兩種不同的適應(yīng)度函數(shù)，分別應(yīng)用于對(duì)種群的選擇操作和對(duì)局部搜索的最優(yōu)解選擇操作。

Figure 1 Diagram of elite solutions storage and coordination mechanism圖1 精英解的存儲(chǔ)和協(xié)調(diào)機(jī)制示意圖

種群的選擇操作采用基于Pareto排序和擁擠度的度量方法［10］，即：

其中，第一項(xiàng)rank（x）表示Pareto占優(yōu)的層級(jí)關(guān)系，rank（x）＜rank（y）表示解x占優(yōu)y。第二項(xiàng)Crowding－distance（x）是擁擠距離，描述了在同一rank中x與相鄰兩個(gè)解的距離，距離越大表示該解越好。在進(jìn)行選擇操作時(shí)，對(duì)父代種群、子代種群和存儲(chǔ)池中的所有解按照第一關(guān)鍵字是rank升序、第二關(guān)鍵字是Crowding－distance降序的方式進(jìn)行排序，然后選擇前N個(gè)（N為種群規(guī)模200）個(gè)體進(jìn)入下一代。

在局部搜索過程中，每次都要從候選的鄰域解列表中選擇一個(gè)最好的解來更新當(dāng)前解，然后繼續(xù)搜索其鄰域，因此可以引入Pareto強(qiáng)度的概念來定義局部搜索運(yùn)用的適應(yīng)度函數(shù)［11］。

其中，S（x）是在存儲(chǔ)池中被x占優(yōu)的解的個(gè)數(shù)，W（x）是在存儲(chǔ)池中占優(yōu)x的解的個(gè)數(shù)。局部適應(yīng)度函數(shù)反映了解x在解集中Pareto占優(yōu)關(guān)系的強(qiáng)弱程度，若x強(qiáng)度大，則適應(yīng)度高，表明x在解集中處于優(yōu)勢(shì)地位，可以在局部搜索過程中優(yōu)先搜索處于優(yōu)勢(shì)地位解的鄰域。

3.3 染色體編碼方式、初始種群的生成及交叉算子

MOMA算法采用車輛行駛路徑順序的自然數(shù)編碼方式。用自然數(shù)表示顧客；0表示車庫，用來區(qū)分不同車輛的行駛路徑。假如，三輛車的行駛路徑分別為（1→2→3）、（4→5）和（6→7→8），車庫中有五輛車，則染色體編碼為（0，1，2，3，0，4，5，0，6，7，8，0，0）。

采用隨機(jī)車輛配載方法生成初始種群個(gè)體，每個(gè)個(gè)體對(duì)應(yīng)一個(gè)可行解。具體方法為：首選，對(duì)顧客按照時(shí)間窗結(jié)束時(shí)間Li由早到晚排序得到顧客序列，根據(jù)載重量和時(shí)間窗估計(jì)每輛車服務(wù)顧客的數(shù)量N＊；然后，在顧客序列中以大致等長(zhǎng)的間隔隨機(jī)抽取N＊個(gè)顧客組成一條路徑，并保證滿足時(shí)間窗和載重量約束。要求間隔的選擇具有一定的隨機(jī)性，這樣就可以生成不同的初始解。

交叉算子采用Ombuki等［8］的方法，隨機(jī)選擇兩個(gè)父代染色體P1、P2，每個(gè)染色體隨機(jī)選取一輛車所服務(wù)的顧客序列作為交叉信息，記為…和s…，然后把…從P1中移除，應(yīng)用插入可行鄰域［12］，再依次把…插回到P1中，得到子代個(gè)體。同樣，把s…先從P中移除再2依次插回，得到另一個(gè)子代個(gè)體。

3.4 局部禁忌搜索機(jī)制

利用插入可行鄰域和2－Opt可行鄰域［12］兩種鄰域結(jié)構(gòu)，對(duì)父代種群交叉操作后得到的中間種群進(jìn)行禁忌搜索，鄰域結(jié)構(gòu)采取隨機(jī)選擇的策略。插入可行鄰域的禁忌對(duì)象設(shè)置為鄰域類型以及插入的顧客和插入點(diǎn)的緊后顧客組成的顧客對(duì)；2－Opt可行鄰域的禁忌對(duì)象設(shè)置為鄰域類型以及兩個(gè)路徑斷點(diǎn)的緊后顧客組成的顧客對(duì)。禁忌長(zhǎng)度設(shè)置最小值LMINTA和最大值LMAXTA，在局部搜索中禁忌長(zhǎng)度由最小值均勻地增大到最大值。藐視準(zhǔn)則為若禁忌對(duì)象對(duì)應(yīng)的適應(yīng)度函數(shù)fit2（x）優(yōu)于最好解，則無視其禁忌屬性而仍采納其為當(dāng)前選擇。設(shè)置兩種停止規(guī)則：一種是設(shè)置一個(gè)最大迭代數(shù)IMTA；另一種是在INMTA（INMTA＜IMTA）次迭代內(nèi)所發(fā)現(xiàn)的最好解無法改進(jìn)，即停止局部搜索。

3.5 算法總體流程

MOMA結(jié)合了種群搜索和個(gè)體搜索，選擇不同的進(jìn)化操作和局部搜索策略構(gòu)成不同的MOMA。本文選擇對(duì)初始種群和進(jìn)行交叉操作后得到的子代種群進(jìn)行局部搜索，MOMA的具體流程如算法1的偽代碼所示。

4 仿真實(shí)驗(yàn)

測(cè)試采用Solomon的r1和rc1兩類benchmark數(shù)據(jù)（數(shù)據(jù)來自http：//web.cba.neu.edu/～msolomon/problems.htm），r類數(shù)據(jù)集節(jié)點(diǎn)的地理位置為隨機(jī)生成，rc類數(shù)據(jù)集的每個(gè)算例的一部分顧客需求是隨機(jī)生成，另一部分顧客需求在地理位置或者服務(wù)時(shí)間窗上具有聚集特征。算法用VC＋＋6.0編程實(shí)現(xiàn)，在Intel Pentium Dual T2410 CPU 2 GHz、1 GB內(nèi)存、Windows XP SP3的主機(jī)上運(yùn)行。

與不帶局部搜索的多目標(biāo)算法NSGA－Ⅱ和線性加權(quán)的單目標(biāo)MA算法進(jìn)行對(duì)比實(shí)驗(yàn)，以驗(yàn)證本文提出的MOMA算法的有效性。經(jīng)多次反復(fù)實(shí)驗(yàn)設(shè)置MOMA算法的參數(shù)為：種群規(guī)模200，進(jìn)化代數(shù)80，候選解數(shù)目300，LMINTA＝5，LMAXTA＝20，IMTA＝1000，INMTA＝100。MA采取順序優(yōu)化的方式，首先優(yōu)化車輛使用數(shù)目標(biāo)，然后優(yōu)化車輛行駛總路徑長(zhǎng)度，可以加權(quán)目標(biāo)函數(shù)為min（1000f1＋f2），并作為個(gè)體的適應(yīng)度，在種群選擇過程中選取適應(yīng)度小的個(gè)體進(jìn)入下一代。

NSGA－Ⅱ參數(shù)為：進(jìn)化代數(shù)800，變異算子為2－Opt可行鄰域，變異概率0.2，其余參數(shù)和MOMA相同。GA較MA選擇較大的進(jìn)化代數(shù)是考慮了收斂效果和計(jì)算耗時(shí)兩個(gè)因素。每個(gè)算例均獨(dú)立運(yùn)行10次，記錄最好解。性能對(duì)比結(jié)果如表1所示，每個(gè)解包括使用的車輛數(shù)nv、總路徑長(zhǎng)度和平均運(yùn)行時(shí)間。對(duì)比三種算法的求解結(jié)果，用加粗的字體顯示了較好的解和較快的求解時(shí)間。

從計(jì)算耗時(shí)來看，NSGA－Ⅱ、MA和MOMA呈遞增趨勢(shì)，這是因?yàn)榫植拷伤阉餍枰趥€(gè)體的基礎(chǔ)上搜索大量的鄰域結(jié)構(gòu)，從而增加了程序的運(yùn)行時(shí)間，而基于Pareto的排序又增加了MOMA的運(yùn)算時(shí)間。但是，從求解質(zhì)量上看，MA和MOMA都要明顯優(yōu)于NSGA－Ⅱ，說明局部搜索策略可以顯著提高算法的尋優(yōu)能力。比較MA和MOMA，有10個(gè)算例雙方都得到了唯一解。這10個(gè)算例中MA和MOMA各有5個(gè)解要好于對(duì)方，說明基于Pareto的優(yōu)化方式在求解有唯一最優(yōu)解的情況時(shí)不差于線性加權(quán)的方法，魯棒性較好。在其余的10個(gè)算例中，MOMA都得到了多個(gè)解，其中有7個(gè)算例MOMA得到的Pareto最優(yōu)解都要好于MA，有2個(gè)算例（r102和r109）MA得到的最優(yōu)解好于MOMA的某個(gè)最優(yōu)解，而只有1個(gè)算例（rc101）MA得到的最優(yōu)解好于MOMA得到的所有Pareto最優(yōu)解，說明MOMA求解多目標(biāo)問題時(shí)具有很大的優(yōu)勢(shì)。

5 結(jié)束語

本文提出了求解VRPTW問題的多目標(biāo)文化基因算法，種群搜索采用遺傳算法的進(jìn)化模式，局部搜索采用禁忌搜索機(jī)制。種群的選擇操作采用基于Pareto排序和擁擠度的度量方法來定義適應(yīng)度函數(shù)，局部搜索采用Pareto強(qiáng)度來定義適應(yīng)度函數(shù)。對(duì)比實(shí)驗(yàn)結(jié)果表明，帶局部搜索機(jī)制的

MOMA明顯優(yōu)于不帶局部搜索的NSGA－Ⅱ，而且

MOMA的多目標(biāo)機(jī)制對(duì)優(yōu)化最優(yōu)解唯一的問題具有魯棒性，是求解VRPTW問題的一種有效的多目標(biāo)優(yōu)化算法。這對(duì)研究其他類型的車輛路徑問題和多目標(biāo)優(yōu)化方法提供了一定的參考。

［1］ Gendreau M，Hertz A，Laporte G.A tabu search heuristic for the vehicle routing problem［J］.Management Science，1994，40（10）：1276－1290.

［2］ Chen Sen，Jiang Jiang，Chen Ying－wu，et al.A class of nondeterministic vehicle routing problem model and its algorithm design［J］.Computer Engineering，2011，37（14）：186－188.（in Chinese）

［3］ Krasnogor N，Smith J.A tutorial for competent memetic algorithms：Model，taxonomy，and design issues［J］.IEEE Transactions on Evolutionary Computation，2005，9（5）：474－488.

［4］ Labadi N，Prins C，Reghioui M.A memetic algorithm for the vehicle routing problem with time windows［J］.Rairo－Operations Research，2008，42（3）：415－431.

［5］ Qian B，Wang L，Huang D－X，et al.Scheduling multi－objective job shops using a memetic algorithm based on differential evolution［J］.International Journal of Advanced Manufacturing Technology，2008，35（9－10）：1014－1027.

Table 1 Experimental results表1 程序運(yùn)行結(jié)果

［6］ Pishvaee M S，F(xiàn)arahani R Z，Dullaert W.A memetic algorithm for bi－objective integrated forward/reverse logistics network design［J］.Computers ＆Operations Research，2010，37（6）：1100－1112.

［7］ Burke E K，de Causmaecker P，de Maere G，et al.A multiobjective approach for robust airline scheduling［J］.Computers ＆Operations Research，2010，37（5）：822－832.

［8］ Ombuki B，Ross B J，Hanshar F.Multi－objective genetic al－gorithms for vehicle routing problem with time windows［J］.Applied Intelligence，2006，24（1）：17－30.

［9］ Jozefowiez N，Semet F，Talbi E G.An evolutionary algorithm for the vehicle routing problem with route balancing［J］.European Journal of Operational Research，2009，195（3）：761－769.

［10］ Deb K，Pratap A，Agarwal S，et al.A fast and elitist multiobjective genetic algorithm：NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197.

［11］ Carcangiu S，F(xiàn)anni A，Montisci A.Multiobjective tabu search algorithms for optimal design of electromagnetic devices［J］.IEEE Transactions on Magnetics，2008，44（6）：970－973.

［12］ Wang Jun，Li Bo.Multi－objective tabu search algorithm for vehicle routing problem with fuzzy due－time［J］.Computer Integrated Manufacturing Systems，2011，17（4）：858－866.（in Chinese）

附中文參考文獻(xiàn)：

［2］ 陳森，姜江，陳英武，等.一類非確定性車輛路徑問題模型及其算法設(shè)計(jì)［J］.計(jì)算機(jī)工程，2011，37（14）：186－188.

［12］ 王君，李波.帶模糊預(yù)約時(shí)間的車輛路徑問題的多目標(biāo)禁忌搜索算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（4）：858－866.