[發(fā)明專利]用于規(guī)劃快遞員投遞路線的方法、系統(tǒng)及存儲介質(zhì)

有效

• 申請?zhí)枺?/td>: 201911242644.0
• 申請日: 2019-12-06
• 公開（公告）號: CN111144622B
• 公開（公告）日: 2022-11-01
• 發(fā)明（設(shè)計）人: 蔣麗;朱樂樂;董駿峰;梁昌勇;陸文星;趙樹平;顧東曉
• 申請（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京潤平知識產(chǎn)權(quán)代理有限公司 11283
• 代理人: 肖冰濱;劉兵

1.一種用于規(guī)劃快遞員投遞路線的方法，其特征在于，所述方法包括：

形成初始的快遞投遞方案并初始化迭代次數(shù)；

采用擾動法更新所述快遞投遞方案；

采用插入改進法更新擾動法更新后的所述快遞投遞方案；

計算更新后的所述快遞投遞方案的目標(biāo)值；

判斷第一迭代次數(shù)是否大于或等于預(yù)設(shè)的第一次數(shù)閾值；

在判斷所述第一迭代次數(shù)小于所述第一次數(shù)閾值的情況下，更新所述第一迭代次數(shù)，并返回執(zhí)行采用擾動法更新所述快遞投遞方案的步驟；

在判斷所述第一迭代次數(shù)大于或等于所述第一次數(shù)閾值的情況下，選取目標(biāo)值最小的所述快遞投遞方案作為最佳的投遞路線；

形成初始的快遞投遞方案具體包括：

采用網(wǎng)絡(luò)圖G表示投遞快遞的區(qū)域，其中，所述網(wǎng)絡(luò)圖G＝(V,E∪A)，V＝{v₀}∪V_C∪V_B，為所述區(qū)域內(nèi)的節(jié)點的集合，v₀為所述區(qū)域內(nèi)的倉庫，V_C＝{v₁,…,v_i,…,v_n}，為所述區(qū)域內(nèi)的客戶點的集合，v_i為第i個所述客戶點，n為所述客戶點的數(shù)量，V_B＝{v_n+1,…,v_n+b,…v_n+m}，為所述區(qū)域內(nèi)的快遞柜的集合，v_n+b為第b個所述快遞柜，m為所述快遞柜的數(shù)量，E＝{v_i,v_j|v_i,v_j∈V}，為所述區(qū)域內(nèi)的邊的集合，每條邊e＝v_i,v_j表示從節(jié)點v_i到節(jié)點v_j的投遞路徑，A＝{v_i,v_b|v_i∈V_C,v_b∈V_B}，為所述區(qū)域內(nèi)的弧的集合，每個弧a＝v_i,v_b表示從客戶節(jié)點v_i到快遞柜v_b的自取路徑；

采用數(shù)量為n+m+1個節(jié)點構(gòu)成的節(jié)點序列表示所述快遞投遞方案；

采用擾動法更新所述快遞投遞方案具體包括：

初始化第二迭代次數(shù)；

從所述快遞投遞方案的快遞柜集合中隨機選取一個快遞柜；

判斷選取的所述快遞柜的當(dāng)前容量是否為空；

在判斷所述當(dāng)前容量為空的情況下，提取選取的所述快遞柜的服務(wù)半徑內(nèi)的客戶點子集合；

判斷所述客戶點子集合中的客戶點數(shù)量是否小于或等于所述快遞柜最大容量；

在判斷所述客戶點子集合中的客戶點數(shù)量小于或等于所述快遞柜最大容量的情況下，將所述客戶點子集合中的全部客戶點放入所述快遞柜中；

在判斷所述客戶點子集合中的客戶點數(shù)量大于所述快遞柜最大容量的情況下，從所述客戶點子集合中隨機選取所述快遞柜最大容量個客戶點，并將選取的所述客戶點放入所述快遞柜中；

在判斷所述當(dāng)前容量不為空的情況下，將所述當(dāng)前容量置為空，并提取所述快遞柜中的所有客戶點至所述快遞柜外；

更新所述第二迭代次數(shù)；

判斷所述第二迭代次數(shù)是否大于或等于預(yù)設(shè)的第二次數(shù)閾值；

在判斷所述第二迭代次數(shù)小于所述第二次數(shù)閾值的情況下，返回執(zhí)行從所述快遞柜集合中隨機選取一個快遞柜的步驟；

在判斷所述第二迭代次數(shù)大于所述第二次數(shù)閾值的情況下，輸出所述擾動法更新后的所述快遞投遞方案；

采用插入改進法更新擾動法更新后的所述快遞投遞方案具體包括：

從所述快遞投遞方案的節(jié)點集合中隨機選取一個節(jié)點作為提取節(jié)點；

根據(jù)所述提取節(jié)點的類型計算從所述快遞投遞方案中提取所述提取節(jié)點的提取成本；

從所述快遞投遞方案的節(jié)點集合中隨機選取一個節(jié)點作為插入節(jié)點；

根據(jù)所述插入節(jié)點與所述提取節(jié)點的關(guān)系計算將所述提取節(jié)點插入至所述插入節(jié)點的編碼前的插入成本；

判斷所述插入成本是否小于所述提取成本；

在判斷所述插入成本大于或等于所述提取成本的情況下，返回執(zhí)行從所述快遞投遞方案的節(jié)點集合中隨機選取一個節(jié)點作為提取節(jié)點的步驟；

在判斷所述插入成本小于所述提取成本的情況下，將所述提取節(jié)點插入至所述插入節(jié)點的編碼前；

判斷所述節(jié)點集合是否存在未被選取的節(jié)點；

在判斷所述節(jié)點集合存在未被選取的節(jié)點的情況下，返回執(zhí)行從所述快遞投遞方案的節(jié)點集合中隨機選取一個節(jié)點作為提取節(jié)點的步驟；

在判斷所述節(jié)點集合不存在未被選取的節(jié)點的情況下，輸出所述改進插入法處理后的所述快遞投遞方案。