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

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

0 引言

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

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

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

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

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

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

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

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

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

1.3 智能取件車輛運(yùn)行模式

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

圖2 動(dòng)態(tài)集散點(diǎn)智能取件車服務(wù)模式

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

2.1 層次聚類分析方法

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

2.2 動(dòng)態(tài)集散點(diǎn)設(shè)置方法

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

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

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

圖3 動(dòng)態(tài)集散點(diǎn)設(shè)置算法流程

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

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

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

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

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

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

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

3 仿真算例及分析

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

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

去掉特殊需求點(diǎn)及其周邊的一般需求點(diǎn)，剩下了22個(gè)一般需求點(diǎn)，如圖5所示：

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

圖5 去掉特殊位置及周邊需求點(diǎn)后剩下的需求點(diǎn)圖

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

dmax為300時(shí)，由圖可知，系統(tǒng)將剩下的22個(gè)需求點(diǎn)聚類形成了8個(gè)集散點(diǎn)，分別為J1～J9，每個(gè)集散點(diǎn)包含的需求點(diǎn)變化如下，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所示：

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

4 結(jié)束語(yǔ)

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

圖6 需求點(diǎn)聚類樹(shù)圖

圖7 集散點(diǎn)分布情況圖

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