程松山，楊 濤 CHENG Song-shan,YANG Tao

車輛路徑優(yōu)化問題 （Vehicle Routing Problem，VRP）最早是由Dantzig[1]提出的，是現(xiàn)代物流系統(tǒng)中關(guān)鍵的一環(huán)。時(shí)間窗的車輛路徑問題 （Vehicle Routing Problem with Time Window,VRPTW）是對簡單車輛路徑問題（VRP）的進(jìn)一步擴(kuò)展。目前，國內(nèi)外關(guān)于VRPTW的研究很多，如Braysy O[2]、KIT M[3]、Joe[4]、李軍[5]和朗茂祥[6]等。本文提出一種基于小生境的改進(jìn)的混合遺傳算法，采用并行選擇法構(gòu)造Pareto解以及精英保留策略，從而克服了遺傳算法搜索速度慢、局部搜索能力差以及 “早熟”的先天性不足。

1 數(shù)學(xué)模型

1.1 VRPTW問題描述

假設(shè)中心倉庫有k輛載重均為Q的車，為n個(gè)等待客戶服務(wù)，已知倉庫中心和每個(gè)客戶端位置坐標(biāo)、客戶的貨物需求量和允許的服務(wù)的時(shí)間窗口以及服務(wù)時(shí)間。試尋求最優(yōu)的車輛配送路線，使得分派到車輛數(shù)最少，且配送過程中的總行駛路程最短。

1.2 數(shù)學(xué)模型

式中：M為車輛數(shù)目集，M=｛k=1,2,…,m ｝，m是一個(gè)待定的決策的變量；C為客戶集，C=｛i,j=1,2,…,m ｝，i,j=0時(shí)為中心倉庫；dij為客戶i與客戶j之間的距離；qi為客戶i的需求量；sik為車輛k到達(dá)客戶i的時(shí)間；si為車輛在客戶i處的服務(wù)時(shí)間。

式 （1）表示總行車路程最短；式 （2）表示指派最少的車輛；式 （3）表示從中心倉庫出發(fā)點(diǎn)車輛數(shù)不能超過故有的車輛數(shù)m；式 （4）表示每一個(gè)客戶只能有一輛車輛服務(wù)且每個(gè)客戶均能得到服務(wù)；式 （5）表示保證車輛從中心倉庫出發(fā)并最終回到中心倉庫；式 （6）表示每輛車輛運(yùn)送的貨物重量不能超過車輛的定額載荷；式 （7）表示每輛車服務(wù)的客戶總數(shù)不能大于客戶總數(shù)目；式 （8）客戶i允許的服務(wù)時(shí)間窗口。

2 算法設(shè)計(jì)

2.1 染色體的編碼方式及初始群體的生成

本文染色體采用自然數(shù)編碼方式。即染色體V=｛vi｝（i=1,2,…,n ），vi表示染色體的基因，對應(yīng)于第i個(gè)客戶的編號，如，V=｛4,2,5,3,1 ｝就是一條染色體。染色體中沒有路線分界點(diǎn)的基因位。

初始群體個(gè)體初始化的方法是前相插入法，生成一個(gè)好的可行個(gè)體，然后在此個(gè)體的鄰域內(nèi)生成部分個(gè)體，這些個(gè)體數(shù)占初始群體規(guī)模的十分之一，余下的十分之九的個(gè)體隨機(jī)產(chǎn)生。

2.2 適應(yīng)函數(shù)的構(gòu)造

本文適應(yīng)函數(shù)的構(gòu)造采用Murata，Ishibuchi和Tanaka提出的隨機(jī)權(quán)重法 （random-weight approach）[7-8]。該方法能夠使得遺傳算法具有可變搜索方向，在整個(gè)Pareto前沿面上進(jìn)行均勻采樣的能力。

設(shè)最小化的q個(gè)目標(biāo)函數(shù)，權(quán)重和目標(biāo) （weighted-sum objective）如下所示：

其中fk（）x=zk,k=1,2，隨機(jī)權(quán)重wk由下式計(jì)算：

其中ri是非負(fù)隨機(jī)數(shù)。

但是式 （9）實(shí)際存在問題，那就是fk（x）之間的單位不統(tǒng)一，而且兩者之間的數(shù)據(jù)相差幾十倍，這樣如果不將其進(jìn)行改進(jìn)，f1（x）的量有可能將f2（x ）的量 “淹沒”，這樣就會導(dǎo)致f2（x ）這個(gè)目標(biāo)值名存實(shí)亡。鑒于此，本文將其改進(jìn)為：

其中fkmax（x）是每一代過程中種群最大值。

2.3 交叉操作

首先隨機(jī)地在染色體串中選擇一個(gè)交叉區(qū)域。如兩父串及交叉區(qū)域?yàn)?，A=1|234|5，B=2|341|5，然后將B的交叉區(qū)域放到A的最前面，將A的交叉區(qū)域放到B的最前面，分別得到A′=34112345，B′=23423415，最后分別在A′和B′中最交叉區(qū)域后依次刪除與交叉區(qū)域相同的點(diǎn)，得到最終交叉后產(chǎn)生的兩個(gè)新染色體，A′=34125，B′=23415。該方法對維持種群的多樣性有較好的作用。

2.4 變異操作

傳統(tǒng)的均勻操作不便于對某一重點(diǎn)區(qū)域進(jìn)行局部搜索，其局部操作能力較差，故本文采用非均勻變異操作[9]。在進(jìn)行由V=v1v2…vk…vp向的非均勻變異操作時(shí)，若變異點(diǎn)vk的基因值取值范圍為則新的基因值由下式確定：

式中t是循環(huán)變量，T是最大進(jìn)化代數(shù)，b是一個(gè)系統(tǒng)參數(shù)，決定算法的收斂壓力，r是一個(gè)0,（）1內(nèi)均勻產(chǎn)生的隨機(jī)數(shù)。

2.5 混合并行遺傳算法

多目標(biāo)優(yōu)化問題的遺傳算法的選擇操作有并列選擇法、排序選擇法和共享函數(shù)法等多種方法。各種方法都有自己的優(yōu)缺點(diǎn)[9]，鑒于此，本文混合使用上述幾種求解多目標(biāo)優(yōu)化問題的方法，盡可能的克服各自的缺點(diǎn)，而充分發(fā)揮各自的優(yōu)點(diǎn)。把它叫做混合并列選擇法[9]，其選擇過程如下：

（1）并列選擇過程。按所求多目標(biāo)優(yōu)化問題的子目標(biāo)函數(shù)的個(gè)數(shù)，將整個(gè)群體均等劃分為一些子群體，各個(gè)子目標(biāo)函數(shù)在相應(yīng)的子群體中產(chǎn)生其下一代群體。

（2）保留Perato最優(yōu)個(gè)體過程。在每一代的過程中，對于各個(gè)子群體中的Perato最優(yōu)個(gè)體，不讓其參與個(gè)體的交叉和變異運(yùn)算，而是讓其直接保留到下一代子群體中。這樣可以避免因交叉和變異運(yùn)算導(dǎo)致的破壞良好的染色體，加快其搜索速度。

（3）共享函數(shù)處理過程。若得到的Perato最優(yōu)個(gè)體是數(shù)量已超過規(guī)定的群體規(guī)模，則需要利用共享函數(shù)法對最優(yōu)個(gè)體進(jìn)行挑選，以形成規(guī)定規(guī)模的新一代群體。

3 實(shí)例與分析

為了測試算法的有效性，分別采用文獻(xiàn)[10-13]的5個(gè)典型問題進(jìn)行了測試，并于目前已知的最好解進(jìn)行了比較。

算法用Java語言編程，在PC586兼容機(jī)上運(yùn)行。參數(shù)設(shè)置：種群規(guī)模M=100，最大進(jìn)化代數(shù)為200，交叉概率pc=0.8，pm=0.001。計(jì)算最好目標(biāo)值和最差目標(biāo)值，然后計(jì)算平均值，測試結(jié)果如表1所示。以問題1（見表2）為例，給出所求最好解的各條路徑。

從表1可見：

（1）在算法中采用非均勻變異，適應(yīng)值的計(jì)算采用隨機(jī)權(quán)重法，這樣該算法在初始運(yùn)行階段進(jìn)行均勻隨機(jī)搜索，而在其后期運(yùn)行階段進(jìn)行局部操作，使得該算法所得的解與已知最優(yōu)解的偏差小，而且明顯好于參考文獻(xiàn)[14]的結(jié)果。

（2）小生境的混合并行選擇法以及精英保留策略使得本算法有較高的運(yùn)行效率和收斂性，使得解的質(zhì)量和求解速度上都得到了提高。

表1 測試結(jié)果

從表2中可以看出，各條路徑中的車輛的裝載率都比較高。因此本算法是有效的。

表2 n=50,Q=160

4 結(jié) 論

本文在描述問題模型的基礎(chǔ)上，從多目標(biāo)角度出發(fā)，針對傳統(tǒng)的遺傳算法存在的收斂速度慢、易早熟、局部搜索能力差等缺點(diǎn)，采用精英保留策略，引入自適應(yīng)變異算子，并使用隨機(jī)權(quán)重的適應(yīng)函數(shù)，從而構(gòu)造了一種基于小生境的混合并行選擇法的改進(jìn)遺傳算法。仿真實(shí)驗(yàn)表明該算法對于解決車輛數(shù)不確定的時(shí)間窗車輛路徑問題提供了一個(gè)非常有效的求解方法。

[1] Dantzig G,Ramser J.The truck dispatching problem[J].Management Science,1959(6):80-91.

[2]BRAYSY O,DULLAERTW,GENDREAUV M.Evolutionary algorithms for the vehicle routing problem with time windows[J].J Heu-ristics,2004,10(6):5872-11.

[3]KITM,HBR ID A.Genetic algorithm for the vehicle routing problem with time windows[J].International J on Artificial Intelligence Tools,2001,10(3):431-449.

[4] Joe L,Rover L.Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms[C]//Proceedings of the Fifth International Conference on Genetic Algorithms,1993:452-459.

[5] 李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社，2001.

[6] 朗茂祥，胡思繼.用混合遺傳算法求解物流配送路線優(yōu)化問題的研究[J].中國管理科學(xué)，2003(4):51-56.

[7] Ishibuchi,H.,T.Murata.A multiobjective genetic local search algorithm and its application to flowshop scheduling[J].IEEE Transaction on Systems,Man and Cybernetic,1998,28(3):392-403.

[8]Murata,T.,H.Ishibuchi,H.Tanaka,Multiobjective genetic algorithm and its application to flowshop scheduling[J].Computers and Industrial Engineering,1994,72:417-431.

[9] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1998.

[10] Marshall L Fisher.Optimal solution of vehicle routing problems using minimum K-trees[J].Operations Research,1994,42(4):626-642.

[11] Glover Fred.Tabu search-partⅠ[J].ORSA Journal on Computing,1989,1(3):190-205.

[12] Glover Fred.Tabu Search-partⅡ[J].ORSA Journal on Computing,1990,2(1):4-32.

[13] Christofides N,Eilon S.An algorithm for the vehicle dispatching problems[J].Operations Research,1969,20:309-323.

[14] 張濤,等.不確定車輛數(shù)的車輛路徑問題模型和混合算法[J].系統(tǒng)工程理論方法應(yīng)用，2002,11(2):121-130.