配送時間窗約束下的車輛調度遺傳算法研究_懲罰函數-論文網
論文摘要：通過改進傳統(tǒng)的遺傳算法，結合中海油服物資配送特點，采用啟發(fā)式交叉算子的方法，確保了算法迭代中的種群多樣性的保持。制定了基于配送時間窗約束情況下模糊預約時間的鉆井平臺損失懲罰函數，對可行解的范圍進行了限定，從而加速收斂，保證了運算的效率。通過案例進行分析證明了可行性。
論文關鍵詞：遺傳算法,啟發(fā)式,交叉算子,時間窗,懲罰函數
前言
在中海油田服務股份有限公司的生產物資配送中，不但要滿足各個鉆井平臺對實物的需求，還要滿足船期對配送時間的限制，針對各個鉆井平臺的訂單往往會考慮一定前置期的特點，鉆井平臺上盡量減少庫存，對配送服務的時間要求比較嚴格，因此及時配送變得越來越重要。滿足鉆井平臺對配送時間窗的限制，是制定配送車輛路線應該優(yōu)先考慮的問題。因此，本文主要選擇帶時間窗約束的VRP問題進行研究。
對配送路線進行優(yōu)化，一般都要求符合以下約束條件：
(1)必須滿足鉆井平臺對貨物到達的時間或時間窗的要求；
(2)對每一輛運輸車輛的裝載容量有一定的限制，不允許裝載量超過車輛的載重量和容量；
(3)滿足鉆井平臺對貨物規(guī)格、品種和數量的要求，且一次完成配送；
(4)員工的休息時間的限制(工作時間、用餐時間限制)；本文構建的模型所考慮的主要約束條件如上所述。
2．模型建立
2.1時間窗問題
在進行貨物配送時，若采購計劃沒有對配送的時間提出要求，那么物供中心可以根據自己的配送進程來組織車輛配送，但如果采購計劃要求在規(guī)定的時間段內完成貨物的配送，這就需要考慮鉆井平臺對時間的要求，VRP問題轉化為VRPTW問題。
設完成任務i需要的時間(包括裝貨、卸貨)為Ti，同時任務i的開始時間必需要在規(guī)定的時間窗(
,
)內，其中表示為任務i最早的允許開始時間，為任務i最遲的允許開始時間。如果配送車輛到達任務i的時間早于,，車輛必須在i處的碼頭等待裝船，如果配送車輛到達任務i的時間晚于，任務i要等下個船期才能進行運輸。若
表示車輛到達i點的時間，應滿足關系式
。VRPTW問題中的時間窗限制又可以分為軟時間窗問題和硬時間窗問題，其中軟時間窗VRPTW表示如果配送車輛無法在要求的時間窗內將貨物送達鉆井平臺的客戶手中，則必須按照違反時間的長短支付一定的懲罰費用；硬時間窗VRPTW表示每項任務必須在規(guī)定的時間范圍內將貨品送達鉆井平臺的客戶手中，不論是早到或遲到都完全被接受。相對于軟時間窗而言，如果車輛在之前到達任務點i，車輛在i處等待，產生了機會成本的損失。如果車輛在之后到達任務點i，服務被延遲，必須支付一定的懲罰費用：對于硬時間窗VRPTW來說，當貨品送達的時間超出時間窗范圍時，其懲罰值定義為一個非常大的正數M，這表示在硬時間窗的限制下，如果服務超過時間窗范圍，配送成本巨大，此時的解為不可行解。
2.2改進懲罰函數
若配送作業(yè)違反了采購計劃的時間窗約束，勢必會造成采購計劃的延遲，從而造成企業(yè)的損失，配送作業(yè)的目標是在追求成本最低化的情況下，實現企業(yè)生產利潤的最大化。因此有必要將時間成本考慮在內。
在油田生產過程的配送中，鉆井平臺會在一定程度的時間范圍內接受配送服務，而超過這部分的時間范圍，會對企業(yè)的生產造成影響，我們選擇用圖2-1所示的罰函數，
在時間窗左側的是提前到達的情況，這一段時間的函數線條比較平緩，表示，雖然會有懲罰，但是能忍受提前到達的時限范圍較長，因為不會造成生產損失；而在時間窗右側的是滯后到達，這種對企業(yè)生產造成的損失巨大，所以線條斜率較大。其中時間區(qū)間[ET，LT]表示鉆井平臺可以忍受的最大損失的服務時間范圍，而[ET，LT]表示鉆井平臺能進行配送服務的時間范圍，即模糊預約時間。
圖2-1有時間窗的配送損失量函數
從模糊預約時間的界定可以知道，鉆井平臺損失量可以通過關于模糊預約時間的函數來表示，對于鉆井平臺i來說，當服務開始的時間為ti時，鉆井平臺損失懲罰函數可以表示為：
式（2-1）
2.3改進交叉算子
本文采用啟發(fā)式遺傳算法的基因換位算子來實現染色體的交叉，過程如下：
(1)首先在兩個父代字符串A，B中隨機的選擇一個交叉點，并且A，B中隨機的選擇一個交叉點后的碼頭作為第一個子染色體對應位置需訪問的碼頭；
(2)將B中對應位置的6與3交換，以避免以后發(fā)生結點重復遍歷的現象；
(3)比較A，B中結點6與后面結點的距離，如果c>c。，則選擇B中的結點7作為子代對應位置的結點，交換A中1與7的位置，以避免后面發(fā)生結點重復遍歷的現象：
(4)如此反復執(zhí)行(3)中的操作，直至遍歷完兩父代字符串的所有結點，此時得具有同時配送和收集需求的車輛路徑問題研究到一個子代字符串。
例：A:8207405|6013A’:8207405|6013
父代B:5410780|3602B’:5410780|6302
子代C:*******|6***
采取該算法，即使種群中所有個體都相同，也不會影響算法的運行。這樣就很好的擺脫了傳統(tǒng)遺傳算法對種群多樣性的要求，較好的解決了傳統(tǒng)遺傳算法中早熟和收斂的問題。
2.4車輛調度模型的建立
為構建上述模型，先建立如下變量
模型的目標函數如下：
式(2-2)
S.T.
式(2-3)
式(2-4)
式(2-5)
式(2-6)
式中：式(2-2)為目標函數，表示使車輛完成配送任務時的總配送費用最小，由以下幾個部分組成：總配送距離產生的成本，加班工作產生的額外成本，車輛延時造成的配送成本，車輛提前到達增加的配送成本和違反時間窗要求對生產計劃造成的損失量，式(2-3)為車輛的裝載能力約束，表示某車運輸所裝載的物資總量不能超過該車輛本身的最大載重量；式(2-4)式(2-5)表示到達某一碼頭的車輛的約束，即每一個碼頭可以最多有n輛車同時進行裝卸；式(2-6)用來確保平臺i由總共小于n輛車完成配送任務。
論文關鍵詞：遺傳算法,啟發(fā)式,交叉算子,時間窗,懲罰函數
前言
在中海油田服務股份有限公司的生產物資配送中，不但要滿足各個鉆井平臺對實物的需求，還要滿足船期對配送時間的限制，針對各個鉆井平臺的訂單往往會考慮一定前置期的特點，鉆井平臺上盡量減少庫存，對配送服務的時間要求比較嚴格，因此及時配送變得越來越重要。滿足鉆井平臺對配送時間窗的限制，是制定配送車輛路線應該優(yōu)先考慮的問題。因此，本文主要選擇帶時間窗約束的VRP問題進行研究。
對配送路線進行優(yōu)化，一般都要求符合以下約束條件：
(1)必須滿足鉆井平臺對貨物到達的時間或時間窗的要求；
(2)對每一輛運輸車輛的裝載容量有一定的限制，不允許裝載量超過車輛的載重量和容量；
(3)滿足鉆井平臺對貨物規(guī)格、品種和數量的要求，且一次完成配送；
(4)員工的休息時間的限制(工作時間、用餐時間限制)；本文構建的模型所考慮的主要約束條件如上所述。
2．模型建立
2.1時間窗問題
在進行貨物配送時，若采購計劃沒有對配送的時間提出要求，那么物供中心可以根據自己的配送進程來組織車輛配送，但如果采購計劃要求在規(guī)定的時間段內完成貨物的配送，這就需要考慮鉆井平臺對時間的要求，VRP問題轉化為VRPTW問題。
設完成任務i需要的時間(包括裝貨、卸貨)為Ti，同時任務i的開始時間必需要在規(guī)定的時間窗(
,)內，其中表示為任務i最早的允許開始時間，為任務i最遲的允許開始時間。如果配送車輛到達任務i的時間早于,，車輛必須在i處的碼頭等待裝船，如果配送車輛到達任務i的時間晚于，任務i要等下個船期才能進行運輸。若表示車輛到達i點的時間，應滿足關系式。VRPTW問題中的時間窗限制又可以分為軟時間窗問題和硬時間窗問題，其中軟時間窗VRPTW表示如果配送車輛無法在要求的時間窗內將貨物送達鉆井平臺的客戶手中，則必須按照違反時間的長短支付一定的懲罰費用；硬時間窗VRPTW表示每項任務必須在規(guī)定的時間范圍內將貨品送達鉆井平臺的客戶手中，不論是早到或遲到都完全被接受。相對于軟時間窗而言，如果車輛在之前到達任務點i，車輛在i處等待，產生了機會成本的損失。如果車輛在之后到達任務點i，服務被延遲，必須支付一定的懲罰費用：對于硬時間窗VRPTW來說，當貨品送達的時間超出時間窗范圍時，其懲罰值定義為一個非常大的正數M，這表示在硬時間窗的限制下，如果服務超過時間窗范圍，配送成本巨大，此時的解為不可行解。2.2改進懲罰函數
若配送作業(yè)違反了采購計劃的時間窗約束，勢必會造成采購計劃的延遲，從而造成企業(yè)的損失，配送作業(yè)的目標是在追求成本最低化的情況下，實現企業(yè)生產利潤的最大化。因此有必要將時間成本考慮在內。
在油田生產過程的配送中，鉆井平臺會在一定程度的時間范圍內接受配送服務，而超過這部分的時間范圍，會對企業(yè)的生產造成影響，我們選擇用圖2-1所示的罰函數，
在時間窗左側的是提前到達的情況，這一段時間的函數線條比較平緩，表示，雖然會有懲罰，但是能忍受提前到達的時限范圍較長，因為不會造成生產損失；而在時間窗右側的是滯后到達，這種對企業(yè)生產造成的損失巨大，所以線條斜率較大。其中時間區(qū)間[ET，LT]表示鉆井平臺可以忍受的最大損失的服務時間范圍，而[ET，LT]表示鉆井平臺能進行配送服務的時間范圍，即模糊預約時間。
圖2-1有時間窗的配送損失量函數
從模糊預約時間的界定可以知道，鉆井平臺損失量可以通過關于模糊預約時間的函數來表示，對于鉆井平臺i來說，當服務開始的時間為ti時，鉆井平臺損失懲罰函數可以表示為：
式（2-1）2.3改進交叉算子
本文采用啟發(fā)式遺傳算法的基因換位算子來實現染色體的交叉，過程如下：
(1)首先在兩個父代字符串A，B中隨機的選擇一個交叉點，并且A，B中隨機的選擇一個交叉點后的碼頭作為第一個子染色體對應位置需訪問的碼頭；
(2)將B中對應位置的6與3交換，以避免以后發(fā)生結點重復遍歷的現象；
(3)比較A，B中結點6與后面結點的距離，如果c>c。，則選擇B中的結點7作為子代對應位置的結點，交換A中1與7的位置，以避免后面發(fā)生結點重復遍歷的現象：
(4)如此反復執(zhí)行(3)中的操作，直至遍歷完兩父代字符串的所有結點，此時得具有同時配送和收集需求的車輛路徑問題研究到一個子代字符串。
例：A:8207405|6013A’:8207405|6013
父代B:5410780|3602B’:5410780|6302
子代C:*******|6***
采取該算法，即使種群中所有個體都相同，也不會影響算法的運行。這樣就很好的擺脫了傳統(tǒng)遺傳算法對種群多樣性的要求，較好的解決了傳統(tǒng)遺傳算法中早熟和收斂的問題。
2.4車輛調度模型的建立
為構建上述模型，先建立如下變量
模型的目標函數如下：
式(2-2)
S.T.
式(2-3)式(2-4)式(2-5)式(2-6)式中：式(2-2)為目標函數，表示使車輛完成配送任務時的總配送費用最小，由以下幾個部分組成：總配送距離產生的成本，加班工作產生的額外成本，車輛延時造成的配送成本，車輛提前到達增加的配送成本和違反時間窗要求對生產計劃造成的損失量，式(2-3)為車輛的裝載能力約束，表示某車運輸所裝載的物資總量不能超過該車輛本身的最大載重量；式(2-4)式(2-5)表示到達某一碼頭的車輛的約束，即每一個碼頭可以最多有n輛車同時進行裝卸；式(2-6)用來確保平臺i由總共小于n輛車完成配送任務。
關鍵字：其它
