[發(fā)明專(zhuān)利]基于啟發(fā)式策略的帶容量約束車(chē)輛路由問(wèn)題的優(yōu)化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810095693.5
• 申請(qǐng)日: 2018-01-31
• 公開(kāi)（公告）號(hào): CN108364070A
• 公開(kāi)（公告）日: 2018-08-03
• 發(fā)明（設(shè)計(jì)）人: 王竹榮;李猷;黑新宏
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安理工大學(xué)
• 主分類(lèi)號(hào): G06N3/12
• 分類(lèi)號(hào): G06N3/12;G06Q10/04
• 代理公司: 西安弘理專(zhuān)利事務(wù)所 61214
• 代理人: 許志蛟

1.基于啟發(fā)式策略的帶容量約束車(chē)輛路由問(wèn)題的優(yōu)化方法，其特征在于，包括以下步驟：

步驟1，對(duì)給定的圖問(wèn)題G＝{V,E}，V是頂點(diǎn)集合，E是邊的集合，建立頂點(diǎn)對(duì)的關(guān)聯(lián)系數(shù)矩陣CoefM；

步驟2，對(duì)于步驟1圖問(wèn)題中所求問(wèn)題，統(tǒng)計(jì)現(xiàn)有方法得到最好解，并計(jì)算最好解包含邊的位序秩，構(gòu)建關(guān)鍵模式數(shù)據(jù)庫(kù)；

步驟3，按隨機(jī)方式生成所求問(wèn)題的初始解種群、并記錄最好解個(gè)體x_best，具體為：

按隨機(jī)方式生成步驟1圖問(wèn)題中所求問(wèn)題的初始解種群，并計(jì)算初始解種群中個(gè)體x的適應(yīng)值，按個(gè)體x適應(yīng)值進(jìn)行排序，并記錄當(dāng)前的最好解個(gè)體x_best；

步驟4，對(duì)種群中每一個(gè)體x執(zhí)行模式運(yùn)算操作，得到生成的子個(gè)體x'；

步驟5，通過(guò)對(duì)比每一個(gè)體x與步驟4中生成的子個(gè)體x'，更新步驟2中關(guān)鍵模式數(shù)據(jù)庫(kù)信息；

步驟6，重復(fù)步驟4和步驟5，直到步驟3的初始解種群中所有解個(gè)體x質(zhì)量不再發(fā)生變化，則輸出所求問(wèn)題的最好解，計(jì)算結(jié)束。

2.根據(jù)權(quán)利要求1所述的基于啟發(fā)式策略的帶容量約束車(chē)輛路由問(wèn)題的優(yōu)化方法，其特征在于，所述步驟1具體為：

步驟1.1，根據(jù)Dijkstra算法計(jì)算圖問(wèn)題中任意頂點(diǎn)v_i到其它頂點(diǎn)v_j的最短距離md(v_i,v_j)，

步驟1.2，針對(duì)每一個(gè)頂點(diǎn)，按照步驟1.1的方法計(jì)算出到其他頂點(diǎn)的距離，并按照距離值大小由小到大進(jìn)行排序；

步驟1.3，依據(jù)步驟1.2中排序的距離值給相應(yīng)的頂點(diǎn)對(duì)(v_i,v_j)分配序號(hào)值rak(v_i,v_j)，對(duì)序號(hào)值rak(v_i,v_j)按照距離值由小到大分別取值為1，2，3，...，其中相同的距離值取相同的序號(hào)值；

步驟1.4，對(duì)步驟1.1中任意頂點(diǎn)v_i及步驟1.3的序號(hào)值建立頂點(diǎn)對(duì)關(guān)聯(lián)系數(shù)矩陣CoefM，

其中為n整數(shù)且n≥1。

3.根據(jù)權(quán)利要求1所述的基于啟發(fā)式策略的帶容量約束車(chē)輛路由問(wèn)題的優(yōu)化方法，其特征在于，所述步驟2具體為：

步驟2.1，對(duì)最好解包含邊進(jìn)行分解，計(jì)算任意一邊e_i的位序秩RankCount(e_i)，如公式(3)所示；

RankCount(e_i)＝rak(v(e_{i_left}),v(e_{i_pre_right}))+rak(v(e_{i_right}),v(e_{i_next_left})) (3)

其中v(e_{i_left})和v(e_{i_right})分別表示最好解任意一邊e_i的左邊頂點(diǎn)和右邊頂點(diǎn)，v(e_{i_pre_right})和v(e_{i_next_left})分別表示最好解任意一邊e_i的前一條邊的右頂點(diǎn)和后一條邊的左頂點(diǎn)；

步驟2.2，將步驟2.1中最好解中具有較小位序秩值的邊及其關(guān)聯(lián)的邊包含的模式信息作為所求問(wèn)題初始優(yōu)良基因庫(kù)信息，建立關(guān)鍵模式數(shù)據(jù)庫(kù)。