基于智能調度的散點貨源動態集散點設置研究

翟江蘇，韓寶睿 ZHAI Jiangsu,HAN Baorui

（南京林業大學 汽車與交通工程學院，江蘇 南京 210037）

0 引言

傳統的寄件過程，一般是由發件人自行尋找附近的快遞網點投遞，或者是通過電話預約快遞員上門取件。隨著貨源不斷增加，能夠發現傳統攬件模式的效率會逐漸降低、取件成本也會不斷增加。此外，如果過多地設置貨物攬收點，會導致企業成本大幅提高，而且對于提升系統運行效率的效果也并不明顯。在這種情況下，無人取件車網上預約收件模式能夠更好地適應攬收快件工作。近年來，隨著無人駕駛技術的逐步成熟，快遞智能無人收派車的概念也被提出[1]，城市快件智能化收集也將逐步成為現實。智能取件系統的關鍵技術在于貨物動態集散點的設置以及車輛動態路徑的規劃。其中動態集散點設置實質上也是路徑規劃中的一個組成部分。當前車輛路徑規劃問題研究比較成熟，在調度方法以及模型算法上都取得了一些研究成果[2-5]。然而目前的車輛路徑規劃研究絕大多數集中在靜態路徑規劃，而對于隨機動態需求下的散點貨源動態集散點設置以及路徑規劃研究相對較少，雖然一些論文研究可變線路客流的動態集散點設置方法[6]，但是客流集散點主要是以固定站點為主，且客流的時間約束較大，因而通常客流動態集散點的應用情況不是太多，而貨源往往隨機性更大，需求的時空分布更加廣泛，時間約束相對較低，因此對貨流的動態集散點設置往往更加具有實際應用意義。

目前，我國城市的住宅主要以“小區式”為主，城市的快件貨源一般呈片區分布。此外，相對于客流而言，雖然快件貨源的時間分布更加分散，不像客流有明顯的高峰時段，但是其對于時間的約束相對較低，因而對散點貨源進行動態集散點設置更加具有現實意義。為了適應散點貨源的這些特點以及提升系統收件的效率，對貨源動態集散點設置進行模型方法研究，是實現快件智能化收集需要解決的重要問題。

1 系統相關概述

1.1 智能取件系統運行流程

智能調度的快遞物件收集是依靠互聯網以及無人駕駛技術，根據用戶的請求，自動規劃取送點以及行駛路線，從而使系統高效、快捷的運行。整個系統運行過程分為：網上預約取件—系統取件時間制定—貨件集散點規劃—車輛路徑規劃—車輛取件。具體如圖1所示：

圖1 智能調度下的系統收件流程

通過該流程，能夠看出此流程的核心在于合理地設置取件時間、規劃散點貨物集散點以及設置一條最優取件路徑，從而使取件車輛能夠迅速到達取件點。相較于定制公交的網上預約模式，智能取件網上預約的需求隨機性更強，客戶一般都是在取件當天某個時間進行預約，系統只能完全根據即刻的預約來迅速響應。因此，系統為了能夠適應需求的隨機性，最大化地滿足取件需求，系統需要解決兩個關鍵問題，一方面是要將用戶已經預約的需求盡量集中，對于動態及時的需求，系統要能夠即時將貨物位置更新到已有路徑中，及時插入集散點，從而使得系統的取件效率達到最大化；另一方面是要規劃一條滿足有效的取件路徑，使得系統用戶能夠在規定的時間內最大限度地滿足攬件需求以及減少運輸成本。其中，將用戶的需求集中不僅僅是要在時間段上的集中，還要使得相近需求的取件點位置的集中，這也是本文的研究重點。

1.2 智能取件系統集散點設置過程

客戶在網上預約取件申請后，系統會按照不同的取件時間段來將各個取件點進行分類。分類完成后，系統首先會尋找位置特殊的需求點（客戶指定的取件點），將其位置作為貨源集散點，然后系統繼續分析其它客戶的請求位置，通過距離判斷這些需求點是否滿足到周邊固定集散點或者特殊位置需求點，如果能夠滿足，系統會直接將其取件位置設置在固定集散點或特殊位置需求點處。如不滿足，系統會根據其它在位置上相近的需求點來設置一個或多個臨時集散點。臨時集散點能夠滿足客戶的隨機性需求，彌補固定集散點的缺陷，然而臨時集散點也會存在貨物安全性以及造成客戶等待問題，因此系統要與客戶“協商”好取件時間。

1.3 智能取件車輛運行模式

與可變線路式公交類似，智能取件車也是按照客戶要求的一種路線可變的智能車輛，當沒有臨時集散點的時候，車輛一般會沿著固定站點位置所在的基準路線運行，當有臨時動態的集散點出現時，車輛會根據時間限制要求進行合理的偏移。具體運行如圖2所示：

圖2 動態集散點智能取件車服務模式

2 基于層次聚類分析法的動態集散點的設置研究

2.1 層次聚類分析方法

聚類分析的思想是根據對象差異，把不同類的對象區分開。它的目標是把混雜在一起的數據盡可能的分隔開，使同一類對象的相似程度盡可能大，使不同對象的相似程度盡可能小。層次聚類法[7]是對數據對象進行分解，基于距離或者密度或者連通性分層。其原理是：首先將給定的N個對象分為N類；然后計算兩個類距離最小并進行合并；其次重新計算類之間的距離，直至所有的聚類完成，形成一個完整的聚類樹。

2.2 動態集散點設置方法

設置貨源動態集散點的目的是使收件車輛能夠在經過盡可能少的服務點的情況下，覆蓋所有的客戶需求點，提高整個系統的運行效率，達到近似“點到點”的服務，將客戶的自行送貨距離限制在一定的范圍內，建立的集散點設置模型如下：

上述的模型中，i和j分別為貨源系統分配的集散點和客戶的需求點，P和S分別表示系統設置的集散點集合和客戶預約需求點集合，nij為二進制變量，當nij=1時表示需求點j分配至集散點i，否則j在i未獲得服務。dij為需求點j與集散點i之間距離，dmax為客戶能夠接受的最大送件距離，dmax與客戶種類、貨物種類等有關。式（1）目標函數表示為系統設置的動態集散點數量最少，式（2）控制客戶從需求點到達最終集散站點的距離不超過最大送件距離，式（3）表示每個需求都要在某個集散站點的服務范圍內。

由集散點設置模型可以看出，當目標函數越小時，系統設置的集散點數目越小，取件車繞行的路程就越小，系統的效率越高。然而集散點數目越少，客戶的送件距離就越大，從而會降低系統服務水平，部分用戶會無法獲得服務。同樣，當系統設置的集散點過多時，整個的收件效率就會下降，因此要找到既能夠滿足系統效率最大，也要能夠滿足絕大多數客戶的需求。此外，對于一般需求點周圍存在位置要求的需求點時，一般的需求點應盡可能先往特殊位置需求點去集散，具體算法流程如圖3所示。具體過程如下：

圖3 動態集散點設置算法流程

步驟1：根據需求點的坐標劃分需求點所在固定集散點范圍。

步驟2：尋找有特殊位置要求的需求點，并計算其它需求點到其距離，若滿足式（2），則優先將其位置更換成特殊位置點。

步驟3：將在同一固定集散點區間內剩下的每個需求點作為一簇，計算兩兩需求點之間距離，生成距離矩陣。

步驟4：搜索距離矩陣中的最小值，該值對應的兩個簇組成新簇，所有新簇中需求點的中心坐標即為新簇的坐標。

步驟5：計算新簇中每個需求點到簇的距離，若滿足約束式（2）則返回步驟3，否則該固定集散點區間內的需求點聚類完成，進入步驟6。

步驟6：重復步驟3至步驟5，直到所有固定集散點區間聚類完成。

步驟7：輸出結果，包括動態集散點坐標，集散點需求數量，以及集散點的客戶平均送件距離等。

3 仿真算例及分析

考慮到固定集散點設置的成本以及使用效率，本文將仿真區域設置為2 000m*2 000m的矩形區域。因為固定集散點的取件幾乎不受時間限制，因此本論文重點仿真某時間段內動態的臨時集散點設置。區域內的需求點隨機生成。本文按照需求點數量以及最大送件距離不同分別進行仿真。以下是以30個普通需求點，2個特殊位置需求點，最大送件距離取300m進行仿真的過程。

隨機生成的需求點如圖4所示：

去掉特殊需求點及其周邊的一般需求點，剩下了22個一般需求點，如圖5所示：

圖4 隨機生成的需求點圖

圖5 去掉特殊位置及周邊需求點后剩下的需求點圖

經過聚類算法形成的聚類樹如圖6所示：

dmax為300時，由圖可知，系統將剩下的22個需求點聚類形成了8個集散點，分別為J1～J9，每個集散點包含的需求點變化如下，J1｛2,3,10,17,21 ｝；J2｛7 ｝；J3｛9,22 ｝；J4｛5,6,1 3｝；J5｛12｝；J6｛1,4,8,11,15,16,18,20｝；J7｛14｝；J8｛19｝；如圖7所示：

按照不同的需求點以及送件距離進行仿真結果如表1所示。

4 結束語

通過對不同需求數量以及送件距離進行的仿真試驗，聚類分析方法能夠將全部的需求點進行合理地集散點設置，充分降低取件點數量，減少車輛繞行，能夠實現“公平送件距離”。且當需求點數量越大時，集散效果越明顯。此外，當系統突然插入需求點時，仍然可以將新的需求點直接聚集到已有的集散點中，這樣既可以客戶不斷變化送件位置，也可以保證車輛到達取件點的準時性，減少拒絕率。

圖6 需求點聚類樹圖

圖7 集散點分布情況圖

表1 不同需求量及最大送件距離下的集散點數量