[發明專利]基于集群旅行商問題的協同配送路徑優化方法

在審

• 申請號: 202110390408.4
• 申請日: 2021-04-12
• 公開（公告）號: CN112862414A
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 鐘萍;陳元明;杜志成;丁梓原;儲惠龍
• 申請（專利權）人: 中南大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08
• 代理公司: 長沙永星專利商標事務所(普通合伙) 43001
• 代理人: 周詠;米中業

1.一種基于集群旅行商問題的協同配送路徑優化方法，包括如下步驟：

S1.獲取待分析區域的區域參數；

S2.根據步驟S1獲取的區域參數，構建具有覆蓋的多集群旅行商問題模型；

S3.根據區域內的總配送請求，進行分區平衡優化；

S4.隨機構建初始路徑；

S5.采用擾動機制對步驟S4的初始路徑進行優化；

S6.對后續路徑進行再優化；

S7.重復步驟S5和S6直至達到設定的條件，得到最終的協同配送路徑優化結果。

2.根據權利要求1所述的基于集群旅行商問題的協同配送路徑優化方法，其特征在于步驟S2所述的構建具有覆蓋的多集群旅行商問題模型，具體為以配送員個數，客戶遍歷次數，自提點遍歷次數，路徑連續性，子行程約束，自提點容量限制以及自提點服務范圍為限制條件，以最小化配送成本為目標，構建目標函數：

約束條件：

u_i-u_j+(n-m+1)x_ij≤n-m-1,1≤i≠j≤n

式中V為節點集合，且V＝V_D∪V_S∪V_C，V_D為倉庫，V_S為自提點(SDF)集合，V_C為客戶節點集合；x_ij為決策變量，當且僅當邊(i,j)在路線上時x_ij＝1，否則x_ij＝0；c_ij為邊(i,j)對應的路徑成本；x_0j為0-1變量，且取值為1時表示存在一條從倉庫0出發到節點j的路徑，取值為0時表示不存在一條從倉庫0出發到節點j的路徑；m為快遞員的個數；x_i0為0-1變量，且取值為1時表示存在一條從節點i返回倉庫0的路徑，取值為0時表示不存在一條從節點i返回倉庫0的路徑；z_il為決策變量，當且僅當客戶節點i被自提點節點l覆蓋時z_il＝1，否則z_il＝0；u_i為在遍歷節點i之前路徑的負載；n為需要服務的客戶節點個數；v_b為自提點b的容量限制；R_b為自提點b的服務半徑。