貪心免疫優化算法求解帶時間窗的冷鏈物流選址路徑問題

寧雅敬 張惠珍

摘 要：文章針對冷鏈物流選址路徑問題，提出了一種貪心免疫優化算法。首先，建立了考慮物流時間窗約束的選址路徑模型，以最小化選址成本、車輛啟用成本和運輸成本為目標。其次，設計了貪心免疫優化算法來解決該問題。該算法使用六層抗體編碼方法，有效提高了抗體突變控制精度和抗體解碼效率。通過對初始抗體群體進行貪心預優化，在不壓縮丟失抗體突變空間的前提下，提高了初始抗體的適應性。通過對抗體突變方向權值的自適應迭代，提高了算法的優化效率。數值分析結果表明，提出的算法在有時間窗的定位路徑問題中具有較好的優化能力，構建的模型可以有效降低定位路徑問題的總成本。

關鍵詞：選址路徑；時間窗；貪心免疫優化

中圖分類號：F252；U116文獻標志碼：ADOI：10.13714/j.cnki.1002-3100.2024.08.036

Abstract： This paper proposes a greedy immune optimization algorithm for cold chain logistics location and routing problems. Firstly， the paper establishes a location path model that considers logistics time window constraints， with the goal of minimizing location costs， vehicle activation costs， and transportation costs. Secondly， the paper designs a greedy immune optimization algorithm to solve this problem. This algorithm uses a six layer antibody encoding method， effectively improving the accuracy of antibody mutation control and antibody decoding efficiency. By performing greedy pre optimization on the initial antibody population， the adaptability of the initial antibody is improved without compressing the loss of antibody mutation space. The optimization efficiency of the algorithm has been improved through adaptive iteration of antibody mutation direction weights. The numerical analysis results indicate that the proposed algorithm has good optimization ability in location path problems with time windows， and the constructed model can effectively reduce the total cost of location path problems.

Key words： site selection path; time window; greedy immune optimization

0 ? ?引 ? ?言

近年來，隨著物流業的發展和人們對食品安全的關注度不斷提高，冷鏈物流逐漸成為物流行業中的重要領域[1]。冷鏈物流在運作過程中需要嚴格控制時間窗口、溫度、濕度等因素，因而其選址路徑成為十分關鍵的問題，直接影響著物流成本、效率和服務質量。因此，如何有效地求解帶時間窗的冷鏈物流選址路徑問題已經成為學術界和工程界研究的重點之一。

傳統的LRPTW優化求解方法包括暴力搜索[1-3]、貪心算法[4]、遺傳算法[5]、模擬退火算法[6]等。隨著物流路徑的復雜程度和配送中心、客戶數量的逐步提升，LRPTW問題的求解空間呈現現出非線性增長趨勢，傳統算法的尋優效率和求解精度較難滿足復雜場景下的計算需求。免疫優化算法（Immune Optimization Algorithm，IOA）作為一種新興的啟發式算法，通過模擬免疫學功能、原理和模型來解決復雜的自適應系統，在計算機安全、路徑優化、數據挖掘等領域具有很好的應用潛力和可拓展性[7]。姚翠平[8]提出一種基于免疫算法的船舶運輸路徑優化方法，通過綜合評估提出優化運輸路徑的最優方案。王永成等[9]利用免疫算法解決多無人機任務最優規劃問題。然而，傳統免疫優化算法在解決帶時間窗的冷鏈物流選址路徑問題時顯現出了搜索速度較慢、精度有限、收斂性差等缺點。王杰等[10]提出一種基于改進免疫遺傳算法和Holt-Winters模型的電能計量器具配送網絡優化策略。

本文對傳統免疫算法進行改進，在其基礎上引入貪心優化策略，重新設計抗體編碼和自適應抗體變異權重，提升了算法在帶時間窗的冷鏈物流選址路徑問題中的尋優效率和能力。重點在于重新設計了六層結構的抗體編碼方式，增強了變異控制和解碼效率；采用貪心優化策略對初始抗體群進行了預優化，提高了初始抗體的適應性；通過自適應迭代抗體變異方向權重，加速了算法的尋優過程。案例分析表明，GIOA有效克服了原算法的局部最優和收斂速度慢等問題，在解決復雜VRPTW問題上具有理論和實際應用意義。

1 ? ?帶時間窗的選址路徑問題

1.1 ? ?問題描述

本文所研究的帶時間窗的冷鏈物流選址路徑問題涉及選址和路徑規劃兩個方面。選址的目標是確定最少的配送中心并計算總建設成本；路徑規劃的目標是通過合理分配和運輸安排最小化物流總成本，包括配送中心建設成本、運輸成本、車輛啟用成本和時間窗懲罰成本。

在本文所建立的模型中，供應商若干個，候選配送中心若干，終端網點若干；

供應商、候選配送中心、終端網點的位置己知，在從配送中心到終端網點的配送過程中將時間窗因素考慮在內，設定超出規定時間而產生的懲罰成本與時間有線性函數關系；

終端網點需求量已知，在一定時間內需求不存在波動；

支線運輸（從配送中心至終端網點）過程中采用統一標準的車輛，每輛車僅聽從一個配送中心的調遣，但是每輛車可以服務多個終端網點，但每個終端網點只能由一輛車進行配送；

運輸過程中車輛的終點為配送中心，配送途中車輛的速度己知且固定；

在配送中心等候提供派遣服務的車輛數量足夠多，并且每個配送中心的存儲量己知；

運輸車一直處于恒溫狀態，其他影響因素忽略不計；

干線運輸（從供應商至配送中心）過程中采用統一標準的車輛，每輛車的起點均為供應商，但每輛車僅服務一個配送中心。

1.2 ? ?模型符號的定義

對生鮮冷鏈物流配送中心選址及路徑優化模型中的各變量符號定義如下。

R=｛r｜r=1，2，3，…，r｜r≤10｝，表示供應商集合；

J=｛j｜j=1，2，3，…，j｜j≤10｝，表示候選配送中心集合；

N=｛n｜n=1，2，3，…，n｝，表示終端網點集合；

K=｛k｜k=1，2，3，…，k｝，表示從配送中心到終點網點的運輸車輛集合；

F表示配送中心的固定建設和運作成本；

Zj表示是否在此處建立配送中心；Zj=

drj表示從供應商到配送中心的歐氏距離；

Crj表示從供應商到配送中心之間的單位運輸成本；

djn表示從配送中心（或終端網點）到終端網點的歐氏距離；

Cjn表示從配送中心（或終端網點）到終端網點的單位運輸成本；

Bk表示從配送中心到終端網點的配送過程中啟動車輛k的固定使用成本；

Mn（tn）表示終端網點的懲罰成本；

tjn表示從配送中心（或終端網點）到終端網點所用的時間；

Yjn表示終端網點是由配送中心出發并進行配送；

C1表示車輛提前到達終端網點發生的單位時間的懲罰成本；

C2表示車輛超出規定時間到達終端網點發生的單位時間的懲罰成本；

Rn表示時間窗是否得到滿足，Rn=；

Xjk為0～1變量，表示車輛在行駛過程中的時間窗約束。

超出規定時間帶來的總懲罰成本：

1.3 ? ?帶時間窗選址路徑模型

下式表示選址路徑模型最小化的物流總成本，其中包括生鮮食品從供應商r到冷鏈配送中心j的運輸成本、配送中心的總建設成本、生鮮食品從被選配送中心j到終端零售門店n的運輸成本、車輛啟用成本、車輛早到以及遲到的懲罰成本。

約束條件S.T.。

決策變量如下。

式（1）表示至少建一個配送中心；

式（2）表示配送中心總配送量能夠滿足終端網點的總需求量；

式（3）表示每個終端網點都由一個選中的配送中心有且僅為其提供一次配送服務；

式（4）表示每輛車最多被啟用一次；

式（5）表示每一輛車不能超過其最大載重量；

式（6）表示從配送中心到終端網點的進出車輛相同；

式（7）表示限制了從配送中心到終端網點的過程中各個配送中心之間不允許存在路徑；

式（8）表示配送車輛的最大行駛距離限制；

式（9）表示消除子路徑；

式（10）和（11）表示X kjn和Zj這兩個決策變量之間的關系；

式（12）表示每個終端網點都指定一個被選中的配送中心為其提供配送服務；

式（13）表示如果配送車輛在經過j點后到達n點，則車輛k到達節點n的時間是車輛k到達上一節點j的時間加上在n點的服務時間再加上jn間行駛消耗的時間，否則該約束松弛；

式（14）（15）（16）（17）（18）表示條件的滿足狀態。

2 ? ?貪心免疫優化算法

2.1 ? ?抗體種群貪心初始化（見圖1）

在本文GIOA中，首先使用貪心優化算法對初始種群進行優化，將種群劃分為若干個簇（Cluster）。然后，在每個簇內部應用貪心優化算法，以尋找更好的局部解。同時，引入一些新種群，以維持種群的多樣性和避免早熟現象。

2.2 ? ?抗體編碼方式（見圖2）

為解決J選址和J2N路徑編碼問題，設計如下抗體變量，其中第一層是N編碼，編碼范圍是1—N；第二層是J編碼，編碼范圍是1—J；第三層是路徑選擇編碼，范圍是0—1。（見圖3）

為了確保該抗體可以轉譯出合理的路徑和J選址，規定該抗體編碼第一層為1—N的排列數，第二層為1—J的隨機數，第三層為0—1的隨機數據。

運輸路徑的解碼規則為，每一列上層N與下層J是一一對應關系，當有多個N對應同一J時，有第三層編碼決定是否有同一班次K運送。

抗體4—6層是R的編碼，當該列非0時，該列的J由R配送。（見圖4）

2.3 ? ?免疫操作（見圖5）

本文設計的免疫操作包含抗體變異、鄰域搜索、自適應權重三個步驟。

2.3.1 ? ?變異操作

在完成每次免疫個體之間的克隆操作后，引入變異操作。變異操作旨在擴大搜索范圍，增加多樣性，從而防止算法過早收斂。

針對本文設計的抗體編碼結構，抗體交叉變異分為四種類型：

第一層變異，隨機生成范圍1—N的兩個位置數，交換該位置里的數據；

第二層變異，隨機生成范圍1—N的1個位置數和范圍1—J的數據數用于替換該位置內的數據；

第三層變異，隨機生成范圍1—N的1個位置數和范圍0—1的數據數用于替換該位置內的數據；

第四到六層變異，隨機生成范圍1—N的1個列位置數、范圍3—6的1個行位置數，用范圍0—R的數據數來替換該位置的數據。

2.3.2 ? ?鄰域搜索

當迭代到指定的停止條件時，在每個最優解周圍添加一個鄰域，通過鄰域搜尋最優解。鄰域搜索的具體過程如下：首先選定一個鄰域半徑，如4個變異層的距離；然后通過隨機搜索來計算該變異層的適應度值，不斷改變變異層并篩選出最優解作為當前搜索的最優解。

2.3.3 ? ?自適應變異權重

記錄每次抗體變異的方向及其適應度，建立抗體變異權重向量，當某個方向的變異使得抗體適應度增加時，則增加相應方向的變異權重。

2.4 ? ?算法步驟（見圖6）

改進的免疫優化算法主要包括以下幾個步驟。

初始化參數：確定算法的基本參數，包括種群數量size-pop、記憶庫容量over-best、期望繁殖概率的多樣性評價參數p-s、交叉概率p-cross、變異概率p-mutation抗體的長度length、初始抗體的數目number、迭代次數iteration、抗體間相似度的閾值r；

生成初始免疫個體：隨機生成一組初始解作為免疫個體，并計算其適應度函數值；

克隆操作：按照適應度函數值選擇并克隆免疫個體，生成新的解，這些新解會受到一定程度的“突變”影響，以增加種群的多樣性；

交叉操作：在完成每個免疫個體之間的克隆操作后，引入交叉操作。選擇兩個免疫個體，并利用交叉方法生成另外兩個新的免疫個體；

選擇操作：選擇經過克隆和交叉后的所有新解中k個最優解作為下一次搜索的初始點；

鄰域搜索：當迭代到指定的停止條件時，在每個最優解周圍添加一個鄰域，并通過鄰域搜索尋找更優的解；

重復操作：在新選擇的k個解作為免疫個體的基礎上，重新進行克隆、交叉、選擇和鄰域搜索操作，直到達到預設的進化次數。

3 ? ?算例分析

為了驗證模型的可行性和有效性，以及評估改進的免疫優化算法求解帶時間窗的選址路徑問題的性能，使用MatlabR2018b實現該算法，并在Windows7系統下，在一臺配備2.7GHz主頻處理器和4GB內存的PC機上進行大量的數值試驗。

3.1 ? ?算例原始參數

在初始種群優化中，設置免疫個體200個，初始種群簇1 000個，種群簇融合概率0.5；設置免疫算法最大迭代次數1 000次，抗體克隆次數20次，單抗體變異3次，變異類型4種，新舊抗體比列1：1；自適應領域搜索中設置搜索次數5 000次，初始變異概率相同。

算例中設置5個供應商，10個候選中轉站，20個客戶點。

3.2 ? ?算例結果與分析

為說明本文改進免疫算法的有效性，將本文GIOA算法、無初始種群優化IA算法和無領域優化IA算法進行對比分析。

算例5-10-20下本文GIOA算法結果如圖7所示，相關的指標見表1。

算例5-10-20下無初始種群優化IA算法結果如圖8所示，相關的指標見表1。

算例5-10-20下無領域優化IA算法結果如圖9所示，相關的指標見表1。

在三種算法對比中，可以發現在小規模算例中，本文所提的GIOA算法的尋址時間較長，這是因為無初始種群優化GIOA算法和無領域優化GIOA算法只能改進免疫優化算法中的局部。改進的免疫算法由于加入了初始解的生成操作和多種不同的交叉變異操作，在使得求解質量更優的同時，耗費了一定的程序時間。但考慮到運輸建設成本以及對應的總成本，該算法的求解質量具有較大優勢。

3.3 ? ?算法性能分析

為進一步驗證本文所提出的GIOA算法的有效性，將其與傳統免疫算法和遺傳算法在5-10-20、5-10-100、5-20-20、5-20-100、10-10-20、10-10-100、10-10-20、10-20-100這8種規模算例中進行對比分析，取5次計算結果，取得的最優成本結果如圖10所示，平均成本和時間如表2所示，其中總成本單位為103，時間單位為秒。

通過表2可以看出，與傳統免疫算法相比，本文所提出的改進面議算法的運行時間略長，主要是因為改進的免疫算法中加入了初始解的生成操作和多種不同的交叉變異操作。但從總成本角度看，改進免疫算法明顯優于另外三種算法。

4 ? ?結 ? ?語

本文對帶時間窗的冷鏈物流選址路徑問題進行了研究，并使用改進的免疫優化算法進行求解。通過引入動態調整機制、粒子初始位置的啟發式選擇以及避免全局信息丟失等方式，對免疫優化算法進行了改進，有效改善了傳統免疫算法過早陷入局部最優解、收斂速度慢、在高維空間內搜索能力差的問題。對比GA和CPLEX，本文所提出的改進免疫算法對于帶時間窗的冷鏈物流選址路徑問題有良好的優化性能。

參考文獻：

[1] 李震，段力偉．“公轉鐵”背景下鐵路冷鏈運輸發展對策[J]．鐵道貨運，2020，38（6）：37-41.

[2] 虎翼飛，張惠珍，陳曦．改進野馬算法求解低碳開放式送取貨選址路徑問題[J/OL]．包裝工程，2024：1-14.[2024-01-20].

http：//kns.cnki.net/kcms/detail/50.1094.TB.20230818.1308.004.html.

[3] 張戩，劉煒，潘衛國，等．基于改進暴力搜索算法的全雙向變流供電系統參數設計[J]．電工技術學報，2021，36（23）：4896-4904.

[4] 徐小小，周啟銀，婁成龍，等．基于貪心算法的自動路徑規劃送藥小車[J]．中國新技術新產品，2023（8）：21-23.

[5] 李家碧，韓曙光．考慮客戶等級和時變路況的無人物流配送路徑[J]．浙江大學學報（工學版），2023，57（10）：2018-2027.

[6] 賓厚，張路行，王素杰，等．基于改進多目標遺傳算法的農村低碳物流配送路徑優化[J]．中國農業大學學報，2023，

28（7）：224-237.

[7] 馬元鋒，李昂儒，余慧敏，等．基于動態擁擠距離的混合多目標免疫優化算法[J]．計算機科學，2018，45（S1）：63-68.

[8] 姚翠平．結合免疫算法的船舶運輸路徑優化方法研究[J]．艦船科學技術，2019，41（12）：58-60.

[9] 王永成，蔡晨曉．免疫算法在多無人機任務最優規劃中的應用[J]．機械設計與制造，2023（8）：237-241.

[10] ?王杰，孫林，鄭直，等．基于改進免疫遺傳算法和Holt-Winters的電能計量器具配送優化[J]．電力科學與技術學報，2022，

37（2）：156-163.