[發(fā)明專利]基于改進(jìn)萬(wàn)有引力算法的多時(shí)間窗車輛路徑選擇方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310470013.0
• 申請(qǐng)日: 2013-09-21
• 公開（公告）號(hào): CN103530699A
• 公開（公告）日: 2014-01-22
• 發(fā)明（設(shè)計(jì)）人: 高淑萍;屈明恩;梁原
• 申請(qǐng)（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06Q50/28
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 王品華;朱紅星

1.一種基于改進(jìn)萬(wàn)有引力算法的多時(shí)間窗車輛路徑選擇方法，包括如下步驟：

（1）輸入客戶分布位置情況,車場(chǎng)中的車輛數(shù)M，下層迭代次數(shù)D和上層調(diào)整次數(shù)U，對(duì)客戶進(jìn)行快速聚類處理，即隨機(jī)選擇M個(gè)點(diǎn)作為聚類中心，設(shè)聚類調(diào)整次數(shù)I＝1；

（2）聚類分組：對(duì)每輛車進(jìn)行編號(hào)，令第一輛車的序號(hào)k＝1；以車場(chǎng)為中心，根據(jù)聚類中心，將客戶分布區(qū)域分為車輛數(shù)個(gè)片區(qū)，確定每輛車服務(wù)的客戶集合；

（3）初始化種群：記第k輛車服務(wù)的客戶集為一個(gè)種群，在t＝0時(shí)刻，初始化該種群中每個(gè)個(gè)體的空間位置；

（4）利用萬(wàn)有引力算法尋優(yōu)：在t時(shí)刻，選取種群中適應(yīng)度值最好的m個(gè)個(gè)體，經(jīng)萬(wàn)有引力作用使其施力于種群中的其他個(gè)體，然后更新一次個(gè)體速度和個(gè)體位置，得到T＝t+1時(shí)刻種群初始速度和位置，令t＝t+1；

（5）局部搜索：

（5a）對(duì)更新后的種群中每個(gè)個(gè)體進(jìn)行一次交叉操作，得到一個(gè)臨時(shí)種群，再對(duì)臨時(shí)種群中每個(gè)個(gè)體執(zhí)行邊界約束檢查，若該種群中存在目標(biāo)值優(yōu)于初始個(gè)體目標(biāo)值的個(gè)體，則用其替換初始個(gè)體，否則種群中每個(gè)個(gè)體的位置不變；

（5b）比較T與下層迭代次數(shù)D，若T≤D,返回步驟（4）；否則，記錄第k輛車的最優(yōu)路徑、路徑長(zhǎng)及遲到時(shí)間；

（6）下層終止判斷：將車輛序號(hào)k+1與車輛數(shù)M進(jìn)行比較，若(k+1)≤M，則返回步驟（3）；否則，計(jì)算當(dāng)前分組下尋得的最優(yōu)個(gè)體，并將該最優(yōu)個(gè)體與種群中已知最優(yōu)個(gè)體相比較，若當(dāng)前分組下尋得的最優(yōu)個(gè)體的目標(biāo)函數(shù)值小于種群中已知最優(yōu)個(gè)體的目標(biāo)函數(shù)值，則用當(dāng)前分組下尋得的最優(yōu)個(gè)體替換種群中已知最優(yōu)個(gè)體；否則，保持種群中已知最優(yōu)個(gè)體不變；

（7）上層終止判斷：將聚類調(diào)整次數(shù)I+1與上層調(diào)整次數(shù)U進(jìn)行比較，若(I+1)≤U，則對(duì)輸入的客戶重新進(jìn)行聚類，確定聚類中心，并返回步驟（2）；否則，停止聚類，并返回記錄的已知最優(yōu)路徑、路徑長(zhǎng)及遲到時(shí)間，該路徑即為所選多時(shí)間窗車輛路徑的最優(yōu)路徑。

2.根據(jù)權(quán)利要求1所述的基于改進(jìn)萬(wàn)有引力算法的多時(shí)間窗車輛路徑選擇方法，其中所述步驟（3）中初始化種群中每個(gè)個(gè)體的空間位置，按如下公式進(jìn)行：

pji=(b-a)R+a,pji∈[a,b],i=1,2,...,L,j=1,2,...,Nk]]>

其中，是第i個(gè)個(gè)體在第j維空間的位置坐標(biāo)，R是[0,1]內(nèi)的隨機(jī)數(shù)，L為種群規(guī)模，k表示車輛編號(hào)，N_k表示第k輛車服務(wù)客戶數(shù)目，[a,b]為空間范圍。

3.根據(jù)權(quán)利要求1所述的基于改進(jìn)萬(wàn)有引力算法的多時(shí)間窗車輛路徑選擇方法，其中步驟（4）所述的更新一次個(gè)體速度和個(gè)體位置，按如下公式進(jìn)行：

vid(t+1)=R×vid(t)+aid(t),pid(t+1)=pid(t)+vid(t+1)]]>

其中，(t)為t時(shí)刻個(gè)體i在第d維空間中的速度，(t)為t時(shí)刻個(gè)體i在第d維空間中的加速度，(t)為t時(shí)刻個(gè)體i在第d維空間中的位置，R是[0,1]內(nèi)的隨機(jī)數(shù)。