[發(fā)明專利]一種降低煙草配送里程的方法

有效

• 申請?zhí)枺?/td>: 202010870443.1
• 申請日: 2020-08-26
• 公開（公告）號: CN112001678B
• 公開（公告）日: 2022-07-19
• 發(fā)明（設(shè)計）人: 陳是建;陳奮勵;葉清云;陳益航;蘇志欣;蔡文魁;張劍雄
• 申請（專利權(quán)）人: 莆田煙草物流有限公司
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06K9/62
• 代理公司: 福州旭辰知識產(chǎn)權(quán)代理事務所(普通合伙) 35233
• 代理人: 程勇

1.一種降低煙草配送里程的方法，其特征在于：所述方法包括如下步驟：

步驟S1、調(diào)整送貨結(jié)構(gòu)，即獲取一周出車趟次，并獲得配送車輛的數(shù)量；

步驟S2、構(gòu)建客戶最小配送單元；

步驟S3、通過客戶最小配送單元來重新編排送貨線路；

所述步驟S2進一步具體為：通過聚類算法，根據(jù)經(jīng)緯度的相似程度，將客戶分為若干個最小配送單元，對相近客戶進行合并，使其形成各自的最小配送單元；設(shè)定配送的客戶集合為V＝{v₁,v₂,...,v_n}，客戶的經(jīng)緯度屬性為x_i，構(gòu)建出k個聚類子集{c₁,c₂,...,c_k}，使得k個聚類子集中的客戶差異化最小；即其中，為聚類子集{c₁,c₂,...,c_k}中聚類c_j(j＝1,2,...,k)的聚類中心，v_i表示聚類c_j中所有的客戶；則聚類中心的選取方法為公式：其中，|c_j|是聚類j中的客戶數(shù)量，x_j表示c_j中客戶的經(jīng)緯度數(shù)據(jù)；

聚類算法以歐氏距離作為客戶節(jié)點的相似度，所以任意兩個客戶節(jié)點的歐式距離d(x_i,x_j)表示為：

所述步驟S3進一步具體為：步驟31：獲得客戶最小配送單元；

步驟32：設(shè)置初始化參數(shù)，即設(shè)置初始溫度T₀，終止溫度T_f；

步驟33：產(chǎn)生初始解X₀，即將初始解X₀作為當前最優(yōu)解X_best＝X₀，獲取模擬退火算法的目標函數(shù)f(X₀)；該步驟中將具有最大訂單量的子路徑中的客戶節(jié)點插入到具有最小客戶訂單量的子路徑中，不斷調(diào)整后得到模擬退火算法的一個初始可行解；

步驟34：局部搜索得新解，即對當前最優(yōu)點作一隨機變動，產(chǎn)生一新解X_k，獲取新的模擬退火算法目標函數(shù)f(X)，并獲取目標函數(shù)的增量Δf＝f(X)-f(X₀)，令k＝k+1，k為迭代次數(shù)；

步驟35：判斷新解是否能成為當前最優(yōu)解，即若Δf＜0，則接受新解X成為當前最優(yōu)解，X_best＝X；否則以概率p＝exp(-Δf/T)接受X作為新的當前最優(yōu)解，T為最優(yōu)解X所對應的溫度T；

步驟36：判斷模擬退火算法是否結(jié)束，若當前溫度大于終止溫度T_f轉(zhuǎn)回步驟34，否則輸出當前解為最優(yōu)解，并結(jié)束算法。

2.根據(jù)權(quán)利要求1所述的一種降低煙草配送里程的方法，其特征在于：所述方法還包括：步驟S4、通過禁忌搜索算法優(yōu)化所述送貨線路；該步驟S4進一步具體為：基于客戶最小配送單元，將客戶節(jié)點位置定義為每個最小配送單元的平均經(jīng)緯度信息，對其中任意兩個客戶節(jié)點通過鄰近KNN算法判斷兩客戶節(jié)點的距離是否小于預設(shè)定的Q值，若滿足則進行兩種鄰域搜索操作，并記入訪問過的鄰域解；若不滿足則放棄這對節(jié)點，對其他節(jié)點進行同一操作。

3.根據(jù)權(quán)利要求2所述的一種降低煙草配送里程的方法，其特征在于：所述步驟S4進一步具體為：步驟41：獲得客戶最小配送單元；

步驟42：設(shè)置初始化參數(shù)，設(shè)置初始溫度T₀，終止溫度T_f，以及KNN算法中的G值；通過預設(shè)定的G值將不符合KNN算法的最遠節(jié)點舍棄，減少鄰域搜索的范圍；

步驟43：產(chǎn)生初始解X₀，即將初始解X₀作為當前最優(yōu)解X_best＝X₀，獲取模擬退火算法的目標函數(shù)f(X₀)；該步驟中將具有最大訂單量的子路徑中的客戶節(jié)點插入到具有最小客戶訂單量的子路徑中，不斷調(diào)整后得到混合模擬退火算法的一個初始可行解；

步驟44：局部搜索得新解，即在當前解X₀的鄰域內(nèi)分別進行交換法和插入法的局部搜索操作產(chǎn)生新的可行解X，獲取新的模擬退火算法的目標函數(shù)f(X)，并獲取目標函數(shù)的增量Δf＝f(X)-f(X₀)，令k＝k+1，k為迭代次數(shù)；

步驟45：判斷新解是否能成為當前最優(yōu)解，若Δf＜0，則接受新解X成為當前最優(yōu)解，X_best＝X；否則以概率p＝exp(-Δf/T)接受X作為新的當前最優(yōu)解，T為最優(yōu)解X所對應的溫度T；

步驟46：判斷是否完成所有鄰域搜索，即在當前溫度T下，若還未完成所有鄰域搜索則轉(zhuǎn)至步驟47，否則轉(zhuǎn)回步驟44；

步驟47：判斷混合模擬退火算法是否結(jié)束，若當前溫度大于終止溫度T_f轉(zhuǎn)回步驟44，否則輸出當前解為最優(yōu)解，并結(jié)束算法。