[發明專利]用于路徑規劃的搜索方法

有效

• 申請號: 200910161350.5
• 申請日: 2009-07-31
• 公開（公告）號: CN101650805A
• 公開（公告）日: 2010-02-17
• 發明（設計）人: 梅一;唐珂;姚新;傅浩波
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06Q10/00
• 分類號: G06Q10/00;G06Q50/00;G06N3/00
• 代理公司: 北京市立方律師事務所
• 代理人: 張 磊

1.一種用于路徑規劃的搜索方法，其特征在于，所述搜索方 法包括以下步驟：

a)對對應路徑圖的路徑規劃方案的種群中各個個體進行初始 化，其中每個個體S包括按照所述路徑圖對各個車輛規劃的任務 回路序列，每個任務回路中包括一個車輛對應的回路任務序列；

b)對每個個體S依次執行傳統步長的局部搜索和大于所述傳 統步長的可變步長局部搜索，以獲得對應的局部最優解個體S’；

c)根據每個個體對應的所有回路總消耗和/或每個個體違背 容量約束的程度對所有的局部最優解個體S’進行排序；以及

d)根據所述排序確定所述路徑圖的最優路徑規劃方案。

2.如權利要求1所述的搜索方法，其特征在于，所述步驟a 包括：

對所述路徑圖對應的所有任務邊進行編號，其中每個任務邊 以其對應的兩個端點表示；以及

對于每個車輛對應的回路任務序列，從所有任務邊的未選取 任務編號中選擇可在不違反容量約束條件的條件下插入對應序列 的任務編號。

3.如權利要求1所述的搜索方法，其特征在于，所述步驟b 包括：

首先對每個個體S執行所述傳統步長的局部搜索，獲得對應 的第一局部最優解個體S1；

對每個第一局部最優解個體S1執行所述可變步長的局部搜 索，獲得對應的第二局部最優解個體S2；以及

再次對每個第二局部最優解個體S2執行所述傳統步長的局部 搜索，獲得所述對應的局部最優解個體S’。

4.如權利要求1或3所述的搜索方法，其特征在于，所述可 變步長局部搜索包括：

從每個個體包含的任務回路序列中選擇部分任務回路，并將 所述部分任務回路對應的車輛回路任務序列融合為一個任務序 列；

按照所選任務不違背容量約束且任務之間距離最近的條件， 從所述融合任務序列依次選擇任務進行排序；

利用Ulusoy劃分算法將所述排序的任務重新劃分為回路，以 使得重新劃分后每個回路產生的額外消耗最小；以及

以所述重新劃分的回路來替換所述部分任務回路。

5.如權利要求4所述的搜索方法，其特征在于，若每次選擇 時存在多個任務滿足所述條件，進一步利用下面多個規則中至少 一個比較所述多個任務以選擇一個任務進行當前排序；

所述多個規則包括：1.最大化任務與倉庫之間的距離；2.最小 化任務與倉庫之間的距離；3.最大化任務的需求量與服務消耗之 比；和4.最小化任務的需求量與服務消耗之比。

6.如權利要求5所述的搜索方法，其特征在于，若當前排序 中任務的總需求量小于容量的一半，采取所述規則1；否則采取所 述規則2。

7.如權利要求1所述的搜索方法，其特征在于，在所述步驟 b之前還包括：

利用每個個體S交叉生成不同于個體S的后代群體；

分別計算所述后代群體的每個個體與所有個體S之間的距離；

按照所述后代群體的每個個體距離個體S的距離最小值排序 選擇所述后代群體的部分個體來替代個體S。

8.如權利要求7所述的搜索方法，其特征在于，所述距離為 兩個個體分別對應的任務鄰接矩陣之間的距離。

9.如權利要求7所述的搜索方法，其特征在于，所述步驟c 包括：

將所述后代群體的部分個體與所述局部最優解個體S’進行 合并；以及

對所述合并的個體進行排序。

10.如權利要求1或9所述的搜索方法，其特征在于，所述 排序步驟c包括：

計算每個個體的違背容量約束的程度和每個個體對應的所有 回路總消耗；

在比較任意兩個個體時，若其對應的違背容量約束的程度為 零，則根據其對應的所有回路總消耗大小排序；

若其對應的違背容量約束的程度大于零，則根據以預定概率 比較其對應的違背容量約束的程度和以預定概率比較其對應的所 有回路總消耗來進行排序。