基于改進(jìn)蟻群算法的時(shí)間窗車輛配送路徑優(yōu)化研究

呂再生，樊 航，董寶力，賈江鳴

(浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(xué)院，浙江 杭州 310018)

整車制造企業(yè)通常采用傳統(tǒng)型多品種、小批量的混流生產(chǎn)模式.其復(fù)雜的工藝特性和繁多的零部件種類導(dǎo)致其物流配送要求極為嚴(yán)格，生產(chǎn)物流同步是其追求的終極目標(biāo)，同時(shí)一直是國(guó)內(nèi)外學(xué)者關(guān)注的重點(diǎn).

張資淵探討了看板、配套、順序等各種補(bǔ)貨方法的優(yōu)勢(shì)和劣勢(shì)，通過(guò)建立零部件層級(jí)成本計(jì)算模型，提出了用成本決定最優(yōu)補(bǔ)貨方法的策略[1].洪旭東等提出了基于看板的生產(chǎn)線物料循環(huán)配送方式，通過(guò)優(yōu)化看板數(shù)量、循環(huán)周期等參數(shù)提升了配送的及時(shí)性和準(zhǔn)確性[2].李偉等針對(duì)汽車總裝線邊空箱拉動(dòng)供料模式下的物料配送問(wèn)題，以配送路徑最短和配送路線需求點(diǎn)配送頻次均衡化為目標(biāo)，建立了空箱拉動(dòng)模式零件配送路徑優(yōu)化模型[3-4].Banos R等基于平行多目標(biāo)模擬退火遺傳算法解決帶時(shí)間窗的車輛調(diào)度問(wèn)題時(shí)，通過(guò)最大限度地減少車輛的行駛距離和線路不合理多目標(biāo)約束構(gòu)建了模型[5].張小龍等構(gòu)建目標(biāo)聯(lián)運(yùn)路徑優(yōu)化模型時(shí)，引入了混合時(shí)間窗概念，并利用基于Pareto適應(yīng)度的遺傳算法，求解了一個(gè)多式聯(lián)運(yùn)的算例[6-7].尚文利等提出了基于射頻識(shí)別技術(shù)RFID(Radio Frequency Identification)的車輛追蹤和基于條碼的無(wú)線物料庫(kù)存管理方法，并設(shè)計(jì)了裝配生產(chǎn)線的物料動(dòng)態(tài)配送調(diào)度業(yè)務(wù)流程[8].黨立偉等根據(jù)制造BOM(Bill of Material)和裝配工藝流程，求出了最優(yōu)配送周期和每次配送量[9].丁佳祺等以成本最小為目標(biāo)，考慮線邊庫(kù)存容量和牽引車最大運(yùn)輸量約束，確定了最優(yōu)循環(huán)周期和看板數(shù)量[10].

物料配送的相關(guān)研究大多集中于傳統(tǒng)的紙質(zhì)看板環(huán)境下通過(guò)手工輸入信息，獲取零件看板，且主要通過(guò)優(yōu)化看板數(shù)量及配送頻次，或者改變配送方式來(lái)提升零件配送效率.傳統(tǒng)的被動(dòng)式配送服務(wù)存在如下缺陷：①看板卡片容易丟失，線邊拉動(dòng)需求往往無(wú)法及時(shí)傳遞至配料區(qū)；②容易受配送人員主觀因素的影響，導(dǎo)致線邊零件短缺或溢庫(kù)；③內(nèi)、外部物流信息無(wú)法及時(shí)有效共享.因此，本文將條碼、RFID、信息集成等技術(shù)用于汽車總裝生產(chǎn)線，通過(guò)獲取汽車總裝生產(chǎn)線的零件電子看板信息，對(duì)其內(nèi)部配送路徑進(jìn)行帶時(shí)間窗約束的路徑規(guī)劃，實(shí)現(xiàn)小批量、多頻次的零部件物流供應(yīng)，使生產(chǎn)線邊的庫(kù)存最小化，達(dá)到廠內(nèi)外物流信息共享，實(shí)現(xiàn)生產(chǎn)物流的同步.

1 電子看板環(huán)境下的零件同步物流配送系統(tǒng)

電子看板是將信息技術(shù)應(yīng)用于生產(chǎn)可視化的一種工具，它避免了傳統(tǒng)實(shí)物看板模式下信息在傳遞過(guò)程中產(chǎn)生的丟失、涂改和損壞現(xiàn)象，同時(shí)增強(qiáng)了信息傳遞的及時(shí)性和可靠性[11].

電子看板環(huán)境下的零件配送過(guò)程主要包括零件信息收集、揀配單生成、揀配、配送后回到倉(cāng)庫(kù).其具體業(yè)務(wù)流程如圖1所示.在生產(chǎn)線上，通過(guò)RFID技術(shù)可識(shí)別每個(gè)車身的車輛識(shí)別號(hào)碼(Vehicle Identification Number,VIN).當(dāng)車身經(jīng)過(guò)設(shè)定的掃描站點(diǎn)時(shí)，零件同步物流配送系統(tǒng)向車體自動(dòng)識(shí)別系統(tǒng)(Automatic Vehicle Identification System,AVI)發(fā)送車體到位信號(hào)，觸發(fā)RFID天線進(jìn)行載碼體的讀寫，將數(shù)據(jù)傳輸至制造執(zhí)行系統(tǒng)(Manufacturing Execution System,MES)的相應(yīng)模塊，MES依據(jù)企業(yè)資源計(jì)劃(Enterprise Resouce Planning,ERP)中的BOM信息，計(jì)算汽車總裝生產(chǎn)線的零件供貨指示信息.針對(duì)SPS(Set Parts System)零件，可自動(dòng)生成揀配單，在SPS揀配區(qū)域揀配并等待車輛同步上線；供應(yīng)商根據(jù)車輛上線順序?qū)IS(Just In Sequence)零件進(jìn)行排序配送，并按需要的時(shí)間配送至廠區(qū)；電子看板零件數(shù)達(dá)到系統(tǒng)設(shè)定的包裝數(shù)量后，生成相應(yīng)的零件揀配單.配送中心每隔一段時(shí)間處理并打印一次揀配單.揀配人員按照揀配單的要求對(duì)零件進(jìn)行揀配并入庫(kù).當(dāng)達(dá)到配送時(shí)間要求時(shí)，配送人員對(duì)零件進(jìn)行配送服務(wù)并收取相應(yīng)的空料箱，將空料箱置于指定區(qū)域并集中返回配送中心.

圖1 基于電子看板的配送業(yè)務(wù)流程

2 基于時(shí)間窗電子看板零件配送的路徑規(guī)劃

2.1 設(shè)定電子看板零件時(shí)間窗

帶時(shí)間窗車輛問(wèn)題(Vehicle Routing Problem with Time Windows,VRPTW)是在傳統(tǒng)的車輛路徑問(wèn)題上加上時(shí)間窗的約束.它通?？梢苑譃橛矔r(shí)間窗、軟時(shí)間窗和混合時(shí)間窗.本文研究的是混流裝配線，對(duì)物料配送要求比較嚴(yán)格，一旦零件配送晚于裝配線需求時(shí)間，將導(dǎo)致整條汽車總裝生產(chǎn)線的停產(chǎn)，故采用硬時(shí)間窗類型.這里，零件配送要求最晚到達(dá)時(shí)間為：

LTims=ETims+TSi

(1)

式中：ETims為看板零件達(dá)到包裝量后系統(tǒng)顯示的最早需求時(shí)間；T為生產(chǎn)線節(jié)拍；Si為掃描站點(diǎn)與工位i之間的待裝配車輛數(shù)量.

2.2 建立配送路徑規(guī)劃數(shù)學(xué)模型

本文在零件配送時(shí)間窗要求下，以配送總成本為目標(biāo)函數(shù)，對(duì)配送路徑進(jìn)行具體優(yōu)化，并給出如下假設(shè)：①配送小車從配送中心出發(fā)，最后返回配送中心；②配送小車的總配送量不允許超過(guò)其最大載荷，否則將受到額外懲罰；③允許配送小車提前對(duì)零件進(jìn)行配送，但將產(chǎn)生提前配送成本；④每個(gè)工位所需零件只允許一輛配送小車為其服務(wù).

基于時(shí)間窗約束的配送路徑優(yōu)化模型包括目標(biāo)函數(shù)和約束條件兩部分.其中目標(biāo)函數(shù)由三部分組成.第一部分為小車的啟動(dòng)成本f1.

minf1=c1V

(2)

式中：c1為啟動(dòng)每輛配送小車的固定成本；V為配送周期內(nèi)所需配送小車的數(shù)量.

第二部分為指定批次零件配送所需小車服務(wù)費(fèi)用f2.

(3)

第三部分為零件ms在配送過(guò)程中提前配送至工位而產(chǎn)生的額外等待成本f3.

(4)

因此，目標(biāo)函數(shù)為：

(5)

約束條件為：

(6)

(7)

配送小車均從物料超市出發(fā)，即：

(8)

配送小車完成物料配送后最終返回物料超市，即：

(9)

工位j所需零件ms來(lái)自工位i,即：

(10)

配送小車到達(dá)工位i的時(shí)間不能晚于工位i要求的最遲到達(dá)時(shí)間，即：

ms=1,2,…,M)

(11)

在零件ms配送過(guò)程中，每次配送量不能超過(guò)配送小車所能承受的最大載荷，即：

(12)

式中：Jims為零件ms每次配送至工位i的量；Q為配送小車所能承受的最大載荷.

3 改進(jìn)蟻群算法的實(shí)現(xiàn)

蟻群算法是一種用來(lái)優(yōu)化路徑的概率型算法，屬于啟發(fā)式全局優(yōu)化算法，適用于求解復(fù)雜的組合優(yōu)化問(wèn)題[12].在該算法中，螞蟻通過(guò)判斷信息素濃度來(lái)選擇下一節(jié)點(diǎn).信息素濃度越大，選擇該節(jié)點(diǎn)的概率就越大，導(dǎo)致該條路徑的信息素進(jìn)一步增強(qiáng)，容易產(chǎn)生早熟、停滯現(xiàn)象.因此，本文對(duì)選擇策略進(jìn)行如下改進(jìn)：當(dāng)搜索陷入局部最優(yōu)時(shí)，增大隨機(jī)選擇的概率，從而避免蟻群進(jìn)入早熟、停滯現(xiàn)象.

2-opt(2-optimization)算法是基于“交換”的啟發(fā)式思想，將一條路徑轉(zhuǎn)換為另一條路徑，在給定可行路徑中，只要能降低目標(biāo)函數(shù)值，算法就會(huì)在選定集合內(nèi)進(jìn)行反復(fù)操作，直到產(chǎn)生局部最優(yōu)路徑為止.其原理是用(i，j)，(i+1，j+1)來(lái)替換(i，i+1),(j，j+1).如此變換后，路線中的路徑(i+1，…，j)被反向處理，且交換后路徑權(quán)值減小，即滿足如下條件：

Ci j+Ci+1,j+1

(13)

2-opt交換算法如圖2所示.

圖2 2-opt交換算法

改進(jìn)蟻群算法的實(shí)現(xiàn)步驟如下：

步驟1：初始化參數(shù)并設(shè)置計(jì)數(shù)器NC=0，把M只螞蟻放置于配送中心，同時(shí)建立禁忌表，設(shè)定每條路徑的初始信息素濃度τi j(0)，并找出全局初始解Lgb.

(14)

步驟3：確定節(jié)點(diǎn)i與節(jié)點(diǎn)j上總貨物量sum_g并與小車所能承受的最大載荷Q進(jìn)行比較.如果sum_g小于Q，則繼續(xù)選擇下一節(jié)點(diǎn)；否則將節(jié)點(diǎn)j加入禁忌表中，并跳轉(zhuǎn)至步驟5.

步驟4：計(jì)算到達(dá)時(shí)間Tj.如果Tj滿足節(jié)點(diǎn)的時(shí)間要求，就計(jì)算節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑長(zhǎng)度和費(fèi)用，轉(zhuǎn)至步驟2；否則進(jìn)入下一步驟.

步驟5：計(jì)算配送小車的數(shù)量并判斷allow表.若該表為空，則進(jìn)入下一步驟；否則從該表中得到未經(jīng)過(guò)的節(jié)點(diǎn)，并從各節(jié)點(diǎn)中選擇開(kāi)始時(shí)間最早的點(diǎn)，轉(zhuǎn)入步驟2.在每只螞蟻確定配送路徑后進(jìn)行局部搜索，并對(duì)部分更優(yōu)的路徑采用2-opt方法進(jìn)行可行解的領(lǐng)域搜索.

步驟6：對(duì)每只螞蟻所經(jīng)過(guò)的路徑進(jìn)行局部信息素更新和信息素增量更新.當(dāng)螞蟻決定按照轉(zhuǎn)移概率訪問(wèn)下一節(jié)點(diǎn)時(shí)，路徑(i，j)上螞蟻留下的信息素被更新為：

τi j(t+n)=(1-ρ)τi j(t)+Δτi j(t)

(15)

步驟7：求出M只螞蟻搜索的最短路徑和費(fèi)用，并更新信息素.如果M只螞蟻已全部走過(guò)一遍，那么更新螞蟻搜索過(guò)節(jié)點(diǎn)的信息素；不然則更新本次循環(huán)的最好路徑.

步驟8：記錄本次路徑長(zhǎng)度Lopt與對(duì)應(yīng)的路徑表.本次最優(yōu)路徑Llocal與全局最優(yōu)解Lgb進(jìn)行比較，記錄兩者間最優(yōu)解并更新最優(yōu)路徑表.

步驟9：判斷計(jì)數(shù)器的值是否達(dá)到最大迭代次數(shù).如果已經(jīng)達(dá)到最大迭代次數(shù)，那么流程結(jié)束；否則，清空禁忌表，返回步驟2并重復(fù)操作.

4 實(shí)例驗(yàn)證

某總裝生產(chǎn)線有20個(gè)工位需要進(jìn)行零件配送.圖3所示為其各需求點(diǎn)的分布狀況.其各工位基本需求信息如表1所示.單元之間的標(biāo)準(zhǔn)配送時(shí)間如表2所示.假設(shè)配送小車的固定消耗成本為80元/輛，小車的最大容量為6 m3，單位距離運(yùn)輸成本為0.5元/m.蟻群的種群規(guī)模為50只，最大迭代次數(shù)為250，α=1.5，β=2，γ=0.9，小車超載的懲罰因子為10 000元，提前送至工位產(chǎn)生的單位時(shí)間等待成本為30元/min，延遲送至線邊的成本為+∝.可采用Matlab軟件求得最優(yōu)方案.

圖3 總裝生產(chǎn)線各需求點(diǎn)的分布狀況

序號(hào)零件名稱包裝量/個(gè)配送總?cè)萘?m3最早配送時(shí)間要求最晚配送時(shí)間要求卸貨/裝空架時(shí)間/min000102030405060708091011121314151617181920/前圍內(nèi)減震墊后保險(xiǎn)杠左側(cè)尾燈前地毯總成后擋風(fēng)玻璃總成轉(zhuǎn)向節(jié)帶制動(dòng)器真空助力器總成前頂燈總成油箱固定帶儀表板橫梁轉(zhuǎn)向管柱中間軸總成散熱器總成前門密封條總成動(dòng)力轉(zhuǎn)向器總成增壓器輸氣軟管天窗總成前副車架總成右前門鎖總成左后輪眉總成后懸置支架總成右前腳踏墊/301015241830241218402850251271024401510/1.290.590.602.000.790.500.581.461.150.691.091.410.670.870.670.930.551.140.571.20016:00:1916:01:5416:02:3516:02:2316:02:0416:00:0116:02:3516:02:1816:03:1816:01:3316:02:0416:01:4916:03:4616:02:3516:00:1616:00:0016:03:1716:01:1416:01:3616:01:0416:15:0016:08:1916:09:5416:10:3516:10:2316:10:0416:08:0116:10:3516:10:1816:11:1816:09:3316:10:0416:09:4916:11:4616:10:3516:08:1616:08:0016:11:1716:09:1416:09:3616:09:0400.420.450.170.340.410.350.350.490.590.530.540.480.230.580.130.160.230.480.420.45

表2 單元之間的標(biāo)準(zhǔn)配送時(shí)間 min

用傳統(tǒng)蟻群算法和改進(jìn)蟻群算法對(duì)目標(biāo)函數(shù)進(jìn)行求解，可得圖4所示的種群迭代進(jìn)化圖.對(duì)于此次求解過(guò)程，改進(jìn)蟻群算法在迭代次數(shù)為95時(shí)曲線趨向收斂，比傳統(tǒng)蟻群算法收斂得更快，得出的值更優(yōu).

針對(duì)配送路徑問(wèn)題，采用改進(jìn)蟻群算法求解時(shí)路徑信息如表3所示.改進(jìn)蟻群算法與傳統(tǒng)蟻群算法的路徑優(yōu)化結(jié)果如表4所示.

圖4 蟻群算法的種群迭代進(jìn)化圖

配送路徑配送子路徑配送容量/m3路徑行駛時(shí)間/min路徑配送成本/元配送小車有效裝載率/%路徑10,12,20,11,18,14,05.71210.938 2294.495.2路徑20,16,15,2,4,7,10,19,05.20311.669 9395.686.7路徑30,1,6,9,5,3,8,05.79113.287 2265.396.5路徑40,17,13,01.2217.228 893.920.3

表4 路徑優(yōu)化結(jié)果對(duì)比效果 元

從表4可知，針對(duì)每批次零件配送任務(wù)，改進(jìn)蟻群算法比傳統(tǒng)蟻群算法節(jié)省1輛配送小車，配送總成本降低了(1 525.930 8元-1 369.285 4元)，約156.6元.

5 結(jié)束語(yǔ)

本文主要研究了汽車總裝車間的零件配送優(yōu)化問(wèn)題，分析了基于電子看板的汽車總裝生產(chǎn)線的零件配送流程，建立了一種定時(shí)定量的配送方式.在此配送模式下，針對(duì)汽車總裝生產(chǎn)線的零件配送時(shí)間窗，以配送總成本為目標(biāo)函數(shù)進(jìn)行配送路徑優(yōu)化，采用改進(jìn)蟻群算法求解并進(jìn)行了實(shí)例仿真，得出了能夠滿足現(xiàn)有條件的最佳配送路徑，提升了生產(chǎn)線的整體配送效率.