黃瑞銘 （中海油田服務(wù)股份有限公司，河北 三河 065201）

·交通運輸·

配送時間窗約束下車輛調(diào)度遺傳算法研究

黃瑞銘 （中海油田服務(wù)股份有限公司，河北 三河 065201）

在中海油田服務(wù)股份有限公司的生產(chǎn)物資配送中，不但要滿足各個鉆井平臺對實物的需求，還要滿足船期對配送時間的限制，針對各個鉆井平臺的訂單往往會考慮一定前置期的特點，鉆井平臺上盡量減少庫存，對配送服務(wù)的時間要求比較嚴(yán)格，因此及時配送變得越來越重要[1]。滿足鉆井平臺對配送時間窗的限制，是制定配送車輛路線應(yīng)該優(yōu)先考慮的問題[2]。因此，本文主要選擇帶時間窗約束的VRP問題進(jìn)行研究。

對配送路線進(jìn)行優(yōu)化，一般都要求符合以下約束條件：

（1）必須滿足鉆井平臺對貨物到達(dá)的時間或時間窗的要求；

（2）對每一輛運輸車輛的裝載容量有一定的限制，不允許裝載量超過車輛的載重量和容量；

（3）滿足鉆井平臺對貨物規(guī)格、品種和數(shù)量的要求，且一次完成配送；

（4）員工休息時間的限制 （工作時間、用餐時間限制）；本文構(gòu)建的模型所考慮的主要約束條件如上所述[3]。

1 模型建立

1.1 時間窗問題

在進(jìn)行貨物配送時，若采購計劃沒有對配送的時間提出要求，那么物供中心可以根據(jù)自己的配送進(jìn)程來組織車輛配送，但如果采購計劃要求在規(guī)定的時間段內(nèi)完成貨物的配送，這就需要考慮鉆井平臺對時間的要求，VRP問題轉(zhuǎn)化為VRPTW問題[4]。

設(shè)完成任務(wù)i需要的時間 （包括裝貨、卸貨）為Ti，同時任務(wù)i的開始時間必需要在規(guī)定的時間窗 （ETi,LTi）內(nèi)，其中ETi表示為任務(wù)i最早的允許開始時間，LTi為任務(wù)i最遲的允許開始時間。如果配送車輛到達(dá)任務(wù)i的時間早于ETi，車輛必須在i處的碼頭等待裝船，如果配送車輛到達(dá)任務(wù)i的時間晚于LTi，任務(wù)i要等下個船期才能進(jìn)行運輸。若ti表示車輛到達(dá)i點的時間，應(yīng)滿足關(guān)系式ETi≤ti≤LTi。VRPTW問題中的時間窗限制又可以分為軟時間窗問題和硬時間窗問題，其中軟時間窗VRPTW表示如果配送車輛無法在要求的時間窗內(nèi)將貨物送達(dá)鉆井平臺的客戶手中，則必須按照違反時間的長短支付一定的懲罰費用；硬時間窗VRPTW表示每項任務(wù)必須在規(guī)定的時間范圍內(nèi)將貨品送達(dá)鉆井平臺的客戶手中，不論是早到或遲到都完全被接受。相對于軟時間窗而言，如果車輛在ETi之前到達(dá)任務(wù)點i，車輛在i處等待，產(chǎn)生了機會成本的損失。如果車輛在LTi之后到達(dá)任務(wù)點i，服務(wù)被延遲，必須支付一定的懲罰費用：對于硬時間窗VRPTW來說，當(dāng)貨品送達(dá)的時間超出時間窗范圍時，其懲罰值定義為一個非常大的正數(shù)M，這表示在硬時間窗的限制下，如果服務(wù)超過時間窗范圍，配送成本巨大，此時的解為不可行解。

1.2 改進(jìn)懲罰函數(shù)

若配送作業(yè)違反了采購計劃的時間窗約束，勢必會造成采購計劃的延遲，從而造成企業(yè)的損失，配送作業(yè)的目標(biāo)是在追求成本最低化的情況下，實現(xiàn)企業(yè)生產(chǎn)利潤的最大化。因此有必要將時間成本考慮在內(nèi)。

在油田生產(chǎn)過程的配送中，鉆井平臺會在一定程度的時間范圍內(nèi)接受配送服務(wù)，而超過這部分的時間范圍，會對企業(yè)的生產(chǎn)造成影響，我們選擇用圖1所示的罰函數(shù)。

圖1 有時間窗的配送損失量函數(shù)

在時間窗左側(cè)的是提前到達(dá)的情況，這一段時間的函數(shù)線條比較平緩，表示，雖然會有懲罰，但是能忍受提前到達(dá)的時限范圍較長，因為不會造成生產(chǎn)損失；而在時間窗右側(cè)的是滯后到達(dá)，這種對企業(yè)生產(chǎn)造成的損失巨大，所以線條斜率較大。其中時間區(qū)間 [ETi,LTi]表示鉆井平臺可以忍受的最大損失的服務(wù)時間范圍，而 [ETd,LTd]表示鉆井平臺能進(jìn)行配送服務(wù)的時間范圍，即模糊預(yù)約時間。

從模糊預(yù)約時間的界定可以知道，鉆井平臺損失量可以通過關(guān)于模糊預(yù)約時間的函數(shù)來表示，對于鉆井平臺i來說，當(dāng)服務(wù)開始的時間為ti時，鉆井平臺損失懲罰函數(shù)可以表示為：

1.3 改進(jìn)交叉算子

本文采用啟發(fā)式遺傳算法的基因換位算子來實現(xiàn)染色體的交叉，過程如下：

（1）首先在兩個父代字符串A，B中隨機地選擇一個交叉點，并且A，B中隨機的選擇一個交叉點后的碼頭作為第一個子染色體對應(yīng)位置需訪問的碼頭；

（2）將B中對應(yīng)位置的6與3交換，以避免以后發(fā)生結(jié)點重復(fù)遍歷的現(xiàn)象；

（3）比較A，B中結(jié)點6與后面結(jié)點的距離，如果c61＞c67。，則選擇B中的結(jié)點7作為子代對應(yīng)位置的結(jié)點，交換A中1與7的位置，以避免后面發(fā)生結(jié)點重復(fù)遍歷的現(xiàn)象；

（4）如此反復(fù)執(zhí)行 （3）中的操作，直至遍歷完兩父代字符串的所有結(jié)點，此時得具有同時配送和收集需求的車輛路徑問題研究到一個子代字符串。

例：A:8 2 0 7 4 0 5|6 0 1 3 A':8 2 0 7 4 0 5|6 0 1 3

父代B:5 4 1 0 7 8 0|3 6 0 2 B':5 4 1 0 7 8 0|6 3 0 2

子代C:*******|6***

采取該算法，即使種群中所有個體都相同，也不會影響算法的運行。這樣就很好的擺脫了傳統(tǒng)遺傳算法對種群多樣性的要求，較好的解決了傳統(tǒng)遺傳算法中早熟和收斂的問題。

1.4 車輛調(diào)度模型的建立

為構(gòu)建上述模型，先建立如下變量：

模型的目標(biāo)函數(shù)如下：

式中：式 （2）為目標(biāo)函數(shù)，表示使車輛完成配送任務(wù)時的總配送費用最小，由以下幾個部分組成：總配送距離產(chǎn)生的成本，加班工作產(chǎn)生的額外成本，車輛延時造成的配送成本，車輛提前到達(dá)增加的配送成本和違反時間窗要求對生產(chǎn)計劃造成的損失量，式 （3）為車輛的裝載能力約束，表示某車運輸所裝載的物資總量不能超過該車輛本身的最大載重量；式 （4）、式 （5）表示到達(dá)某一碼頭的車輛的約束，即每一個碼頭可以最多有n輛車同時進(jìn)行裝卸；式 （6）用來確保平臺i由總共小于n輛車完成配送任務(wù)。其中，θtp表示第p輛車的行車時間，t0為發(fā)車時間，為收車時間；eθtp表示第 p輛車的加班時間，eθtp=max

2 車輛調(diào)度遺傳算法案例

2.1 問題描述

處理過的塘沽物供中心的數(shù)據(jù)如表1、2所示：

表1 庫房和碼頭之間的距離表

表2 碼頭裝船8點到9點之間的配送量和配送時間窗

2.2 編碼及初始種群的生成

由于VRP問題用二進(jìn)制編碼具有先天性的不足，為了彌補這一缺的，本案例采用序數(shù)編碼，其中0代表庫房，自然數(shù)表示碼頭的編號，本案例中有8個碼頭，隨機產(chǎn)生一個序列23786154，然后按以下步驟進(jìn)行染色體的生成操作：

（1）從左向右累計碼頭需要運輸量，一旦累計運輸量大于運輸車輛容量時，記錄此時的累計次數(shù)i，記錄斷點一為i-1，累計量清零；

（2）從序列的第i個數(shù)字重新累計碼頭需要運輸量，當(dāng)累計需求量大于運輸車輛容量時，記錄此時的次數(shù)j，記錄斷點二為i+j-l，累計量清零；

（3）重復(fù)以上操作直至結(jié)束，生成斷點集；

（4）對斷點集進(jìn)行操作，在每個斷點的后面插入 “0”，表示重新從庫房出發(fā)；

（5）在序列首未位添加 “0”，染色體生成完成。

現(xiàn)以序列23786154為例說明解碼過程，設(shè)生成的斷點集合為式3,6,（）5 ，則首先在序列的第2、第5及第7位后加 “0”，序列變?yōu)?3078601504。然后在序列前段加 “0”，則染色體為023078601504，表示配送方案由4條路線組成，其中運輸車輛l的路線為：庫房0—碼頭2—碼頭3；運輸車輛2的路線為庫房0—碼頭7—碼頭8—碼頭6；運輸車輛3的路線為庫房0—碼頭1—碼頭5；運輸車輛4的路線為庫房0—碼頭4。至此完整的染色體生成，然后通過重復(fù)染色體生成過程，直至達(dá)到種群規(guī)模，即為算法的初始種群。

2.3 選擇算子

選擇算子的實現(xiàn)具體操作如下：

（1）首先隨機生成n組序列，通過序列加 “0”，生成n個染色體；

（2）對這n個染色體進(jìn)行按適應(yīng)函數(shù)進(jìn)行適應(yīng)值fk計算；

（5） 生成呈均勻分布的隨機數(shù)r（ 0≤r≤1 ）， 若r≤d1， 則選擇第1個染色體， 若以dk-1≤r≤dk（l=2,3,…,n ），則選擇第k個染色體，重復(fù)以上操作直至選擇的染色體達(dá)到種群規(guī)模。由于選擇的隨機性，在染色體選擇后，當(dāng)代群體中的最佳染色體可能會喪失繁殖能力，為了提高算法的性能，在輪盤賭的基礎(chǔ)上再采用精英保留策略。

2.4 算法的終止

由于遺傳算法搜索路徑具有較大的隨機性，根據(jù)啟發(fā)式算法的終止條件，本文給定適當(dāng)?shù)慕K止參數(shù)e、λ、Y。只要算法滿足下列條件之一，就認(rèn)為算法收斂。

（1）計算每代群體中染色體的適應(yīng)度方差，當(dāng)方差小于e時，則認(rèn)為算法收斂；

（2）計算每代群體中適應(yīng)度的均值，當(dāng)均值與最佳染色體適應(yīng)度的比值大于λ時，認(rèn)為算法收斂；

（3）由于計算時間是有限的，計算代數(shù)不能無限長，故當(dāng)?shù)螖?shù)達(dá)到規(guī)定的Y時，停止計算。

3 結(jié) 論

考慮生產(chǎn)計劃損失量函數(shù)對車輛調(diào)度的情況下計算得出最終優(yōu)化解為4 226元。最后得到車輛的行駛路線為0—5—2—0；0—4—3—0；0—8—7—6，總的行駛距離為460km。經(jīng)檢驗，此路徑安排完全滿足各碼頭的運輸需求量約束和裝載車輛的承載量約束，是此問題的一個較優(yōu)的可行解。

此結(jié)果表明，經(jīng)過改進(jìn)遺傳遺傳算法優(yōu)化之后，鉆井平臺的采購計劃可以在最大程度上滿足，而且能盡量避免因為配送延遲造成的生產(chǎn)計劃的延時，從而使企業(yè)能將生產(chǎn)成本控制在比較低的范圍。

[1] 郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學(xué)，2002,10(5)：51-56.

[2] 邢文川，謝金星.現(xiàn)代優(yōu)化計算方法[M].北京：清華大學(xué)出版社，1999.

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

[4] 林郁丞.基于聚類分析和遺傳算法的帶時間窗車輛路徑問題研究[D].福州：福建農(nóng)林大學(xué)，2009.

Research on the Genetic Algorithm for Vehicle Routing Problem with Delivery Time Windows

HUANG Rui-ming (China Oilfield Services Limited,Sanhe 065201,China)

通過改進(jìn)傳統(tǒng)的遺傳算法，結(jié)合中海油服物資配送特點，采用啟發(fā)式交叉算子的方法，確保了算法迭代中的種群多樣性。制定了基于配送時間窗約束情況下模糊預(yù)約時間的鉆井平臺損失懲罰函數(shù)，對可行解的范圍進(jìn)行了限定，從而加速收斂，保證了運算的效率。通過案例進(jìn)行分析證明了可行性。

遺傳算法；啟發(fā)式；交叉算子；時間窗；懲罰函數(shù)

By improving the traditional genetic algorithm,we combine with the material distribution characteristics of COSL.We use the method of heuristic crossover operator,ensure that the iteration of the algorithm to maintain the diversity.Application of the penalty function about the increase of costs oil platform with delivery time windows,the scope of the feasible solution has limited and convergence has been accelerated.Ensure the efficiency of operations.Through a case analysis proves the feasibility of the research method.

genetic algorithm;heuristic algorithm;crossover operators;time windows;penalty function

TP301.6

A

2011-01-28

黃瑞銘（1964-），男，廣東潮州人，中海油田服務(wù)股份有限公司，工程師，研究方向：企業(yè)信息化。

1002-3100(2011)04-0116-04