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

有效

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

1.一種應用于物流配送領域的路徑優化方法,用以解決物流配送中大規模目的地路徑優化問題，其特征在于，將這類問題的計算分為三個階段，稱為三級過程算法：

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

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

c)第三階段，利用中國郵遞員問題算法，確定團簇內行走時的最短路徑和行走次序，最終計算得到面向所有目的地點的最優化路徑解；(1)在第一階段中，結合路口點的約束條件，構造各點間距離的鄰接矩陣

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

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

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

a)路口不能有孤立的，即沒有零連通的路口點；

b)單連通的路口點的表示：路口點的單連通相當于1條路的終點，設0為需描述的該路口點，1表示與其相連接的另一路口點；單連通的點僅能與另外的一個點連通，即單連通的點可以表示為：1→0→1；

c)雙連通的路口點的表示：雙連通的路口點可以與其它一共2個路口點連通，設0表示需描述的該路口點，1、2表示與其相連的另兩個路口點，則其通過性可描述為：1→0→1，1→0→2，2→0→1，2→0→2這四種情況，則使用一個長度為4的字符串可以表示該路口的通過性信息，字符串中1表示通，0表示不通；

d)三連通的路口點的表示：三連通的路口點可以與其它一共3個路口點連通，用0表示需描述的該路口點，1、2、3表示與其相連的另兩個路口點，則其通過性可描述為：1→0→1，1→0→2，1→0→3；2→0→1，2→0→2，2→0→3；3→0→1，3→0→2，3→0→3；則使用一個長度為9的字符串可以表示該路口的通過性信息；

e)四連通的路口點的表示：四連通的路口點可以與其它一共4個路口點連通，用0表示需描述的該路口點，1、2、3、4表示與其相連的另兩個路口點，則其通過性可描述為：1→0→1，1→0→2，1→0→3，1→0→4；2→0→1，2→0→2，2→0→3，2→0→4；3→0→1，3→0→2，3→0→3，3→0→4；4→0→1，4→0→2，4→0→3，4→0→4；則使用一個長度為16的字符串可以表示該路口的通過性信息；

f)依此類推，對應n連通的點，點本身標記為0，與其相連通的n個點，分別標記為1、2、3、4、5……n，則其通過性可以用一個n×n的矩陣表示；用長度為n²的字符串即可描述其通過性；字符串的排列方式為由左向右開始排列，如下所示：

n×n矩陣：

矩陣中的每個位置的元素分別為0、1、2、3、4、5…n；采用不同的數字表示不同的通過性，先排列矩陣的第一行對應的字符，再排第二行字符，一直繼續，直到排列矩陣的第n行，得到一個由n²字符構成的一個字符串來描述該路口的連通性；

②路口數據屬性描述

所述路口信息的數據存儲方式，包括數據表，數據表中有以下幾項：唯一ID；X；Y；Z；Connection；Describe；唯一ID表示路口的唯一編號；X；Y；Z；分別表示路口的X坐標、Y坐標、Z坐標；Connection表示與路口相連接的其它路口的ID；Describe表示連通性描述字符串；

③出發點、目的地距離表的計算與生成

計算過程中，關鍵是要得到路口與路口之間的距離，通過第一階段路口的連通性處理及路口的自身屬性，借助堆優化Dijkstra算法，可以快速計算出兩點之間的最短路徑距離，最終可以求得出發點到每個目的地點的距離、各個目的地點之間的距離，構成一個出發地、目的地距離表；

(2)模擬退火計算團簇

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

①定義目標函數與約束條件

不同的路徑優化計算過程，目標函數與約束條件都不一樣，根據具體的問題設定具體的目標函數與約束條件都可以進行計算；

②隨機構建初始隨機解

根據具體的約束條件和目標函數構建一個隨機的初始解：先將目標團簇分為多個組，然后將任意目的地分到各個組中；顯然初始解的效果是不理想的，下一步開始用模擬退火進行交換，以求得滿意解；具體如下：設有具體的路徑優化計算為，從起始點S出發，一共有N個配送目的地，分別是D1、D2、D3、…、DN；

約束條件為：每次配送，從S出發最多只能經過n個點；

目標函數為：配送總路徑最短，即：式中S₁表示從出發點到本次行走第一個目的地點的距離，S₂表示從最后一個目的地點返回出發點的距離，L_ij表示從第i個目的地點到第j個目的地點的距離；用α描述這是第α次行走；

于是構建一個隨機的初始解：先將目標團簇分為η組：η＝INT(N/n)+1，然后將任意目的地分到各個組中；顯然初始解的效果是不理想的，下一步開始用模擬退火進行交換，以求得滿意解；

③采用模擬退火法進行降溫計算，在每個溫度下，進行目的地交換計算，計算規則如下:

a)先確定團簇內交換和團簇間交換的份額β，β＝0.8，產生一個隨機數rnd，若rnd≤β，則進行團簇內交換；若rnd＞β，則進行團簇間交換；

b)采用Metropolis判據e^{-|tagetValueDelta|/T}＞rnd判斷上述交換是否接受，其中targetValueDelta為上一輪目標值和本輪目標值的差，T為本輪溫度，rnd是0-1間的隨機數；

c)通過設定改進迭代和非改進迭代的次數，來限制上述過程中的交換；在某一溫度下隨機進行組內交換或組間交換后，可能導致目標值降低，那么本次交換叫做一次改進迭代，否則叫非改進迭代；

(3)第三階段，利用中國郵遞員問題算法，確定團簇內行走時的最短路徑和行走次序

通過第二階段交換的完成，可以形成一定量相對最優解的團簇；然后，在團簇內部進行郵遞員問題計算行走，以求得團簇內的最優行走順序；因為此時滿足約束條件和目標解的團簇內部目的地點已經比較少，可以通過貪心算法，用郵遞員問題算法最終計算得到面向所有目的地點的最優化路徑解；所述目的地為實體商店，每個商店的訂貨量不同，但每次配送車輛的裝載量是固定的，故約束條件為：其中X_i為各個商店的訂貨量，σ為車輛的最大裝載量。