[發明專利]公共自行車用戶最優路線搜索方法

在審

• 申請號: 201410380287.5
• 申請日: 2014-08-04
• 公開（公告）號: CN104165635A
• 公開（公告）日: 2014-11-26
• 發明（設計）人: 董紅召;吳滿金;劉冬旭;陳寧
• 申請（專利權）人: 浙江工業大學
• 主分類號: G01C21/34
• 分類號: G01C21/34;G06F19/00
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.公共自行車用戶最優路線搜索方法，具體步驟如下：?

1.確定路線選擇范圍；?

連接出行起始租賃點和終點租賃點，得到起止點的直線距離l，以l為弦，αl為弧長畫弧，αl為用戶所能忍受的最大繞行距離，α為大于1為系數，以兩條弧間的范圍作為可行路線的生成范圍，生成合理路線。?

2.生成可行路線選擇集；?

在步驟1確定的合理范圍內，生成出行起始租賃點到終點租賃點這兩點間所有可達性路線的集合，記為S＝{S₁,S₂,…,S_i,…,S_n}；S₁,S₂,…,S_n分別代表不同的可從起點到達終點的路線。?

3.生成目標函數；?

對于公共自行車騎行路線的最優性，需考慮路線總長度，交叉路口延誤時間，以及道路擁堵造成的時間延誤；因此構造目標函數如下：?

F(S_i)＝F_L(S_i)+F_T(S_i)+F_C(S_i)??(1)?

F(S_i)表示公共自行車用戶在第i路線S_i的時耗，當F(S_i)為最小時，S_i即為最優路線；?

其中：?

表示在理想情況下從起點到終點所需的時間；L_i表示路線S_i的實際長度，v表示公共自行車平均速度；?

F_T(S_i)＝nPT，表示交叉口延誤時間；n表示路線S_i中所包含的交叉口數目，P表示公共自行車用戶在紅燈期間到達交叉路口的比率，T表示紅燈的平均等待時間；公共自行車在交叉口基本不會因排隊及路口流量問題造成二次時間延誤，因此以紅燈的等待時間作為交叉口延誤時間；?

表示道路擁堵延誤；L_ij表示路線S_i中的某一擁堵路段j的實際長度，v_ij表示公共自行車用戶在這一擁堵路段的平均速度；表示用戶在路線S_i中的路段j擁堵情況下的時耗，表示理想情況下的時耗，即為用戶在路線S_i中的擁堵路段j的擁堵延誤。?

4.搜索最優路線；?

以公共自行車用戶在路線S_i上的時耗F(S_i)為優化目標，搜索具有最短時耗minF(S)的路線；?

41初始化設定路線S₁為最優路線，即minF(S)＝F(S₁)；?

42遍歷選擇集S的所有可行路線，比較minF(S)與F(S_i)的時耗長短，若路線S₁的時耗比S_i短，則minF(S)不變；若路線S₁的時耗比S_i長，則minF(S)更新為：minF(S)＝F(S_i)；?

43比較計算下一路線時耗與minF(S)數值的大小，執行計算i＝i+1，并重復步驟2)過程；?

44重復步驟2)、步驟3)過程，對可行路線選擇集S進行一次完整的信息遍歷后，最終得到的具有最短時耗的路線即為起始租賃點到終點租賃點的最優路線。?