一種面向物流的動態路徑規劃方法與流程

2023-10-20 10:34:57 1

本發明涉及一種面向物流的動態路徑規劃方法，屬於物流配送技術領域。

背景技術：

隨著網際網路的不斷普及推動了物流行業的發展，而其中物流配送是物流系統中的重要環節之一，配送效率的高低直接影響到整個物流網絡效率的高低，同樣也關係到許多相關行業競爭力的強弱。配送環節的核心是針對路網對配送點進行逐一的配送，這其中選擇何種路線進行配送直接影響到配送成本。配送成本的增加不僅僅體現在運力的浪費上，還體現在線路的錯誤選擇上，這些浪費直接導致的結果就是配送效率低、配送成本高。同時，在實際的配送過程中，常常會受到交通管理、交通事故、天氣變化、上下班高峰期等因素的影響，都會使配送車輛的行駛時間增加。所以根據實際路網的信息怎樣選擇一條配送時間以及行程相對較短的路線，是目前物流配送需要解決的問題。

物流配送車輛路徑問題(vehicleroutingproblem，vrp)，最早是由danting和ramser於1959年首次提出的，並且很快就在運籌學、管理學、計算機應用、圖論等學科中得到了運用。具體來說就是，就是在客戶需求已知的情況下，確定車輛在各個客戶間的行程路線，使得運輸路線最短或者運輸成本最低。通過研究vrp可以合理使用調用工具，優化運輸路線，降低企業物流成本。目前，隨著全球定位系統、地理信息技術以及4g時代的到來，使得智能交通系統日益完善，實時獲取交通信息已成為可能。所以vrp在解決實時路網的物流配送中還存在以下問題：

1、vrp中大多數學者考慮的信息往往都是靜態的，即任意兩個節點之間的行駛時間固定不變。但是在實際物流配送中配送車輛在配送點路段之間的配送時間往往會受到交通事故、天氣變化、上下班高峰期等因素的影響，從而導致配送車輛陷入城市擁擠的交通環境中。

2、同樣，傳統的vrp在配送過程中，一般配送點的個數是固定不變的。然而在實際配送過中，配送車輛在配送過程中可能會動態的增減配送點的需求，目前針對這種情況的需求求解辦法相對較少。

3、目前用於求解vrp的智能算法往往需要較長的計算時間，而在實際物流配送過程中，結合實際的路網信息，需要在短時間內規劃出最優路徑。

技術實現要素：

本發明所要解決的技術問題是：提供一種面向物流的動態路徑規劃方法，採用結合了二邊逐次修正法的遺傳算法進行物流配送的路線規劃，車輛在行駛過程中每到達一個配送點之後，根據接收到的交通信息以及當前配送點的個數進行路線的更新。

本發明為解決上述技術問題採用以下技術方案：

一種面向物流的動態路徑規劃方法，包括如下步驟：

步驟1，初始化l＝0；

步驟2，根據當前所有配送點n，隨機獲得k組各不相同、且分別由n個配送點所構成的配送點排列，每一組配送點排列代表一個配送序列即配送路線，其中，n為大於等於2的整數，k為偶數，且表示n個配送點所組成的配送點排列的總數；

步驟3，採用二邊逐次修正法對每條配送路線進行優化，並用優化之後的替代原先的配送路線；

步驟4，對所有的配送路線進行交叉、變異、選擇操作；具體步驟如下：

步驟41，初始化v＝1；

步驟42，隨機生成一個0～1之間的隨機數，判斷該隨機數是否小於等於交叉概率閾值pc，是則進入步驟43；否則進入步驟44；

步驟43，在k個配送序列中，隨機挑選兩個配送序列，並對這兩個配送序列進行交叉操作，產生兩個新的配送序列，將這兩個新的配送序列添加到步驟3得到的配送序列中，然後進入步驟44；

步驟44，判斷v是否等於是則進入步驟45；否則用v的值加1對v進行更新，並返回步驟42；

步驟45，初始化u＝1；

步驟46，隨機生成一個0～1之間的隨機數，判斷該隨機數是否小於等於變異概率閾值pm，是則進入步驟47；否則進入步驟48；

步驟47，在k個配送序列中，隨機挑選一個配送序列，並對該配送序列進行變異操作，產生一個新的配送序列，將這個新的配送序列添加到步驟3得到的配送序列中，然後進入步驟48；

步驟48，判斷u是否等於k，是則進入步驟49；否則用u的值加1對u進行更新，並返回步驟46；

步驟49，經過交叉和變異操作產生的配送序列加上原來的k個配送序列，共k+k*(pc+pm)個配送序列，根據配送序列得到上述k+k*(pc+pm)個配送序列分別所對應的路程，將每個配送序列對應路程的倒數作為每個配送序列的適應度值，然後進入步驟410；

步驟410，將k+k*(pc+pm)個適應度值從大到小進行排序，選擇適應度值最大的前k個對應的配送序列即配送路線進行下一次迭代計算，並將當前適應度值最大的配送序列保存；

步驟411，將l的值加1對l進行更新，判斷更新後的l是否等於預設迭代次數l，若是，則迭代結束，進入步驟5；否則，重複執行步驟3-步驟4；

步驟5，從每一次迭代保存的當前迭代適應度值最大的配送序列中，找到適應度值最大的配送序列作為最優配送路線。

作為本發明的一種優選方案，所述步驟3的具體過程為：

步驟31，對於k個配送序列，任取其中的一個c0；

步驟32，在c0的所有配送點中，任取兩個不連續的配送點vi,vj，1≤i≤n,1≤j≤n，若存在w(vi,vj)+w(vi+1,vj+1)<w(vi,vj+1)+w(vj,vj+1)，則在c0中將邊w(vi,vj+1)和w(vj,vj+1)刪除，並加入邊w(vi,vj)和w(vi+1,vj+1)，形成新的配送路線，其中，w(vi,vj)代表兩個配送點之間的時間開銷，n為所有配送點的總數；

步驟33，對c0重複執行步驟32，直到條件不滿足為止，得到較優配送路線。

作為本發明的一種優選方案，步驟43所述交叉操作的具體過程為：

針對其中一個配送序列p1隨機確定兩個起止位置，將起止位置之間的配送點序列取出記為δp1，δp1長度小於p1，生成一個新的配送序列，其中δp1部分的配送點位置和配送序列保持不變，將另一個配送序列p2中與δp1相同的配送點序列去除，剩餘的配送點按照原先在p2中的順序依次添加到新的配送序列中，構成一個新的配送序列；

同時，針對配送序列p2隨機確定兩個起止位置，將起止位置之間的配送點序列取出記為δp2，δp2長度小於p2，生成一個新的配送序列，其中δp2部分的配送點位置和配送序列保持不變，將配送序列p1中與δp2相同的配送點序列去除，剩餘的配送點按照原先在p1中的順序依次添加到新的配送序列中，構成一個新的配送序列；獲得配送序列p1和p2對應的新的配送序列。

作為本發明的一種優選方案，步驟47所述變異操作的具體過程為：在該配送序列中隨機選擇兩個配送點進行位置交換實現變異操作，獲得新的配送序列。

作為本發明的一種優選方案，所述交叉概率閾值pc為被選擇進行交叉操作的配送序列的數目佔總的k個配送序列的比例。

作為本發明的一種優選方案，所述變異概率閾值pm為被選擇進行變異操作的配送序列的數目佔總的k個配送序列的比例。

本發明採用以上技術方案與現有技術相比，具有以下技術效果：

1、本發明在配送過程中，每到達一個配送點之後，能夠根據實時的交通信息，以及配送點個數的變更，在每一個配送點進行配送路線的更新。這樣一旦檢測到原本配送路線發生交通擁堵或者交通事故時，可以及時的更新路線，節約配送的時間。

2、本發明提出的求解方法具有較快的求解速度，能夠在較短的時間內對於環境變化找到最優的配送線路。

附圖說明

圖1是本發明一種面向物流的動態路徑規劃方法的流程圖。

圖2是本發明中二邊逐次修正法對配送路線進行修正的示意圖，其中，(a)為初始配送路線，(b)為修正後的配送路線。

圖3是本發明中配送區域中配送路線示意圖，其中，(a)為eil51優化圖，(b)為eil101優化圖，(c)為st70優化圖，(d)為eil76優化圖。

具體實施方式

下面詳細描述本發明的實施方式，所述實施方式的示例在附圖中示出。下面通過參考附圖描述的實施方式是示例性的，僅用於解釋本發明，而不能解釋為對本發明的限制。

本發明所要解決的技術問題是帶有實時交通信息的動態路網的物流路線配送問題。該問題需要根據實時的交通信息，將每一個配送點記為一個關鍵點。在配送過程中每到一個關鍵點後根據實時的交通信息及時調整路線，節省配送時間，提高配送效率。該問題所考慮的背景為城市動態交通環境，假設交通信息可以事先獲取到。同樣，配送點需求的動態變更也可以提前獲知。若某條路段上發生交通擁堵，則也有其他可代替的路線，且配送點的順序可以根據實際交通信息更換。

如圖1所示，本發明所設計面向實時交通的物流配送方法，配送車輛每到達一個配送點，就根據實時交通的情況進行一次路線規劃。以此來安排下一個配送點以及路線。

步驟1，初始化l＝0。根據當前所有配送點n，隨機獲得k組各不相同、且分別由n個配送點所構成的配送點排列，每一個排列代表一種配送序列即配送路線，然後進入步驟2。其中，n≥2，k為偶數，且表示n個配送點所組成的配送點排列的總數。

步驟2，採用二邊逐次修正法對每條配送路線進行優化(如圖2所示，其中，(a)為初始配送路線，(b)為修正後的配送路線)，並用優化之後的取代原先的配送路線。具體步驟如下：

步驟201，對於k組配送序列，任取其中的一組c0＝v1,v2,…,vi,…,vj,…,vn，其中vi代表某一個配送點，i代表當前配送點的序號；

步驟202，在該組所有的配送點中，任取兩個i,j，1<i+1<j<n。若存在w(vi,vj)+w(vi+1.vj+1)<w(vi,vj+1)+w(vj,vj+1)，其中w(vi,vj)代表兩個配送點之間的時間開銷，則在c0中刪去邊w(vi,vj+1)和w(vj,vj+1)，而加入邊w(vi,vj)和w(vi+1,vj+1)，形成新的配送序列即c＝v1,v2,…,vi,vj,vj-1,…,vi+2,vi+1,vj+1,…,vn，即將vi+1至vj之間(包括vi+1和vj)所有配送點的順序顛倒過來；

步驟203，對c0重複執行步驟202，直到條件不滿足為止，最後得到較優配送序列c。

步驟3，對所有的配送路線進行交叉、變異、選擇操作，具體步驟如下：

步驟301，初始化v＝1，系統隨機生成一個0～1之間的隨機數，判斷該隨機數是否小於等於交叉概率閾值pc，是則進入步驟302；否則進入步驟303；其中，交叉概率閾值pc表示被選擇進行交叉操作的配送序列的數目佔總的k組配送序列數目的比例；

步驟302，在該k組配送序列中，隨機挑選兩組配送序列，並對這兩組配送序列進行交叉操作，產生兩組新的配送序列，將這兩組配送序列添加到總的配送序列中。然後進入步驟303；

交叉操作具體包括如下操作：首先針對其中的一組配送序列p1隨機確定兩個起止位置，將起止位置之間的配送點序列取出記為δp1，其中δp1長度小於p1。生成一個新的配送序列，其中δp1部分的配送點位置和配送序列保持不變，將另一組配送序列p2中與δp1相同的配送點序列去除，剩餘的配送點按照原先在p2中的順序依次添加到新的配送序列中，構成一組新的配送序列組合；

同時，針對另一組配送序列p2中隨機確定兩個起止位置，將起止位置之間的配送點序列取出記為δp2，其中δp2長度小於p2。生成一個新的配送序列，其中δp2部分的配送點位置和配送序列保持不變，將另一組配送序列p1中與δp2相同的配送點序列去除，剩餘的配送點按照原先在p1中的順序依次添加到新的配送序列中，構成一組新的配送序列組合；

由此獲得配送序列p1和配送序列p2所對應的兩組新的配送序列。

步驟303，判斷v是否等於是則進入步驟304；否則用v的值加1針對v進行更新，並返回步驟301；

步驟304，初始化u＝1，系統隨機生成一個0～1之間的隨機數，並判斷該隨機數是否小於等於變異概率閾值pm，是則進入步驟305；否則進入步驟306；其中，變異概率閾值pm表示被選擇進行變異操作的配送序列的數目佔總的k組配送序列數目的比例；

步驟305，在該k組配送序列中，隨機挑選一組配送序列，將該配送序列進行變異操作，產生一組新的配送序列，將這一組配送序列添加到總的配送序列中。然後進入步驟306；

變異操作具體包括如下操作：將該配送序列中隨機選擇兩個配送點進行位置交換實現變異操作，並將變異操作所獲新的配送序列添加到總的配送序列中。

步驟306，判斷u是否等於k，否則用u的值加1針對u進行更新，並返回步驟304；

步驟307，將經過交叉與變異操作產生的新的配送序列添加到原先k個配送序列中，此時一共k+k*(pc+pm)組配送點有序排列組合，獲得由當前配送點為起始點、沿配送序列的配送點順序所遍歷的路程，即獲得該k+k*(pc+pm)組配序列分別所對應的路程；接著將該k+k*(pc+pm)組配送點有序排列組合分別所對應路程的倒數，分別作為對應配送點有序排列組合的適應度值，即獲得該k+k*(pc+pm)組配送點有序排列組合分別所對應的適應度值，然後進入步驟308；

步驟308，將k+k*(pc+pm)組對應的適應度值進行從大到小排序，從上往下選擇k組配送路線進行下一次計算，並將當前適應度值最大的配送序列保存；

步驟309，將l的值加1針對l進行更新，判斷l是否等於預設迭代次數l，是的話，就將目前為止適應度值最大的配送序列輸出。否則繼續執行步驟1。

步驟4，挑選出每一代中的最優個體作為最優解。

為了驗證本發明的效果，我們通過從tsplib中選擇四個具有代表性的測試集作為實驗數據：eil51、eil101、st70、eil76來模擬配送過程中客戶節點數量以及客戶之間距離變化的情況，定義dtsp(t)為：

該實驗主要測試算法在不同採樣周期內的性能。設定δt為2s，算法在δt內分別獨立運行十次。設置參數：迭代次數l為10次，種群規模psize為10，交叉概率pc為0.80，變異概率pm為0.05。實驗結果分別如圖3的(a)、(b)、(c)、(d)所示。

以上實施例僅為說明本發明的技術思想，不能以此限定本發明的保護範圍，凡是按照本發明提出的技術思想，在技術方案基礎上所做的任何改動，均落入本發明保護範圍之內。