常建娥 王 璐 莫易敏 張 峰 李佛勝

(武漢理工大學(xué)機(jī)電工程學(xué)院1) 武漢 430070) (上汽通用五菱汽車股份有限公司2) 柳州 545000)

基于Manhattan距離的汽車總裝車間帶時(shí)間窗多AGV小車調(diào)度優(yōu)化

常建娥1)王 璐1)莫易敏1)張 峰1)李佛勝2)

(武漢理工大學(xué)機(jī)電工程學(xué)院1)武漢 430070) (上汽通用五菱汽車股份有限公司2)柳州 545000)

為解決汽車總裝車間物料配送AGV的調(diào)度問題，針對汽車流水線的布局特征，以AGV小車?yán)眯首罡摺?shù)量配置最少為目標(biāo)建立數(shù)學(xué)模型，提出了一種改進(jìn)的兩階段啟發(fā)式算法.通過基于Manhattan距離、時(shí)間聚集度的啟發(fā)式分類算法將物料配送點(diǎn)進(jìn)行聚類；按照聚類的結(jié)果，以及物料配送點(diǎn)的優(yōu)先級，得到優(yōu)化后AGV的行駛路徑.最后通過某汽車企業(yè)總裝車間多AGV調(diào)度優(yōu)化的實(shí)例，與原先的調(diào)度方案進(jìn)行結(jié)果對比，驗(yàn)證了該方法的有效性和可行性.

汽車總裝車間流水線布局；Manhattan距離；時(shí)空聚集度；AGV調(diào)度優(yōu)化

0 引 言

多車型混流生產(chǎn)模式下，零部件種類、數(shù)量增多，給總裝物流帶來一系列的挑戰(zhàn)，例如，線旁物料存儲面積不夠，物料配送頻次增多，物料配送不及時(shí)導(dǎo)致的停線次數(shù)增多等.面對這些挑戰(zhàn)，各主機(jī)廠紛紛采取自動導(dǎo)航小車(automated guided vehicle，AGV)拉動單臺份物料的SPS(set parts supply)配送模式，來滿足混流生產(chǎn)物流需求.

在SPS物料配送模式中，最重要的是確定AGV的行駛路線，即AGV的路徑規(guī)劃問題，其本質(zhì)上是VRP(vehicle routing problem)問題.國內(nèi)外對AGV的調(diào)度研究主要集中在AGV的路徑規(guī)劃、AGV的數(shù)量配置以及AGV的任務(wù)分配三個(gè)方面.同時(shí)也分為單AGV和多AGV系統(tǒng)的調(diào)度問題.Wassan[1]提出一種基于變鄰域搜索方法來求解MT-VRPB；Abel等[2]針對多目標(biāo)的VRPB問題提出了一種基于相似性選擇的進(jìn)化算法；于濱等[3]提出一個(gè)兩階段的啟發(fā)式算法研究帶時(shí)間窗的多中心車輛路徑優(yōu)化問題(MDVRPTW)；黃一鈞等[4]借助排隊(duì)論模型，以最小總成本為目標(biāo)建立了AGV小車數(shù)量配置計(jì)算模型；劉健等[5]基于Plant Simulation建立了某電表自動化檢測線中的AGVS模型，通過分析其仿真運(yùn)行狀況確定系統(tǒng)所需AGV的最佳數(shù)量；朱琳等[6]提出一種改進(jìn)的遺傳算法對配料區(qū)AGV小車進(jìn)行了任務(wù)分配的優(yōu)化并通過仿真的手段對配料區(qū)的物料儲存布局進(jìn)行了優(yōu)化改進(jìn)；邊培瑩等[7]以提高生產(chǎn)效率為目標(biāo)，提出了一種基于粒子群算法的AGV動態(tài)調(diào)度策略，均衡多個(gè)AGV的任務(wù)量，并使得AGV數(shù)量總體最優(yōu)；Qi等[9]綜合考慮空間距離和時(shí)間要求，對需求點(diǎn)進(jìn)行劃分，提出了一種基于時(shí)空距離的聚類思想，用于多任務(wù)的調(diào)度.

以上研究多集中在單AGV的路徑優(yōu)化、多AGV運(yùn)輸總距離最小以及物料配送系統(tǒng)中AGV數(shù)量配置最少的規(guī)劃問題.而汽車總裝車間布局模式以及精益生產(chǎn)要求物料及時(shí)配送，對AGV路徑規(guī)劃問題提出新的挑戰(zhàn).本文對SPS物料配送系統(tǒng)中的多AGV多個(gè)任務(wù)請求的調(diào)度優(yōu)化進(jìn)行研究，針對汽車總裝流水線布局特征，采用基于Manhattan距離、時(shí)間聚集度的兩階段啟發(fā)式算法，得到多個(gè)AGV任務(wù)分配的優(yōu)化結(jié)果和單個(gè)AGV的優(yōu)化路徑.

1 汽車總裝生產(chǎn)特征分析

在汽車總裝車間，根據(jù)裝配順序與工藝，分為內(nèi)飾、底盤與終線三部分，而這些工段通常是平行布置的.為了提高裝配效率，一般對大件總成物料采取模塊化供貨，即在內(nèi)飾、底盤、終線工段旁建立平行于工段的車門、儀表盤、發(fā)動機(jī)分裝線，以及座椅、輪胎的輸送鏈運(yùn)送物料到線旁.因此形成了間隔式Bay Layout布局[10].

此外，隨著汽車制造技術(shù)的發(fā)展，總裝車間生產(chǎn)節(jié)拍普遍達(dá)到了40JPH(job per hour)，有些甚至達(dá)到了60JPH，即在1 min之內(nèi)裝配完一輛車.在混流生產(chǎn)模式下，裝配流水線上每個(gè)工位每種車型所需物料也都不一樣，要滿足高節(jié)拍生產(chǎn)裝配，需要保障物料配送的及時(shí)性，即AGV的配送有時(shí)間窗要求.

為了滿足多品種、中小批量、高節(jié)拍的混流生產(chǎn)模式的物料供應(yīng)，大部分主機(jī)廠都采用SPS物料拉動模式.其運(yùn)作模式大致如下：在配載區(qū)將單臺份物料裝載到SPS料車上，由AGV將其配送到指定上線點(diǎn)；隨即AGV行駛至SPS空料車下線點(diǎn)，回收SPS空料車送到配載區(qū)；AGV回到充電點(diǎn)進(jìn)行周期性充電，接著開始下一周期的配送任務(wù).即AGV需要在指定的時(shí)間點(diǎn)到達(dá)指定的途經(jīng)點(diǎn)，形成一個(gè)回路.

綜上所述，汽車總裝車間多AGV的任務(wù)調(diào)度問題是一個(gè)基于汽車總裝車間Bay Layout布局的帶時(shí)間窗的路徑規(guī)劃問題VRPTW(vehicle routing problem with time window)，其最終目標(biāo)是提高送料AGV的利用率，減少AGV的配置數(shù)量，從而降低物流設(shè)備的投入成本、降低物流費(fèi)用.

2 基于Manhattan距離與時(shí)空距離的路徑規(guī)劃問題

2.1 汽車總裝車間AGV途經(jīng)點(diǎn)Manhattan空間距離

汽車總裝車間工段之間大多是間隔式布局.而在Bay Layout布局下，AGV途經(jīng)點(diǎn)之間的距離是不能用兩點(diǎn)之間的直線段即常用的歐式距離來計(jì)算的.圖1為汽車總裝車間兩個(gè)工段布局的簡化圖，由于AGV的磁帶軌道是平行于工段進(jìn)行鋪設(shè)的，且不能直接越過工段，因此只能按照上述箭頭所指的“正交路線”運(yùn)動.鑒于汽車總裝車間流水線Bay Layout布局對AGV運(yùn)動路徑的限制，本文基于Manhattan距離，計(jì)算并修正AGV途經(jīng)點(diǎn)之間的距離，得到最接近現(xiàn)實(shí)的途經(jīng)點(diǎn)距離.

注：A，B，C，D，E為裝配工位；M，N為內(nèi)飾一、內(nèi)飾二工段的定點(diǎn)位置坐標(biāo).圖1 汽車總裝車間工位Manhattan距離示意圖

在計(jì)算工位之間距離時(shí)，可以分為流水線兩工段之間工位(inter-bay)與流水線工段內(nèi)工位(intra-bay),計(jì)算公式為

A.B距離=Manhattan距離=

(1)

(2)

應(yīng)用修正后的Manhattan距離可以較為精確的計(jì)算AGV途經(jīng)點(diǎn)之間的距離，從而能得到更合理的途經(jīng)點(diǎn)聚類結(jié)果.

2.2 汽車總裝車間AGV途經(jīng)點(diǎn)時(shí)間距離

汽車總裝車間高節(jié)拍下的裝配生產(chǎn)需要穩(wěn)定、準(zhǔn)時(shí)的物料配送做保障，配送AGV要在途經(jīng)點(diǎn)所限定的時(shí)間窗內(nèi)到達(dá).因此，在對AGV進(jìn)行任務(wù)分配時(shí)，不僅要考慮途經(jīng)點(diǎn)間的空間距離，還要考慮其時(shí)間窗的關(guān)系.如果兩個(gè)途經(jīng)點(diǎn)的空間距離很近，但時(shí)間窗上相隔較久，則AGV在到達(dá)下一個(gè)制定位置之后還需要等待一段時(shí)間才能夠進(jìn)行作業(yè)，會產(chǎn)生浪費(fèi)；反之亦然.用時(shí)間距離DijT來度量兩個(gè)途經(jīng)點(diǎn)被相繼被同一輛AGV服務(wù)的便利程度，時(shí)間距離越小，則兩個(gè)途經(jīng)點(diǎn)越容易被同一輛AGV服務(wù)；時(shí)間距離越大，則兩個(gè)途經(jīng)點(diǎn)就越不容易被同一輛AGV服務(wù).

假設(shè)一輛AGV依次經(jīng)過點(diǎn)i和點(diǎn)j，其時(shí)間窗分別是Ti=[a,b]和Tj=[c,d]，設(shè)a≤c，從點(diǎn)i到點(diǎn)j需要花費(fèi)的時(shí)間為tij，假設(shè)在每個(gè)途經(jīng)點(diǎn)不作停留.

1) 若tij>d-a，即AGV從點(diǎn)i到達(dá)點(diǎn)j所需要的時(shí)間大于途經(jīng)點(diǎn)之間的最長時(shí)間間隔，AGV無法在同一任務(wù)中同時(shí)經(jīng)過點(diǎn)i和點(diǎn)j，因此，將途經(jīng)點(diǎn)i和j的時(shí)間距離設(shè)為無窮大.

2) 若c-b

3) 若tij

綜上所述，時(shí)間距離的計(jì)算公式為

(3)

2.3 汽車總裝車間AGV途經(jīng)點(diǎn)時(shí)空距離歸一化

汽車總裝車間送料AGV的任務(wù)是在規(guī)定的時(shí)間內(nèi)將規(guī)定的物料零部件配送到指定工位，既有空間距離上的要求，又有時(shí)間限制.一般的聚類方法都只以空間距離為分類依據(jù)，鮮少同時(shí)考慮到空間距離與時(shí)間窗要求.

文獻(xiàn)[9]借用時(shí)間地理學(xué)中的時(shí)空路徑概念來表達(dá)車輛的路徑，其中二維坐標(biāo)平面表示空間位置，垂直坐標(biāo)表示時(shí)間窗.根據(jù)這一原理，汽車總裝車間VRPTW問題的解也可以表示為AGV的時(shí)空路徑.圖2為汽車總裝車間AGV時(shí)空路徑示意圖.

圖2 汽車總裝AGV車間時(shí)空路徑示意圖

由圖2可知，AGV小車從O點(diǎn)出發(fā)，必須在時(shí)間窗要求內(nèi)依次達(dá)到各個(gè)途經(jīng)點(diǎn)配送物料、回收空車、進(jìn)行周期性充電等，且AGV的運(yùn)動路徑受限于總裝車間工段及分裝線的布局，只能按照圖中的“正交”路徑行駛.

Ds′ij=DTij×v

(4)

(5)

3 模型的建立與求解

3.1 汽車總裝車間AGV調(diào)度優(yōu)化模型

如果對AGV任務(wù)分配得不合理，就會導(dǎo)致有些AGV的配送任務(wù)過多、配送路徑過長，使得有些區(qū)域的物料配送不及時(shí)，很容易影響生產(chǎn)節(jié)拍甚至造成停線.為了保障混流生產(chǎn)，需要合理正確地將任務(wù)分配給多個(gè)AGV，并規(guī)劃出其行駛路徑，使得AGV的利用率最高.

汽車總裝車間多AGV的任務(wù)調(diào)度優(yōu)化問題存在以下假設(shè)和約束：

1) 汽車總裝車間各工段各工位布局及AGV可行走的路徑通道已經(jīng)確定，即途經(jīng)點(diǎn)的空間坐標(biāo)、時(shí)間窗要求以及任務(wù)優(yōu)先級已知.

2) 每輛AGV初始位置在集配區(qū)的充電樁處，當(dāng)AGV完成上料工位物料配送以及空車回收任務(wù)之后回到初始位置進(jìn)行充電.

3) 任何任務(wù)都可以分配給其中一輛AGV，且每輛AGV都相同.

4) AGV能夠滿足SPS料車上線任務(wù)和SPS空車下線任務(wù)的載重.

5) 每個(gè)指定的途經(jīng)點(diǎn)都要被經(jīng)過，且每個(gè)途經(jīng)點(diǎn)只能由一輛AGV經(jīng)過一次.

6) 滿足每個(gè)途經(jīng)點(diǎn)的時(shí)間窗要求，否則不可行.

在汽車總裝車間內(nèi)有一個(gè)SPS集配區(qū)，多輛配料AGV可供調(diào)度.整個(gè)汽車總裝車間有多個(gè)途經(jīng)點(diǎn)，可分為SPS料車上線點(diǎn)、SPS空車下線點(diǎn)、配載區(qū)AGV裝載點(diǎn)以及配載區(qū)AGV充電點(diǎn)四類，不妨設(shè)途經(jīng)點(diǎn)的編號為i∈{1,2,…,M},其中每個(gè)途經(jīng)點(diǎn)表示為Ci(xi,yi,ti)，xi為途經(jīng)點(diǎn)的橫坐標(biāo)；yi為途經(jīng)點(diǎn)的縱坐標(biāo)；ti=[tis,tie]為途經(jīng)點(diǎn)的時(shí)間窗要求；AGV的編號為k∈{1,2,…,N}；每輛AGV可經(jīng)過多個(gè)途徑點(diǎn)，AGV的途經(jīng)點(diǎn)編號為s∈{1,2,…,P},設(shè)SPS物料集配區(qū)編號為0.在上述假設(shè)和約束的前提下，使得汽車總裝車間AGV利用率最高，AGV總數(shù)最小，每輛AGV分配到的任務(wù)的時(shí)空距離最小，建立數(shù)學(xué)模型為

(6)

mink

(7)

λik0=0,?i,k

(8)

λik1≥λik2≥…≥λikp,?i,k

(9)

(10)

式(6)為每輛AGV所分配到的途經(jīng)點(diǎn)的時(shí)空距離之和最??；式(7)為AGV數(shù)量最少；式(8)為每個(gè)途經(jīng)點(diǎn)只由一輛AGV經(jīng)過；式(9)為每輛AGV的初始位置在SPS物料配載區(qū)；式(10)為每個(gè)途經(jīng)點(diǎn)從每輛AGV的第一個(gè)途經(jīng)點(diǎn)開始依次排列，保證每輛AGV的多個(gè)途經(jīng)點(diǎn)是連續(xù)排列的.

3.2 基于K-means算法的汽車總裝車間AGV調(diào)度模型求解

聚類是根據(jù)途經(jīng)點(diǎn)兩兩之間的時(shí)空距離來對其進(jìn)行分組，使得組內(nèi)途經(jīng)點(diǎn)之間的時(shí)空距離較小，而組間較大.劃分聚類問題是NP-完全問題.而對于汽車總裝車間裝配流水線來說，上料工位個(gè)數(shù)有限，而K-means算法在小范圍空間聚類被證明是穩(wěn)健的，因此采用K-means算法基于時(shí)空距離對AGV途經(jīng)點(diǎn)進(jìn)行聚類.

傳統(tǒng)的K-means算法的基本思想是：隨機(jī)或人為給定初始聚類中心點(diǎn)，按照最鄰近原則，將剩下的點(diǎn)根據(jù)距離被分配到距其最近的中心點(diǎn).然后在不斷迭代的過程中，中心點(diǎn)不斷改變，以便聚類的族群更密集地分布.文中采用修正后的Manhattan距離結(jié)合時(shí)空距離，設(shè)計(jì)了基于時(shí)空距離的K-means聚類的解決方法.具體計(jì)算過程為：

步驟1 確定聚類的數(shù)目 根據(jù)實(shí)際生產(chǎn)經(jīng)驗(yàn)，k(即AGV的配置數(shù)量)一般不會設(shè)置很大，可以通過枚舉，令k從2到一個(gè)固定值如10，在每個(gè)k值上重復(fù)運(yùn)行數(shù)次K-means，并計(jì)算當(dāng)前k的平均輪廓系數(shù)，最后選取輪廓系數(shù)最大的值對應(yīng)的k作為最終的集群數(shù)目.

步驟2 隨機(jī)選取k個(gè)初始中心點(diǎn)，依據(jù)Manhattan時(shí)空距離計(jì)算公式，計(jì)算其余點(diǎn)和初始中心點(diǎn)的空間距離和時(shí)間窗距離，選取ω1=0.5,ω2=0.5，將時(shí)空距離進(jìn)行歸一化處理，按照最鄰近原則，劃分到相應(yīng)的類別.

步驟3 在初始分類的結(jié)果上按平均值的方法重新計(jì)算聚類中心點(diǎn)，再重復(fù)步驟2，進(jìn)行迭代.

步驟4 直到最后每個(gè)類組內(nèi)時(shí)空距離之和最小，算法收斂，聚類數(shù)目最小且不再變動，則結(jié)束.

4 案例分析

4.1 汽車總裝車間平面布局及相關(guān)數(shù)據(jù)

以某汽車企業(yè)總裝車間內(nèi)飾工段為例，利用基于時(shí)空距離的K-means聚類算法對其總裝車間內(nèi)飾工段的送料AGV任務(wù)分配和排序進(jìn)行優(yōu)化.該汽車總裝車間采用SPS物料拉動模式，設(shè)有一個(gè)SPS物料配載區(qū)，放置內(nèi)飾一和內(nèi)飾二工段的SPS物料.當(dāng)裝配流水線上缺少物料時(shí)，AGV拉著滿載的SPS料車從配載區(qū)出發(fā)，將SPS料車送至相應(yīng)工段的上料點(diǎn)，然后空車下線點(diǎn)回收SPS空車，回到配載區(qū)卸下空車并進(jìn)行周期性充電.每個(gè)工段有一個(gè)上線點(diǎn)，一個(gè)下線點(diǎn)，一個(gè)拆包裝點(diǎn)，圖3為汽車總裝車間內(nèi)飾工段現(xiàn)行AGV行駛路徑示意圖.

圖3 汽車總裝車間內(nèi)飾工段現(xiàn)行AGV路徑示意圖

由圖3可知，一組AGV負(fù)責(zé)內(nèi)飾一工段，其行駛路徑如紅線所示；另外一組AGV負(fù)責(zé)內(nèi)飾二工段，其行駛路徑如綠線所示.兩組AGV均隨行于SPS料車，在SPS料車上線之后到下線之前AGV均處于空載等待狀態(tài)，導(dǎo)致AGV單次運(yùn)行周期過長，需要配置較多的AGV來滿足物料的實(shí)時(shí)配送.內(nèi)飾工段途經(jīng)點(diǎn)的坐標(biāo)以及時(shí)間窗要求見表1.

4.2 優(yōu)化結(jié)果及分析

為最大限度提高AGV的利用率，減少AGV的數(shù)量配置.下面依照上述基于Manhattan距離的時(shí)空聚類方法對AGV的任務(wù)分配進(jìn)行優(yōu)化.

對兩兩途經(jīng)點(diǎn)之間的Manhattan空間距離以及時(shí)間窗距離進(jìn)行計(jì)算，并最終進(jìn)行歸一化處理得到時(shí)空距離，并依據(jù)時(shí)空距離對其進(jìn)行聚類，聚類結(jié)果為

表1 各途經(jīng)點(diǎn)的空間坐標(biāo)及時(shí)間窗要求

AGV1：0-1-2-6-7

AGV2：0-4-5-3-7

內(nèi)飾一 AGV由SPS配載區(qū)起點(diǎn)出發(fā)，經(jīng)過內(nèi)飾一物料拆包裝點(diǎn)，到達(dá)內(nèi)飾一SPS料車上線點(diǎn)，后穿過內(nèi)飾一和內(nèi)飾二過道，到達(dá)內(nèi)飾二SPS料車下線點(diǎn)，拉回內(nèi)飾二空料車回到SPS配載區(qū)充點(diǎn)電進(jìn)行周期性充電.

內(nèi)飾二 AGV由SPS配載區(qū)起點(diǎn)出發(fā)，穿過內(nèi)飾一和內(nèi)飾二過道到達(dá)內(nèi)飾二物料拆卸點(diǎn)，然后達(dá)到內(nèi)飾二SPS料車上線點(diǎn)，再穿過過道去內(nèi)飾一SPS料車下線點(diǎn)拉回內(nèi)飾一空料車回到SPS配載區(qū)充電點(diǎn)進(jìn)行周期性充電.

優(yōu)化后的兩組AGV的行駛路徑示意圖見圖4.

圖4 優(yōu)化后內(nèi)飾工段AGV行駛路徑示意圖

由圖4可知，配料AGV的任務(wù)分配不再只是按照工段，二是依據(jù)時(shí)空距離就近進(jìn)行分配.很明顯，配送內(nèi)飾一SPS料車以及回收內(nèi)飾二SPS料車的一組AGV的單次配送時(shí)間縮短，由原來的1 252 s縮短到610 s；配送內(nèi)飾二SPS料車以及回收內(nèi)飾一SPS料車的一組AGV單次配送時(shí)間也有小幅降低，由原來的2 008 s縮短到1 736 s.

按照60JPH，一輛AGV單次周期配送三輛SPS料車進(jìn)行計(jì)算，任務(wù)分配優(yōu)化后，汽車總裝車間內(nèi)飾工段配料AGV的數(shù)量縮減為

內(nèi)飾一工段：(1252-610)/(3×60)=3.57≈3

內(nèi)飾二工段：(2008-1736)/(3×60)=1.51≈1

即通過基于Manhattan距離結(jié)合時(shí)間窗距離的時(shí)空聚類方法來分配AGV的任務(wù)點(diǎn)，能夠在一定程度上減少AGV的空載等待以及AGV的空載行駛距離，提高AGV的利用率，從而縮短AGV的單次配送周期，最終減少AGV的配置數(shù)量，降低物流配送成本.

5 結(jié) 束 語

針對多途徑點(diǎn)帶時(shí)間窗的多AGV任務(wù)分配問題，根據(jù)汽車總裝車間的Bay Layout布局，對途經(jīng)點(diǎn)之間的Manhattan距離進(jìn)行了修正，提出了改進(jìn)的基于時(shí)空距離的K-means算法，將優(yōu)化方法運(yùn)用到某汽車企業(yè)總裝車間內(nèi)飾工段配料AGV的調(diào)度上，改進(jìn)后的方案使得AGV的單次配送周期縮短、AGV的利用率提高、總的AGV配置數(shù)量減少，證明了該優(yōu)化方法的有效性.本文對實(shí)際的多AGV任務(wù)分配問題進(jìn)行了一定程度的簡化，忽略了物料的裝卸時(shí)間和可能出現(xiàn)的AGV碰撞問題.在今后進(jìn)一步的研究中，可以考慮存在碰撞情況下AGV路徑的規(guī)劃問題.

[1]WASSAN N. The multiple trip vehicle routing problem with backhauls: formulation and a two-level variable neighbourhood search[J]. Computers and Operations Research, 2016(1)：55-58.

[2]ABEL G N, JOHN A， MIGUEL A，et al. An evolutionary approach for multi-objective vehicle routing problems with backhauls [J].Computers & Industrial Engineering,2015,81:90-108.

[3]于濱，靳鵬歡，楊忠振.兩階段啟發(fā)式算法求解帶時(shí)間窗的多中心車輛路徑問題[J].系統(tǒng)工程理論與實(shí)踐，2012,32(8)：1793-1800.

[4]黃一鈞.車身車間AGV物料搬運(yùn)系統(tǒng)小車數(shù)量配置規(guī)劃[J].工業(yè)工程與管理，2016(4)：156-162.

[5]劉健，黃奇峰，王忠東,等.基于Plant Simulation 的AGV輸送系統(tǒng)仿真分析及其應(yīng)用[J].現(xiàn)代制造工程，2013(11):13-19.

[6]朱琳，范秀敏，何其昌.柔性生產(chǎn)系統(tǒng)配料區(qū)多自動導(dǎo)航小車調(diào)度優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2012(6):1168-1175.

[7]邊培瑩，李德信，包寶軍,等.粒子群算法在生產(chǎn)物流調(diào)度中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(17)：220-223.

[8]戚銘堯，張金金，任麗.基于時(shí)空聚類的帶時(shí)間窗車輛路徑規(guī)劃算法[J].計(jì)算機(jī)科學(xué)，2014，41(3)：218-222.

[9]QI M Y, LIN W H, LI N,et al. A spatiotemporal partitioning approach for large-scale vehicle routing problem with time windows[J].Transportation Research Part E, 2012,48:248-257.

[10]WANG H F, CHANG C M. Facility layout for an automated guided vehicle system[J]. Procedia Computer Science, 2015,55:52-61.

Multiple AGVs Scheduling with Time Windows in the Automotive General Assembly Shop Based on the Manhattan Distance

CHANG Jian’e1)WANG Lu1)MO Yimin1)ZHANG Feng1)LI Fosheng2)

(SchoolofMechanicalandElectronicEngineering,WuhanUniversityofTechnology,Wuhan430070,China)1)(SAIC-GM-WULINGAutomobileCo.Ltd.,Liuzhou54500,China)2)

To solve the scheduling problem of material distribution AGVs in the General Assembly shop, the paper proposes an improved two-phase heuristic algorithm based on the layout of the automotive assembly line and develops a mathematical model which aims at the highest utilization and the minimum quantity of the AGVs. Firstly, the material demanding stations with the heuristic sorting algorithm are clustered based on both the Manhattan distance and the time requirements. Besides, according to the results of clustering and the priority of material demanding stations, the optimal paths of AGVs are scheduled. At last, through AGVs scheduling examples in the automotive GA shop, the feasibility and the validity of this method are verified based on the comparison with its former AGVs scheduling scheme.

the layout of the automotive assembly line in the GA shop; the Manhattan distance; concentration of time and space; AGV scheduling optimization

2017-05-26

TP391

10.3963/j.issn.2095-3844.2017.04.011

常建娥(1962—):女，碩士，教授，主要研究領(lǐng)域?yàn)闄C(jī)械設(shè)計(jì)與理論、物流工程