[發明專利]復雜推移式活動隔斷系統軌道布局優化方法

有效

• 申請號: 201710543103.6
• 申請日: 2017-07-05
• 公開（公告）號: CN107274034B
• 公開（公告）日: 2020-04-14
• 發明（設計）人: 劉冠群;張汝波;尚秋慧;唐莉莉;溫乃峰;于海洋;藺蘭;吳俊偉;楊大偉
• 申請（專利權）人: 大連民族大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F30/20;G06F30/13;G06F111/04
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 劉斌

1.一種復雜推移式活動隔斷系統軌道布局優化方法，其特征在于,包括如下步驟：

(1)隔斷系統所要分割的區域為矩形，軌道將整個區域劃分為X×Y個大小相同的正方形網格區域，并對行分隔線和列分隔線按任意順序進行編號；每塊隔板的寬度與網格的邊長相等；通過軌道將隔板運送到指定的軌道段，并占據軌道段形成隔斷；

(2)用無向圖對分隔區域的拓撲結構進行建模，用無向圖的頂點表示軌道的交點，并按任意順序對無向圖的頂點進編號，第i個頂點記為v_i，1≤i≤(X+1)×(Y+1)，用頂點v_i所在行分隔線序號和列分隔線的序號(x,y)表示v_i的坐標，x是v_i所在行分隔線序號，y是v_i所在列分隔線序號，用無向圖的邊表示兩個相鄰頂點之間的連線,v_i和v_j之間的邊記為e_ij；

(3)將隔斷系統所要形成的第k個隔斷方案表示成無向圖邊的集合S_k，假設用戶共有K個隔斷方案，用S表示S_k的并，即設集合S的大小為M，則表示構成隔斷時第m塊隔板的應在位置，將隔斷系統隔板運送的起始位置所在的頂點記為v_s，設其坐標為(x_s,y_s)；

(4)用v_e表示e_ij的兩個頂點中任一頂點v_i或v_j，將從v_s到v_e之間的軌道連線定義為將隔板運送到應在位置e_ij的一條運送路徑，在同一條路徑中同一頂點不能重復出現，從v_s到e_ij的路徑有很多條，用表示第k條路徑,v_e為v_i或v_j；隔板運送路徑的長度定義為所包含的頂點個數；

(5)將隔板運送路徑長度T作為軌道布局優化的約束條件，T＝X+Y+1；

(6)設集合P為所有符合條件的隔板運送路徑集合，初始化

(7)令m＝1；

(8)取集合S的第m個元素利用深度優先算法求隔板從出發點v_s到長度小于T的所有運送路徑，并用集合表示符合條件的路徑集合，P_m的大小為N_m，p_i表示第i條路徑；

(9)將新得到的路徑集合P_m并入到集合P中，即P＝P∪P_m；

(10)令m＝m+1，若m≤M，跳到步驟(8)；

(11)統計頂點v_i，1≤i≤(X+1)×(Y+1)在集合P的路徑中出現的次數，并將頂點v_i出現的次數記為c_i；

(12)根據c_i的大小對所有c_i>0的頂點v_i進行排序，如果c_i>c_j，則對應的頂點v_i排在v_j的前面，可得到頂點序列L表示序列中頂點的個數；

(13)令m＝1；

(14)求集合P_m中的路徑數目N_m，如果N_m＝＝1，跳到步驟(19)；

(15)令k＝1；

(16)取序列Q中的第k個元素

(17)從P_m中刪除不包含頂點的路徑；

(18)令k＝k+1，若k≤L，跳到步驟(16)；

(19)令m＝m+1，若m≤M，跳到步驟(15)；

(20)令將P的每條路徑中的相鄰頂點變換成軌道段集合R，則集合R就是滿足用戶需求的所需鋪設的軌道段集合，方法結束。