面向船舶制造企業(yè)車間作業(yè)過(guò)程物料配送優(yōu)化方法

段金健，王美清，王澤宇

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

0 引言

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

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

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

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

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

1.1 研究假設(shè)

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

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

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

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

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

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

針對(duì)物料配送優(yōu)化問(wèn)題約束多、優(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)過(guò)第p條道路時(shí)的費(fèi)用，opij表示在從工作地i到工作地j是否經(jīng)過(guò)道路p，是為1，否為0。通過(guò)式(2)將從工作地i到工作地j的最短距離集傳遞，Cij表示由工作地i到j(luò)的最小花費(fèi)，通過(guò)這個(gè)模型尋找各工作地間的最短道路。

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

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

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

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

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

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

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

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

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

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

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

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

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

第1步：參數(shù)初始化，導(dǎo)入工作地位置、道路關(guān)鍵節(jié)點(diǎn)、節(jié)點(diǎn)間的聯(lián)通情況、各個(gè)道路的長(zhǎng)度、設(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步：逐個(gè)螞蟻開始尋找下一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)是從除去禁忌表中已走過(guò)的節(jié)點(diǎn)，若沒(méi)有可選節(jié)點(diǎn)，則代表其進(jìn)入死區(qū)，這時(shí)需要終止這只螞蟻循環(huán)，并對(duì)其在后期釋放信息素時(shí)給予相應(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ī)決定螞蟻爬向的下一個(gè)節(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ù)每只螞蟻的路線更新信息素，更新信息素時(shí)采用分級(jí)蒸發(fā)策略，路程越長(zhǎng)的路徑蒸發(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 基于圖論的問(wèn)題轉(zhuǎn)化

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

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

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

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

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

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ù)以上概念對(duì)給出的任務(wù)分配進(jìn)行連續(xù)劃分，在圖3中{V1，V2，V3}就是有向無(wú)環(huán)圖G(V，E)的一個(gè)連續(xù)劃分。

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

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

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

第1步：參數(shù)初始化，首先任意給出一個(gè)工序排列，再對(duì)其進(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)行左右長(zhǎng)移，計(jì)算過(guò)左右長(zhǎng)移使Σc(i，j)增加的成本，記為Pv，則接受這次新解的概率為：

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

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

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

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

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

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

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

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

第4步：計(jì)算當(dāng)前排列下最佳劃分的割和經(jīng)過(guò)邊的總權(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)過(guò)程中的物料配送問(wèn)題的車輛最優(yōu)路徑搜索算法。

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

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

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

表1 10個(gè)工作地的任務(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的變異概率仍然會(huì)有路徑發(fā)生變異，本算法能較好的生成各工作地之間的最短路徑集。

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

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

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

圖5 10個(gè)工作地分配后的最優(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個(gè)、20個(gè)和30個(gè)工作地配送任務(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)化后的平均路程小于直接按工序順序的平均路程，在保證各個(gè)工序連通性和車輛的容量要求下平均路程有效減少。

4 結(jié)語(yǔ)

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