[發明專利]一種求解多目標多車場帶時間窗車輛路徑問題的智能算法

在審

• 申請號: 201611237837.3
• 申請日: 2016-12-28
• 公開（公告）號: CN106651043A
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 王甲海;翁太耀;印鑒
• 申請（專利權）人: 中山大學;廣東恒電信息科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 廣州粵高專利商標代理有限公司44102
• 代理人: 林麗明

1.一種求解多目標多車場帶時間窗車輛路徑問題的智能算法，其特征在于，包括以下步驟：

S1：在決策空間中尋找極值解；

S2：利用尋找到的極值解，在整個決策空間中搜索一組兼顧收斂性與多樣性的解。

2.根據權利要求1所述的求解多目標多車場帶時間窗車輛路徑問題的智能算法，其特征在于，所述步驟S1的具體過程如下：

S11：根據給定的多車場帶時間窗車輛路徑問題的服務需求，初始化尋找極值解的初始種群P_I，其種群大小為N_I；

S12：以種群P_I中的個體初始化存檔A，存檔用于收集求解過程中得到的非占優解；

S13：從P_I中隨機選取出兩個個體x₁和x₂，交叉產生一個子代個體o_I，重復N_I次產生子種群Q，以Q中個體更新存檔A得到新的存檔A1，令A＝A1；

S14：使用局部搜索優化Q中的個體，得到種群Q₁，以Q₁中個體更新存檔A得到新的存檔A2，令A＝A2；

S15：使用快速非占優排序及極值擁擠距離從P_I∪Q₁中選取出N_I個個體P_I'，令P_I＝P′_I；

S16：重復步驟S13-S15直到評估次數達到e_I，輸出種群P_I。

3.根據權利要求2所述的求解多目標多車場帶時間窗車輛路徑問題的智能算法，其特征在于，所述步驟S2的具體過程如下：

S21：生成一組均勻分布的向量Λ¹,Λ²,Λ³,...,個數為N_II；

S22：基于歐幾里德距離，為每個向量Λⁱ計算得到一組距離最近的向量從而得到向量Λⁱ的鄰域向量集合B(i)＝{i₁,i₂,i₃,...,i_T}；

S23：種群P_I交叉產生N_II個個體Q₂，基于切比雪夫方程從P_I∪Q₂中不重復地為每個向量選取最優的個體；

S24：對于任意i∈{1,2,3,...,N_II}，從B(i)中選取兩個下標p和q，個體x^p和x^q交叉產生子代o_II，使用局部搜索優化得到x′，以x′更新存檔A得到新的存檔A3，令A＝A3；

S25：對于B(i)中每個下標j，若g^te(x′|Λ^j,z^*)≤g^te(x^j|Λ^j,z^*)，則令x^j＝x′；

S26：重復步驟S24-S25直到評估次數達到e_II，輸出存檔A。

4.根據權利要求3所述的求解多目標多車場帶時間窗車輛路徑問題的智能算法，其特征在于，f₁為車輛數目，計算方式如下：

f₁＝|R|

f₂為總行駛距離，包含每個車輛的行駛距離，計算方式如下：

其中，為路徑的行駛距離；

f₃為最長工作時間，是所有路徑中最長的行駛時間，計算方式如下：

其中，為路徑的行駛時間；

f₄為總等待時間，當車輛提前于客戶的時間窗到達時，必須進行等待，直到客戶的服務時間窗開始才能進行服務，計算方式如下：

其中，為路徑的等待時間；

f₅為總延遲時間，當車輛在客戶的時間窗之后到達，即產生延遲時間，計算方式如下：

其中，為路徑的延遲時間。

5.根據權利要求4所述的求解多目標多車場帶時間窗車輛路徑問題的智能算法，其特征在于，所述局部搜索的過程如下：

S41：令p＝random(0,1)，若p＜p_inter，則隨機選取一個車場間操作，否則隨機選取一個車場內操作；

S42：使用選取的操作，根據g^te(x|λ,z^*)對解x進行優化，替換策略為最優提升策略；

S43：重復步驟S41-S42直到達到搜索深度I_max，結束局部搜索過程。