基于改進(jìn)ALNS 算法的離散制造車間物料配送路徑優(yōu)化研究

何家錚，王家海

（同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804）

0 引言

在離散制造領(lǐng)域，為了滿足個(gè)性化和快速響應(yīng)市場的需求，多品種、小批量的生產(chǎn)模式變得越來越普遍。這種生產(chǎn)模式的靈活性雖然能夠滿足市場多變的需求，但同時(shí)也大幅增加了車間內(nèi)物料配送的難度和復(fù)雜性。物料配送的效率和準(zhǔn)確性直接影響到整個(gè)生產(chǎn)流程的順暢和成本控制[1]，如何在保證物料按時(shí)供應(yīng)的同時(shí)，減少配送時(shí)間和成本，如何優(yōu)化配送路徑以適應(yīng)車間內(nèi)復(fù)雜多變的布局和需求，都是亟待解決的問題。

在這樣的背景下，研究和開發(fā)高效的物料配送路徑優(yōu)化算法變得尤為重要。車輛路徑規(guī)劃問題（VRP）被學(xué)者廣泛研究，例如唐等[2]利用蟻群算法求解，也有部分學(xué)者探索了柔性制造車間的物料配送問題[3]，但通常未能精確結(jié)合車間實(shí)際情況，采用歐式距離作為節(jié)點(diǎn)距離，本文考慮車間通道約束、時(shí)間窗、小車容量、線邊庫容量等因素，通過引入和改進(jìn)自適應(yīng)大領(lǐng)域搜索（ALNS）算法解決求解離散制造車間物料配送的路徑優(yōu)化問題。

1 數(shù)學(xué)模型建立

1.1 問題描述

一個(gè)離散型制造車間，車間內(nèi)有一個(gè)中心倉庫和N 個(gè)物料需求工位點(diǎn)，由配送能力為Q 的AGV 執(zhí)行物料配送作業(yè)，每個(gè)由物料需求的工位對物料存在時(shí)間窗要求[ETi，LTi]，找到最佳的運(yùn)輸車輛數(shù)以及最佳的運(yùn)輸路線。

基本假設(shè)如下：

（1）車輛從車間倉庫裝貨后出發(fā)，經(jīng)過各車間工位后最終返回車間倉庫。

（2）單個(gè)工位的物料需求量不超過AGV 的運(yùn)輸載荷。

（3）一次配送任務(wù)中，單個(gè)工位的物料由同一輛AGV 小車完成配送，若配送完畢后有新的物料需求，增加新的配送任務(wù)由其他AGV 進(jìn)行配送。

（5）物料需求點(diǎn)時(shí)間窗為軟時(shí)間窗，且AGV 允許部分超載。

1.2 符號說明

在詳細(xì)闡述具體的模型建立和求解過程之前，對模型中涉及的關(guān)鍵符號及變量進(jìn)行詳細(xì)定義，以確保理論推導(dǎo)的嚴(yán)密性和結(jié)果解讀的一致性，相關(guān)符號變量見表1。

表1 數(shù)學(xué)模型符號說明

1.3 工位物料時(shí)間窗模型

針對晚于LTi到達(dá)的情況，該工位生產(chǎn)停滯，長時(shí)間后會(huì)影響相應(yīng)工序的其他工位生產(chǎn)，對生產(chǎn)系統(tǒng)整體影響較大。針對早于ETi到達(dá)的情況，AGV 送抵的物料會(huì)超出線邊庫的最大庫存，因此需等待線邊庫有足夠庫位后進(jìn)行服務(wù)。即當(dāng)ATi＜LTi時(shí)，令A(yù)Ti=ETi，同時(shí)由于等待會(huì)產(chǎn)生等待懲罰。

1.4 車間通道約束下的距離模型

如圖1 左所示，在傳統(tǒng)車輛路徑問題（VRP）中，節(jié)點(diǎn)間距離通常通過歐氏距離計(jì)算。適用于直線可達(dá)的場景。在車間環(huán)境中，由于路線限制和復(fù)雜布局，工位間不能直接以直線方式行駛，必須沿固定路徑，如圖1 右所示。采用像Floyd 算法這樣的圖論方法來計(jì)算最短路徑以及尋找其路由[4]，比直線距離更能反映車間內(nèi)的實(shí)際行駛條件，為車間VRP 問題提供更準(zhǔn)確的解決方案。

圖1 傳統(tǒng)VRP 路徑與車間通道約束下的路徑圖

1.5 物料配送成本模型

式（4）是以配送成本最小為目標(biāo)函數(shù)，包括路徑成本、超載懲罰和時(shí)間窗懲罰，每輛小車r成本的具體計(jì)算方式為：遍歷小車（路徑）r下的k個(gè)路徑節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)k至節(jié)點(diǎn)k+1 的路徑距離并累加，計(jì)算該路徑下k個(gè)節(jié)點(diǎn)的需求量之和小車載重之差并附加超載懲罰系數(shù)，以及通過式（3）計(jì)算時(shí)間窗懲罰；式（5）確保配送順序合理，同一條線路中當(dāng)前節(jié)點(diǎn)小車的到達(dá)時(shí)間需大于等于上一個(gè)節(jié)點(diǎn)的到達(dá)時(shí)間、上一個(gè)節(jié)點(diǎn)的服務(wù)時(shí)間、兩點(diǎn)之間移動(dòng)時(shí)間之和；式（6）表示除了倉庫節(jié)點(diǎn)0和i的集合完全相等，即每個(gè)工位一次只能由一輛配送小車配送，且只能被一輛AGV 配送一次；式（7）表示每輛AGV 的起點(diǎn)和終點(diǎn)都是車間倉庫。

再者，這里是具有造船傳統(tǒng)的女真人聚居區(qū)。遠(yuǎn)的不說，女真人的先世挹婁人就能造船，元代的女真人已能建造遠(yuǎn)征日本的大型戰(zhàn)船。選擇在這里造“巨舡”，不缺人才和技術(shù)，能夠迅速完成造船任務(wù)。據(jù)此，明廷把船廠設(shè)在今吉林市阿什哈達(dá)村。

2 模型求解

基于車間布局、工位和拐點(diǎn)的位置，建立初始距離矩陣，并利用Floyd 算法求解通道約束下的最短距離矩陣，并基于此矩陣?yán)酶倪M(jìn)的ALNS 方法進(jìn)行車間物料配送路徑規(guī)劃問題的求解，如圖2 所示。

圖2 模型求解流程圖

2.1 Floyd 算法預(yù)處理

初始化，根據(jù)車間布局，基于圖論，將同一通道上相鄰的工位節(jié)點(diǎn)或車間拐點(diǎn)認(rèn)定為“聯(lián)通”，并設(shè)置最短距離為實(shí)際直線距離，對于不同通道上的節(jié)點(diǎn)，需要經(jīng)過車間通道拐點(diǎn)到達(dá)，因此距離初始為無窮大，得到一個(gè)包含車間拐點(diǎn)的（N+t）×（N+t）初始距離矩陣A0。

迭代更新，對于不直接連通的節(jié)點(diǎn)對，利用式（8）找到通過一個(gè)或多個(gè)中間節(jié)點(diǎn)的最短路徑，從而更新這些節(jié)點(diǎn)對之間的最短距離，每次迭代更新距離矩陣Ant。

當(dāng)?shù)螖?shù)nt=N+t時(shí)，迭代終止，移除車間拐點(diǎn)即得到N×N的基于車間路徑約束的實(shí)際節(jié)點(diǎn)距離矩陣A′。Floyd 算法的時(shí)間復(fù)雜度是O（n3），空間復(fù)雜度是O（n2），其中，節(jié)點(diǎn)距離矩陣A′是后續(xù)物料配送的必要環(huán)節(jié)，其僅需要在車間布局變化時(shí)重新運(yùn)算，否則只需運(yùn)算一次。

2.2 ALNS 算法求解車間物料配送的VRPTW 問題

自適應(yīng)大領(lǐng)域搜索算法（ALNS），是一種用于求解復(fù)雜優(yōu)化問題的啟發(fā)式算法[5]。它通過不斷地摧毀和修復(fù)當(dāng)前解的一部分來探索解空間，可以根據(jù)歷史表現(xiàn)適應(yīng)性的調(diào)整摧毀和修復(fù)的使用頻率。

改進(jìn)的ALNS 算法采用外層模擬退火，內(nèi)層ALNS 的方式減少陷入局部最優(yōu)的概率。ALNS 的每次迭代后進(jìn)行成本比較，若新解是最優(yōu)解則接受，否則以采用Metropolis 準(zhǔn)則的方式接受相對劣解。

2.2.1 生成初始解

初始解編碼示例如圖3 所示。打亂節(jié)點(diǎn)數(shù)組I，依次分配給小車，當(dāng)∑Di＞Q時(shí)，新增一輛小車，直至所有節(jié)點(diǎn)分配完畢。

圖3 初始解編碼示例

2.2.2 破壞和修復(fù)算子

本研究共采用3 個(gè)破壞算子和3 個(gè)修復(fù)算子，根據(jù)算子權(quán)重選擇破壞算子和修復(fù)算子。如圖4 所示，第一步：破壞，遍歷當(dāng)前解中的所有路徑的節(jié)點(diǎn)，依據(jù)不同破壞規(guī)則從節(jié)點(diǎn)數(shù)組中選取一定數(shù)量的節(jié)點(diǎn)進(jìn)行破壞移除，并加入移除節(jié)點(diǎn)列表；第二步：修復(fù)，根據(jù)不同的修復(fù)規(guī)則，將移除節(jié)點(diǎn)列表中插入被破壞的節(jié)點(diǎn)列表中。

圖4 破壞和修復(fù)

（1）相關(guān)性破壞算子，也稱Shaw 移除算子，目的是通過破壞相似或相關(guān)的節(jié)點(diǎn)來探索解空間的不同區(qū)域，本文基于節(jié)點(diǎn)的距離、時(shí)間窗和物料需求的相關(guān)性進(jìn)行移除，節(jié)點(diǎn)與的相關(guān)性表達(dá)式為：其中，ω1、ω2、ω3表示的是距離、時(shí)間窗和物料需求的權(quán)重系數(shù)，R（i，j）越大表示節(jié)點(diǎn)的相關(guān)性越小。

（2）貪心破壞算子，一次移除一個(gè)節(jié)點(diǎn)，選擇移除后成本降低最多的節(jié)點(diǎn)。每次移除節(jié)點(diǎn)前，計(jì)算當(dāng)前總成本，并與移除每個(gè)可能節(jié)點(diǎn)后的新成本進(jìn)行比較。選擇使總成本降低最多的節(jié)點(diǎn)進(jìn)行移除。

（3）隨機(jī)破壞算子，隨機(jī)選取一定數(shù)量的節(jié)點(diǎn)，并將這些節(jié)點(diǎn)從其所在的路線中刪除。

（4）后悔插入算子，評估每個(gè)被移除節(jié)點(diǎn)插入任何位置的“后悔值”，選擇當(dāng)前具有最大后悔值的節(jié)點(diǎn)進(jìn)行插入，目的是避免過早做出可能限制未來選擇的決策，不僅考慮當(dāng)前的最佳插入位置，還考慮對未來選擇的潛在影響。

其中，Va是某節(jié)點(diǎn)插入后的成本，Vb是某節(jié)點(diǎn)插入前的成本，VI是插入成本，min2VI表示次佳插入成本，minVI表示最佳插入成本，最大后悔值VR是次佳插入成本min2V和最佳插入成本minVI之差。

（5）貪心修復(fù)算子，對于每個(gè)被移除的節(jié)點(diǎn)，考慮所有可能的插入位置，并選擇使總成本增加最少的位置進(jìn)行插入。

（6）隨機(jī)修復(fù)算子，將之前被破壞的節(jié)點(diǎn)隨機(jī)插入回路線中。對于每個(gè)被移除的節(jié)點(diǎn)，隨機(jī)選擇一條路線和該路線上的位置，并將節(jié)點(diǎn)插入到該位置。

3 實(shí)驗(yàn)分析

以某離散制造車間為案例，并使用改進(jìn)的ALNS算法進(jìn)行求解。該車間有1 個(gè)車間倉庫、6 臺數(shù)控車床、3 臺數(shù)控銑床、1 臺數(shù)控鏜床、4 臺鉆床、3 個(gè)檢測臺，總計(jì)1 個(gè)車場和17 個(gè)需求節(jié)點(diǎn)，另有路徑拐點(diǎn)10 個(gè)，如圖5 所示。

圖5 離散制造車間模型

車間工位位置、需求和時(shí)間窗等信息和拐點(diǎn)位置信息見表2，其中節(jié)點(diǎn)0 表示車間倉庫，t1 -t10 為車間拐點(diǎn)。首先，利用節(jié)點(diǎn)坐標(biāo)、拐點(diǎn)坐標(biāo)和車間路徑圖，根據(jù)之間聯(lián)通的節(jié)點(diǎn)（拐點(diǎn)）建立初始距離矩陣，并使用Floyd 算法得出個(gè)節(jié)點(diǎn)之間的最短距離矩陣，見表3。

表2 節(jié)點(diǎn)需求信息

表3 節(jié)點(diǎn)最短路徑矩陣

本實(shí)驗(yàn)使用IDEA2021，CPU 為12600 k，利用ALNS 算法結(jié)合模擬退火，實(shí)驗(yàn)部分參數(shù)設(shè)置為：溫度下降率0.99，最大迭代次數(shù)400，超載懲罰系數(shù)γ=1000，時(shí)間窗提前懲罰系數(shù)α=10，時(shí)間窗超期懲罰系數(shù)β=2，可提供的最大運(yùn)力車輛為3，破壞算子和修復(fù)算子初始權(quán)重相等。

從表4 和圖6 可知，在相同迭代次數(shù)下，ALNS 加入模擬退火后，求解時(shí)間略高于ALNS，但總體速度接近，可以滿足車間物料配送的決策實(shí)時(shí)性，在求解時(shí)間接近的情況下跳出局部最優(yōu)，獲得成本更低的解。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效規(guī)劃物料配送路徑，減少配送時(shí)間和成本，并確保物料按時(shí)供應(yīng)，提高了生產(chǎn)效率。

圖6 收斂曲線對比

表4 基于車間路徑約束的配送路徑序列

4 結(jié)語

本研究通過構(gòu)建離散制造車間物料配送路徑優(yōu)化的數(shù)學(xué)模型，并基于自適應(yīng)大領(lǐng)域搜索（ALNS）算法進(jìn)行了求解，有效地解決了多品種、小批量生產(chǎn)模式下的物料配送問題。實(shí)驗(yàn)結(jié)果表明，該模型能夠有效地規(guī)劃物料配送路徑，減少配送時(shí)間，確保物料按時(shí)供應(yīng)，同時(shí)降低物料配送成本。此外，通過引入車間路徑約束、時(shí)間窗和車輛容量限制，模型更貼近實(shí)際生產(chǎn)環(huán)境，提高了其應(yīng)用價(jià)值。未來的研究可以在此基礎(chǔ)上同時(shí)取送貨的車間道路約束下的車輛路徑問題，以及考慮動(dòng)態(tài)車間環(huán)境下的物料配送路徑優(yōu)化問題，引入實(shí)時(shí)數(shù)據(jù)反饋和機(jī)器學(xué)習(xí)技術(shù)。