考慮工位服務(wù)滿意度的物料配送路徑優(yōu)化研究

張守京，段 嬌，童傅嬌

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

0 引言

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

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

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

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

1 問題描述與符號(hào)說明

1.1 研究問題

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

圖1 時(shí)間窗懲罰示意圖

文中的工位服務(wù)滿意度可表示為：

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

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

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

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

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

1.2 符號(hào)與決策變量

由于本文符號(hào)和變量較多，為方便分析，在此將各符號(hào)按表1進(jìn)行解釋說明。

表1 符號(hào)說明

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

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

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

3 改進(jìn)蟻群算法設(shè)計(jì)

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

3.1 轉(zhuǎn)移規(guī)則設(shè)計(jì)

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

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

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

3.2 自適應(yīng)信息素更新策略

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

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

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

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

3.3 2-opt局部?jī)?yōu)化

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

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

圖2 2-opt交換示意圖

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

改進(jìn)后的蟻群算法步驟如下：

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

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

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

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

5）對(duì)當(dāng)次迭代的最優(yōu)解按式(18)采用2-opt算法進(jìn)行局部?jī)?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達(dá)到最大設(shè)定值時(shí)，更新全局信息素，否則返回循環(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é)果。

改進(jìn)后蟻群算法流程圖如圖3所示

圖3 改進(jìn)后蟻群算法流程圖

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

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

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

表3 各工位配送任務(wù)表

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

本文分別使用基本蟻群算法及改進(jìn)的蟻群算法在MATLAB2018b上進(jìn)行求解，且設(shè)定螞蟻初始數(shù)量為m=50，最大迭代次數(shù)為NC_max100，信息素重要因子α=1，啟發(fā)函數(shù)重要因子為β=3時(shí)，時(shí)間窗跨度重要因子γ=2，基本蟻群算法中信息素?fù)]發(fā)因子ρ=0.4；改進(jìn)后最大信息素?fù)]發(fā)因子為ρmax=0.85，最小為ρmin=0.15，且全局信息素常量為Q=5，當(dāng)兩種算法在迭代100次后，小車配送路徑圖如圖4、圖5所示，不同顏色的路線代表不同配送小車的配送路徑。當(dāng)使用基本蟻群算法對(duì)問題進(jìn)行求解，得出整個(gè)配送過程需要5輛配送小車進(jìn)行配送，配送路徑圖如圖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 改進(jìn)的蟻群算法-小車配送路徑圖

當(dāng)使用改進(jìn)后的蟻群算法對(duì)問題進(jìn)行求解，得出整個(gè)配送過程只需要4輛配送小車，配送路徑圖如圖5所示，且改進(jìn)后配送小車的具體配送路線為：小車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為基本蟻群算法和改進(jìn)后蟻群算法求解出的最優(yōu)路徑長(zhǎng)度收斂趨勢(shì)圖，從圖6可以明顯的看出改進(jìn)后的蟻群算法求解的結(jié)果比基本蟻群算法更優(yōu)，且收斂速度更快，具體仿真結(jié)果如表5所示。

圖6 最短路徑收斂對(duì)比圖

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

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

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

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

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

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

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

5 結(jié)語

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