[發明專利]基于離散粒子群優化算法的智能物流配送

無效

• 申請號: 201010566908.0
• 申請日: 2010-11-29
• 公開（公告）號: CN102117441A
• 公開（公告）日: 2011-07-06
• 發明（設計）人: 張軍;龔月姣
• 申請（專利權）人: 中山大學
• 主分類號: G06Q10/00
• 分類號: G06Q10/00;G06Q50/00;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域：

本發明涉及智能計算和物流配送兩大領域，主要使用一種基于集合和概率的離散化粒子群優化算法對物流配送中的運輸車輛進行調度和路徑優化。

背景技術：

車輛路徑調度是物流配送研究中的一項重要內容，該問題的研究目標是，對一系列的顧客需求網點設計適當的路線，使車輛有序地通過，在滿足一定的約束條件下，達到一定的優化目標。其約束條件一般為：貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等，優化目標一般為：里程最短、費用最少、時間盡量少、車隊規模盡量小、車輛利用率高等。車輛路徑調度包含了經典NP難組合優化問題旅行商問題作為它的子問題，因此它也是NP難的。此外，帶時間窗的車輛路徑調度由于涉及了更多的約束條件，非常難解，目前已被證明甚至連找到一個可行解都是NP難的。

帶時間窗的車輛路徑調度，由于其更加地貼近物流公司的現實需求，在過去受到了廣泛關注，已有研究提出了不同的方法。過去的方法主要可以分為如下兩類：精確算法和近似算法。精確算法指可求出最優解的算法，如集分割和列生成算法、分支限界法、拉式松弛法、動態規劃法等。它們在求解時引入了嚴格的數學方法，能夠保證找到配送的最佳方案。但這類算法無法避開指數爆炸問題，只能有效求解小規模的物流配送。并且通常這些算法都是針對某一特定問題設計的，適用能力較差，因而在實際中其應用范圍很有限。隨著現代計算方法的發展，一些近似算法如局部搜索算法、禁忌搜索算法、模擬退火算法、遺傳算法等都被應用于求解車輛路徑規劃問題，能夠求解較大規模客戶網點的運輸車輛規劃，但它們存在著局部最優、算法參數魯棒性差等缺點。此外，蟻群優化算法作為一種天然地解決組合優化問題的方法，自然而然地被應用于車輛路徑規劃，也得到了較為優秀的結果。但蟻群優化算法存在計算過程復雜、收斂速度慢等缺點，仍具有一定局限性。粒子群優化算法作為智能計算領域的一種新興算法，它的算法性能在這幾年已經被廣泛認可，應用領域正在被不斷擴充。因此，近來也有研究人員嘗試用粒子群優化算法求解帶時間窗的車輛路徑調度問題，但這些研究僅僅是簡單地將連續空間的粒子位置取整來描述運送方案，求解效果較差。

發明內容：

為了克服既有的計算方式在計算速率不夠高、調度質量不佳、不適用于大規模物流配送等方面的問題，本發明提出一種能夠高效對運輸車輛進行調度和路徑規劃的離散粒子群優化算法，運用智能化的計算方法，在最小化所需運輸車輛數的同時也力求運輸的路徑最短，從而最大化地縮減物流配送商的運輸成本。

本發明解決其技術問題所采用的技術方案是：

(1)采用一種基于集合和概率的粒子編碼方式，使粒子群優化算法適用于解決離散的組合優化問題(車輛路徑調度屬于組合優化問題的一種)。組合優化問題，可以被定義為(S，f，Ω)，其中S表示所有可行解的集合，f是目標函數，Ω是約束條件。問題的目標就是在滿足約束Ω的條件下，找到一組可行解X^*∈S使得f最優化。在本發明所采用的離散粒子群算法中，一個組合優化問題(S，f，Ω)與如下特征相關聯：

●一個通用集合E，E可被劃分為n維，即E＝E¹∪E²∪...∪Eⁿ。

●一個候選解集合X∈S與通用集E相關聯。X∈E且X¹∈E¹，X²∈E²，...，Xⁿ∈Eⁿ。

●當X滿足約束條件Ω時，X為可行解。

●算法的目標就是找到一個使f最優化的可行解X^*。

根據如上定義，用粒子群優化算法求解一個組合優化問題的過程可以被認為是選擇一些元素構成通用集E的一個子集以優化目標函數的過程。