[發明專利]基于混合局部搜索和蟻群優化的混裝線序列恢復方法

有效

• 申請號: 202010585223.4
• 申請日: 2020-06-24
• 公開（公告）號: CN111784037B
• 公開（公告）日: 2022-10-28
• 發明（設計）人: 曹璨;孫輝
• 申請（專利權）人: 東南大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/00
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 常虹

1.基于混合局部搜索和蟻群優化的混裝線序列恢復方法，其特征在于，包括：

S1、確定上游序列S_up中車輛的總數T、每一個車輛在目標序列中的位置p_i，緩沖區車道數L和每條車道的容量W；T≤L×W；

S2、設置局部搜索算法的最大迭代次數s_max，初始化局部搜索算法迭代次數s＝1；根據填充規則為上游序列的每一個車輛選擇進入的緩沖區車道，構建緩沖區內初始車輛排布方案A(0)，作為初始的最優車輛排布方案A_best；根據釋放規則得到所述初始車輛排布方案A(0)對應的下游序列，作為初始的最優恢復序列S_down；

S3、對車輛排布方案A(s-1)進行擾動，得到第s代車輛排布方案A(s)；

S4、采用蟻群算法優化第s代車輛排布方案A(s)的釋放順序，得到第s代車輛排布方案對應的最優下游序列S_best(s)；

S5、如果S_up釋放為S_best(s)的車輛總位置偏移量小于S_up釋放為最優恢復序列S_down的車輛總位置偏移量，將最優恢復序列S_down更新為S_best(s)，最優車輛排布方案A_best更新為A(s)；

S6、判斷是否滿足局部搜索算法結束條件；如不滿足，令s＝s+1，跳轉至步驟S3進行下一次局部搜索；如滿足，最優恢復序列S_down即為上游序列S_up恢復后的序列，最優車輛排布方案A_best為與S_down對應的緩沖區內車輛排布方案。

2.根據權利要求1所述的混裝線序列恢復方法，其特征在于，所述步驟S2中根據填充規則選擇上游序列第i輛車進入的車道步驟為：

(A.1)如果i＝1，隨機選取一條車道；

(A.2)如果未填滿車道l最后一輛車在上游序列中的序號為j，且滿足p_i＝p_j+1，則選擇車道l；其中p_i、p_j分別為第i輛車、第j輛車在目標序列中的位置；l∈[1,2,…,L]；

(A.3)如果緩沖區存在空車道，任選一條空車道；

(A.4)如果緩沖區內的未填滿車道滿足第一條件，則選擇該車道；如滿足第一條件的車道數大于1，則選擇其中p_i-p_j最小的車道；所述第一條件為：最后一輛車在上游序列中的序號為j，且p_i-p_j1；

(A.5)如果緩沖區內的未填滿車道滿足第二條件，則選擇該車道；如滿足第二條件的車道數大于1，則選擇其中p_j-p_i最小的車道；所述第二條件為：最后一輛車在上游序列中的序號為j，且p_i-p_j0。

3.根據權利要求1所述的混裝線序列恢復方法，其特征在于，所述步驟S2中的釋放規則用于從緩沖區內所有非空車道最前端車輛中選擇一輛車釋放，直到緩沖區為空，構成下游序列；具體步驟為：

(B.1)n＝1；

(B.2)緩沖區內所有非空車道最前端的車輛組成候選集；

如果候選集中存在車輛m滿足條件：p_m＝n，則釋放車輛m；如不存在，則釋放在目標序列中的位置最小的車輛；

(B.3)令n＝n+1，跳轉至步驟(B.2)選擇下一輛釋放車輛，直到緩沖區為空。

4.根據權利要求1所述的混裝線序列恢復方法，其特征在于，所述步驟S3中的擾動操作為：

隨機選擇緩沖區內兩輛位于不同車道的車輛，交換所述兩輛車所在的車道，并按照先到達先進入的原則調整所述兩車道內車輛的停放順序。