[發明專利]一種基于約束規劃的帶時間窗車輛路徑問題建模及優化方法

有效

• 申請號: 201810856546.5
• 申請日: 2018-07-31
• 公開（公告）號: CN109034481B
• 公開（公告）日: 2022-07-05
• 發明（設計）人: 陳鵬;童睿;王云鵬;魯光泉;鹿應榮
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于約束規劃的帶時間窗車輛路徑問題建模及優化方法，包括以下幾個步驟：

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

步驟二、基于車輛路徑問題的數學模型，建立帶時間窗車輛路徑問題的約束規劃基本模型，如下：

目標函數為：

約束條件為：

其中，變量定義如下：

c_ij從i到j所需要的配送成本；

N要求服務的客戶總數量，N＝{1...n}；

i，j單個客戶點，i，j∈N；

M各個車輛的編號，亦是路線編號，M＝{1,2,...,m}；

Q車輛的最大負載量；

c_ij客戶點i到客戶點j的運輸成本，此處單位距離成本為1，其中i≠j，i，j∈N；

t_ij從客戶點i到客戶點j所花費的時間，其中i≠j，i，j∈N；

D_i客戶點i的貨物需求量，且max D_i≤Q，i∈N；

E_i客戶i可以接受服務的最早時間，i∈N；

L_i客戶i可以接受服務的最晚時間，i∈N；

S_i對客戶點i服務所需要的時間，i∈N；

T_i客戶點i開始進行服務的時刻，i＝{0,1,2,...,n+2m}，0代表配送中心；

S所有的出發點，S＝{n+1,...,n+m}；

E所有的結束點，E＝{n+m+1,...,n+2m}；

V所有的客戶點，V＝N∪S∪E；

V_S所有具有繼承點的客戶點，V_S＝N∪S；

V_E所有具有前身點的客戶點，V_E＝N∪E；

s_i表示客戶點i的下一個客戶點，i∈V_S；

p_i表示客戶點i的上一個客戶點，i∈V_E；

r_i表示客戶點i所屬的路徑編號，i∈m；

q_i車輛到達客戶點i后的載貨量，i∈N∪S；

步驟三、添加其他的約束條件，以優化基本約束規劃模型，包括通過啟發式方法，設置更合理的模型解空間關鍵參數；

步驟四、導入用于驗證和測試模型的基準測試包，并讀取客戶點信息，包括客戶點位置坐標、貨物需求量、時間窗信息；

步驟五、調用CPLEX優化器求解帶時間窗車輛路徑問題的約束規劃模型，實驗并進行結果分析。

2.根據權利要求1所述的一種基于約束規劃的帶時間窗車輛路徑問題建模及優化方法，所述的步驟三中，添加的其他約束條件具體如下：

a)根據所有客戶的總需求量和車輛最大載貨量估算需要的車輛數，具體如下：

m＝2*IloSum(D)/Q+1；

其中，D為存儲客戶的貨物需求量的數組，IloSum的作用是對數組D中的各元素進行求和，Q為車輛的最大載重量，加1意義是對于前面所得結果向上取整數，由于只取一倍時，車輛數過少，可能會求不到最優解，所以取兩倍的客戶總需求量與最大負載量的比值；

b)消除車輛對稱性：由于車輛的型號和最大運載量相同，所以車輛之間具有對稱性，這將導致求解器找到最優的路線規劃方案后，它將繼續尋找那些分配不同的車輛按同樣的路線運輸貨物的解，會浪費大量的求解時間，所以，應消除車輛之間的對稱性，基本思路是優先安排編號較小的車輛，即最先派出一號車，再派出二號車，直至車輛數足夠，實現方法是令一號起點的下一個點的編號小于二號起點的下一個點的編號，二號起點的下一個點的編號小于三號起點的下一個點的編號，以此類推；

c)增加路徑變量約束：在初始模型中，約束已經可以對所有點的路徑變量加以限制，但實驗表明，加上一些冗余約束可以加速求解過程的結束；

d)調用IloAllDiff約束：由于每一個客戶點只能由一輛車訪問一次，所以每一個客戶點的前一個點和下一個點都必須是唯一的，因此，模型中的每個前身變量和繼承變量的值都是各不相同的；同時，將約束條件IloAllDiff的AllDiffInferenceLevel參數改為Extended，更利于求解；

e)更改搜索方式

對AllDiffInferenceLevel參數進行設置外，還可以通過調整其他的參數來調整搜索方案，在CPLEX優化器中，有三種搜索方式，分別是Restart、DepthFirst和MultiPoint，選用DepthFirst的搜索方式對測試包進行測試時，大部分的測試包均可以最快的結束求解過程。