[發(fā)明專利]一種基于A星策略的最優(yōu)多會合點路徑搜索方法及裝置

有效

• 申請?zhí)枺?/td>: 201511018390.6
• 申請日: 2015-12-30
• 公開（公告）號: CN105678054B
• 公開（公告）日: 2020-06-30
• 發(fā)明（設(shè)計）人: 李榮華;邱宇軒;毛睿;秦璐;鐘舒馨
• 申請（專利權(quán)）人: 深圳大學(xué)
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/29
• 代理公司: 深圳市興科達知識產(chǎn)權(quán)代理有限公司 44260
• 代理人: 王翀

本發(fā)明提供了一種基于A星策略的最優(yōu)多會合點路徑搜索方法及裝置，其中的方法包括：獲取路徑搜索預(yù)設(shè)信息，包括：圖G＝(V,E,W)，點集U，α，出發(fā)點s，目的點t；然后，在執(zhí)行以下步驟：使用全集合路徑算法計算C(x,y,U),其中x,y∈U；當(dāng)時，返回α×min_x∈U,y∈U(dist(s,x)+C(x,y,U)+dist(y,t))；求出從s到t的最短路徑P'；計算α×c(P')+(1?α)×Σ_x∈U(min_v∈VP′dist(x,v))，并賦值給best；初始化隊列Q和集合D，將初始狀態(tài)和加入隊列Q，其中l(wèi)b()是計算下界的操作，其結(jié)果lb是隊列Q的優(yōu)先序；當(dāng)隊列Q不為空時通過循環(huán)操作以找到最優(yōu)解。本發(fā)明能夠更加高效地解決實時合乘應(yīng)用中技術(shù)難點，大大提升了高效性與實用性。

技術(shù)領(lǐng)域

本發(fā)明涉及實時合乘應(yīng)用技術(shù)領(lǐng)域，尤其涉及一種應(yīng)用于實時合乘的基于A星策略的最優(yōu)多會合點路徑搜索方法及裝置。

背景技術(shù)

實時合乘，又被稱作動態(tài)拼車，是現(xiàn)代交通系統(tǒng)中一種頗具發(fā)展前景的節(jié)省燃油并減輕交通擁堵的方式。最近一段時間以來，許多實時合乘應(yīng)用，諸如Uber(www.uber.com)、Lyft(www.lyft.com)，在智能手機用戶中越來越受歡迎，因為這可以幫助他們規(guī)劃旅程。在典型的實時合乘系統(tǒng)中，有兩種實體：駕駛者和乘客。乘客可以通過他們帶定位功能的智能手機來預(yù)定汽車。他們需要提供他們的地理位置信息給系統(tǒng)，隨后系統(tǒng)動態(tài)地安排駕駛者為這些乘客提供合乘服務(wù)。

架設(shè)一個這樣的實時合乘系統(tǒng)不是一件容易的事。主要的技術(shù)難點有兩個：1、如何快速地找到可以服務(wù)進來的用戶請求的駕駛者；2、匹配好了駕駛者和乘客之后，又該如何快速地確定最優(yōu)的路徑讓駕駛者可以接上所有的匹配的乘客。在文獻里，現(xiàn)有的一些研究主要集中在解決第一個問題。

例如，在文獻[2]―S.Ma,Y.Zheng,and O.Wolfson,―T-share:A large-scaledynamic taxi ridesharing service,‖in 2013IEEE 29th International Conferenceon Data Engineering(ICDE),2013,pp.410–421‖和文獻[3]―S.Ma and O.Wolfson,―Analysis and evaluation of the slugging form of ridesharing,‖in Proceedingsof the 21st ACM SIGSPATIAL International Conference on Advances in GeographicInformation Systems,2013,pp.64–73‖中，Shuo Ma等人做出了一個叫T-share的系統(tǒng)，用于的士合乘應(yīng)用中，駕駛者和乘客的實時匹配。在文獻[1](Y.Huang, R.Jin,F.Bastani,and X.S.Wang,―Large Scale Real-time Ridesharing with Service Guarantee onRoad Networks,‖ArXiv13026666Cs,Feb.2013)中，Yan Huang等人提出了一種高效的活動樹算法來支持一種有服務(wù)保證的駕駛者和乘客之間的匹配。這幾種算法的工作都集中在開發(fā)一種實用的算法來高效地解決駕駛者和乘客之間的匹配問題，即上文所述的技術(shù)難點1。而對于上文所述的技術(shù)難點2，本申請人在申請?zhí)枮?01510274711.2、名稱為“應(yīng)用于實時合乘的最優(yōu)多會合點路徑搜索方法及裝置”的專利申請[4]中提出了OMMPR算法的解決方案。