[發明專利]一種基于混合禁忌搜索的車輛路徑優化方法及系統

在審

• 申請號: 202111178059.6
• 申請日: 2021-10-09
• 公開（公告）號: CN114091722A
• 公開（公告）日: 2022-02-25
• 發明（設計）人: 金輝;李俊青
• 申請（專利權）人: 山東師范大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q10/06;G06N3/12
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 張勇

1.一種基于混合禁忌搜索的車輛路徑優化方法，其特征在于，包括：

獲取顧客時間窗和顧客需求；

采用混合禁忌搜索算法求解目標函數，得到全局最優路徑，所述目標函數基于所述顧客時間窗、顧客需求、車輛數目和負載能力構建；

其中，混合禁忌搜索算法使用禁忌搜索和變鄰域搜索進行個體優化，通過人工免疫算法進行種群優化。

2.如權利要求1所述的一種基于混合禁忌搜索的車輛路徑優化方法，其特征在于，所述變鄰域搜索包括：對于每個個體，交換路線內的顧客位置、在路線之間交換顧客位置、在同一條路線上重定位顧客位置、在不同路線間重定位顧客位置、消除最小路線和消除隨機路線。

3.如權利要求1所述的一種基于混合禁忌搜索的車輛路徑優化方法，其特征在于，所述人工免疫算法對種群進行選擇操作，得到新的種群，具體為：

按設定比列將種群分為第一種群、第二種群和第三種群；

所述第一種群進行最優選擇，具體為：計算第一種群中所有個體的綜合指標，選擇綜合指標值最小的個體進行多次復制，并將復制的個體加入到新的種群；

所述第二種群進行錦標賽選擇，具體為：在第二種群中按照設定的種群大小隨機選擇多個樣本，選擇每個樣本中綜合指標最小的個體，加入到新的種群；

所述第三種群進行輪盤選擇，具體為：計算每個個體的綜合指標在整體綜合指標中所占的比例，遍歷所有個體，如果個體的比例值小于閾值，則將該個體添加到新的種群，否則更新閾值。

4.如權利要求3所述的一種基于混合禁忌搜索的車輛路徑優化方法，其特征在于，所述人工免疫算法對所述新的種群進行交叉操作，具體為：

遍歷每個個體時，產生一個隨機數；

若個體的隨機數在設定空間之間，則該個體和下一個個體作為兩個父代，并隨機選擇一種交叉策略進行交叉操作，得到兩個子代；

所述子代代替父代加入種群。

5.如權利要求4所述的一種基于混合禁忌搜索的車輛路徑優化方法，其特征在于，所述交叉策略為：

構建鄰接表，鄰接表記錄新的種群中不同顧客組合出現的次數；如果父代1中有兩個相鄰的顧客在鄰接表中，則將這兩個顧客復制到子代1的相同位置；將父代2出現在鄰接表中的顧客復制到子代2的相同位置；以相反的順序從父代1檢索子代2沒有的顧客并將它們插入子代2中；以相反的順序從父代2檢索子代1沒有的顧客并將它們插入子代1中；

或者，

隨機選擇父代1的交叉區域1和父代2的交叉區域2，交叉區域1和交叉區域2的起止位置相同；將交叉區域2和父代1組合起來，形成一個臨時個體；刪除臨時個體中后出現的重復元素，得到子代1；刪除交叉區域1和父代2組合起來的臨時個體中后出現的重復元素，得到子代2；

或者，

隨機選擇父代1的交叉區域1和父代2的交叉區域2，交叉區域1和交叉區域2的起止位置相同；對于交叉區域1和交叉區域2的同一個位置，確定父代2中該位置的客戶，在父代1中查找該客戶，并在父代1中該位置的客戶互換位置；同時，確定父代1中該位置的客戶，在父代2中查找該客戶，并在父代2中該位置的客戶互換位置；直到交叉區域1和交叉區域2的所有位置被遍歷，得到兩個子代。

6.如權利要求4所述的一種基于混合禁忌搜索的車輛路徑優化方法，其特征在于，所述人工免疫算法對所述交叉操作后的種群進行變異操作，具體為：遍歷每個個體時，產生一個隨機數；若個體的隨機數小于突變率，則對該個體隨機選擇一種變異方法進行變異操作；

所述變異方法為：

隨機選取個體的變異區域，然后將區域的元素進行逆序；

或者，

在個體中隨機選擇兩個不同的顧客，然后將這兩個客戶的位置互換。