基于啟發(fā)式搜索的快遞員配送路徑規(guī)劃Android端設計與實現(xiàn)

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

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

0 引言

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

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

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

1 問題描述及數(shù)學模型

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

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

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

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

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

2 系統(tǒng)分析及設計

整個軟件主要分為以下五個模塊，每個模塊對應的功能如下：

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

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

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

（4）配送信息獲?。嚎爝f員打開配送端App，App將通過對應快遞員的id查詢對應配送路線數(shù)據(jù)。

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

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

圖2 項目邏輯流程圖

3 數(shù)據(jù)庫設計

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

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

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

（3）當天訂單（daily_orders）：快遞員對當天的訂單進行掃碼入庫，來源為總訂單庫。包括訂單id、訂單編號、配送地址、收件人、寄件地址、聯(lián)系方式、下單時間；

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

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

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

5 結(jié)語

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

圖3 App軟件首頁界面

圖4 快遞站點列表

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