配送時間窗約束下車輛調度遺傳算法研究

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

·交通運輸·

配送時間窗約束下車輛調度遺傳算法研究

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

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

對配送路線進行優化，一般都要求符合以下約束條件：

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

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

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

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

1 模型建立

1.1 時間窗問題

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

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

1.2 改進懲罰函數

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

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

圖1 有時間窗的配送損失量函數

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

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

1.3 改進交叉算子

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

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

（2）將B中對應位置的6與3交換，以避免以后發生結點重復遍歷的現象；

（3）比較A，B中結點6與后面結點的距離，如果c61＞c67。，則選擇B中的結點7作為子代對應位置的結點，交換A中1與7的位置，以避免后面發生結點重復遍歷的現象；

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

例：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***

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

1.4 車輛調度模型的建立

為構建上述模型，先建立如下變量：

模型的目標函數如下：

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

2 車輛調度遺傳算法案例

2.1 問題描述

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

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

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

2.2 編碼及初始種群的生成

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

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

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

（3）重復以上操作直至結束，生成斷點集；

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

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

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

2.3 選擇算子

選擇算子的實現具體操作如下：

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

（2）對這n個染色體進行按適應函數進行適應值fk計算；

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

2.4 算法的終止

由于遺傳算法搜索路徑具有較大的隨機性，根據啟發式算法的終止條件，本文給定適當的終止參數e、λ、Y。只要算法滿足下列條件之一，就認為算法收斂。

（1）計算每代群體中染色體的適應度方差，當方差小于e時，則認為算法收斂；

（2）計算每代群體中適應度的均值，當均值與最佳染色體適應度的比值大于λ時，認為算法收斂；

（3）由于計算時間是有限的，計算代數不能無限長，故當迭代次數達到規定的Y時，停止計算。

3 結 論

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

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

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

[2] 邢文川，謝金星.現代優化計算方法[M].北京：清華大學出版社，1999.

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

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

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

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

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

遺傳算法；啟發式；交叉算子；時間窗；懲罰函數

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-），男，廣東潮州人，中海油田服務股份有限公司，工程師，研究方向：企業信息化。

1002-3100(2011)04-0116-04