[發明專利]一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法

在審

• 申請號: 202010887052.0
• 申請日: 2020-08-28
• 公開（公告）號: CN112101747A
• 公開（公告）日: 2020-12-18
• 發明（設計）人: 張衛東;杜彬;陸宇;黃宇波;曹剛;蔡云澤
• 申請（專利權）人: 上海交通大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06F17/11;F41H11/00
• 代理公司: 上海科盛知識產權代理有限公司 31225
• 代理人: 楊宏泰

1.一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，包括以下步驟：

1)根據攔截艇和入侵艇的實時信息進行初期投標，獲得初期中標列表，即初期攔截艇和入侵艇對應的攔截序列；

2)根據通信記錄矩陣確定能夠實現相互通信的攔截艇，并進行相互通信，消除初期中標列表中的沖突，并更新初期中標列表為中期中標列表；

3)將中期中標列表作為禁忌優化算法的初始解序列，進行每回合多次交換操作后，獲取最優解序列，并根據該最優解序列進行當前時間的攔截任務分配方案；

4)實時獲取并更新攔截艇和入侵艇的實時信息，重復步驟1)-3)，實現動態攔截任務方案的再分配。

2.根據權利要求1所述的一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，所述的步驟1)具體包括以下步驟：

11)當當前攔截艇i已經投標攔截入侵艇j時，計算攔截艇i初期投標方案的得分Score_ij，則有：

Score_ij＝Reward_ij-Cost_ij

其中，Reward_ij為初期投標方案的收益值，Cost_ij為初期投標方案的花費，Fu為行駛單位距離的能耗，x_i、x_j和y_i、y_j分別為攔截艇i與入侵艇j的橫、縱坐標。

12)選擇得分最高的初期投標方案作為當前攔截艇的初期中標方案；

13)遍歷所有的攔截艇，將所有攔截艇的初期中標方案合并形成初期中標列表。

3.根據權利要求2所述的一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，所述的步驟2)中，在通信記錄矩陣G(t)中，若攔截艇i與攔截艇k的在當前時刻能夠實現相互通信，則通信記錄矩陣G(t)中的對應元素G_jk(t)＝1，否則G_jk(t)＝0。

4.根據權利要求3所述的一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，所述的步驟2)具體包括以下步驟：

21)根據通信記錄矩陣G(t)判斷兩攔截艇是否能夠實現相互通信；

22)當兩個攔截艇之間能夠實現相互通信時，則互相比較各自方案的得分，并將得分較高的攔截艇的初期中標方案作為該攔截艇的中期中標方案；

23)在剔除該攔截艇的初期中標方案后返回步驟11)，剩余的攔截艇重新進行初期投標，并更新初期中標列表后進行步驟21)，直至消除初期中標列表中的沖突，將所有攔截艇的中期中標方案合并成中期中標列表。

5.根據權利要求1所述的一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，所述的步驟3)具體為：

31)將中期中標列表作為禁忌優化算法的初始解序列，并計算該初始解序列對應的得分Score；

32)進行多回合且每回合內多次的兩兩序列元素的隨機交換，并獲取每次序列元素隨機交換形成的新解序列對應的得分Score，該得分Score由解序列中所有攔截艇的投標方案對應的得分求和得到；

33)在隨機交換結束后獲取得分最高的解序列，作為最優解序列，即當前時間的攔截任務分配方案。

6.根據權利要求5所述的一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，所述的步驟32)中，若在隨機交換后得到的新解序列的得分變化值ΔScore超過了禁忌交換的閾值，則將此次隨機交換操作放入禁忌表中，用以阻止該交換操作在后續的隨機交換中被交換。

7.根據權利要求6所述的一種基于禁忌共識拍賣算法的無人艇攔截任務分配方法，其特征在于，所述的禁忌交換的閾值額的取值為所有解序列中最高得分的10％。