[發明專利]應用于求解電動貨車集散貨路徑規劃的方法及裝置

在審

• 申請號: 202210546556.5
• 申請日: 2022-05-19
• 公開（公告）號: CN114897249A
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 成明;張成浩;謝剛;黎怡彤;王馨恬;王靜妍;鄭鍇
• 申請（專利權）人: 蘇州大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06F30/20;G06F111/06;G06F111/08
• 代理公司: 蘇州市中南偉業知識產權代理事務所(普通合伙) 32257
• 代理人: 李柏柏

1.一種應用于求解電動貨車集散貨路徑規劃的方法，其特征在于，包括以下步驟：

S1：輸入車場數據、需求節點數據、充電站節點數據以及電動貨車數據；

S2：以最小化總時間為目標，將所有的需求節點插入進車場到車場的路徑中，生成包含有若干條路徑的初始解，設置最大迭代次數，令當前解x_c為初始解，對當前解x_c進行迭代；

S3：若當前迭代次數i能夠被Nsr整除，則轉到S4，否則轉到S5，其中Nsr表示執行移除充電站操作的迭代次數；

S4：根據充電站移除算子概率分布從充電站移除算子集合中選擇充電站移除算子，并執行充電站移除操作，得到破損解x_d1，使用充電站插入算子集合中的貪婪插入算子對破損解x_d1進行修復，得到x_n1，并轉到S8；

S5：若當前迭代次數i能夠被Nrr′整除，則轉到S6，否則轉到S7，其中Nrr′表示執行移除路徑操作的迭代次數；

S6：根據路徑移除算子概率分布從路徑移除算子集合中選擇路徑移除算子，并執行路徑移除操作，得到破損解x_d2，根據需求插入算子概率分布從需求插入算子集合中選擇需求插入算子，并對破損解x_d2進行需求插入操作，得到x_n2，并轉到S8，其中所述需求插入算子包括等待時間插入算子，其用于將需求節點插入總成本最少位置；

S7：根據需求移除算子概率分布選擇需求移除算子集合中的需求移除算子，并執行需求移除操作，得到破損解x_d3，根據需求插入算子概率分布從需求插入算子集合中選擇需求插入算子，并對破損解x_d3進行需求插入操作，得到x_n3，并轉到S8，所述需求移除算子包括shaw移除算子和等待時間移除算子，shaw移除算子用于移除相似度高的需求，等待時間移除算子用于移除等待時間長的需求；

S8：將x_n1或x_n2或x_n3賦給新解x_n，對x_n進行評分，根據評分結果給予移除算子或插入算子相應的分數，使用模擬退化算法判斷是否接受新解x_n，若判斷結果為是，則將x_n賦給x_c，否則x_c維持不變；

S9：若當前迭代次數i能夠被Npsr整除，則轉到S10，否則轉到S11，其中Npsr表示更新充電站移除算子概率分布的迭代次數；

S10：根據充電站移除算子集合中各個算子的累計得分更新充電站移除算子概率分布，并清空得分，轉到S13；

S11：若當前迭代次數i能夠被Nprr′整除，則轉到S12，否則轉到S13，其中Nprr′表示更新路徑移除算子概率分布的迭代次數；

S12：根據路徑移除算子集合中各個算子的累計得分更新路徑移除算子概率分布，并清空得分，轉到S13；

S13：若當前迭代次數i能夠被Nprr整除，則轉到S14，否則轉到S15；

S14：根據需求移除算子集合和需求插入算子集合中各算子的累計得分分別更新需求移除算子概率分布和需求插入算子概率分布，并清空得分；

S15：i←i+1，并返回S2。

2.根據權利要求1所述的應用于求解電動貨車集散貨路徑規劃的方法，其特征在于，在S2中，生成包含有若干條路徑的初始解的方法包括：

S2.1：生成車場到車場的路徑；

S2.2：依次在路徑中以增加時間最短為條件插入需求節點，當電量不足時插入充電站節點，直至無法插入節點時重新生成新的路徑，在所有的需求節點均被插入時即生成初始解，初始解中包含有若干條路徑。