張守京，段 嬌，童傅嬌

（1.西安工程大學 機電工程學院，西安 710600；2.西安市現(xiàn)代智能紡織裝備重點實驗室，西安 710048）

0 引言

隨著全球化經(jīng)濟進程的加速，離散制造企業(yè)之間的競爭愈發(fā)激烈，在車間運行過程中，生產(chǎn)物流中的輔助時間（物料的存儲、搬運等）占總時間的90%～95%[1]，因此優(yōu)化生產(chǎn)物流的運行水平對企業(yè)的生存與發(fā)展起著至關(guān)重要的作用，但是在目前離散制造車間生產(chǎn)物流的運行環(huán)節(jié)中，普遍存在著運輸成本高、配送效率低、工位服務滿意度差等問題[2]。隨著生產(chǎn)精益化、智能化、協(xié)同化的不斷發(fā)展，如何改善現(xiàn)有離散制造車間生產(chǎn)物流的運輸效率，提高工位服務滿意度，已經(jīng)成為了廣大離散制造企業(yè)亟需解決的重大難題之一。

車間物料配送路徑優(yōu)化問題本質(zhì)上是車輛路徑問題（Vehicle Routing Problem，VRP），由學者Danting和Ramser于1959年首次提出[3]。從理論研究方面看，物料配送路徑優(yōu)化問題已被證實是NP-hard問題[4]，其求解復雜度高，計算量大。初期對該類問題的研究主要集中在以行駛路徑最短、消耗成本最低或所用時間最少等單目標優(yōu)化方面，隨著科技的進步，研究熱點逐漸轉(zhuǎn)向多目標優(yōu)化，考慮因素更加多樣，更符合車間物料實際配送過程，Muller[5]在考慮軟時間窗的基礎上，將多目標優(yōu)化問題進行分解，并采用啟發(fā)式算法對其進行求解；Murao H[6]等對帶有模糊變量和懲罰函數(shù)的軟時間窗約束的VRP進行了研究；Xia Y[7]分析了開放式車輛路徑問題（OVRP），在考慮軟時間窗和滿意率的基礎上建立了雙目標OVRP模型，并運用帶自適應懲罰機制和多鄰域結(jié)構(gòu)的改進禁忌搜索算法（ITSA）進行求解；樓振凱[8]則針對配送多目標優(yōu)化問題，綜合考慮了車輛使用數(shù)及運輸總里程，基于雙層規(guī)劃思想，建立了帶模糊時間窗的多目標優(yōu)化模型，并運用模擬退火算法進行求解；張佳佳[9]等研究了裝卸點可充電模式下的電動汽車冷鏈配送路徑優(yōu)化問題，以配送總成本為優(yōu)化目標，使用粒子群算法進行求解，研究結(jié)果表明這種邊充電邊卸載的方式有效的降低了在配送過程中由于充電而帶來的成本增加問題。

現(xiàn)階段，學者們對車輛路徑問題的研究主要集中在模型建立和求解算法兩方面，在模型建立方面，主要是從優(yōu)化目標和約束條件等對模型進行改進；李思國，郭宇等[10]針對離散制造車間環(huán)境復雜、外部干擾因素眾多的情況，提出了基于改進遺傳算法的物料配送路徑實時規(guī)劃方法，建立了車間實時環(huán)境下的物料配送模型，并使用融合TSA和GA對模型進行求解；嚴正峰[11]等為解決實際生產(chǎn)過程中工位物料需求時間不確定的問題，提出了基于模糊軟時間窗的復雜機械裝配車間配送路徑優(yōu)化方法，并建立了帶模糊軟時間窗的物料配送路徑優(yōu)化模型，采用動態(tài)規(guī)劃算法和模擬退火算法相結(jié)合的混合算法對模型進行求解；在算法求解方面，主要從對智能算法的應用及改進入手，如Ferani E.Zulvia，R.J[12]等針對易腐產(chǎn)品的運輸成本高、空氣污染嚴重等問題，提出了一個可優(yōu)化易腐產(chǎn)品運輸成本、變質(zhì)成本、碳排放的綠色車輛路徑問題，并使用多目標梯度進化算法（MOGE）進行求解；Asma M.Altabeeb，Abdulqader[13]等針對電容車輛路徑問題，提出了一種新的混合型車輛路徑規(guī)劃算法，即CVRP-FA算法，該算法結(jié)合了兩種局部搜索算子和遺傳算子，提高了求解質(zhì)量，加快了收斂速度，并通過在82個基準測試實例上測試，結(jié)果表明該算法具有較快的收斂速度和計算精度；Zhong X[14]等在研究了物流配送中的兩階段車輛路徑問題（2E-VRP）之后，運用人工蜂群和遺傳算法相結(jié)合的混合算法（ABCGA）進行求解，試驗結(jié)果表明ABCGA 算法具有效果穩(wěn)定、效率高等優(yōu)點。

結(jié)合以上文獻的研究內(nèi)容，以及對現(xiàn)有車間物料配送路徑優(yōu)化問題分析后，發(fā)現(xiàn)在部分車間內(nèi)部存在著由于配送小車不能在各工位規(guī)定的時間窗內(nèi)將所需物料送達，導致時間懲罰成本較高，工位服務滿意度較低；不合理的路線規(guī)劃，使得配送過程中小車使用數(shù)量增多，配送距離增大，配送成本增加等問題。因此，本文在考慮各工位生產(chǎn)物料需求的基礎上，建立了多目標車間物料配送路徑優(yōu)化模型，蟻群算法是一種正反饋群智能優(yōu)化算法，且具有并行性、強魯棒性、適應性、易與其他算法相結(jié)合等優(yōu)勢，但其收斂速度較慢，容易陷入局部最優(yōu)，因此本文分別使用基本蟻群算法和改進的蟻群算法對模型進行求解，并將其所得結(jié)果進行對比，結(jié)果顯示改進的蟻群算法可以減少配送小車使用數(shù)量及配送成本、提高工位服務滿意度并縮短配送距離。

1 問題描述與符號說明

1.1 研究問題

在傳統(tǒng)車間物料配送路徑優(yōu)化問題中，優(yōu)化目標常常為配送距離最短、所用時間最少或者配送成本最低，往往忽略了配送過程中配送小車的服務質(zhì)量或各工位的服務滿意度，即配送小車是否能夠在工位要求的配送時間窗內(nèi)將所需物料按時送達，避免出現(xiàn)因物料配送不及時而導致的工位停工停產(chǎn)現(xiàn)象發(fā)生。隨著科技的發(fā)展與進步，在日益激烈的社會環(huán)境下，提高“服務質(zhì)量”或“服務水平”等標語在各大車間內(nèi)隨處可見，顯然其已經(jīng)成為了企業(yè)提高自身競爭能力、生產(chǎn)效率以及服務質(zhì)量的重要因素之一，但是在離散制造車間的生產(chǎn)物料配送過程中，各種不確定因素會導致工位生產(chǎn)節(jié)拍發(fā)生波動，致使各工位的物料需求時間也隨之發(fā)生變化，各配送小車對工位的服務質(zhì)量千差萬別，進而導致各工位對不同時間內(nèi)物料配送活動的服務滿意度不盡相同，因此本文將工位服務滿意度作為優(yōu)化目標之一，并用懲罰代價最小來描述工位服務滿意度最高，結(jié)合配送路徑最短、配送小車使用數(shù)量最少，構(gòu)成多目標車間物料配送路徑優(yōu)化模型，分別使用基本蟻群算法和改進的蟻群算法對模型進行求解，將結(jié)果進行對比，從而體現(xiàn)出改進后算法對該問題求解的有效性。時間窗懲罰示意圖如圖1所示。

圖1 時間窗懲罰示意圖

文中的工位服務滿意度可表示為：

某離散制造車間內(nèi)有K輛容量為Q的配送小車，現(xiàn)需要對N個待配送工位進行物料配送任務，各工位位置和所需物料數(shù)量等均為已知，則考慮工位服務滿意度的車間物料配送任務為各配送小車將車間配送中心的物料在各工位需求的時間窗內(nèi)配送至各工位，在配送過程中，配送小車按照規(guī)劃的路線進行配送，并根據(jù)各工位時間窗跨度大小調(diào)整配送工位的服務順序，保證優(yōu)先服務物料需求緊急程度較高的工位，從而提高配送車間物料的配送效率，確保整個配送過程中使用小車數(shù)最少、配送路徑最短以及工位服務滿意度最高。當配送小車將工位所需物料送達至工位且返回原配送中心時，表示該配送任務結(jié)束。為了便于研究，該任務需要滿足以下約束條件。

1）運載能力約束。每個工位i的物料需求量qi均已知，每條配送路徑上各工位的物料需求量之和不能超過配送小車的最大載重量Q。

2）配送小車約束。配送小車的停止、啟動、裝卸料時間及小車故障等因素均忽略不計；所有配送小車從配送倉庫出發(fā)，完成任務后返回配送中心；一輛配送小車可以同時服務多個工位，但每個工位只能由一輛配送小車進行物料配送活動；在整個配送過程中，配送小車的行駛速度已知且恒定。

3）配送中心約束。車間內(nèi)僅有一個物料配送中心，且配送中心位置已知，物料充足，能夠滿足所有工位的物料需求。

4）時間窗約束。如圖1所示，對于每個工位i，配送小車必須在內(nèi)進行服務，若配送小車到達時間早于ei，則必須在工位處等待，若配送小車到達時間晚于li，則服務必須被延遲。

1.2 符號與決策變量

由于本文符號和變量較多，為方便分析，在此將各符號按表1進行解釋說明。

表1 符號說明

2 數(shù)學模型

在上述多目標優(yōu)化模型中，i，j=0表示配送小車的起始點和終止點，dij表示工位i到工位j之間的距離，式(2)表示配送小車行駛的距離最小，式(3)表示工位服務滿意度最大，即懲罰代價最小，式(4)表示所用配送小車的數(shù)量最少，式(5)表示每輛配送小車配送的物料需求量不能超過小車的最大載重量，式(6)表示每個工位只能由一輛配送小車進行配送，式(7)表示配送小車從配送倉庫出發(fā)，最終返回配送倉庫，式(8)表示消除支路，式(9)表示到達和離開配送工位為同一配送小車，式(10)、式(11)為決策變量。

上述所建模型屬于多目標優(yōu)化模型，為便于求解，本文結(jié)合單位配送成本ck、單位等待懲罰成本ce、單位延遲懲罰成本c1以及配送小車固定啟動成本ca，將其轉(zhuǎn)化為單目標優(yōu)化模型，即求配送小車在配送過程中的總成本，處理后的目標函數(shù)為：

3 改進蟻群算法設計

本文所研究的車間物料配送路徑優(yōu)化問題屬于NPhard問題，隨著社會的發(fā)展和算法的演變，目前對該類問題的求解研究較多的是啟發(fā)式算法[15～17]，比如：遺傳算法（GA）、禁忌搜索算法（TSA）、模擬退火算法（SA）等，在眾多啟發(fā)式算法中，蟻群算法憑借其具有采用分布式并行計算機制，有自組織、正反饋與較強的魯棒性，可以使問題在較短的時間內(nèi)得到較為滿意的可行解，且易于其他啟發(fā)式算法相融合的優(yōu)勢，深受大多數(shù)學者喜愛，但其也存在因搜索時間較長而導致收斂速度較慢，易陷入局部最優(yōu)的缺陷。因此本文對基本蟻群算法進行改進，主要分為三部分：1）通過在基本蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則上加入 “時間窗跨度”因素，調(diào)整待配送工位的服務順序，對物料需求緊急程度較高的工位優(yōu)先配送，從而提高配送小車服務質(zhì)量，提升工位服務滿意度；2）得到當次迭代最優(yōu)解時，使用2-opt局部鄰域搜索算法，對最優(yōu)解進行交叉操作，并對交叉后的結(jié)果進行比較，從而得出全局最優(yōu)解，幫助其跳出局部最優(yōu)；3）采用自適應信息素更新策略，對信息素揮發(fā)因子做分段取值處理，使其在各階段能動態(tài)調(diào)整信息素更新，以此來提高算法的全局搜索能力，加快收斂速度。

3.1 轉(zhuǎn)移規(guī)則設計

在基本蟻群算法的轉(zhuǎn)移規(guī)則中，狀態(tài)轉(zhuǎn)移概率僅與信息素濃度和可見度有關(guān)，本文為了使配送小車可優(yōu)先服務物料需求緊急程度較高的工位，加入了“時間窗跨度”因素，即優(yōu)先配送時間窗跨度值較小的工位，從而提高工位服務滿意度。具體描述如下：

令工位i的時間窗跨度為with=li-ei，當兩個待配送工位i1、i2均未被訪問過時，比較這兩個工位的時間窗跨度值，若i1的跨度值比i2低，說明工位i1的物料需求緊急程度高于工位i2，即兩工位相比，i1更具有配送任務緊迫性，故在配送過程中應優(yōu)先服務工位i1。因此設是螞蟻k從工位i轉(zhuǎn)移到工位j的狀態(tài)轉(zhuǎn)移概率，則轉(zhuǎn)移規(guī)則如式(13)所示：

在式(13)中，τij為信息素濃度，ηij為可見度，且ηij=1/dij，α為信息素重要因子，表示軌跡的相對重要性，反應了螞蟻在運動過程中所積累的信息在螞蟻運動時所起的作用，β為啟發(fā)函數(shù)重要因子，表示能見度的相對重要性，反映了螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑的受重視程度，γ為時間窗跨度重要因子，表示待配送工位的服務順序，反映了當工位物料需求緊急程度較高時執(zhí)行該任務的緊迫程度，且γ為在[0，1]上的服從均勻分布的隨機變量，γ0(0≤γ0≤1)為用來控制轉(zhuǎn)移規(guī)則的參數(shù)，本文取γ0=0.5；為配送小車k從i點出發(fā)可以訪問的所有工位點j的集合，其中工位點j表示未被服務過且均滿足容量約束和時間窗約束。令一只螞蟻從車間配送中心出發(fā)，按照式(13)的轉(zhuǎn)移規(guī)則計算狀態(tài)轉(zhuǎn)移概率，并使用輪盤賭法依次選擇下個待訪問工位點j，若找不到滿足要求的工位j，則該螞蟻返回配送中心，繼續(xù)派遣另一只螞蟻按上述步驟依次進行，直到所有待配送工位點全部被訪問完成為止。

3.2 自適應信息素更新策略

對蟻群算法而言，螞蟻在搜索路徑的過程中分為兩個階段，即全局搜索階段和收斂階段，并且在整個路徑搜索過程中，信息素揮發(fā)因子的取值將直接關(guān)系到蟻群算法的全局搜索能力和收斂速度，若的取值過大，則螞蟻選擇已經(jīng)搜索過的路徑可能性較大，很容易出現(xiàn)局部收斂；若的取值過小，會影響算法的收斂速度，因此，本文采取自適應信息素更新策略，即隨著算法迭代次數(shù)的增加，將算法分為初期、中期和后期，信息素揮發(fā)因子按照每個時期的設定值進行動態(tài)調(diào)整。初期的取值較大，加強信息素濃度，以此增強算法的全局搜索能力，而在中期和后期，的取值較小，進而降低信息素對蟻群的影響，以便較快的收斂到最優(yōu)解，具體取值規(guī)則如式(14)所示：

為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，當所有螞蟻完成一次循環(huán)后，需要對殘留信息素進行更新，由此，t+1時刻在路徑(i，j)上的信息量可按式(15)進行調(diào)整：

在式(15)和式(16)中，ρ為信息素揮發(fā)因子，(1-ρ)表示信息素殘留因子，為了防止信息素無止境增加，在基本蟻群算法中，ρ的取值范圍是(0，1)；Δτij(t)表示本次循環(huán)中路徑(i，j)上的信息素增量，在初始時刻，表示第k只螞蟻在本次循環(huán)中留在路徑(i，j)上的信息量。

在式(17)中，Q為常數(shù)，表示每只螞蟻所釋放的信息素總和，Lk表示第K只螞蟻在本次循環(huán)中所走路徑的總長度。

3.3 2-opt局部優(yōu)化

2-opt屬于局部搜索算法，其基本思想是“交換”，即將一條路徑轉(zhuǎn)化為另一條路徑，只要操作能降低當前路徑的長度和成本，算法則會在給定集合內(nèi)反復進行操作，直到任何操作都不能繼續(xù)更新為止，即產(chǎn)生了一條局部最優(yōu)路徑[18]。其基本原理是：用(i，j)，(i+1，j+1)來替換(i，i+1)，(j，j+1)經(jīng)過變換之后線路中的路徑(i+1，...，j)被進行反向處理，即滿足以下條件時：

變換后的路徑如圖2所示。

圖2 2-opt交換示意圖

蟻群算法每次迭代后，大部分螞蟻搜索的結(jié)果對當前最優(yōu)解并沒有貢獻，若對這些沒有貢獻的路徑使用2-opt，會消耗大量的運行時間，針對該問題，本文采取的方法是當所有螞蟻完成遍歷后得到單次最優(yōu)解時，使用2-opt局部搜索算法進行二次優(yōu)化，對最優(yōu)解進行交叉操作，從而擴大解的搜索空間，改善種群信息結(jié)構(gòu)，幫助算法大概率的跳出局部最優(yōu)解，提高算法的搜索能力。

改進后的蟻群算法步驟如下：

1）初始化dij、NC_max、n、m、α、β、γ等參數(shù)。

2）將m只螞蟻全部放置到車間配送中心，創(chuàng)建并初始化禁忌表tabuk，按照式(14)設置ρ的值。

3）在滿足配送小車裝載量限制以及工位配送時間窗約束的前提下，每只螞蟻按照式(13)計算狀態(tài)轉(zhuǎn)移概率，根據(jù)輪盤賭選擇策略選擇下一個待訪問工位點j′，并判斷配送小車是否滿足約束，并將其路徑添加至禁忌表tabuk中。

4）修改禁忌表tabuk，直到所有螞蟻遍歷完所有工位點并返回配送中心，且禁忌表更新滿足時間窗約束和載重約束。

5）對當次迭代的最優(yōu)解按式(18)采用2-opt算法進行局部優(yōu)化，得出優(yōu)化后的成本f(t)和f(t+1)。

6）比較f(t)和f(t+1)的大小，若f(t)?f(t+1)，則返回f(t)，否則返回f(t+1)，直到t達到最大設定值時，更新全局信息素，否則返回循環(huán)，t=t+1。

7）判斷是否滿足結(jié)束條件(N c ＞N c_m a x？)若Nc≤Nc_max，則Nc=Nc+1，并轉(zhuǎn)至步驟2)，若Nc＞Nc_max，則完成迭代，輸出最終結(jié)果。

改進后蟻群算法流程圖如圖3所示

圖3 改進后蟻群算法流程圖

4 實例驗證

為了驗證改進后蟻群算法的可行性，假設某離散制造車間有1個物料配送中心、14個待配送工位，以及多輛配送小車，小車最大載荷量為Q=50kg，行駛速度為S=50m/min，本文采用軟時間窗，配送小車早到的單位等待成本為ce=5元/h，晚到的單位延遲成本為cl=10元/h，單位行駛費用為ck=5元/m，固定啟動成本為ca=50元/輛，分別用基本蟻群算法和改進后的蟻群算法對問題進行求解。在Windows10環(huán)境下，運用MATLABR2018b語言進行編程，蟻群算法相關(guān)參數(shù)如表2所示，各工位配送任務表如表3所示，工位與配送中心以及工位間的距離如表4所示。

表2 蟻群算法參數(shù)

表3 各工位配送任務表

表4 工位與配送中心間以及工位間的距離

本文分別使用基本蟻群算法及改進的蟻群算法在MATLAB2018b上進行求解，且設定螞蟻初始數(shù)量為m=50，最大迭代次數(shù)為NC_max100，信息素重要因子α=1，啟發(fā)函數(shù)重要因子為β=3時，時間窗跨度重要因子γ=2，基本蟻群算法中信息素揮發(fā)因子ρ=0.4；改進后最大信息素揮發(fā)因子為ρmax=0.85，最小為ρmin=0.15，且全局信息素常量為Q=5，當兩種算法在迭代100次后，小車配送路徑圖如圖4、圖5所示，不同顏色的路線代表不同配送小車的配送路徑。當使用基本蟻群算法對問題進行求解，得出整個配送過程需要5輛配送小車進行配送，配送路徑圖如圖4所示，具體配送路線為：小車1：0-1-6-3-0；小車2：0-12-10-5-0；小車3：0-11-0；小車4：0-2-14-9-0；小車5：0-13-7-4-8-0；

圖4 基本蟻群算法-小車配送路徑圖

圖5 改進的蟻群算法-小車配送路徑圖

當使用改進后的蟻群算法對問題進行求解，得出整個配送過程只需要4輛配送小車，配送路徑圖如圖5所示，且改進后配送小車的具體配送路線為：小車1：0-1-6-3-0；小車2：0-5-10-7-4-11-0；小車3：0-13-12-8-0；小車4：0-2-14-9-0；

圖6為基本蟻群算法和改進后蟻群算法求解出的最優(yōu)路徑長度收斂趨勢圖，從圖6可以明顯的看出改進后的蟻群算法求解的結(jié)果比基本蟻群算法更優(yōu)，且收斂速度更快，具體仿真結(jié)果如表5所示。

圖6 最短路徑收斂對比圖

表5 最短路徑長度仿真結(jié)果

圖7為基本蟻群算法和改進后蟻群算法求解出的最優(yōu)成本收斂趨勢圖，具體仿真結(jié)果如表6所示。

圖7 最優(yōu)成本收斂對比圖

表6 最優(yōu)成本仿真結(jié)果

蟻群算法和改進后蟻群算法求出的結(jié)果對比如表7所示。

表7 兩種算法結(jié)果對比

正如表7所示，改進前配送小車的最短距離為440m，即運輸成本為2200元；配送工位的服務滿意度成本為372.5元；配送過程需要5輛配送小車，即小車的固定啟動成本為250元，總成本為2822.5元。改進后配送小車的最短距離為360m，即運輸成本為1800元；配送工位的服務滿意度成本為322.5元；配送過程需要4輛配送小車，即小車的固定啟動成本為200元，總成本為2322.5元。將兩種算法的求解結(jié)果對比得出：最短距離減少了18.2%；工位服務滿意度提高了13.4%；小車數(shù)量減少了1輛；總成本降低了17.8%，以上數(shù)據(jù)驗證了改進后蟻群算法對求解本文所研究問題的有效性。

5 結(jié)語

針對離散制造車間的物料配送路徑優(yōu)化問題，多數(shù)均單純從配送的經(jīng)濟性角度進行考慮，即以最低的總成本滿足所有工位的需求，往往忽略了配送小車的服務質(zhì)量或配送工位的服務滿意度，而在當前激烈的市場競爭中，滿意度已經(jīng)成為了車間物料配送路徑優(yōu)化問題不得不考慮的重要因素之一，因此本文建立了考慮工位服務滿意度的車間物料配送路徑優(yōu)化模型，并分別使用基本蟻群算法和改進蟻群算法對該模型進行求解，最后通過在MATLAB上對實例進行仿真，發(fā)現(xiàn)改進后的蟻群算法與基本蟻群算法相比，在解決配送距離、工位服務滿意度以及小車使用數(shù)等三方面都有一定程度的提升和降低，進一步驗證了該模型和算法的合理性和普適性。