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

有效

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

1.一種基于線性時序邏輯的移動端快遞派送路徑規劃方法，具體步驟如下：

步驟1：在Android平臺上，基于百度地圖開發包進行加權切換系統的構建；

根據快遞派送任務地點，將快遞派送轉化為旅行商問題，避開百度地圖復雜道路網絡的建模，僅將任務地點建模為一個加權的有限狀態切換系統，即weighted finite-statetransition system,簡稱WFTS；WFTS是一個元組T＝(Q,q₀,δ_T,AP,L_T,ω_T)，其中Q是一個有限的狀態集；q₀∈Q是初始狀態，代表派送員派送的起點；δ_T∈Q×Q代表切換關系；AP代表原子命題集；L_T:Q→2^AP代表標識函數集；ω_T:代表兩狀態之間切換的成本，即時間和距離；基于百度地圖開發包能夠獲取地圖中任意兩點之間的實際駕車距離，將實際駕車距離作為它們間的切換權重；距離的獲取是通過調用百度地圖開發包的兩點駕駛距離方法得到，即算法一中的BmapDrivingDis()，進而將任務點構建為有限狀態的加權切換系統WFTS，算法一具體過程如下：

算法一：構建加權切換系統T，即ConstructT()

1)首先輸入派送起點P0，派送地點集P；

2)令Q＝P，q₀＝P₀，i＝0,1,2...n，j＝0,1,2...n；

3)如果i≠j且q_j∈δ(q_i)時，ω(q_i,q_j)＝BmapDrivingDis(q_i,q_j)，否則ω(q_i,q_j)＝inf；

4)循環步驟3，直至全部ω(q_i,q_j)都被賦值；

5)輸出加權切換系統T；

步驟2：線性時序邏輯語言描述多點快遞派送任務；

針對快遞員派送任務，線性時序邏輯語言能夠方便的描述這些任務，它由原子命題和操作符構成，具有如下形式：

其中，α∈AP是一個原子命題，符號∨即與、和即非是標準布爾操作符，F即最終，G即總是和U即直到是時序操作符，Fφ₀表示φ₀的最終狀態為真，實現訪問，表示全局總是避免φ₃，能夠用于避障，φ₄Uφ₅表示直到φ₅為真，φ₄一直保持為真；得到快遞任務公式φ后，通過LTL2BA工具包將其轉化為一個Büchi自動機，Büchi自動機是一個元組A_φ:＝(S_φ,S₀,∑_φ,δ_φ,F_φ)，其中S_φ代表一個有限的狀態集；S₀∈S_φ代表初始狀態；∑_φ代表輸入的字符表；代表切換函數；代表最終狀態集；

步驟3：構建任務可行網絡拓撲；

為將環境信息與任務信息相融合確保最終搜索的路徑既滿足環境信息又符合快遞派送需求，通過將加權切換系統與Büchi自動機笛卡爾乘積，利用Product自動機構建任務可行網絡拓撲，即它也是一個元組A_P＝(S_P,S_P0,δ_P,ω_P,F_P)，其中是狀態集；S_P0＝{q₀}×S₀代表初始狀態集；δ_P:代表狀態間的切換函數，其定義為當且僅當q_j∈δ_T(q_i)并且s_l∈δ_φ(s_k,L_B(q_i))時，(q_j,s_l)∈δ_P((q_i,s_k))成立；ω_P:S_P×S_P→R⁺繼承自T且為正的權重函數，即當(q_j,s_l)∈δ_P((q_j,s_k))時，則ω_P((q_i,s_k),(q_j,s_l))＝ω_T(q_i,q_j)；F_P＝Q×F_φ代表一個最終的接收狀態集；對于任務可行網絡拓撲的一個搜索路徑r_P，如果那么此r_P是可被接受的，其中inf(r_P)代表路徑的循環部分；

步驟4：快遞派送最優離散路徑搜索；

在構建任務可行網絡拓撲A_P后，根據快遞派送的起始狀態，最終接收狀態和狀態間的切換關系，利用Dijkstra最短路徑搜索算法搜索最終的可行離散路徑，Dijkstra()代表Dijkstra算法，minCost()為求最小花費方法，算法過程如算法二所示：

算法二：搜索最優路徑r_P，即OptimalPath()

6)首先輸入T，A_φ，搜索起點s_P0＝(q₀,s₀)；

7)然后構建任務可行網絡拓撲S_P0＝s_P0；

8)如果Product自動機的最終接收狀態集則返回空路徑；

9)否則，對于A_P每一個最終接收狀態f_P∈F_P，利用Dijkstra算法搜索可行路徑r_P；

10)如果可行路徑則路徑不存在，返回空路徑；

11)當路徑存在時，r_P＝{r_P'|minCost(r_P'),r_P'∈r_P}；

12)輸出可行最優路徑r_P；

步驟5：快遞員實際環境派送路線搜索；

對于在任務可行網絡拓撲上搜索出的滿足派件任務需求的任意路徑r_P＝(p₀,s₀)→(p₁,s₁)→(p₂,s₂)...，在加權切換系統T中都有與之對應的路徑r_T＝p₀→p₁→p₂...存在，且r_T同樣滿足派送任務需求，r_T與r_P的總耗費相同，該路徑滿足派送任務需求的同時保證了路徑最優性；最后在Android平臺上，基于百度地圖開發包的兩點間的駕駛導航方法將映射回加權切換系統中的離散路徑r_T連續化，進行二次規劃獲得派送員實際可駕駛派送路線R，二次規劃的權重問題在步驟1的算法一中已經被考慮，實現過程如算法三所示；

算法三：離散路徑連續化，即ProjectToR()

13)輸入加權切換系統中的離散路徑r_T；

14)對于x＝0,1,2...m-1，m為r_T路徑節點數；

15)如果x＝m-1，R(m-1)＝BmapDriving(r_T(m-1),r_T(0))，否則R(x)＝BmapDriving(r_T(x),r_T(x+1))；

16)循環步驟15直至全部路徑節點都映射回現實路徑；

17)輸出快遞員實際駕駛派送路徑R＝R(0)R(1)R(2)...R(m-1)。