[發明專利]一種資源回收的路線規劃方法

在審

• 申請號: 201910244069.1
• 申請日: 2019-03-28
• 公開（公告）號: CN109978266A
• 公開（公告）日: 2019-07-05
• 發明（設計）人: 廖詩怡;陳靜;閆曉惠;張香梁;王龍寶;李聰
• 申請（專利權）人: 河海大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 梁耀文

1.一種資源回收的路線規劃方法，其特征在于，包括如下步驟：

(1)回收員在客戶端下單，回收員平臺采集用戶的訂單信息，根據訂單信息決定回收員是否需要繼續接單；

(2)根據回收員接收的N個訂單信息可以得到構成待回收訂單的多維信息矩陣；

(3)根據地圖、實時路況和訂單信息矩陣，得出包括回收中心所在地在內的所有目標點兩兩之間每一條路徑的運輸成本、道路堵塞情況、用戶的預期回收時間，并將其綜合成一個權值；

(4)綜上可以得到一個加權連通圖Z＝(W,I)，根據KRUSKAL理論可以得到一個最小生成樹Z1＝(W,I)，W為各個目標回收點，I為各個目標點之間的路徑；

(5)因為綜合考慮了用戶預期回收時間、運輸成本、道路堵塞情況、路徑長度、單次貨物的重量，所以得到的最小生成樹就是一條距離短、時間少、成本低、用戶滿意度的路線。

2.所述步驟(2)中所述多維信息矩陣中矩陣內容包括：用戶地址信息和聯系方式、預期的回收時間、待回收資源的重量、類別。

3.所述步驟(1)中決定回收員是否能繼續接單取決于回收員所接訂單的總重量x是否在回收區間[a,b]內，a為可以進行回收的最低閾值，b為回收員所能接收訂單的最大閾值。若x<a,則回收員繼續接單，若x>b,則將訂單拆分成幾個子訂單。

4.所述步驟(3)中每一條路徑權值W的最終確定綜合考慮了用戶預期回收、訂單重量、路徑長度和路徑的擁塞程度,并且根據實際情況賦予其不同的權重；

S(W)＝a*(L*LW+W*WW+C*CW)

其中a為時間系數根據其緊急情況分為1、2、3、4級，L為路徑的長度，W為訂單重量，C為路徑的擁塞程度，LW,WW,CW分別表示路徑的長度，訂單重量，路徑的擁塞程度在計算總權值的時候所占的比重，具體的數值根據實際情況來確定。

5.所述步驟(4)中如何根據KRUSKAL理論從圖Z＝(W,I)中得到我們需要的最小生成樹Z1的具體步驟如下：

(4.1)假設圖Z的最小生成樹為Z1，Z1的初始狀態就為T＝(W,{})，即開始時最小生成樹是由圖G中的n個頂點、零條邊構成的，T中的各個頂點獨自構成一個連通分量；

(4.2)按照邊上權值從小到大的順序，考察無向帶權連通圖Z的邊集I中的各條邊；如果被考察邊的兩個頂點分別屬于最小生成樹Z1中兩個不同的連通分量，則將此邊加入到Z1中，此時兩個連通分量變成一個連通分量；如果被考察邊的兩個頂點一同屬于一個連通分量，則不能將此邊加入Z1中，以免造成回路；

(4.3)如此繼續下去，當Z1中只有一個連通分量時，此連通分量便是圖Z的一棵最小生成樹；簡單說，就是從余下的邊中選擇出來一條不會產生回路且具有最小權值的邊加入到已選擇的邊的集合中。