[發(fā)明專利]基于雙層遺傳編碼的應(yīng)急物資運輸與裝載協(xié)同優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 202110576710.9
• 申請日: 2021-05-26
• 公開（公告）號: CN113222272B
• 公開（公告）日: 2022-09-20
• 發(fā)明（設(shè)計）人: 楊敏;黃志恒;李凱莉;安慶賢;戴前智;陳亞
• 申請（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/12
• 代理公司: 安徽省合肥新安專利代理有限責(zé)任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于雙層遺傳編碼的應(yīng)急物資運輸與裝載的協(xié)同優(yōu)化方法，其特征是，應(yīng)用于由m種模塊化應(yīng)急物資的種類集合A＝{w₁,w₂,...,w_α,...,w_m}、n個受災(zāi)地區(qū)的物資需求點集合N＝{d₁,d₂,...,d_i,...,d_j,...,d_n}、運輸車輛集合K＝{h₁,h₂,...,h_k,...,h_c}和一個物資出救點d₀構(gòu)成的應(yīng)急物流網(wǎng)絡(luò)中，其中，w_α代表第α種模塊化應(yīng)急物資，且第α種模塊化應(yīng)急物資w_α的單位體積為b_α，第α種模塊化應(yīng)急物資w_α的單位重量為m_α，同時第α種模塊化應(yīng)急物資w_α滿足w_α＝{λ₁θ₁,λ₂θ₂,...,λ_sθ_s,...,λ_Sθ_S}，系數(shù){λ₁,λ₂,...,λ_s,...,λ_S}表示各類應(yīng)急物資在第α種模塊化應(yīng)急物資w_α中的比例關(guān)系，λ_s表示第s類應(yīng)急物資在第α種模塊化應(yīng)急物資w_α中的比例關(guān)系；d_i表示第i個受災(zāi)地區(qū)的物資需求點，第i個受災(zāi)地區(qū)的物資需求點d_i和第j個受災(zāi)地區(qū)的物資需求點d_j之間的距離為d_ij；h_k代表第k個運輸車輛，且第k個運輸車輛h_k的額定容積為v_k，第k個運輸車輛h_k的額定載重為g_k，使用第k個運輸車輛h_k的總成本為c_k，α＝1,2,...,m，i＝1,2,...,n，j＝1,2,...,n，k＝1,2,...,c，s＝1,2,...,S；m表示模塊化應(yīng)急物資的種類，n表示受災(zāi)地區(qū)物資需求點的數(shù)量，c表示運輸車輛的數(shù)量，S表示模塊化應(yīng)急物資中包含的物資種類；

所述協(xié)同優(yōu)化方法是按如下步驟進行：

步驟1、將第i個受災(zāi)地區(qū)的物資需求點d_i對第α種模塊化應(yīng)急物資w_α的需求量記為且第i個受災(zāi)地區(qū)的物資需求點d_i所需的模塊化應(yīng)急物資需求總量為D_i；

步驟2、假設(shè)第k個運輸車輛h_k對第α種模塊化應(yīng)急物資w_α的裝載數(shù)量為且第k個運輸車輛h_k對模塊化物資的總裝載體積和裝載重量不能超過其額定容積v_k和額定載重g_k；

步驟3、初始化遺傳算法的各個參數(shù)，包括：種群規(guī)模Z、當前進化次數(shù)G、最大進化代數(shù)G_max，種群交叉概率p_c，種群變異概率p_v，初始化G＝1；

步驟4、產(chǎn)生初始種群，獲得第G代第r個染色體的基因變量集合其中，表示第G代第r個染色體第一層的第l個基因變量，表示第G代第r個染色體第二層的第l個基因變量，l＝1,2,...,L，r＝1,2,...,Z；Z表示種群規(guī)模，L表示單層染色體長度；

步驟4.1、循環(huán)遍歷所述物資需求點集合N，產(chǎn)生第i個受災(zāi)地區(qū)的物資需求點d_i對第α種模塊化應(yīng)急物資w_α的需求量的值，并使得產(chǎn)生的模塊化應(yīng)急物資需求量集合滿足關(guān)系式(3)：

步驟4.2、循環(huán)遍歷所述運輸車輛集合K，產(chǎn)生第k個運輸車輛h_k對第α種模塊化應(yīng)急物資w_α的裝載數(shù)量的值，記為并使得產(chǎn)生的模塊化應(yīng)急物資裝載量集合滿足關(guān)系式(4)和(5)：

步驟4.3、采用雙層編碼來表示物資需求點被訪問的順序和相應(yīng)的訪問車輛：第一層為基于物資需求點的編碼，記為需求碼層；第二層為基于訪問車輛的編碼，記為車輛碼層；

步驟4.3.1、用L_i表示第i個受災(zāi)地區(qū)的物資需求點d_i被車輛訪問的總次數(shù)，記L為n個受災(zāi)地區(qū)的物資需求點被車輛訪問的總次數(shù)，則滿足關(guān)系式(6)：

步驟4.3.2、令第一層和第二層的編碼長度均為L；

令第G代第r個染色體的基因變量集合中的需求碼對應(yīng)于被訪問的物資需求點d_i，表示在需求碼中物資需求點d_i出現(xiàn)在第l個位置，在需求碼中第λ次出現(xiàn)表示物資需求點d_i被第λ次訪問，l＝1,2,...,L，λ＝1,2,...,L；

令第G代第r個染色體的基因變量集合中的車輛碼對應(yīng)于訪問車輛h_k，表示在車輛碼中訪問車輛h_k出現(xiàn)在第l個位置，在車輛碼中第μ次出現(xiàn)表示訪問車輛h_k到達的第μ個物資需求點，l＝1,2,...,L，μ＝1,2,...,L；

每一個對應(yīng)一個根據(jù)集合和的一一對應(yīng)關(guān)系，從而確定每個需求點被訪問的車輛和每個車輛所訪問的需求點；

步驟5、計算第G代所有染色體在目標函數(shù)下的適應(yīng)度值集合為其中，表示第G代第r個染色體在目標函數(shù)下的適應(yīng)度值；

步驟6、對第G代所有染色體適應(yīng)度值集合F中的所有適應(yīng)度值進行比較，保存第G代最大適應(yīng)度值對應(yīng)的染色體，記為并保存對應(yīng)的第G代最大適應(yīng)度值

步驟7、將種群規(guī)模為Z的第G代種群進行交叉和變異操作，生成第G代種群的子代種群為其種群規(guī)模同樣為Z；

步驟8、按照步驟5計算第G代種群的子代種群中第r個染色體在目標函數(shù)下的適應(yīng)度值f_r′^(G)；

步驟9、采用輪盤賭選擇法對染色體進行選擇；

步驟9.1、對子代種群中的染色體按照適應(yīng)度值f_r′^(G)的大小進行升序排序；

步驟9.2、利用式(1)計算第r個染色體被選擇的概率p_r：

步驟9.3、利用式(2)計算在升序排序后，前e個染色體被選擇的累計概率q_e：

步驟9.4、采用模擬賭盤操作，來確定遺傳到下一代的染色體：

步驟9.4.1、隨機生成0到1之間的隨機數(shù)，記為rand_num，記q₀＝0，若q_e-1＜rand_num≤q_e，則表示第e個染色體被選中，能遺傳到下一代；

步驟9.4.2、循環(huán)執(zhí)行步驟9.4.1Z次，從而得到第G代種群的子代種群中被選擇的Z個染色體，使得種群規(guī)模為Z；

步驟10、將所述第G代種群的子代種群中被選擇的Z個染色體作為第G+1代的父代種群

步驟11、按照步驟5的過程計算步驟10中第G+1代的父代種群中所有染色體的適應(yīng)度值集合記第G+1代所有染色體的適應(yīng)度值集合F^(G+1)中的最大適應(yīng)度值為其對應(yīng)的染色體記為若大于步驟6中的則更新最大適應(yīng)度值為并保存其對應(yīng)的染色體否則，用第G代染色體中最大適應(yīng)度值對應(yīng)的染色體代替第G+1代染色體中最小適應(yīng)度值對應(yīng)的染色體，并進入下一代；

步驟12、將G+1賦值給G，判斷G＜G_max是否成立，若成立，則執(zhí)行步驟7；否則，表示完成G_max次迭代，最終得到的種群記為A；

步驟13、將種群A中的染色體作為最優(yōu)解集，以所述最優(yōu)解集對應(yīng)的模塊化應(yīng)急物資運輸與裝載方案則為最優(yōu)方案。

2.根據(jù)權(quán)利要求1所述的基于雙層遺傳編碼的應(yīng)急物資運輸與裝載的協(xié)同優(yōu)化方法，其特征在于，所述步驟7的交叉和變異的步驟是如下過程進行：

步驟7.1、雙層交叉：

對染色體中的需求碼層和車輛碼層均采用兩點交叉法，在需求碼層中，隨機選擇兩個父本染色體，并隨機生成兩個整數(shù)t₁和t₂作為兩個父本染色體基因序數(shù)，且t₁＜t₂＜L，將兩個父本染色體對應(yīng)序數(shù)t₁和t₂之間所有的基因互換，從而得到兩個子代染色體；同理得到車輛碼層的交叉過程；

步驟7.2、雙層變異，分別包括需求碼層變異和車輛碼層變異：

對于需求碼層變異采用兩點互易變異法，即針對單個染色體，隨機產(chǎn)生兩個整數(shù)t₃和t₄作為步驟7.1得到的子代染色體的基因序數(shù)，且t₃＜t₄＜L，將t₃和t₄位置上的基因交換，從而得到新的子代染色體；

對于車輛碼層變異則采用單點變異法。