基于啟發式搜索的快遞員配送路徑規劃Android端設計與實現

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

（嘉興學院數理與信息工程學院，嘉興 314001）

0 引言

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

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

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

1 問題描述及數學模型

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

圖1 快遞配送路線規劃示意圖

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

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

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

2 系統分析及設計

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

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

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

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

（4）配送信息獲取：快遞員打開配送端App，App將通過對應快遞員的id查詢對應配送路線數據。

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

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

圖2 項目邏輯流程圖

3 數據庫設計

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

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

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

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

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

4 系統功能實現

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

5 結語

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

圖3 App軟件首頁界面

圖4 快遞站點列表

圖5 快遞員配送路線規劃示意圖