[發(fā)明專利]一種基于帝國主義競爭算法的車輛路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201710073254.X
• 申請日: 2017-02-10
• 公開（公告）號: CN106845907B
• 公開（公告）日: 2020-06-02
• 發(fā)明（設(shè)計）人: 陳豪;王耀宗;張丹;蔡品隆;張景欣
• 申請（專利權(quán)）人: 泉州裝備制造研究所
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06N3/00
• 代理公司: 泉州市文華專利代理有限公司 35205
• 代理人: 陳云川

1.一種基于帝國主義競爭算法的車輛路徑規(guī)劃方法，其特征在于，包括以下步驟：

S1、建立區(qū)域環(huán)境交通圖，結(jié)合區(qū)域環(huán)境交通圖給出物流中心和配送點的點集、弧集，以及給出物流中心及各配送點相互間的距離值；所述點集指物流中心和配送點在區(qū)域環(huán)境交通圖上的位置點集合，弧集指物流中心與配送點之間的道路集合；

S2、建立初始帝國，通過亂序算法并依據(jù)步驟S1的點集與弧集隨機生成N個路徑，計算各路徑的總距離，定義N個國家，通過路徑總距離與國家權(quán)力的關(guān)系式來評估各國家的國家權(quán)力，接著按照國家權(quán)力排序并將所有國家分成殖民國家和殖民地，生成權(quán)力最大的N_imp個殖民國家，即N_imp個帝國和N_col＝N-N_imp個殖民地，分別存儲殖民國家和殖民地的權(quán)力表；

S3、帝國內(nèi)的同化操作：殖民國家以自身路徑為基準(zhǔn)，依據(jù)一定同化率隨機地替換和改變殖民地路徑中的部分點集；

S4、帝國內(nèi)的革命操作：殖民地隨機改變自身路徑的部分地點位置，變化方式為節(jié)點的0-1交換和1-1交換，并重新評估殖民國家和殖民地的權(quán)力，若后者力大于前者，則取代前者形成新的帝國；

S5、帝國內(nèi)的增強操作：根據(jù)殖民國家權(quán)力表，對權(quán)力最小的殖民國家進行增強，增強方式為：隨機移除該殖民國家路徑中部分點集，再將移除的點集隨機重排并依次插入剩余地點中所以可能的位置，接著重新評估殖民國家增強前后的權(quán)力，保留權(quán)力大的殖民國家；

S6、帝國間的競爭操作：以帝國為單位，計算帝國內(nèi)殖民國家和所有殖民地的標(biāo)準(zhǔn)化加權(quán)權(quán)力和，通過評估所有帝國權(quán)力，將最弱帝國的最弱殖民地分配給最強帝國，此外，當(dāng)某個帝國內(nèi)沒有任何殖民地時視為帝國消失，則該帝國的殖民國家也被分配給最強帝國作為殖民地；

S7、迭代判斷：判斷是否一個帝國是否到達(dá)預(yù)設(shè)迭代次數(shù)，若是則停止運算，輸出權(quán)力最大殖民國家的路徑作為最優(yōu)解，若否，則返回S3。

2.如權(quán)利要求1所述的一種基于帝國主義競爭算法的車輛路徑規(guī)劃方法，其特征在于，所述步驟S1具體包括：首先給出物流中心和配送點的點集，定義G＝(V,E,D)為需要貨物配送的區(qū)域環(huán)境交通圖，其中V＝{1,2,…,M}為物流中心和要經(jīng)過的配送點的集合，即點集，設(shè)V₁為物流中心，E＝{(i,j)|(i,j∈V),i≠j}為物流中心與各配送點之間的道路集合，即弧集，距離矩陣D＝[d_ij]_M×M中每一個元素表示物流中心或配送點i與物流中心或配送點j的距離，且有d_ij0,d_ii＝+∞,i,j∈V。