面向船舶制造企業車間作業過程物料配送優化方法

段金健，王美清，王澤宇

（北京航空航天大學 機械工程及自動化學院，北京 100191）

0 引言

在市場經濟環境下，制造企業增加利潤的主要方式有兩種，獲得更多的訂單和降低自身的成本。近年來，國際船舶行業需求低迷，船舶行業迎來持續寒冬，訂單量持續減少，這使得降低制造成本成為企業獲得利潤的主要途徑。船舶制造過程具有制造場所地理位置分散、物料存放點多，制造過程物料運輸環節多等特點，物料配送的效率成為影響企業提高生產效率、降低生產成本的瓶頸之一。因此研究面向車間作業的船舶制造企業物料配送優化問題既可以減少運輸成本，又可以提高生產效率，減少空間資源浪費，從而降低船舶生產成本，為企業贏得市場競爭力。

船舶制造企業的物料配送優化問題，主要研究如何在資源約束條件下將正確的物料運送到正確的地點，并且保證成本最低，已有人證明這是一個NP問題[1]。NP問題是完全多項式非確定性問題，所以用啟發式算法解決該類問題是一個研究熱點。常見的啟發式算法有禁忌搜索算法、模擬退火算法、遺傳算法、蟻群算法、神經網絡算法、粒子群算法等。利用啟發式算法解決此類問題，國內外學者進行了大量研究。物料配送過程中主要有能力約束和時間約束。針對能力約束，張濤等[2]利用遺傳算法提出了在容量和重量限制下重復使用車輛的物流優化模型，不過其假設所有車輛載重、容量都一致；陳宏程等[3]提出了多車輛多車型的物流配載優化模型，將物流的路徑優化模型和多車輛配載相結合，提出了具有裝載關系的配送模型，并利用遺傳算法對其進行驗證，取得了一定的效果。針對時間約束，侯占亭等[4]利用多目標分解的進化算法對帶有時間窗的物流優化問題進行了詳細研究，提出了一種搜索效果更好的交換算子；Olli Br?ysy[5]提出了一種層次化的解決方法，首先通過進化算法找到最短路徑，再通過相同路線比較各車輛的花費差異，最后確定最優的路徑和車輛搭配；Phuong Khanh Nguyen[6]提出了一個等待區模型，當在時間窗外達到目的地時進入等待區，此時計算路徑時加入前往等待區的花費，從而尋找最優路徑，這為解決物流配送問題提供了新思路；其他相關研究也為物料配送優化提供了值得借鑒的思路，李冰[7]解決了有順序約束指派問題；葉煒[8]建立了交通管制下的物流優化模型，分析了交通管制對路徑選擇的影響；羅梓瑄[9]通過蟻群算法建立了成本最小化和碳排放量最少化的多目標優化模型。

綜上所述，前人的研究多集中在尋找物流最短路徑方面，但實際船舶制造過程不僅僅要求物料配送路徑最短，還需要考慮多車輛下的派工問題，本文根據船舶制造過程物料配送特點，提出了一種面向船舶制造過程車間作業的物料配送優化方法，建立了船舶制造過程的物料配送優化模型，提出了考慮道路約束、工序約束和容量約束的成本最低配送方案，基于蟻群算法進行了工作地間路徑尋優，融合圖論和退火算法進行任務分配，最終實現了在車間作業約束下搜尋最優派工和最短路徑的目標，并通過MATLAB仿真驗證了所提方法的有效性。

1 面向車間作業的物料配送優化模型建立

面向船舶制造企業車間作業的物料配送模型十分復雜，完全對其進行建模和求解有一定難度。因此本研究取其中適用性高、影響大的因素為優化目標。物料配送優化本質上是搜尋成本最低的配送方案。船舶制造過程中的物流配送特點是：1）各工作地點間的道路并非直線需要考慮工作地間的實際道路，為了方便問題研究，本文將兩目標點間的直線路徑模型稱為“路徑”，將兩目標點間實際存在可達路徑的折線路徑模型稱為“道路”；2）物料的配送有順序，需要按照工序將物料依次送達目的地，因此建立模型時必須引入工序約束；3）船廠配送的物料較多，一般不能由一輛車全部配送完成，因此必須研究車輛的任務分配問題。基于上述特點可以建立如下數學模型。

1.1 研究假設

為了更好的優化目標，假設物料配送過程滿足以下條件：

1）物料運輸方向滿足工序間順序要求，不存在因反向作業，導致的車輛需要多次經過同一工作地的情況；

2）各作業地點間道路通斷情況已知；

3）車輛載重已知，運載時只考慮載重要求，且一個任務地的需求可由一輛車配送。在實際生產中，如果一個工作地需求大于一輛車載重，可以先派出車輛滿載，直至需求減為一輛車載重以下后，再進行任務分配；

4）配送任務和工序作業清單已知。

1.2 數學模型

針對物料配送優化問題約束多、優化層次復雜的特點，建立了面向道路、任務和容量約束的多層次多目標優化數學模型。

1）面向道路約束的最優道路搜索模型

模型的道路約束由式(1)表示，其中Z1(i,j)表示兩工作地間運輸的最小花費，cp表示經過第p條道路時的費用，opij表示在從工作地i到工作地j是否經過道路p，是為1，否為0。通過式(2)將從工作地i到工作地j的最短距離集傳遞，Cij表示由工作地i到j的最小花費，通過這個模型尋找各工作地間的最短道路。

2）面向工序和容量約束的最優任務分配模型

其中式(3)表示第k輛車分配的任務重量小于其載重，形成了容量約束，式(4)表示一個工作地的任務只由一輛車配送，并且所有任務由m輛車完成，式(5)限制到達某工作地的只有一輛車，式(6)表示限制某工作地只有一輛車。表示第k輛車是否經過i、j間的道路，是為1，否為0，表示第i個工作地需要資源重量，表示第k輛車是否經過第i個工作地。式(7)表示工序對路徑選擇的影響，到達每個工作地前必須考慮是否已經經過其前序工序，表示第k輛車分配的任務中是否有i、j工作地，表示第k輛車在到達第j個工作地前是否到達過其前序工序。式(8)表示每輛車交接時工作地間的路程最長，表示第k輛車和第k+1輛車的交接路程。

3）各車輛運輸成本最低模型

其中式(9)表示各車輛運輸成本，其中Zk指第k輛車的運輸成本最小，cij是滿足道路約束時從工作地i到工作地j的最短距離，xijk是滿足工序約束、容量約束最優任務分配模型的工作地i到工作地j間的可行道路。

2 面向車間作業的物料配送優化方法

2.1 面向車間作業的物料配送優化過程模型

根據建立的數學模型將優化流程分為以下三步：

1）搜尋工作地間的最優道路。在實際制造過程中，各個作業地間的距離并不能以直線判定，所以在進行最優的工作地到達順序搜尋時，首先要對各個工作地間的道路進行選擇，從而找到各個工作地間的最短道路和距離，形成最優道路集，由于有道路約束，隨機生成新解和交叉較為困難，采用蟻群算法可以較好地解決這一問題。

2）搜尋最優的車輛任務分配。在配送過程中，由于每個車輛的載重有限，當需要配送的物料總重大于單車輛載重時，需要通過多車輛配送。但是，整個配送任務需要滿足工序要求，因此需要研究在不改變工序要求的目的地到達順序的前提下，尋找分配方案使得多車輛協作時成本最低，通過有向圖可將問題簡化，配合退火算法有利于解決模糊問題。

3）搜尋當前任務下單車輛的最優路徑。形成最優任務分配集后，雖然有工序約束，但是一輛車可能會執行多個產品物料配送，它們的工序是并行的，因此還是會出現多種路徑安排，需要對路徑進行進一步優化，以實現配送成本最低。面向車間作業的物料配送優化過程模型如圖1所示。

圖1 面向車間作業的船廠物料配送優化流程

2.2 基于蟻群算法的工作地間最優路徑搜索

蟻群算法是Marco Dorigo 1992年提出的，用于解決組合尋優問題的啟發式尋優算法。基礎的蟻群算法具有良好的搜索速度，但是也存在容易陷入局部最優解的不足，本文將遺傳變異思想與蟻群算法相結合，提出了面向船舶制造過程中工作地間最優路徑的搜索方法。具體過程方法如下：

第1步：參數初始化，導入工作地位置、道路關鍵節點、節點間的聯通情況、各個道路的長度、設置變異概率、設置當前迭代次數NC=0、設置最大迭代次數NC_MAX、設置螞蟻數、設置初始信息素濃度、信息素揮發率及誘導因子等。

第2步：進入循環，NC NC+1，將所有的螞蟻放置到起點，將起點加入禁忌表。

第3步：逐個螞蟻開始尋找下一個節點，下一個節點是從除去禁忌表中已走過的節點，若沒有可選節點，則代表其進入死區，這時需要終止這只螞蟻循環，并對其在后期釋放信息素時給予相應懲罰。每只螞蟻尋找節點由轉移概率公式決定，即：

其中τij代表節點i到節點j間的信息素濃度；是啟發函數，這里用節點i到節點j間的距離倒數表示，j表示所有可行節點。獲得轉移概率后，將所有可行節點的概率轉化成輪盤賭中可行域的大小，從而隨機決定螞蟻爬向的下一個節點。

第4步：判斷螞蟻爬向的節點是否是終點，如果是終點則終止，記錄這只螞蟻的總花費和路線，如果不是則將這一節點加入禁忌表，返回第3步，直到所有的螞蟻爬到終點。

第5步：設置變異概率，每只螞蟻的爬行路線按一定概率進行變異。

第6步：計算本次迭代的最優解，記錄其路徑，并且依據每只螞蟻的路線更新信息素，更新信息素時采用分級蒸發策略，路程越長的路徑蒸發越快，爬進死區的螞蟻進行懲罰釋放信息素為0。

第7步：判斷NC=NC_MAX，若不等則返回第2步，清空禁忌表，若等于則停止迭代，尋找記錄的各代最優解中的最優的，輸出最優路徑和最少花費。

本算法將遺傳算法中的變異原理融入蟻群算法中以增加算法的隨機性，減少陷入局部最優的可能性。

2.3 基于轉化模型和退火算法的任務分配

2.3.1 基于圖論的問題轉化

船舶制造過程中的物料運輸任務可以描述為有n個工作地，m個運輸車輛，k個產品，每個產品有nk道加工工序，將其排列出來，對工作地進行編號，編號滿足先序任務的工作地編號必須小于后序任務的工作地編號。取一個工作地任務分配實例如圖2所示，其中有14個工作地，3輛運輸車輛，2個產品，產品1有11道工序，產品2有10道工序，將工作地編號形成點，并將工序連接起來形成有向邊。此時便將加工任務轉化為一張有向無環路圖，頂點集為，邊集為，在本實例中n=14，l=16。

圖2 作業任務工作地分配示例

通過以下概念可以將加工任務分配問題轉化為求割通過的邊權值最大問題。

1）劃分：集合{V1，V2，...，VN}是圖G(V，E)的劃分，則應當滿足

2）割：若{V1，V2}是V的劃分總有，v1i＜v2j則稱{V1，V2}是V的割，在本問題中V中所有元素滿足上述編號要求。

3）割點：若{V1，V2}是V的割，取v1i=min(V1)，取v2j=min(V2)，稱{v1i，v2j}是V的割點。

4）連續點集：如果V中的所有的點都是連通的，則稱V為連續點集。

5）連續劃分：集合{V1，V2，...，VN}是圖G(V，E)的割，且滿足V1，V2，...，Vn都是連續點集，則稱{V1，V2，...，VN}是圖G(V，E)的連續劃分。

根據以上概念對給出的任務分配進行連續劃分，在圖3中{V1，V2，V3}就是有向無環圖G(V，E)的一個連續劃分。

滿足上述要求后，1）取工作地需要的資源為點的權重W(i)；2）取工作場地間運送花費為邊的權重，記為c(i，j)。這樣分配問題就轉化為求取最佳劃分問題，取劃分{V1，V2，...，VN}為V連續劃分，則顯然每個Vi是連續點集，這保證每個劃分內部都是連通的。這時最佳分配問題轉化為在滿足劃分內點集的權重總和小于車輛載重時，分割所經過的邊的權重值之和最大，在保證車輛裝卸次數最小的情況下，交換車輛節約的路程最大。

2.3.2 基于圖模型的最優任務分配方法

在將任務分配問題轉化為圖論問題后，將圖論知識與退火算法相融合，設計了最優任務分配搜索算法，具體步驟如下：

第1步：參數初始化，首先任意給出一個工序排列，再對其進行任意連續劃分，這里不需要滿足容量條件，記初始排列為O0，初始劃分為Cut0。設定退火算法初始參數，初始溫度T0=100，溫度衰減系數α=0.95，初始溫度下的搜索次數L=0，最大搜索次數，L_MAX=20迭代次數為NC=0，最大迭代次數NC_MAX=100。

第2步：令NC=NC+1，L=+1，進入循環迭代，首先產生新解，將當前工序按照分割進行左右長移，計算過左右長移使Σc(i，j)增加的成本，記為Pv，則接受這次新解的概率為：

左右長移是在不改變工序順序的情況下進行的排序移動，本文僅介紹右長移的步驟，左長移同理。{V1，V2，...，VN}是圖G(V，E)的一個劃分定義：

即當i，j 之間有邊時f(i，j)=1，當i，j 之間無邊時f(i，j)=0。若f(vp，vp+1)=f(vp，vp+2)=f(vp，vp+n)=0，且f(vp，vp+n+1)≠0，則將點vp移動至vp+n到vp+n+1之間，稱為點的右長移，右長移并不會改變工序順序約束。

第3步：獲得新的排列后，求解其滿足容量約束的最優劃分。設H(v)指圖的最后一個割點為v時的最大成本，S(u，v)是在割點u后增加一個割點v所增加的最大成本，則可以通過以下步驟尋找最佳分割：

1）令v=1，U={1}，u∈U，即u=1，H(v)=0。

2）令v=v+1，U={1，2，...，v-1}，?u?U，同時點集{u,u+1，...，v-1}中點的權值小于車輛總載重，使得H(v)=max[H(u)+s(u,v)]，將此時的{u,v,H(v)}作為一個元素放入集合B中。

3）判斷v=n+1，若不等于重復1），若等于進行4）。

4）在集合B的元素中尋找v=n+1時對應的u，記為um，接著尋找v=un+1時所對應的u，記為um-1，不斷重復直到尋找到v=1時對應的u=1。

5）輸出最佳劃分的割點集合為{1，...，vm-1，vm}。

第4步：計算當前排列下最佳劃分的割和經過邊的總權值Σc(i，j)，并與最大權值比較，若大于最大權值則更新最大權值。

第5步：判斷L≤L_MAX是否成立，成立則返回第2步，不成立到第6步。

第6步：判斷NC≤NC_MAX是否成立，成立則輸出最優排列和最優劃分，如果不成立，則令T=T×α，進行降溫。

2.4 基于蟻群算法的考慮任務分配的車輛最優路徑搜索算法

基于所建立的工作地間最優路徑搜索和基于圖模型的最優任務分配方法，設計了如下的考慮工作地點間工序約束的，面向船舶制造企業生產過程中的物料配送問題的車輛最優路徑搜索算法。

其算法流程與2.2節中所述算法相似。關鍵在于第3步，需要令一只螞蟻爬向下一目標工作地點，下一目標工作地點的選擇有兩個約束，首先其不在禁忌表內，然后其前序工序的工作地在禁忌表內。如果沒有可選目標工作點，判斷是否爬行完所有目標工作點，若沒有則取消這只螞蟻的循環，并加入懲罰，若爬行完則終止。通過此步驟可以在螞蟻選擇道路時添加工序約束。對每個運送車輛執行算法，即可得到在工序約束、容量約束和道路約束下每輛車的最優路徑。

3 試驗仿真與結果分析

按照上述優化流程進行試驗仿真分析，以一個包含10個任務地5個產品的運輸優化任務為例，工作地的坐標和容量如表1所示。按照優化流程首先應當進行工作地間最短道路搜索，形成最短道路集，由于道路集較多，在這里僅展示工作地1，2，3之間的最短道路，仿真的工作地和路口信息如表2所示。

表1 10個工作地的任務基本信息

表2 工作地及路口坐標

利用MATLAB 2018 A 進行仿真，設定m=2 2，NC=300，α=3，β=4，Q=2 0，ρ=0.2，變異概率p=0.3，計算的結果如圖3所示。

圖3 蟻群算法搜索工作地間最短路徑的算法結果

從圖4由可以看出，工作地1到2之間的最短道路為工作地1→路口12→路口10→工作地2。在迭代20次左右算法趨于平穩，由于有0.3的變異概率仍然會有路徑發生變異，本算法能較好的生成各工作地之間的最短路徑集。

按照算法流程進行最優任務分配得到的結果如圖4所示。其中可以看出在工作地6和7之間通過割的邊的權重最大，形成任務分配集。

圖4 10個工作地的最優任務分配

得到任務分配集和由最短道路集生成的最短路徑距離集后對單車輛配送路徑進行優化得到結果如圖5所示。

圖5 10個工作地分配后的最優路徑

可以看出在本實例中車輛1 的運送路徑為1→3→2→5→4→6，車輛2的運送路徑為7→9→8→10，最短的運送距離為41.6454，本方法能完整的完成在工序約束、容量約束和道路約束下的物料配送最優路徑搜索。

隨機取10個、20個和30個工作地配送任務，工作地在相距為10的地圖中隨機生成。為了實現運輸任務完全按照工序順序約束執行，分別計算10次隨機實驗直接按照工序運送和分配優化后的平均路程，得到的結果如表3所示。

表3 按照工序運送和分配優化后的平均路程

由表3可以看出優化后的平均路程小于直接按工序順序的平均路程，在保證各個工序連通性和車輛的容量要求下平均路程有效減少。

4 結語

船舶產品制造過程中物料配送占據了制造成本的很大一部分，本文設計了一種面向車間作業過程的船舶制造過程物料配送方案。通過改進蟻群算法尋找到了各工作地間的最短路徑，采用圖論將任務分配問題轉化成求取連續劃分的割所通過的邊的權值最大問題，基于退火算法實現了車輛容量和工序約束下的任務分配，接著通過蟻群算法在工序約束下進一步優化了單個車輛的配送路徑，并通過仿真對整個算法流程進行了驗證，仿真結果表明該算法能有效減少任務分配后的平均路程，對減少船舶制造過程物料運輸的成本、提高運送效率有重要意義。