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

有效

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

技術領域

本發明屬于運輸智能領域，尤其涉及一種用于路徑規劃的隨機搜索算 法。

背景技術

路徑規劃問題是一個經典的組合優化問題，在工業領域中具有廣泛的 應用。例如城市中的灑水路由、垃圾收集、信件投遞、校車調度等問題均 看看作是路徑規劃問題。路徑規劃問題可看作是在給定的圖上構造若干條 回路，使得這些回路滿足一些特定的條件和約束并且路由這些回路的總消 耗最少。由于路徑規劃問題經常涉及到龐大的市場或巨額的資金，因此設 計有效的解決方法是非常有必要的。然而，經理論證明路徑規劃問題是一 個NP(非確定性多項式時間)難問題，即找到問題的全局最優解的時間隨 著問題規模的增長呈指數級增長。

很多成功的先例已經證明了在傳統的演化算法中加入局部搜索的概念 能夠在路徑規劃問題等這類NP難的組合優化問題表現出有效的性能。這 是因為路徑規劃問題的解空間很大并且復雜，加入局部搜索能夠加強算法 的收斂性從而在有限的時間內得到性能更好的解。然而，這些方法都有一 個共有的缺陷，那就是它們均采用了傳統的小步長局部搜索，在局部搜索 的每一步，只能產生與當前解極為相似的解。這樣在某些情況下，例如問 題的解空間較大或者容量約束較嚴格導致解空間由大量分散的可行區域組 成的情況下，用傳統的小步長局部搜索將不能達到理想的結果。在前一種 情況下，從當前解可能需要很多步局部搜索才能達到全局最優解，而在后 一種情況下，傳統的小步長局部搜索可能導致搜索無法越過可行區域之間 的非可行區域從而跳出當前的局部最優解。

因此確定算法只能適用于小規模的路徑規劃問題，而無法適用于在實 際中常常出現的中等或大規模問題。

發明內容

本發明的目的旨在至少解決現有技術中的上述問題之一。

為此，本發明的實施例提出一種更有效的用于路徑規劃的搜索方法。

根據本發明的一個方面，本發明實施例提出了一種用于路徑規劃的搜 索方法，所述搜索方法包括以下步驟：a)對對應路徑圖的路徑規劃方案的 種群中各個個體進行初始化，其中每個個體S包括按照所述路徑圖對各個 車輛規劃的任務回路序列，每個任務回路中包括一個車輛對應的回路任務 序列；b)對每個個體S依次執行傳統步長的局部搜索和大于所述傳統步長 的可變步長局部搜索，以獲得對應的局部最優解個體S’；c)根據每個個體 對應的所有回路總消耗和/或每個個體違背容量約束的程度對所有的局部 最優解個體S’進行排序；以及d)根據所述排序確定所述路徑圖的最優路 徑規劃方案。

根據本發明進一步的實施例，所述步驟a包括：對所述路徑圖對應的 所有任務邊進行編號，其中每個任務邊以其對應的兩個端點表示；以及對 于每個車輛對應的回路任務序列，從所有任務邊的未選取任務編號中選擇 可在不違反容量約束條件的條件下插入對應序列的任務編號。

根據本發明進一步的實施例，所述步驟b包括：首先對每個個體S執 行所述傳統步長的局部搜索，獲得對應的第一局部最優解個體S1；對每個 第一局部最優解個體S1執行所述可變步長的局部搜索，獲得對應的第二局 部最優解個體S2；以及再次對每個第二局部最優解個體S2執行所述傳統 步長的局部搜索，獲得所述對應的局部最優解個體S’。

根據本發明進一步的實施例，所述可變步長局部搜索包括：從每個個 體包含的任務回路序列中選擇部分任務回路，并將所述部分任務回路對應 的車輛回路任務序列融合為一個任務序列；按照所選任務不違背容量約束 且任務之間距離最近的條件，從所述融合任務序列依次選擇任務進行排序； 利用Ulusoy劃分算法將所述排序的任務重新劃分為回路，以使得重新劃分 后每個回路產生的額外消耗最小；以及以所述重新劃分的回路來替換所述 部分任務回路。

根據本發明再一步的實施例，若每次選擇時存在多個任務滿足所述條 件，進一步利用下面多個規則中至少一個比較所述多個任務以選擇一個任 務進行當前排序；所述多個規則包括：1.最大化任務與倉庫之間的距離； 2.最小化任務與倉庫之間的距離；3.最大化任務的需求量與服務消耗之比； 和4.最小化任務的需求量與服務消耗之比。進一步地，若當前排序中任務 的總需求量小于容量的一半，采取所述規則1；否則采取所述規則2。