[發(fā)明專利]基于改進(jì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
• 代理人: 王品華;朱紅星

技術(shù)領(lǐng)域

本發(fā)明屬于交通運(yùn)輸技術(shù)領(lǐng)域，特別涉及多時(shí)間窗的車輛路徑選擇方法，可用于對(duì)離散型和聚集型的多時(shí)間窗車輛路徑進(jìn)行調(diào)度。

背景技術(shù)

多時(shí)間窗車輛路徑問題是指車輛從配送中心出發(fā)服務(wù)客戶，需要在用戶提供若干個(gè)時(shí)間窗內(nèi)，選擇在唯一的一個(gè)時(shí)間窗內(nèi)抵達(dá)服務(wù)，要求每個(gè)客戶只能被一輛車服務(wù)且僅服務(wù)一次，路徑選擇目標(biāo)是使得在滿足用戶時(shí)間要求及車輛載荷有限等條件下成本最小。基于多時(shí)間窗的車輛路徑問題廣泛存在于當(dāng)今現(xiàn)實(shí)生活的物流運(yùn)輸之中，而國(guó)內(nèi)對(duì)于此問題的研究還較少且一般僅只能解決某種特殊類型的多時(shí)間窗車輛調(diào)度問題。

多時(shí)間窗車輛路徑問題是一個(gè)NP-Hard問題，這意味著在問題規(guī)模增大到一定數(shù)量時(shí)將很難或者根本無法求得問題的全局最優(yōu)解。采用精確算法雖然可以對(duì)小規(guī)模的多時(shí)間窗車輛調(diào)度問題得到最優(yōu)解，但卻不適用于求解現(xiàn)實(shí)中的大規(guī)模的多時(shí)間窗車輛調(diào)度問題。有些學(xué)者運(yùn)用序列插入啟發(fā)式算法求解多時(shí)間窗車輛路徑問題，雖然取得不錯(cuò)結(jié)果，但此種算法只能對(duì)聚集型或離散型多時(shí)間窗車輛路徑選擇起作用，而不能同時(shí)適用于兩種類型的多時(shí)間窗車輛路徑選擇。

發(fā)明內(nèi)容

本發(fā)明的目的在于針對(duì)上述已有技術(shù)的不足，提出一種基于萬有引力算法的多時(shí)間窗車輛路徑選擇方法，以同時(shí)對(duì)兩種類型的多時(shí)間窗車輛路徑進(jìn)行選擇。

實(shí)現(xiàn)本發(fā)明目的技術(shù)思路是對(duì)現(xiàn)有的萬有引力算法GSA進(jìn)行改進(jìn)，以有效解決離散型和聚集型多時(shí)間窗的車輛路徑問題，提高搜索能力，其技術(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）利用萬有引力算法尋優(yōu)：在t時(shí)刻，選取種群中適應(yīng)度值最好的m個(gè)個(gè)體，經(jīng)萬有引力作用使其施力于種群中的其他個(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)路徑。

本發(fā)明與現(xiàn)有技術(shù)相比具有以下優(yōu)點(diǎn)：

1、本發(fā)明通過聚類和改進(jìn)的萬有引力算法，能實(shí)現(xiàn)對(duì)離散型和聚集型的多時(shí)間窗車輛路徑選擇，而目前國(guó)內(nèi)對(duì)于多時(shí)間窗車輛路徑選擇問題的研究較少，且一般研究只能解決特定的一種類型的多時(shí)間窗車輛路徑問題。

2、本發(fā)明與現(xiàn)有的萬有引力算法相比較，表現(xiàn)出更強(qiáng)的搜索能力，而且有效性和實(shí)用性突出。

附圖說明

圖1是本發(fā)明的實(shí)現(xiàn)步驟流程圖。

具體實(shí)施方法：

參照?qǐng)D1，本發(fā)明的實(shí)現(xiàn)步驟如下：

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

步驟2、聚類分組