基于智能調(diào)度的散點貨源動態(tài)集散點設(shè)置研究

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

（南京林業(yè)大學(xué) 汽車與交通工程學(xué)院，江蘇 南京 210037）

0 引言

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

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

1 系統(tǒng)相關(guān)概述

1.1 智能取件系統(tǒng)運行流程

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

圖1 智能調(diào)度下的系統(tǒng)收件流程

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

1.2 智能取件系統(tǒng)集散點設(shè)置過程

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

1.3 智能取件車輛運行模式

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

圖2 動態(tài)集散點智能取件車服務(wù)模式

2 基于層次聚類分析法的動態(tài)集散點的設(shè)置研究

2.1 層次聚類分析方法

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

2.2 動態(tài)集散點設(shè)置方法

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

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

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

圖3 動態(tài)集散點設(shè)置算法流程

步驟1：根據(jù)需求點的坐標(biāo)劃分需求點所在固定集散點范圍。

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

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

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

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

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

步驟7：輸出結(jié)果，包括動態(tài)集散點坐標(biāo)，集散點需求數(shù)量，以及集散點的客戶平均送件距離等。

3 仿真算例及分析

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

隨機(jī)生成的需求點如圖4所示：

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

圖4 隨機(jī)生成的需求點圖

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

經(jīng)過聚類算法形成的聚類樹如圖6所示：

dmax為300時，由圖可知，系統(tǒng)將剩下的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所示：

按照不同的需求點以及送件距離進(jìn)行仿真結(jié)果如表1所示。

4 結(jié)束語

通過對不同需求數(shù)量以及送件距離進(jìn)行的仿真試驗，聚類分析方法能夠?qū)⑷康男枨簏c進(jìn)行合理地集散點設(shè)置，充分降低取件點數(shù)量，減少車輛繞行，能夠?qū)崿F(xiàn)“公平送件距離”。且當(dāng)需求點數(shù)量越大時，集散效果越明顯。此外，當(dāng)系統(tǒng)突然插入需求點時，仍然可以將新的需求點直接聚集到已有的集散點中，這樣既可以客戶不斷變化送件位置，也可以保證車輛到達(dá)取件點的準(zhǔn)時性，減少拒絕率。

圖6 需求點聚類樹圖

圖7 集散點分布情況圖

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