[發(fā)明專利]一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)算法的車輛路徑優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201911116073.6
• 申請(qǐng)日: 2019-11-15
• 公開（公告）號(hào): CN110956311B
• 公開（公告）日: 2023-04-07
• 發(fā)明（設(shè)計(jì)）人: 張景玲;馮勤炳;余孟凡
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06Q10/047
• 分類號(hào): G06Q10/047;G06N3/006;G06Q10/0835
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司 33241
• 代理人: 王利強(qiáng)

1.一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)算法的車輛路徑優(yōu)化方法，其特征在于，所述方法包括以下步驟：

步驟1車輛路徑問題分析，采用Augerat’s?instances數(shù)據(jù)集，車輛路徑問題的成本矩陣的元素是歐幾里得距離；假定配送中心設(shè)為P＝0，客戶點(diǎn)設(shè)為i，客戶點(diǎn)總數(shù)設(shè)為L(zhǎng)，i∈L，最多車輛數(shù)設(shè)為K，每輛車具有相同載重量為q，每個(gè)客戶點(diǎn)需求量設(shè)為d_i，客戶點(diǎn)i到客戶點(diǎn)j的距離設(shè)為c_ij，優(yōu)化的目標(biāo)是行駛距離最短，一個(gè)完整的解包含了全部路徑的集合；

步驟2初始化，先生成Npop組個(gè)體的種群，得到最小路徑，利用聚類思想劃分，h塊區(qū)域，得KC塊，由KC塊隨機(jī)挑選生成可行解組p，可行解組p的元素p_i＝p₁,p₂,p₃,…,p_NP，計(jì)算種群適應(yīng)度f，種群適應(yīng)度f的元素f_i＝f₁,f₂,f₃,…,f_NP；隨機(jī)挑選一組可行解p_i以及對(duì)應(yīng)適應(yīng)度值f_i，設(shè)p_b為最優(yōu)解個(gè)體，f_b為最優(yōu)適應(yīng)度值，設(shè)LLH算子數(shù)量為N^A，初始化p_b＝p_i，f_b＝f_i，State＝0，Action＝random(N^A)，其中Action取值為1至N^A中的任何一個(gè)整數(shù)，表示從范圍1至N^A隨機(jī)挑選一個(gè)整數(shù)作為Action的值；

步驟3經(jīng)驗(yàn)池、序列池存儲(chǔ)，操作上步Action＝random(N^A)后，產(chǎn)生的個(gè)體為Ind，適應(yīng)度值為fit，根據(jù)適應(yīng)度值，判斷立即回報(bào)值Reward，此時(shí)狀態(tài)即為“下一個(gè)狀態(tài)”，判斷該State和State^t所屬狀態(tài)，利用式(1)計(jì)算State^t值：

State^t＝-(fit-fit')/fit'+Ck?????(1)

設(shè)由EP代表經(jīng)驗(yàn)池，將上述值存入，則EP_nE＝[State,Action,Reward,State^t]，nE代表經(jīng)驗(yàn)池中數(shù)據(jù)組數(shù)；當(dāng)達(dá)到設(shè)定次數(shù)后，判斷此時(shí)State值所屬狀態(tài)，如果為15≤State≤25，則此時(shí)Action為路徑內(nèi)算子，對(duì)此時(shí)的序列進(jìn)行篩選，質(zhì)量?jī)?yōu)則存入SP，SP代表序列池，反之，則更新序列；SP設(shè)常量Q_sp為容量，且每次對(duì)比SP中序列，若此時(shí)序列在SP中有對(duì)應(yīng)序列集，則SP中序列計(jì)數(shù)一次，當(dāng)SP容量已滿，則刷新對(duì)比次數(shù)最少的序列；

步驟4解的接受保留，判斷，如果fitfit′，則說明此時(shí)解的適應(yīng)度值更好，則保存解及解的適應(yīng)度值，令State＝State^t，fit′＝fit；如果fit≥fit′，則采用模擬退火判別，隨機(jī)產(chǎn)生一個(gè)值，若退火概率p隨機(jī)值，則同樣保留好解，同時(shí)更新狀態(tài)，反之，則舍去該解，此時(shí)State^t＝State，fit′＝fit′；

步驟5判斷經(jīng)驗(yàn)池容量，判斷經(jīng)驗(yàn)池內(nèi)組數(shù)nE，nE≥N^E，則進(jìn)入步驟8學(xué)習(xí)環(huán)節(jié)，否則，進(jìn)入步驟6選擇Action步驟；

步驟6選擇Action，設(shè)置epsilon值，若隨機(jī)值epsilon，將State值輸入估值網(wǎng)絡(luò)，輸出Q_e值，取max(Q_e)所對(duì)應(yīng)的Action，若隨機(jī)值epsilon，則根據(jù)此時(shí)State值，令A(yù)ction＝random(N^A)，此時(shí)N^A為對(duì)應(yīng)State值的算子序號(hào)；

步驟7保留最優(yōu)解，若fit≤f_b，f_b＝fit，p_b＝Ind，反之則舍棄；

步驟8選擇學(xué)習(xí)樣本，并初始化神經(jīng)網(wǎng)絡(luò)，從EP中隨機(jī)挑選N^S組，作為學(xué)習(xí)樣本，記為ESP，初始化估值網(wǎng)絡(luò)和目標(biāo)值網(wǎng)絡(luò)的閾值ω_e、ω_t與估值網(wǎng)絡(luò)和目標(biāo)值網(wǎng)絡(luò)的權(quán)值b_e、b_t；

步驟9神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)更新，估值網(wǎng)絡(luò)中輸入為ESP樣本中第nS個(gè)樣本中的State值，計(jì)算后取目標(biāo)值網(wǎng)絡(luò)中輸入利用式(2)，計(jì)算損失值Loss，更新估值網(wǎng)絡(luò)的閾值ω_e和權(quán)值b_e；

γ是折扣率；

步驟10更新目標(biāo)值網(wǎng)絡(luò)，判斷學(xué)習(xí)代數(shù)Ln≥LN，則令ω_t、b_t替代ω_e、b_e的值；

步驟11判斷學(xué)習(xí)結(jié)束情況，若學(xué)習(xí)代數(shù)Ln≤(3/4)*N^S，則進(jìn)入步驟8繼續(xù)學(xué)習(xí)更新，反之，則進(jìn)入步驟6選擇Action，返回主循環(huán)；

步驟12程序結(jié)束，輸出車輛路徑距離最優(yōu)值及最優(yōu)值路徑序列。

2.如權(quán)利要求1所述的一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)算法的車輛路徑優(yōu)化方法，其特征在于，所述步驟2中，生成初始種群組的過程如下：

2.1)對(duì)于其中任意一條路徑，先設(shè)配送中心點(diǎn)為P＝0，即該路徑兩端點(diǎn)都記為0；隨機(jī)從L個(gè)客戶點(diǎn)中挑選部分客戶點(diǎn)，加入該路徑的首尾兩端點(diǎn)中間，判斷該車輛現(xiàn)載重量情況；

2.2)從剩下的客戶點(diǎn)中繼續(xù)隨機(jī)挑選，依次加入路線，直到超出標(biāo)準(zhǔn)載重量，則產(chǎn)生第二條路徑；將超出標(biāo)準(zhǔn)載重量的點(diǎn)，加入新路線中；重復(fù)循環(huán)，當(dāng)所有客戶點(diǎn)都被選取，則一個(gè)初始種群個(gè)體生成；

2.3)多次進(jìn)行上述操作，生成設(shè)定數(shù)量個(gè)體的種群，數(shù)量為Npop，對(duì)Npop個(gè)個(gè)體進(jìn)行路徑判斷，選出具有最短路徑數(shù)的個(gè)體，記最短路徑數(shù)為n，將n作為劃分塊的數(shù)量；

2.4)計(jì)算所有客戶點(diǎn)與倉(cāng)庫(kù)點(diǎn)的距離c_i0，為了節(jié)省聚類分類的時(shí)間，將c_i0升序排列，只取前m個(gè)點(diǎn)作為聚類中心點(diǎn)，設(shè)聚類中心點(diǎn)為L(zhǎng)^KC，KC＝1,2,3,…,m，KC代表聚類塊，以除聚類中心點(diǎn)外的其他客戶點(diǎn)，與各聚類中心的距離最短為原則，進(jìn)行聚類；

2.5)隨機(jī)排列KC塊，按車輛載重量分配，依KC塊排列順序，隨機(jī)挑選客戶，若KC塊中客戶點(diǎn)未能滿足第k車輛載重，則向KC+1塊中隨機(jī)抽取客戶點(diǎn)，直至達(dá)到第k輛車載重要求，反之則向后延用至k+1輛車，共組成n條路徑，由此產(chǎn)生一個(gè)初始解個(gè)體。