[發明專利]基于線性時序邏輯的移動端快遞派送路徑規劃方法

有效

• 申請號: 201710265209.4
• 申請日: 2017-04-21
• 公開（公告）號: CN107169591B
• 公開（公告）日: 2020-10-27
• 發明（設計）人: 歐林林;郭永奎;禹鑫燚;汪濤;盧靚;張愛美
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

基于線性時序邏輯理論的移動端快遞派送路徑規劃方法，在Android系統的智能手機平臺上，利用百度地圖開發包構建符合實際派送環境的加權切換系統，同時利用線性時序邏輯語言描述多點派送任務，并將其轉化為Büchi自動機，接著將切換系統與派送任務相融合，構建任務可行網絡拓撲，在任務可行網絡拓撲上利用Dijkstra算法搜索最優路徑，然后將該路徑映射回百度地圖，獲得離散的最優路徑，最后利用百度地圖開發包的定位導航功能，實現離散路徑的連續化。該發明能夠解決多點派送任務與派送區域受約束的問題，并保證快遞員派單路徑的最優性，提高快遞員派送效率，實現互聯網+的智慧派送。

技術領域

本發明涉及針對快遞派送任務的最優路徑規劃領域，針對目前快遞派送任務點較多，派送區域受快遞員熟悉度限制問題，本發明提出了一種基于線性時序邏輯(LTL)的移動端多點快遞派送路徑規劃方法，該方法以移動端百度地圖開發包為基礎，避免了快遞員實際派送環境的復雜建模，能夠解決多點派送任務與派送區域受約束的問題，并保證快遞員派單路徑的最優性。

背景技術

近年來，互聯網得到迅速發展，衍生的電子商務也越來越普遍，網購也被大多數人所接受。隨之帶來的是快遞物流壓力，傳統的快遞物流模式已無法滿足現在的生產生活需求。在物流的倉儲揀貨階段，傳統的人工揀貨已逐漸被倉儲機器人揀貨代替，智能化倉庫已經被大量研究，亞馬遜公司裝備Kiva機器人的智能化倉庫已經帶來巨大效益。而快遞派送作為物流的末端環節，快遞派送的時效性直接影響客戶的滿意度，派送環節就是檢驗快遞服務水平和質量的關鍵。目前，快遞員派送的區域受到快遞員對該區域熟悉度的限制，此外，派送點較多時，快遞員難以憑借對地理熟悉度規劃一條最優派送路線，而現有的地圖導航功能實現的也僅僅是兩點之間的導航，這些約束嚴重影響了快遞派送的時效性。根據快遞員派送任務，規劃一條最優路徑使派送距離最短將提高快遞員的派送效率，多點快遞派送任務的路徑規劃研究具有重要的理論與現實意義。

快遞員派送任務的路徑規劃問題，也就是快遞員從貨物分發處出發，遍歷所有派送點，最后回到分發處，找到一條最短的路徑，該問題屬于典型的TSP問題。當前，關于路徑規劃問題，已經有了一些研究成果。丁浩和萇道方基于Dijkstra算法研究了快遞車輛配送路徑優化問題，考慮了配送車輛行駛的最大距離以及配送負載約束建立約束條件，從配送起點開始搜索，依次搜索距離當前節點最近的地點作為下一節點，直至遍歷所有派送點(基于Dijkstra算法的快遞車輛配送路徑優化.價值工程,2014,(03):15-18)；徐彬,王權鋒和劉斌等將A*算法與貪心算法相結合來解決物流配送路徑的選擇，A*算法加入了啟發函數可以提高搜索效率，利用貪心算法思想實現多點派送的目的(貪婪和A-Star算法在物流配送中的應用及仿真.軟件,2013,34(6):35-39)。但以上這兩種方法，都是在經典的針對點對點路徑規劃算法基礎之上，結合貪心算法思想實現多點派送的路徑規劃任務，該方法很難獲得全局最優路徑，大多得到的是次優路徑，Dijkstra算法能保證兩點間路徑的最優性，但是無法獲得多點快遞派送這類復雜任務的最優路徑。