[發明專利]一種基于Petri網和整數線性規劃的車輛路徑優化方法

有效

• 申請號: 202010096155.5
• 申請日: 2020-02-17
• 公開（公告）號: CN111325389B
• 公開（公告）日: 2022-03-25
• 發明（設計）人: 何舟;董鈺穎;張瑞杰;馬子玥;劉苗;古嬋
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06F30/20;G06F111/04
• 代理公司: 西安智大知識產權代理事務所 61215
• 代理人: 賀建斌

一種基于Petri網和整數線性規劃的車輛路徑優化方法，先根據車輛路徑問題的描述，建立其數學模型；然后基于數學模型，建立車輛路徑問題的Petri網模型；再結合Petri網模型，將數學模型轉換為整數線性規劃問題的程序；然后在MATLAB中導入整數線性規劃問題的程序，并輸入客戶點間的距離、貨物需求量；最后利用YALMIP優化工具箱求解步驟四的整數線性規劃問題，實驗并進行結果分析；本發明能夠得到車輛配送路徑的最優路線，同時獲得的總配送路徑距離最短，有效降低車輛配送成本，具有良好的應用前景。

技術領域

本發明屬于物流配送技術領域，特別涉及一種基于Petri網和整數線性規劃的車輛路徑優化方法。

背景技術

車輛路徑問題(Vehicle Routing Problem，VRP)是物流配送過程中的關鍵問題之一，隨著物流配送行業競爭日益激烈和客戶對物流配送時效性要求越來越高，對車輛路徑問題的研究越來越深入。

車輛路徑優化問題屬于NP難問題，解決辦法包括精確方法和啟發式方法，啟發式方法是目前的研究熱點，但是啟發式方法往往需要設計者擁有較為完備的專業知識并且專用性比較強；另外，啟發式方法往往得不到最優解。

精確方法常用的有線性規劃法、動態規劃法、分支定界法等，其運算量隨著問題規模的擴大呈指數級的增長，精確方法能夠得到最優解，但是不適合求解大規模的問題，求解過程復雜。

發明內容

為了克服上述現有技術的缺點，本發明的目的在于提供了一種基于Petri網和整數線性規劃的車輛路徑優化方法，能夠得到車輛配送路徑的最優路線，同時獲得的總配送路徑距離最短，有效降低車輛配送成本，具有良好的應用前景。

為了達到上述目的，本發明采取的技術方案為：

一種基于Petri網和整數線性規劃的車輛路徑優化方法，包括以下步驟：

步驟一、根據車輛路徑問題的描述，建立其數學模型；

步驟二、基于步驟一的數學模型，建立車輛路徑問題的Petri網模型；

步驟三、結合步驟二的Petri網模型，將步驟一的數學模型轉換為整數線性規劃問題；

步驟四、在MATLAB中導入步驟三內整數線性規劃問題的程序，并輸入客戶點間的距離、貨物需求量；

步驟五、利用YALMIP優化工具箱求解步驟四的整數線性規劃問題，實驗并進行結果分析。

所述的步驟二中建立的Petri網模型如下：

a)P＝{p₀,p₁,…,p_n}，P表示客戶點及配送中心點的庫所集合，其中配送中心點用庫所p₀表示，客戶點i用庫所p_i表示，i＝1,...,n；

b)H表示車輛最多移動步數，車輛每訪問一個點視為移動一步；

c)M_kh＝[M_kh(p₀)，M_kh(p₁)，…，M_kh(p_n)]表示Petri網的位置標識。如果車輛k在第h步的位置為點i(i＝0,1,...,n)，則M_kh(p_i)＝1，否則 M_kh(p_i)＝0；

d)配送中心與任意客戶i之間都有路徑，分別用變遷t_0i和變遷t_i0表示車輛從配送中心點出發到客戶點i,及車輛從客戶點i出發到配送中心；