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

寧雅敬 張惠珍

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

關(guān)鍵詞：選址路徑；時間窗；貪心免疫優(yōu)化

中圖分類號：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 ? ?引 ? ?言

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

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

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

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

1.1 ? ?問題描述

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

在本文所建立的模型中，供應(yīng)商若干個，候選配送中心若干，終端網(wǎng)點若干；

供應(yīng)商、候選配送中心、終端網(wǎng)點的位置己知，在從配送中心到終端網(wǎng)點的配送過程中將時間窗因素考慮在內(nèi)，設(shè)定超出規(guī)定時間而產(chǎn)生的懲罰成本與時間有線性函數(shù)關(guān)系；

終端網(wǎng)點需求量已知，在一定時間內(nèi)需求不存在波動；

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

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

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

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

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

1.2 ? ?模型符號的定義

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

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

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

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

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

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

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

drj表示從供應(yīng)商到配送中心的歐氏距離；

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

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

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

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

Mn（tn）表示終端網(wǎng)點的懲罰成本；

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

Yjn表示終端網(wǎng)點是由配送中心出發(fā)并進行配送；

C1表示車輛提前到達終端網(wǎng)點發(fā)生的單位時間的懲罰成本；

C2表示車輛超出規(guī)定時間到達終端網(wǎng)點發(fā)生的單位時間的懲罰成本；

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

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

超出規(guī)定時間帶來的總懲罰成本：

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

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

約束條件S.T.。

決策變量如下。

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

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

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

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

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

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

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

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

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

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

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

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

式（14）（15）（16）（17）（18）表示條件的滿足狀態(tài)。

2 ? ?貪心免疫優(yōu)化算法

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

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

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

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

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

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

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

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

本文設(shè)計的免疫操作包含抗體變異、鄰域搜索、自適應(yīng)權(quán)重三個步驟。

2.3.1 ? ?變異操作

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

針對本文設(shè)計的抗體編碼結(jié)構(gòu)，抗體交叉變異分為四種類型：

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

第二層變異，隨機生成范圍1—N的1個位置數(shù)和范圍1—J的數(shù)據(jù)數(shù)用于替換該位置內(nèi)的數(shù)據(jù)；

第三層變異，隨機生成范圍1—N的1個位置數(shù)和范圍0—1的數(shù)據(jù)數(shù)用于替換該位置內(nèi)的數(shù)據(jù)；

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

2.3.2 ? ?鄰域搜索

當?shù)街付ǖ耐Ｖ箺l件時，在每個最優(yōu)解周圍添加一個鄰域，通過鄰域搜尋最優(yōu)解。鄰域搜索的具體過程如下：首先選定一個鄰域半徑，如4個變異層的距離；然后通過隨機搜索來計算該變異層的適應(yīng)度值，不斷改變變異層并篩選出最優(yōu)解作為當前搜索的最優(yōu)解。

2.3.3 ? ?自適應(yīng)變異權(quán)重

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

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

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

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

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

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

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

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

鄰域搜索：當?shù)街付ǖ耐Ｖ箺l件時，在每個最優(yōu)解周圍添加一個鄰域，并通過鄰域搜索尋找更優(yōu)的解；

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

3 ? ?算例分析

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

3.1 ? ?算例原始參數(shù)

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

算例中設(shè)置5個供應(yīng)商，10個候選中轉(zhuǎn)站，20個客戶點。

3.2 ? ?算例結(jié)果與分析

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

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

算例5-10-20下無初始種群優(yōu)化IA算法結(jié)果如圖8所示，相關(guān)的指標見表1。

算例5-10-20下無領(lǐng)域優(yōu)化IA算法結(jié)果如圖9所示，相關(guān)的指標見表1。

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

3.3 ? ?算法性能分析

為進一步驗證本文所提出的GIOA算法的有效性，將其與傳統(tǒng)免疫算法和遺傳算法在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種規(guī)模算例中進行對比分析，取5次計算結(jié)果，取得的最優(yōu)成本結(jié)果如圖10所示，平均成本和時間如表2所示，其中總成本單位為103，時間單位為秒。

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

4 ? ?結(jié) ? ?語

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

參考文獻：

[1] 李震，段力偉．“公轉(zhuǎn)鐵”背景下鐵路冷鏈運輸發(fā)展對策[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] 張戩，劉煒，潘衛(wèi)國，等．基于改進暴力搜索算法的全雙向變流供電系統(tǒng)參數(shù)設(shè)計[J]．電工技術(shù)學(xué)報，2021，36（23）：4896-4904.

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

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

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

28（7）：224-237.

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

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

[9] 王永成，蔡晨曉．免疫算法在多無人機任務(wù)最優(yōu)規(guī)劃中的應(yīng)用[J]．機械設(shè)計與制造，2023（8）：237-241.

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

37（2）：156-163.