[發明專利]一種用于物流配送領域的路徑優化方法

有效

• 申請號: 201510066971.0
• 申請日: 2015-02-09
• 公開（公告）號: CN104573880B
• 公開（公告）日: 2017-12-05
• 發明（設計）人: 杜磊;郭利平;耿彥峰;李雪蓮;王晉平
• 申請（專利權）人: 山西大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 太原科衛專利事務所(普通合伙)14100
• 代理人: 朱源

技術領域

本發明為一種用于物流配送領域的路徑優化方法，主要采用模擬退火算法計算大規模目的地的最短、最優路徑。采用該方法與系統，可顯著降低計算時間，具有極高的實用性，可應用于科學計算、物流配送等領域。

背景技術

在科學計算及日常生活中(例如物流配送問題)，經常會計算由某一地點出發，經過多個目的地返回，優化得到最短路徑的問題。在實際應用過程中，如果考慮到路徑的復雜性、多組合約束條件，當目的地數量一旦比較多的時候，問題的計算規模將變得非常龐大，傳統的貪心算法、蒙特卡洛算法、神經網絡算法等，都會面臨計算規模增大、計算時間變長等問題，導致計算效果很不理想。

發明內容

針對背景技術中存在的問題，本發明提供了一種用于物流配送領域的路徑優化方法，可以解決大規模目的地路徑優化問題，同時可處理多約條件的組合優化問題。通過系統的處理與計算，可顯著降低計算時間，具有極高的實用性，可應用于科學計算、物流配送等領域。

路徑優化問題是目前科學計算領域、物流配送等行業中非常重要的一類問題，也是一個復雜的組合優化問題，其中線路的優化需要進行多約束、多目標的決策，屬于路徑優化中的難點。特別是當約束條件較多、目的地數目非常多的情況下，問題的規模將變得非常龐大。

本發明為解決目前路徑優化中存在的當約束條件較多、目的地數目非常多的情況下，問題的規模將變得非常龐大導致計算時間非常長的技術問題，提供一種用于物流配送領域的路徑優化方法。

本發明所述的一種用于物流配送領域的路徑優化方法是采用以下技術方案實現的：一種用于物流配送領域的路徑優化方法,用以解決大規模目的地路徑優化問題，將這類問題的計算分為三個階段，稱為三級過程算法：

a)第一階段，首先通過路口、路口屬性的描述，應用堆優化Dijkstra算法，將出發點與所有目的地點、任意兩個目的地點之間的距離實現表格化，然后通過預先計算各點的距離并存儲；

b)第二階段，采用一種啟發式的模擬退火網格算法，結合約束條件，將大量的目的地點進行劃分或分組，形成一系列滿足約束條件的團簇；

c)第三階段，利用中國郵遞員問題算法，確定團簇內行走時的最短路徑和行走次序，最終計算得到面向所有目的地點的最優化路徑解。

圖1為本發明的工作流程圖。通過步驟a)可極大的優化計算時間；步驟b)形成一系列的團簇之后，此時滿足條件的團簇內的點數目已經較少，成功的降低了計算的規模。本發明通過步驟a)中的對路口、路口屬性的描述以及任意目的地之間距離的表格化描述，滿足了步驟b)中模擬退火網格算法的要求，使得分組更為科學合理，大大降低了計算量。

本發明的有益效果：本發明可應用于科學計算、物流配送等領域，通過三級過程算法，可顯著降低計算時間，具有極高的實用性。特別是面對大規模目的點(超過1萬個目的地)的計算時，本發明的辦法計算時間極短，計算效果佳，幾乎是唯一可行的處理方法。

附圖說明

圖1本發明工作流程圖。

圖2單連通路口的連通性描述示意圖。

圖3雙連通路口的連通性描述示意圖。

圖4三連通路口的連通性描述示意圖。

圖5四連通路口的連通性描述示意圖。

圖6實施例中目的地與路口的示意圖。

圖7實施例中目的地分組的示意圖。

具體實施方式

(1)在第一階段中，結合路口點的約束條件，構造各點間距離的鄰接矩陣

①路口、出發點、目的地等的連通性處理

在科學計算、物流配送問題中，無論出發點、目的地點總是由許多路徑連接構成，而路徑是由最基本的路口這一元素構成；為了準確的計算路徑，考慮到路口的約束條件，首先構建描述路口連通性的體系；

以物流問題為例，實際生活中的路口、道路，構成了連接出發點、目的地點的基本元素。每個路口均有一些約束條件(例如：路口的紅綠燈，是否可以允許掉頭、左轉燈)；

所述路口屬性信息的表示方式，可以準確的表示單連通、雙連通、三聯通、四聯通、…直到n連通的路口信息；以下都用0來表示路口，依次用1、2、3…n表示與其直接連接的其它路口，分別有以下幾種情況：

a)路口不能有孤立的，即沒有零連通的路口點；從實際道路情況看，路口一定在路上，即一定有別的路口點通過路與其相連；