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

有效

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

1.一種基于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出發到配送中心點；

e)對于任意兩個客戶點i和j，i≠j，分別用變遷t_ji和變遷t_ij表示車輛從客戶點j出發到客戶點i,及車輛從客戶點i出發到客戶點j；

f)表示庫所與變遷的前置關聯矩陣,若變遷t是庫所p的輸出變遷，即變遷t是從庫所p發出的一條路線，則Pre(p,t)＝1,否則Pre(p,t)＝0；

g)表示庫所與變遷的后置關聯矩陣,若變遷t是庫所p的輸入變遷，即變遷t指向的終點是庫所p，則Post(p,t)＝1,否則Post(p,t)＝0；

h)ν_ij表示Petri網的載貨向量，車輛從點i到點j所增加的載貨量，i,j＝0,1,...,n,i≠j，即ν_ij＝q_j，q_j為客戶點j處的需求量；

i)Θ_khij＝[θ_kh01，θ_kh02，...，θ_khij，...，θ_kHnn-1]，Θ_khij表示Petri網的路徑向量，若車輛k在第h步經i點出發訪問j點，i≠j，則θ_khij＝1，否則θ_khij＝0。

2.根據權利要求1所述的一種基于Petri網和整數線性規劃的車輛路徑優化方法，其特征在于：所述的步驟三中建立的整數線性規劃問題模型如下：

目標函數為：min f＝∑_k∑_hw_i，jΘ_khij,w_i,j為客戶i、j之間的距離；

約束條件為：

約束條件1：M_kh＝M_kh-1+(Post-Pre)×Θ_khij

約束條件2：M_kh-1-Pre×Θ_khij≥0

約束條件3：∑_kM_k0(p₀)＝∑_kM_kH(p₀)＝K

約束條件4：ν_ij∑_hΘ_khij≤Q，Q表示每輛車的最大載貨量；

約束條件5：∑_k∑_hM_kh(p_c)＝1，M_kh(p_c)表示車輛k在第h步時的位置信息，h＝1,...,H，如果車輛k在第h步的位置為客戶點c，c＝1,...,n，則M_kh(p_c)＝1，否則M_kh(p_c)＝0；

約束條件6：k＝1,2,…,K；h＝1,2,…,H；i,j＝0,1,…,n,i≠j；c＝1,…,n；

其中，變量定義如下：

k是供調用的車輛集合，k＝{1,2,3，…,K}；

h是車輛運動的步數，H是車輛最多移動的步數，h＝{1,2,3，…,H}；

i,j表示客戶點或配送中心點，i＝{0,1,…,n}，j＝{0,1,…,n}。