王 君

（天津財經大學商學院，天津300222）

1 引言

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

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

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

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

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

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

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

V：表示車輛集合；

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

［Ei，Li］：節(jié)點i的時間窗，最早和最遲開始服務時間；

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

Qv：車輛v的載重量；

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

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

滿足以下條件：

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

3 多目標文化基因算法

3.1 精英解的存儲和選擇機制

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

3.2 適應度函數(shù)

因為種群搜索和局部搜索的機制不同，所以在同時考慮個體的兩個目標函數(shù)時，采用兩種不同的適應度函數(shù)，分別應用于對種群的選擇操作和對局部搜索的最優(yōu)解選擇操作。

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

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

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

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

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

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）。

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

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

3.4 局部禁忌搜索機制

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

3.5 算法總體流程

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

4 仿真實驗

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

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

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

從計算耗時來看，NSGA－Ⅱ、MA和MOMA呈遞增趨勢，這是因為局部禁忌搜索需要在個體的基礎上搜索大量的鄰域結構，從而增加了程序的運行時間，而基于Pareto的排序又增加了MOMA的運算時間。但是，從求解質量上看，MA和MOMA都要明顯優(yōu)于NSGA－Ⅱ，說明局部搜索策略可以顯著提高算法的尋優(yōu)能力。比較MA和MOMA，有10個算例雙方都得到了唯一解。這10個算例中MA和MOMA各有5個解要好于對方，說明基于Pareto的優(yōu)化方式在求解有唯一最優(yōu)解的情況時不差于線性加權的方法，魯棒性較好。在其余的10個算例中，MOMA都得到了多個解，其中有7個算例MOMA得到的Pareto最優(yōu)解都要好于MA，有2個算例（r102和r109）MA得到的最優(yōu)解好于MOMA的某個最優(yōu)解，而只有1個算例（rc101）MA得到的最優(yōu)解好于MOMA得到的所有Pareto最優(yōu)解，說明MOMA求解多目標問題時具有很大的優(yōu)勢。

5 結束語

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

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

MOMA的多目標機制對優(yōu)化最優(yōu)解唯一的問題具有魯棒性，是求解VRPTW問題的一種有效的多目標優(yōu)化算法。這對研究其他類型的車輛路徑問題和多目標優(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 程序運行結果

［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）

附中文參考文獻：

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

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