應(yīng) 毅，任 凱，劉亞軍

1.三江學(xué)院 計算機(jī)科學(xué)與工程學(xué)院，南京 210012

2.南京大學(xué) 金陵學(xué)院，南京 210089

3.東南大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，南京 210096

1 引言

隨著信息通信技術(shù)的快速發(fā)展和基于互聯(lián)網(wǎng)/移動互聯(lián)網(wǎng)的各類應(yīng)用的普及，以商品購銷為核心的電子商務(wù)逐漸成為經(jīng)濟(jì)增長的新亮點。第三方物流是為電子商務(wù)活動提供物流服務(wù)的基礎(chǔ)設(shè)施，其基本流程由倉儲系統(tǒng)、運輸主干網(wǎng)、“最后一公里”配送三個階段組成[1]。

在物流末端的配送服務(wù)中，快遞人員從網(wǎng)點出發(fā)，沿預(yù)先設(shè)置好的路徑將快件派送到客戶手中，同時從客戶手中接收快件，最后將所有收件返回網(wǎng)點。在此情況下，快遞人員頻繁往返于客戶和網(wǎng)點之間。該問題在理論上可歸類為車輛路徑問題（Vehicle Routing Problem，VRP）的應(yīng)用。VRP 在 1959 年首次被提出[2]，現(xiàn)已廣泛應(yīng)用在分撥中心（倉庫/集散地）之間的車輛調(diào)度和路徑安排上。

物流管理尤其是物流配送過程對地理空間信息有著較強(qiáng)的依賴性，地理信息系統(tǒng)（Geographic Information System，GIS）[3]具備地理空間信息分析處理能力，能在獲取、存儲相關(guān)數(shù)據(jù)的基礎(chǔ)上進(jìn)行有效加工，幫助決策。在移動操作系統(tǒng)、3G/4G 通信網(wǎng)絡(luò)和GPS 的支持下，基于位置服務(wù)（Location Based Service，LBS）越來越完善，結(jié)合GIS/移動GIS[4]，構(gòu)成智慧物流建設(shè)的關(guān)鍵技術(shù)。文獻(xiàn)[5]結(jié)合GIS手段和SPSS分析對模擬退火算法改進(jìn)來求解VRP問題。文獻(xiàn)[6]提出一種結(jié)合GIS模型約束的啟發(fā)式-模擬退火混合搜索算法解決VRP 問題。文獻(xiàn)[7]設(shè)計了GPS/GIS 協(xié)同下的智能車輛監(jiān)控和調(diào)度系統(tǒng)，構(gòu)建了基于實時信息且?guī)r間窗的動態(tài)VRP 混合整數(shù)規(guī)劃模型。文獻(xiàn)[8]將3G技術(shù)運用于配送管理，設(shè)計了一個物流配送系統(tǒng)模型。文獻(xiàn)[9]將Dijkstra算法與WebGIS相結(jié)合，調(diào)用pgRouting實現(xiàn)起始點定位查詢最短路徑的方法。文獻(xiàn)[10]結(jié)合MapGIS的網(wǎng)絡(luò)分析功能，探討城市配送中心選址及路徑優(yōu)化問題。以上研究皆是依托GIS技術(shù)對傳統(tǒng)VRP求解的擴(kuò)充和優(yōu)化，但物流末端的攬送混合業(yè)務(wù)與單純的投遞業(yè)務(wù)又有較大不同，攬送混合業(yè)務(wù)的目標(biāo)是快速響應(yīng)客戶的寄件請求并保證行駛距離最短。針對此問題，本文在ArcGIS 平臺基礎(chǔ)上，構(gòu)建智能物流信息系統(tǒng)，考慮寄件請求的動態(tài)性和任務(wù)調(diào)度的實時性，提出基于加權(quán)kNN 的實時攬件調(diào)度算法，實現(xiàn)快遞人員的攬件調(diào)度。實驗證明這種利用GIS技術(shù)和數(shù)據(jù)挖掘算法的人員調(diào)度方法，能更快地響應(yīng)客戶需求，更好地縮短行駛距離，有效提高末端物流的配送效率。

本文首先闡述了智能物流信息系統(tǒng)的架構(gòu)設(shè)計；在此框架下，詳述了實時攬件調(diào)度算法的原理和具體實現(xiàn)；最后在菜鳥驛站某網(wǎng)點的配送活動中進(jìn)行算法實驗和應(yīng)用。

2 智能物流信息系統(tǒng)架構(gòu)與實現(xiàn)

現(xiàn)代物流系統(tǒng)是在智能交通和信息技術(shù)的基礎(chǔ)上運作的物流服務(wù)體系，通過對各物流環(huán)節(jié)的信息采集和數(shù)據(jù)處理，為物流企業(yè)和客戶提供高效管理和高質(zhì)量服務(wù)。本文基于GIS 技術(shù)、Web 技術(shù)和移動開發(fā)技術(shù)，構(gòu)建了針對“最后一公里”配送的智能物流信息系統(tǒng)。

2.1 基于ArcGIS的智能物流信息系統(tǒng)架構(gòu)

智能物流信息系統(tǒng)采用三層架構(gòu)體系，由應(yīng)用服務(wù)層、業(yè)務(wù)邏輯層、物流數(shù)據(jù)層組成。如圖1 所示。系統(tǒng)整體基于Java語言和Esri ArcGIS 10.4開發(fā)實現(xiàn)。

圖1 智能物流信息系統(tǒng)架構(gòu)

業(yè)務(wù)邏輯層是本系統(tǒng)的核心，包含Web Server 和ArcGIS Server兩部分，Web Server由傳統(tǒng)的Java EE服務(wù)器JBoss和ArcGIS Web Adaptor組成。Web Adaptor組件使ArcGIS Server 和傳統(tǒng)的Web 服務(wù)器相結(jié)合，提供更豐富的功能和更高的安全性（例如用戶鑒權(quán)），Web Adaptor 是GIS 服務(wù)使用者的單一入口，接收客戶端的請求，然后把請求轉(zhuǎn)發(fā)給站點內(nèi)的ArcGIS Server。與GIS 相關(guān)的服務(wù)由ArcGIS Server 負(fù)責(zé)提供，如：空間數(shù)據(jù)管理、地圖可視化、路徑分析等。

在應(yīng)用服務(wù)層，ArcGIS for Desktop[11]是GIS資源（如地圖）的創(chuàng)建者，并通過ArcMap 連接到ArcGIS Server將本地資源發(fā)布為Web 服務(wù)。ArcMap 是ArcGIS for Desktop中一個主要程序，具有基于地圖的所有功能，包括地圖制作、地理數(shù)據(jù)分析和編輯等。調(diào)度管理和移動終端是GIS服務(wù)的使用者和消費者，其中移動終端是物流配送人員的手持設(shè)備。

物流數(shù)據(jù)層完成數(shù)據(jù)的存儲功能。地理數(shù)據(jù)對象在Oracle數(shù)據(jù)庫中以表的形式保存；MySQL為Java EE應(yīng)用存儲系統(tǒng)的普通業(yè)務(wù)數(shù)據(jù)（如客戶信息）。

2.2 智能物流信息系統(tǒng)的關(guān)鍵技術(shù)實現(xiàn)

（1）ArcGIS網(wǎng)絡(luò)分析與二次開發(fā)

傳統(tǒng)VRP 模型的搜索網(wǎng)絡(luò)圖比較簡單，是以客戶為節(jié)點、已知最短路徑為邊的無向圖?；贕IS的VRP問題的搜索網(wǎng)絡(luò)圖由客戶節(jié)點、路徑節(jié)點和路徑共同構(gòu)成，還需考慮實際道路的通行限制（如單向/雙向行駛、道路通行能力）。因此，GIS 環(huán)境下的VRP 模型更加貼合實際情況，也更加復(fù)雜。

GeoProcessing Service（地理處理服務(wù)）可以將自定義的各種分析處理模型發(fā)布為Web 服務(wù)。智能物流信息系統(tǒng)中針對派件/攬件業(yè)務(wù)的智能調(diào)度算法即通過GeoProcessing 組件的二次開發(fā)來實現(xiàn)，其中ArcGISNetwork Analyst擴(kuò)展模塊具有交通路網(wǎng)分析功能，可以求解實際道路的最短路徑問題，求解過程是在Dijkstra算法基礎(chǔ)上的效率優(yōu)化改進(jìn)。

（2）移動終端的實時定位和跟蹤

移動終端主要針對Android 操作系統(tǒng)，以ArcGIS Runtime SDK for Android 為開發(fā)框架。Android 自身提供了三種定位方式：GPS定位、網(wǎng)絡(luò)定位、基于基站的定位。移動終端每隔指定的時間（例如30 s）通過移動通信網(wǎng)絡(luò)向物流系統(tǒng)報告一次定位信息，信息內(nèi)容包括：經(jīng)度/緯度、車輛速度、行駛方向、上報時間等。物流系統(tǒng)實時接收所有終端定時上報的位置信息，依托ArcGIS的地圖服務(wù)可將這些位置數(shù)據(jù)反映在電子地圖上，方便監(jiān)控物流車輛的運行軌跡和配送人員的活動情況。

（3）移動端功能實現(xiàn)

移動端APP為配送人員提供上報位置信息、接收調(diào)度指令等物流服務(wù)功能。ArcGIS對微軟Bing在線地圖支持較好，但Bing地圖要素精度較差，地址尤其是街道、小路標(biāo)注不夠詳細(xì)，故選擇國內(nèi)高德地圖。通過PcArc-BruTile 插件[12]在 ArcMap 中加載高德地圖為 BaseMap，制作矢量數(shù)據(jù)、配置符號化顯示、屬性域等信息，發(fā)布FeatureServer 至ArcGIS Server，開啟同步功能。ArcGIS Runtime SDK for Android 支持完全離線，移動端APP訪問FeatureServer，下載離線地圖數(shù)據(jù)。

2.3 智能物流業(yè)務(wù)流程

（1）大多數(shù)業(yè)務(wù)由調(diào)度管理或移動端應(yīng)用（APP、微信小程序）觸發(fā)。

（2）ArcGIS Server收到服務(wù)請求后，收集位置信息（包括網(wǎng)點、快遞員、客戶），按需進(jìn)行地址定位服務(wù)。定位服務(wù)是利用全國郵政協(xié)定將地址轉(zhuǎn)換成地理位置的方法，通過地址定位服務(wù)才可以由輸入地址信息找到地圖上對應(yīng)的feature點，但是鑒于國內(nèi)地理編碼工作還不完善，地名數(shù)據(jù)庫僅達(dá)到根據(jù)地名返回坐標(biāo)范圍的程度，所以使用了自開發(fā)的地名地址檢索組件[13]。

（3）ArcGIS Server以地理位置作為輸入數(shù)據(jù)，調(diào)用GeoProcessing 的路徑查詢服務(wù)或二次開發(fā)的智能調(diào)度算法，進(jìn)行地理數(shù)據(jù)的分析處理。

（4）將處理結(jié)果轉(zhuǎn)化成柵格格式數(shù)據(jù)，通過HTTP協(xié)議反饋給調(diào)度管理Web端或移動端APP。

（5）各客戶端通過瀏覽器或ArcGIS 內(nèi)置插件將ArcGIS Server提供的服務(wù)呈現(xiàn)出來。

3 實時攬件調(diào)度算法

當(dāng)前，大多數(shù)網(wǎng)點的派件和攬件業(yè)務(wù)混合在一起由快遞人員完成?；诔杀究紤]，快遞人員會根據(jù)經(jīng)驗預(yù)先設(shè)置好送件路徑，但有些寄件業(yè)務(wù)是實時發(fā)生的。而且，在一個區(qū)域內(nèi)，會同時有若干個快遞人員在工作。調(diào)度哪一個快遞人員前去攬件，在某種程度上決定了物流成本的高低。

直觀上看，快遞人員距離客戶的遠(yuǎn)近決定了收件是否及時。可以將客戶視為kNN 算法中的未知樣本，所有快遞人員看作訓(xùn)練樣本，調(diào)度最合適快遞人員即為尋找最接近新樣本的1個訓(xùn)練樣本。

3.1 kNN分類算法理論

最近鄰分類法（Nearest Neighbor Classifier）[14]基于類比學(xué)習(xí)，通過將給定的檢驗樣本與和它相似的訓(xùn)練樣本進(jìn)行比較來學(xué)習(xí)。當(dāng)給定一個未知樣本時，kNN搜索模式空間，找出最接近未知樣本的k個訓(xùn)練樣本，這k個訓(xùn)練樣本是未知樣本的k個“最近鄰”[15]。當(dāng)k=1 時，未知樣本被指派到模式空間中最接近它的訓(xùn)練樣本所在的類。

世界是五彩繽紛的，色彩存在于人類生活的每一個空間，色彩既可以裝點生活，美化環(huán)境，給人以美的享受，也是社會發(fā)展和人類精神文明的一種體現(xiàn)。色彩具有很強(qiáng)的心理作用,每一種顏色都具有特殊的心理作用，影響人的溫度知覺，給人錯落有致的節(jié)奏感，在園林景觀設(shè)計中，色彩最容易將人的視覺美感激發(fā)起來，最明朗的體現(xiàn)園林景觀的特色，作為園林景觀的重要組成部分，色彩景觀的妥善處理具有十分重要的意義。

3.2 基于加權(quán)kNN的實時攬件調(diào)度算法

作為一種惰性學(xué)習(xí)方法，kNN算法直到有樣本需要分類時才建立分類模型，逐個計算與訓(xùn)練樣本的相似程度，相似程度一般以樣本間的距離作為評判指標(biāo)。

傳統(tǒng)kNN 算法對所有訓(xùn)練樣本同等對待，但攬件調(diào)度的分類過程不僅要考慮實際距離，還要考慮快遞人員是否順路、當(dāng)前道路狀況等因素。因此，使用加權(quán)kNN 算法對訓(xùn)練樣本賦予不同的權(quán)值以體現(xiàn)其貢獻(xiàn)度的高低[16]。一般做法是將距離轉(zhuǎn)換為權(quán)值，較近的訓(xùn)練樣本被賦予較大的權(quán)值。

令di為訓(xùn)練樣本i與未知樣本x的距離，wi代表其權(quán)重，加權(quán)kNN 算法最簡單的形式是返回距離的倒數(shù)，即wi=1/di。但倒數(shù)形式使得近鄰的樣本權(quán)重很大，稍遠(yuǎn)一點的樣本權(quán)重又衰減迅速。高斯函數(shù)克服了倒數(shù)函數(shù)的缺點，在距離為0時權(quán)重為1，隨著距離的增加，權(quán)重逐漸減小，但衰減不會過快，且保證衰減不會為0。其形式為：

同時，設(shè)置懲罰因子δ，通過快遞人員的行駛方向是否與寄件人地址一致來調(diào)整樣本權(quán)值的計算。定義如下：

經(jīng)懲罰因子δ調(diào)整后的權(quán)值計算公式為：

計算所有訓(xùn)練樣本的wi′，wi′最大的訓(xùn)練樣本即為最合適的攬件人員。

在智能物流信息系統(tǒng)的基礎(chǔ)上，結(jié)合加權(quán)kNN 算法的實時攬件調(diào)度過程如下：

（1）客戶下單觸發(fā)攬件調(diào)度任務(wù)，將寄件人地址通過地名地址檢索技術(shù)轉(zhuǎn)換為位置信息。

（2）利用GPS/4G 定位技術(shù)通過移動端APP 的定時上報功能得到各快遞人員的位置信息。

（3）調(diào)用 ArcGIS GeoProcessing 的NAServer 模塊，計算各快遞人員與寄件人在道路網(wǎng)絡(luò)中的實際最短距離di。

（4）根據(jù)di和快遞人員的方向信息執(zhí)行加權(quán)kNN算法計算wi′，選擇最合適的攬件人員，發(fā)送調(diào)度指令。

整個流程如圖2所示。

圖2 實時攬件調(diào)度執(zhí)行流程

4 應(yīng)用實例

4.1 實驗區(qū)域概況

菜鳥驛站莫愁新寓網(wǎng)點為客戶提供自助提貨和送件、收件等門到門服務(wù)。網(wǎng)點配送范圍為漢北街、北圩路、水西門大街、莫愁湖西路、漢中門大街構(gòu)成的四邊形區(qū)域，區(qū)域面積大約0.4 km2，服務(wù)莫愁新寓、勁順花園、金貿(mào)新寓、金基唐城等居民小區(qū)，服務(wù)人口約3.2 萬人。區(qū)域內(nèi)住宅小區(qū)多，人口密度大，對物流服務(wù)質(zhì)量要求高，通過對網(wǎng)點實際配送情況的調(diào)研，將本文設(shè)計的智能物流信息系統(tǒng)進(jìn)行應(yīng)用，取得了較為成功的效果。

4.2 電子地圖制作

城市道路網(wǎng)在電子地圖中的表現(xiàn)形式為數(shù)字化的矢量地圖，GIS 中矢量地圖是按照圖層組織的，每個圖層存放一類專題或一類信息，它由點、線、面等空間對象的集合組成。本次實驗所需的電子地圖制作流程如下：

（1）以高德地圖南京市鼓樓區(qū)地圖為基礎(chǔ)，使用ArcMAP建立配送區(qū)域的矢量地圖底圖（BaseMap）。

（2）制作道路圖層，用于描述道路的地理靜態(tài)信息，如通行車輛限制、單行/雙行、平交/立交，這在NAServer模塊計算最短路徑時具有實際作用。

（3）制作網(wǎng)點和客戶圖層，標(biāo)注網(wǎng)點和主要客戶的經(jīng)度/緯度數(shù)據(jù)，經(jīng)緯度數(shù)據(jù)可以通過定位儀器實地勘測或高德地圖抓取（例如網(wǎng)點門店地理坐標(biāo)為32°03′86″N，118°75′59″E；金貿(mào)新寓西北門坐標(biāo)為 32°03′97″N，118°76′16″E）。實際應(yīng)用時，由于許多客戶距離主干道有一定距離，如小區(qū)內(nèi)的住戶，車輛在小區(qū)內(nèi)行駛不存在優(yōu)化空間。因此，對于非臨街客戶點，簡化的處理方法是將其映射到路邊。這個映射過程由地名地址檢索組件完成。

4.3 實驗結(jié)果分析

網(wǎng)點共有4 名快遞服務(wù)人員，根據(jù)業(yè)務(wù)繁忙情況，一般有2～3人進(jìn)行上門服務(wù)。圖3顯示了一次快遞人員攬件調(diào)度的移動端推送結(jié)果。表1 羅列了2019 年2 月25日上午的實際攬件情況。數(shù)據(jù)表明，快遞人員每一次攬件行駛300～800 m不等，城市道路中電動自行車的行駛速度大約是20 km/h，故一次攬件的服務(wù)響應(yīng)時間不超過5 min。

圖3 攬件調(diào)度移動端推送結(jié)果

表1 2月25日上午的實際攬件情況

表2統(tǒng)計了2019年2月底至3月初網(wǎng)點整體的上門攬件情況。由于服務(wù)區(qū)域大多為居民小區(qū)，攬件需求明顯呈現(xiàn)出節(jié)假日偏多的特性。15天共上門攬件447件，快遞人員共行駛310 249 m，平均一次攬件行駛近700 m。根據(jù)行業(yè)報告[17]，單個收件包裹行駛1 km左右。與此相比，實時攬件調(diào)度方法降低了30%的行駛距離。

為了衡量新方法的有效性和優(yōu)越性，將本文提出的基于加權(quán)kNN的實時攬件調(diào)度算法與基于預(yù)知時間的快遞車輛攬件路徑模型[18]進(jìn)行了對比實驗。以表1所示的2月25日上午的實際情況作為實驗數(shù)據(jù)，假設(shè)有2名快遞人員進(jìn)行配送服務(wù)，初始時刻快遞人員位于網(wǎng)點。根據(jù)客戶的寄件需求，基于預(yù)知時間的快遞車輛攬件路徑模型規(guī)劃出2條攬件路線，對路線結(jié)果在智能物流信息系統(tǒng)中統(tǒng)計總行駛距離，與基于加權(quán)kNN 的實時攬件調(diào)度算法的實際距離進(jìn)行比較，如表3所示。

表2 網(wǎng)點整體攬件情況（15天）

表3 兩種算法計算結(jié)果對比m

分析數(shù)據(jù)可知，基于預(yù)知時間的快遞車輛攬件路徑模型在未考慮實時性的前提下，即寄件需求全部提前知曉，規(guī)劃出的總行駛距離為5 650 m，基于加權(quán)kNN 的實時攬件調(diào)度算法指派快遞人員的實際行駛距離為5 171 m，后者比前者有8.5%的距離優(yōu)化。由此可見，相比傳統(tǒng)算法，本文設(shè)計的實時攬件調(diào)度方法，有效縮短攬件路程，節(jié)省了上門服務(wù)的時間和成本。

5 結(jié)束語

現(xiàn)代物流系統(tǒng)已經(jīng)進(jìn)入了信息化、網(wǎng)絡(luò)化、智能化的發(fā)展階段。本文利用ArcGIS、Android、GPS等關(guān)鍵技術(shù)構(gòu)建了適用于物流末端配送業(yè)務(wù)的智能物流信息系統(tǒng)。在該系統(tǒng)中改進(jìn)加權(quán)kNN分類算法應(yīng)用于快遞人員的實時攬件調(diào)度，實現(xiàn)了調(diào)度結(jié)果在移動端APP上的可視化推送。通過實驗驗證了算法的正確性與GIS 技術(shù)在物流行業(yè)中應(yīng)用模式的有效性，提高了物流信息的管理效率。寄件訂單的并單處理和人員調(diào)度是進(jìn)一步研究的重點，在智能系統(tǒng)下改進(jìn)傳統(tǒng)VRP 模型進(jìn)行送件路徑規(guī)劃也是一個較好的研究方向。