徐易杰，夏小云，袁建中，莊鶴林，劉會(huì)娟，劉一卓

（嘉興學(xué)院數(shù)理與信息工程學(xué)院，嘉興 314001）

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展和信息技術(shù)的不斷演變，電子商務(wù)已經(jīng)進(jìn)入密集創(chuàng)新和快速擴(kuò)張的階段，成為我國(guó)新興產(chǎn)業(yè)的重要組成部分，極大地影響和改變著人們的生活生產(chǎn)方式。在電子商務(wù)飛速發(fā)展的背景下，對(duì)快遞業(yè)的發(fā)展也產(chǎn)生了深遠(yuǎn)的影響。2018年，全國(guó)快遞包裹量突破500億件，快遞從業(yè)人員超過(guò)300萬(wàn)。根據(jù)國(guó)家郵政局統(tǒng)計(jì)數(shù)據(jù)，“十二五”期間國(guó)內(nèi)快遞業(yè)務(wù)量連續(xù)5年保持50%左右的高速增長(zhǎng)，郵政業(yè)發(fā)展“十三五”規(guī)劃預(yù)計(jì)，2018年至2020年快遞業(yè)務(wù)量復(fù)合增長(zhǎng)率為19.5%。

然而，當(dāng)前快遞產(chǎn)業(yè)的發(fā)展仍然落后于電子商務(wù)爆炸式增長(zhǎng)的需求，不斷增長(zhǎng)的業(yè)務(wù)量給物流運(yùn)輸行業(yè)終端帶來(lái)極大的配送壓力。快遞企業(yè)也逐漸認(rèn)識(shí)到，要想獲得絕對(duì)的競(jìng)爭(zhēng)優(yōu)勢(shì)，必須要在最短的時(shí)間內(nèi)，花費(fèi)最低的成本，給顧客提供最好的產(chǎn)品和服務(wù)[1]。

近年來(lái)，研究人員從理論的角度研究了物流配送車(chē)輛路徑問(wèn)題，如考慮交通擁堵情況[2]、考慮駕駛員滿意度[3]等。這類問(wèn)題考慮了配送過(guò)程中的一些特殊情況，但是還不能用于實(shí)際應(yīng)用中。此外，有學(xué)者研究了路徑規(guī)劃的搜索算法，分析比較了混合搜索算法[4]、遺傳算法[5]等在路徑規(guī)劃中的應(yīng)用。物流配送問(wèn)題已成為當(dāng)前物流行業(yè)研究的熱點(diǎn)領(lǐng)域，非常有必要開(kāi)發(fā)一款針對(duì)快遞員的自動(dòng)配送路徑規(guī)劃軟件，快遞員可以通過(guò)Android手機(jī)端App自動(dòng)獲取配送任務(wù)，根據(jù)自動(dòng)規(guī)劃好的路線進(jìn)行快遞配送。

1 問(wèn)題描述及數(shù)學(xué)模型

智慧物流配送路徑規(guī)劃問(wèn)題是物流系統(tǒng)中最受關(guān)注的問(wèn)題之一。該問(wèn)題自提出之后就受到物流科學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)等相關(guān)學(xué)科的學(xué)者和研究人員的廣泛關(guān)注，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的前沿與熱點(diǎn)研究問(wèn)題，也是一直困擾學(xué)術(shù)界和工業(yè)界的難題。快遞配送路徑規(guī)劃問(wèn)題可以建模為一個(gè)帶約束的優(yōu)化問(wèn)題，是一類NP-難問(wèn)題，傳統(tǒng)的優(yōu)化算法設(shè)計(jì)復(fù)雜、收斂速度慢、且不易找到較優(yōu)解。路徑規(guī)劃問(wèn)題可以描述為給定一定數(shù)量的配送車(chē)輛或快遞員，以及已知的客戶數(shù)量及位置，在滿足需要的約束條件之下，要求從配送中心由快遞員將商品送到不同的客戶手中。目標(biāo)是確定一個(gè)配送方案，使得快遞員的總路程或者總代價(jià)最小?；镜奈锪髋渌吐窂揭?guī)劃問(wèn)題如圖1所示。

圖1 快遞配送路線規(guī)劃示意圖

一般的，我們可以將快遞配送路徑規(guī)劃問(wèn)題表示為一個(gè)具有n+1個(gè)節(jié)點(diǎn)的帶全完全圖G=(V,E)[6]。其中V=(0,1,2,...,N)為頂點(diǎn)集合，代表客戶或者運(yùn)輸點(diǎn)i(i=1,2,...,N)和配送中心 0，E={(i,j)：i≠j}為邊的集合。每一條邊(i,j)上具有一個(gè)非負(fù)的權(quán)重dij，表示客戶i與j之間的距離?？蛻鬷的需求為qi，快遞員k的最大運(yùn)輸容量為Qk。則物流配送路徑規(guī)劃問(wèn)題的數(shù)學(xué)模型描述如下。

其中，N表示客戶數(shù)，K為車(chē)輛數(shù)目為由車(chē)輛k從客戶i運(yùn)輸?shù)娇蛻鬸的代價(jià)。約束以及確保每個(gè)客戶不被重復(fù)服務(wù)確保任何一條路徑的總需求不能超過(guò)快遞員的最大運(yùn)輸容量。

需要指出的是，客戶或運(yùn)輸點(diǎn)之間的為歐氏距離，可以根據(jù)配送點(diǎn)的經(jīng)緯度進(jìn)行計(jì)算。假定當(dāng)前派出五名快遞員，則需要?jiǎng)討B(tài)規(guī)劃五個(gè)配送區(qū)域。蟻群算法是一種非常有效的啟發(fā)式搜索算法，在TSP問(wèn)題、調(diào)度問(wèn)題等NP難問(wèn)題中獲得廣泛應(yīng)用[7]。系統(tǒng)中在服務(wù)器端采用蟻群算法自動(dòng)生成配送路徑，然后推送到Android端給快遞員分配相應(yīng)任務(wù)。

2 系統(tǒng)分析及設(shè)計(jì)

整個(gè)軟件主要分為以下五個(gè)模塊，每個(gè)模塊對(duì)應(yīng)的功能如下：

（1）快遞數(shù)據(jù)入庫(kù)：快遞員通過(guò)快遞掃件入庫(kù)端對(duì)快遞掃碼入庫(kù)，并存入訂單數(shù)據(jù)庫(kù)中。

（2）快遞地址逆編碼：把數(shù)據(jù)庫(kù)里面的快遞的地址進(jìn)行逆編碼，將地址轉(zhuǎn)換成經(jīng)緯度信息，再重新更新數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)增加經(jīng)度和緯度字段。

（3）定時(shí)任務(wù)：每天在規(guī)定時(shí)間啟動(dòng)任務(wù)，對(duì)當(dāng)天訂單進(jìn)行運(yùn)算。主要是通過(guò)經(jīng)緯度信息和快遞員數(shù)量并結(jié)合算法進(jìn)行運(yùn)算，得到配送順序，將配送順序以數(shù)組的方式存入數(shù)據(jù)庫(kù)中。

（4）配送信息獲取：快遞員打開(kāi)配送端App，App將通過(guò)對(duì)應(yīng)快遞員的id查詢對(duì)應(yīng)配送路線數(shù)據(jù)。

（5）路線導(dǎo)航：規(guī)劃配送路線，將已規(guī)劃好的路線推送到App上，快遞員進(jìn)行配送時(shí)，App將根據(jù)已有路線自動(dòng)導(dǎo)航。

Android客戶端采用MVP架構(gòu)，多模塊化設(shè)計(jì)，代碼復(fù)用，降低耦合度，提高內(nèi)聚性。項(xiàng)目的邏輯流程如圖2所示。

圖2 項(xiàng)目邏輯流程圖

3 數(shù)據(jù)庫(kù)設(shè)計(jì)

數(shù)據(jù)庫(kù)采用開(kāi)源MySQL數(shù)據(jù)庫(kù)，在數(shù)據(jù)庫(kù)中建立四個(gè)表，分別為用戶表、總訂單表、當(dāng)天訂單表、路線規(guī)劃表。這些數(shù)據(jù)表是軟件的數(shù)據(jù)基礎(chǔ)。

（1）用戶表（user）：對(duì)注冊(cè)的快遞員用戶進(jìn)行統(tǒng)一管理，包括快遞員id、用戶名、密碼、配送公司、實(shí)名及所在配送驛站地址；

（2）總訂單表（all_orders）：快遞中心對(duì)當(dāng)天所有客戶下單所產(chǎn)生的快遞訂單入庫(kù)登記表，包括訂單id、訂單編號(hào)、配送地址、收件人、寄件地址、聯(lián)系方式、下單時(shí)間；

（3）當(dāng)天訂單（daily_orders）：快遞員對(duì)當(dāng)天的訂單進(jìn)行掃碼入庫(kù)，來(lái)源為總訂單庫(kù)。包括訂單id、訂單編號(hào)、配送地址、收件人、寄件地址、聯(lián)系方式、下單時(shí)間；

（4）路線規(guī)劃表（router_plan）：后端根據(jù)當(dāng)天快遞訂單及分派快遞員進(jìn)行路線規(guī)劃，生成配送路線。包括路徑方案id、快遞員id、規(guī)劃路線數(shù)組。

4 系統(tǒng)功能實(shí)現(xiàn)

本節(jié)主要介紹系統(tǒng)的具體功能。系統(tǒng)Android端主要是數(shù)據(jù)采集及數(shù)據(jù)展示。請(qǐng)求服務(wù)器數(shù)據(jù)接口，獲取對(duì)應(yīng)數(shù)據(jù)，供快遞員查看。然后通過(guò)數(shù)據(jù)信息在地圖上進(jìn)行標(biāo)識(shí)，快遞員只需查看對(duì)應(yīng)配送點(diǎn)的信息，包括配送路線、收貨人姓名、收貨人聯(lián)系方式等。圖3為App軟件的首頁(yè)界面，顯示當(dāng)前天氣情況，派送所在地點(diǎn)?？爝f員能夠查看派單的歷史記錄，當(dāng)前的派送任務(wù)等?？爝f員還能查看所在的快遞站點(diǎn)，如圖4所示。服務(wù)器端根據(jù)派送的訂單情況，訂單所在位置等信息自動(dòng)計(jì)算派送路線，然后推送給Android端供快遞員接收派遞任務(wù)，如圖5所示。快遞員能夠在Android端收到派送任務(wù)之后，根據(jù)規(guī)劃好的路線進(jìn)行快遞配送。

5 結(jié)語(yǔ)

物流行業(yè)是當(dāng)下熱門(mén)行業(yè)，其存在的物流配送效率低等問(wèn)題也較為突出。通過(guò)研究快遞配送路線的合理規(guī)劃，確實(shí)幫助快遞小哥尋找最優(yōu)的配送路線，解決當(dāng)前快遞不快的現(xiàn)象，減少客戶因?yàn)榘倪t到而發(fā)生的抱怨、負(fù)面情緒甚至投訴等現(xiàn)象的發(fā)生，真正幫助快遞企業(yè)樹(shù)立良好的企業(yè)形象，降低快遞成本，創(chuàng)造更多價(jià)值。實(shí)現(xiàn)了快遞員配送路線自動(dòng)規(guī)劃需求，極大地將快遞員從繁瑣的任務(wù)中解脫出來(lái)。軟件基于智能手機(jī)Android端實(shí)現(xiàn)，使用非常方便。不僅能夠有效提高物流配送效率，增強(qiáng)客戶服務(wù)的滿意度，減少因客戶投訴以及客戶退貨退款的經(jīng)濟(jì)損失，緩解城市交通壓力，而且能夠減少物流配送過(guò)程給環(huán)境帶來(lái)的影響。

圖3 App軟件首頁(yè)界面

圖4 快遞站點(diǎn)列表

圖5 快遞員配送路線規(guī)劃示意圖