段金健，王美清，王澤宇

（北京航空航天大學(xué) 機(jī)械工程及自動化學(xué)院，北京 100191）

0 引言

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

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

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

1 面向車間作業(yè)的物料配送優(yōu)化模型建立

面向船舶制造企業(yè)車間作業(yè)的物料配送模型十分復(fù)雜，完全對其進(jìn)行建模和求解有一定難度。因此本研究取其中適用性高、影響大的因素為優(yōu)化目標(biāo)。物料配送優(yōu)化本質(zhì)上是搜尋成本最低的配送方案。船舶制造過程中的物流配送特點(diǎn)是：1）各工作地點(diǎn)間的道路并非直線需要考慮工作地間的實(shí)際道路，為了方便問題研究，本文將兩目標(biāo)點(diǎn)間的直線路徑模型稱為“路徑”，將兩目標(biāo)點(diǎn)間實(shí)際存在可達(dá)路徑的折線路徑模型稱為“道路”；2）物料的配送有順序，需要按照工序?qū)⑽锪弦来嗡瓦_(dá)目的地，因此建立模型時必須引入工序約束；3）船廠配送的物料較多，一般不能由一輛車全部配送完成，因此必須研究車輛的任務(wù)分配問題。基于上述特點(diǎn)可以建立如下數(shù)學(xué)模型。

1.1 研究假設(shè)

為了更好的優(yōu)化目標(biāo)，假設(shè)物料配送過程滿足以下條件：

1）物料運(yùn)輸方向滿足工序間順序要求，不存在因反向作業(yè)，導(dǎo)致的車輛需要多次經(jīng)過同一工作地的情況；

2）各作業(yè)地點(diǎn)間道路通斷情況已知；

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

4）配送任務(wù)和工序作業(yè)清單已知。

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

針對物料配送優(yōu)化問題約束多、優(yōu)化層次復(fù)雜的特點(diǎn)，建立了面向道路、任務(wù)和容量約束的多層次多目標(biāo)優(yōu)化數(shù)學(xué)模型。

1）面向道路約束的最優(yōu)道路搜索模型

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

2）面向工序和容量約束的最優(yōu)任務(wù)分配模型

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

3）各車輛運(yùn)輸成本最低模型

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

2 面向車間作業(yè)的物料配送優(yōu)化方法

2.1 面向車間作業(yè)的物料配送優(yōu)化過程模型

根據(jù)建立的數(shù)學(xué)模型將優(yōu)化流程分為以下三步：

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

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

3）搜尋當(dāng)前任務(wù)下單車輛的最優(yōu)路徑。形成最優(yōu)任務(wù)分配集后，雖然有工序約束，但是一輛車可能會執(zhí)行多個產(chǎn)品物料配送，它們的工序是并行的，因此還是會出現(xiàn)多種路徑安排，需要對路徑進(jìn)行進(jìn)一步優(yōu)化，以實(shí)現(xiàn)配送成本最低。面向車間作業(yè)的物料配送優(yōu)化過程模型如圖1所示。

圖1 面向車間作業(yè)的船廠物料配送優(yōu)化流程

2.2 基于蟻群算法的工作地間最優(yōu)路徑搜索

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

第1步：參數(shù)初始化，導(dǎo)入工作地位置、道路關(guān)鍵節(jié)點(diǎn)、節(jié)點(diǎn)間的聯(lián)通情況、各個道路的長度、設(shè)置變異概率、設(shè)置當(dāng)前迭代次數(shù)NC=0、設(shè)置最大迭代次數(shù)NC_MAX、設(shè)置螞蟻數(shù)、設(shè)置初始信息素濃度、信息素?fù)]發(fā)率及誘導(dǎo)因子等。

第2步：進(jìn)入循環(huán)，NC NC+1，將所有的螞蟻放置到起點(diǎn)，將起點(diǎn)加入禁忌表。

第3步：逐個螞蟻開始尋找下一個節(jié)點(diǎn)，下一個節(jié)點(diǎn)是從除去禁忌表中已走過的節(jié)點(diǎn)，若沒有可選節(jié)點(diǎn)，則代表其進(jìn)入死區(qū)，這時需要終止這只螞蟻循環(huán)，并對其在后期釋放信息素時給予相應(yīng)懲罰。每只螞蟻尋找節(jié)點(diǎn)由轉(zhuǎn)移概率公式?jīng)Q定，即：

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

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

第5步：設(shè)置變異概率，每只螞蟻的爬行路線按一定概率進(jìn)行變異。

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

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

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

2.3 基于轉(zhuǎn)化模型和退火算法的任務(wù)分配

2.3.1 基于圖論的問題轉(zhuǎn)化

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

圖2 作業(yè)任務(wù)工作地分配示例

通過以下概念可以將加工任務(wù)分配問題轉(zhuǎn)化為求割通過的邊權(quán)值最大問題。

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

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

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

4）連續(xù)點(diǎn)集：如果V中的所有的點(diǎn)都是連通的，則稱V為連續(xù)點(diǎn)集。

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

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

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

2.3.2 基于圖模型的最優(yōu)任務(wù)分配方法

在將任務(wù)分配問題轉(zhuǎn)化為圖論問題后，將圖論知識與退火算法相融合，設(shè)計(jì)了最優(yōu)任務(wù)分配搜索算法，具體步驟如下：

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

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

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

即當(dāng)i，j 之間有邊時f(i，j)=1，當(dāng)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，則將點(diǎn)vp移動至vp+n到vp+n+1之間，稱為點(diǎn)的右長移，右長移并不會改變工序順序約束。

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

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

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

3）判斷v=n+1，若不等于重復(fù)1），若等于進(jìn)行4）。

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

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

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

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

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

2.4 基于蟻群算法的考慮任務(wù)分配的車輛最優(yōu)路徑搜索算法

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

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

3 試驗(yàn)仿真與結(jié)果分析

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

表1 10個工作地的任務(wù)基本信息

表2 工作地及路口坐標(biāo)

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

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

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

按照算法流程進(jìn)行最優(yōu)任務(wù)分配得到的結(jié)果如圖4所示。其中可以看出在工作地6和7之間通過割的邊的權(quán)重最大，形成任務(wù)分配集。

圖4 10個工作地的最優(yōu)任務(wù)分配

得到任務(wù)分配集和由最短道路集生成的最短路徑距離集后對單車輛配送路徑進(jìn)行優(yōu)化得到結(jié)果如圖5所示。

圖5 10個工作地分配后的最優(yōu)路徑

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

隨機(jī)取10個、20個和30個工作地配送任務(wù)，工作地在相距為10的地圖中隨機(jī)生成。為了實(shí)現(xiàn)運(yùn)輸任務(wù)完全按照工序順序約束執(zhí)行，分別計(jì)算10次隨機(jī)實(shí)驗(yàn)直接按照工序運(yùn)送和分配優(yōu)化后的平均路程，得到的結(jié)果如表3所示。

表3 按照工序運(yùn)送和分配優(yōu)化后的平均路程

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

4 結(jié)語

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