[發明專利]一種物流運輸調度方法與裝置

有效

• 申請號: 201710655727.7
• 申請日: 2017-08-03
• 公開（公告）號: CN107437126B
• 公開（公告）日: 2020-08-11
• 發明（設計）人: 蔡延光;戚遠航;蔡顥;黃何列
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 羅滿

1.一種物流運輸調度方法，其特征在于，包括：

S10：初始化目標參數；

S11：利用基于泰森多邊形的初始化策略得到蝙蝠位置信息；

S12：利用預先設置的尋優規則，對第一蝙蝠位置信息進行優化處理，得到目標蝙蝠位置信息以及對應的目標適應度；其中，所述第一蝙蝠位置信息為所有所述蝙蝠位置信息中的任意一個蝙蝠位置信息；

S13：依據預先設置的向量比較機制，對各個所述目標蝙蝠位置信息對應的適應度進行比較，得到全局最優蝙蝠位置信息以及對應的最優適應度；

S14：按照預先設置的更新規則，對所述目標蝙蝠位置信息進行更新處理，得到更新后的第二蝙蝠位置信息；

S15：利用預先設置的所述尋優規則，對所述第二蝙蝠位置信息進行優化處理，得到第二目標蝙蝠位置信息以及對應的第二適應度；

S16：依據所述第二適應度、所述目標適應度和所述最優適應度，更新全局最優蝙蝠位置信息以及對應的最優適應度；

S17：判斷迭代次數是否達到預設的最大迭代次數，若是，則輸出物流運輸調度的結果；若否則返回所述S14；

在所述S11中包括：

根據公式確定出每個車場對應的泰森多邊形區域V(p_i)；

其中，p_i表示二維歐式平面的離散點集合中的一個離散點；

以車場作為離散點，根據公式P(m)＝{x|x∈V(m)}，確定出車場m的優先配送客戶集合P(m)；

其中，x∈(1,2,…,N)，m∈(N+1,N+2,…,N+M)，M表示車場的個數，車場編號為N+1,N+2,…,N+M，N表示客戶的個數，客戶編號為1,2,…,N；

依據公式確定出車輛的總數目W；

其中，K_m(m＝N+1,N+2,…,N+M)表示各個車場對應的車輛數目；車輛編號為N+1,N+2,…,N+M；

對(N+1,N+2,…,N+M)進行隨機置換，得到B_rand，從左往右搜索B_rand的分量，順序為的分量是屬于車場m的車輛編號，得到車場m的車輛編號集合D(m)；

根據公式C(m)＝P(m)∪D(m)，確定出每個車場對應的C(m)；

依據所述C(m)，隨機生成一組包含C(m)所有元素且不重復的序列其中，所述中第一個分量為車輛編號；

合并所有所述車場對應的得到序列

交換所述C^ALL中第一個分量與值為“N+W”的分量的位置，刪除第一個分量，得到蝙蝠位置信息；

在所述S12中包括：

對第一蝙蝠位置信息進行解碼處理，獲取到各個車輛的配送路徑；

利用2-Opt搜索算法、基于近鄰策略的0-1搜索算法和基于優先配送策略的1-1搜索算法，對各個所述車輛的配送路徑進行優化處理，得到各個所述車輛各自對應的目標配送路徑；

對所述目標配送路徑進行編碼處理，得到目標蝙蝠位置信息以及對應的適應度；

所述第一蝙蝠位置信息進行解碼處理，獲取到各個車輛的配送路徑包括：

依據第一蝙蝠位置信息的定義x_i＝(x_i1,x_i2,…,x_iw)，在蝙蝠位置x_i的分量x_i1前插入一個值為“w+1”的分量，在蝙蝠位置x_i的分量x_iw后插入一個值為“w+2”的分量，得到序列y_i＝(y_i1,y_i2,…,y_i(w+2))；其中，蝙蝠種群的維度w∈N⁺，w＝N+W-1，i＝1,2,…,Q，Q表示蝙蝠種群的規模；

從左往右搜索y_i的每個分量，車輛y_ip到車輛y_iq之間經過的客戶點構成車輛y_ip的配送路徑；其中，y_ip＞N，y_iq＞N，1≤p≤w+2，1≤q≤w+2；

所述對所述目標配送路徑進行編碼處理，得到目標蝙蝠位置信息以及對應的適應度包括：

刪除各個車輛的配送路徑中的最后一個分量，得到序列其中，i＝1,2,…,W；其中，每個車輛的配送路徑有其對應的適應度；

按照車場順序合并各個車輛對應的得到序列X_temp；

交換X_temp中第一個分量與值為“N+W”的分量的位置，刪除第一個分量，得到目標蝙蝠位置信息以及對應的目標適應度；

在所述S13中包括：

參照預先設置的向量比較機制的適應度公式，

其中，m∈{N+1,N+2,…,N+M}，k∈{1,2,…,K_m}，G_a、G_b和G_c分別為適應度的三個等級，G_a表示容量適應度，G_b表示配送路徑適應度，G_c表示所有車輛的總路徑適應度；u表示車場擁有容量；l表示行駛距離；g_i表示客戶i的貨物需求；d_ij表示客戶i到客戶j之間的距離；

判斷是否滿足G_1a＜G_2a；若是，則令G_best＝G₁；若否，則令G_best＝G₂；其中，G₁＝{G_1a,G_1b,G_1c}表示第一目標蝙蝠位置信息對應的適應度，G_1a為所述適應度G₁中包含的容量適應度；G₂＝{G_2a,G_2b,G_2c}表示第二目標蝙蝠位置信息對應的適應度，G_2a為所述適應度G₂中包含的容量適應度，G_best表示最優適應度；

判斷是否滿足G_1a＝＝G_2aG_1b＜G_2b；若是，則令G_best＝G₁；若否，則令G_best＝G₂；其中，G_1b為所述適應度G₁中包含的配送路徑適應度，G_2b為所述適應度G₂中包含的配送路徑適應度；

判斷是否滿足G_1a＝＝G_2aG_1b＝＝G_2bG_1c＜G_2c；若是，則令G_best＝G₁；若否，則令G_best＝G₂；其中G_1c為所述適應度G₁中包含的總路徑適應度，G_2c為所述適應度G₂中包含的總路徑適應度。

2.一種物流運輸調度裝置，其特征在于，包括初始化單元、得到單元、優化單元、比較單元、更新單元和判斷單元，

所述初始化單元，用于初始化目標參數；

所述得到單元，用于利用基于泰森多邊形的初始化策略得到蝙蝠位置信息；

所述優化單元，用于利用預先設置的尋優規則，對第一蝙蝠位置信息進行優化處理，得到目標蝙蝠位置信息以及對應的目標適應度；其中，所述第一蝙蝠位置信息為所有所述蝙蝠位置信息中的任意一個蝙蝠位置信息；

所述比較單元，用于依據預先設置的向量比較機制，對各個所述目標蝙蝠位置信息對應的適應度進行比較，得到全局最優蝙蝠位置信息以及對應的最優適應度；

所述更新單元，用于按照預先設置的更新規則，對所述目標蝙蝠位置信息進行更新處理，得到更新后的第二蝙蝠位置信息；

所述優化單元還用于利用預先設置的所述尋優規則，對所述第二蝙蝠位置信息進行優化處理，得到第二目標蝙蝠位置信息以及對應的第二適應度；

所述更新單元還用于依據所述第二適應度、所述目標適應度和所述最優適應度，更新全局最優蝙蝠位置信息以及對應的最優適應度；

所述判斷單元，用于判斷迭代次數是否達到預設的最大迭代次數，若是，則輸出物流運輸調度的結果；若否則返回所述更新單元；

所述得到單元包括確定子單元、置換子單元、生成子單元、合并子單元和刪除子單元，

所述確定子單元，用于根據公式確定出每個車場對應的泰森多邊形區域V(p_i)；其中，p_i表示二維歐式平面的離散點集合中的一個離散點；

所述確定子單元還用于以車場作為離散點，根據公式P(m)＝{x|x∈V(m)}，確定出車場m的優先配送客戶集合P(m)；

其中，x∈(1,2,…,N)，m∈(N+1,N+2,…,N+M)，M表示車場的個數，車場編號為N+1,N+2,…,N+M，N表示客戶的個數，客戶編號為1,2,…,N；

所述確定子單元還用于依據公式確定出車輛的總數目W；

其中，K_m(m＝N+1,N+2,…,N+M)表示各個車場對應的車輛數目；車輛編號為N+1,N+2,…,N+M；

所述置換子單元，用于對(N+1,N+2,…,N+M)進行隨機置換，得到B_rand，從左往右搜索B_rand的分量，順序為的分量是屬于車場m的車輛編號，得到車場m的車輛編號集合D(m)；

所述確定子單元還用于根據公式C(m)＝P(m)∪D(m)，確定出每個車場對應的C(m)；

所述生成子單元，用于依據所述C(m)，隨機生成一組包含C(m)所有元素且不重復的序列其中，所述中第一個分量為車輛編號；

所述合并子單元，用于合并所有所述車場對應的得到序列

所述刪除子單元，用于交換所述C^ALL中第一個分量與值為“N+W”的分量的位置，刪除第一個分量，得到蝙蝠位置信息；

所述優化單元包括解碼子單元、優化子單元和編碼子單元，

所述解碼子單元，用于對第一蝙蝠位置信息進行解碼處理，獲取到各個車輛的配送路徑；

所述優化子單元，用于利用2-Opt搜索算法、基于近鄰策略的0-1搜索算法和基于優先配送策略的1-1搜索算法，對各個所述車輛的配送路徑進行優化處理，得到各個所述車輛各自對應的目標配送路徑；

所述編碼子單元，用于對所述目標配送路徑進行編碼處理，得到目標蝙蝠位置信息以及對應的適應度；

所述解碼子單元具體用于依據第一蝙蝠位置信息的定義x_i＝(x_i1,x_i2,…,x_iw)，在蝙蝠位置x_i的分量x_i1前插入一個值為“w+1”的分量，在蝙蝠位置x_i的分量x_iw后插入一個值為“w+2”的分量，得到序列y_i＝(y_i1,y_i2,…,y_i(w+2))；其中，蝙蝠種群的維度w∈N⁺，w＝N+W-1，i＝1,2,…,Q，Q表示蝙蝠種群的規模；并從左往右搜索y_i的每個分量，車輛y_ip到車輛y_iq之間經過的客戶點構成車輛y_ip的配送路徑；其中，y_ip＞N，y_iq＞N，1≤p≤w+2，1≤q≤w+2；

所述編碼子單元具體用于刪除各個車輛的配送路徑中的最后一個分量，得到序列其中，i＝1,2,…,W；其中，每個車輛的配送路徑有其對應的適應度；按照車場順序合并各個車輛對應的得到序列X_temp；交換X_temp中第一個分量與值為“N+W”的分量的位置，刪除第一個分量，得到目標蝙蝠位置信息以及對應的目標適應度；

所述比較單元具體用于參照預先設置的向量比較機制的適應度公式，

其中，m∈{N+1,N+2,…,N+M}，k∈{1,2，…,K_m}，G_a、G_b和G_c分別為適應度的三個等級，G_a表示容量適應度，G_b表示配送路徑適應度，G_c表示所有車輛的總路徑適應度；u表示車場擁有容量；l表示行駛距離；g_i表示客戶i的貨物需求；d_ij表示客戶i到客戶j之間的距離；

判斷是否滿足G_1a＜G_2a；若是，則令G_best＝G₁；若否，則令G_best＝G₂；其中，G₁＝{G_1a,G_1b,G_1c}表示第一目標蝙蝠位置信息對應的適應度，G_1a為所述適應度G₁中包含的容量適應度；G₂＝{G_2a,G_2b,G_2c}表示第二目標蝙蝠位置信息對應的適應度，G_2a為所述適應度G₂中包含的容量適應度，G_best表示最優適應度；

判斷是否滿足G_1a＝＝G_2aG_1b＜G_2b；若是，則令G_best＝G₁；若否，則令G_best＝G₂；其中，G_1b為所述適應度G₁中包含的配送路徑適應度，G_2b為所述適應度G₂中包含的配送路徑適應度；

判斷是否滿足G_1a＝＝G_2aG_1b＝＝G_2bG_1c＜G_2c；若是，則令G_best＝G₁；若否，則令G_best＝G₂；其中G_1c為所述適應度G₁中包含的總路徑適應度，G_2c為所述適應度G₂中包含的總路徑適應度。