考慮工位服務滿意度的物料配送路徑優化研究

張守京，段 嬌，童傅嬌

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

0 引言

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

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

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

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

1 問題描述與符號說明

1.1 研究問題

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

圖1 時間窗懲罰示意圖

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

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

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

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

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

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

1.2 符號與決策變量

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

表1 符號說明

2 數學模型

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

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

3 改進蟻群算法設計

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

3.1 轉移規則設計

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

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

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

3.2 自適應信息素更新策略

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

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

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

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

3.3 2-opt局部優化

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

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

圖2 2-opt交換示意圖

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

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

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

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

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

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

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

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

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

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

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

4 實例驗證

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

表2 蟻群算法參數

表3 各工位配送任務表

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

本文分別使用基本蟻群算法及改進的蟻群算法在MATLAB2018b上進行求解，且設定螞蟻初始數量為m=50，最大迭代次數為NC_max100，信息素重要因子α=1，啟發函數重要因子為β=3時，時間窗跨度重要因子γ=2，基本蟻群算法中信息素揮發因子ρ=0.4；改進后最大信息素揮發因子為ρ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為基本蟻群算法和改進后蟻群算法求解出的最優路徑長度收斂趨勢圖，從圖6可以明顯的看出改進后的蟻群算法求解的結果比基本蟻群算法更優，且收斂速度更快，具體仿真結果如表5所示。

圖6 最短路徑收斂對比圖

表5 最短路徑長度仿真結果

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

圖7 最優成本收斂對比圖

表6 最優成本仿真結果

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

表7 兩種算法結果對比

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

5 結語

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