[發(fā)明專利]用于動態(tài)路徑優(yōu)化的系統(tǒng)和方法

在審

• 申請?zhí)枺?/td>: 201310445546.3
• 申請日: 2013-09-26
• 公開（公告）號: CN104517155A
• 公開（公告）日: 2015-04-15
• 發(fā)明（設(shè)計）人: 程羽;王夢蛟;黎文憲
• 申請（專利權(quán)）人: SAP歐洲公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q50/28
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 張麗新

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

本申請總體上涉及數(shù)據(jù)處理的技術(shù)領(lǐng)域，并且在各個實施例中涉及動態(tài)路徑優(yōu)化的方法和系統(tǒng)。

背景技術(shù)

路徑優(yōu)化在諸如物流執(zhí)行、網(wǎng)絡(luò)路由協(xié)議和飛機飛行軌跡優(yōu)化的各種應用中扮演重要角色。然而，在現(xiàn)實世界中經(jīng)常出現(xiàn)復雜情況。

附圖說明

在附圖的圖中通過示例而非限制性地例示了本公開的一些實施例，在附圖中，相似的附圖標號指示類似的元件，并且在附圖中：

圖1圖示根據(jù)一個示例實施例的、反映在地圖上的路徑優(yōu)化的真實世界復雜情況的物流執(zhí)行示例；

圖2是圖示根據(jù)一個示例實施例的客戶端服務器系統(tǒng)的網(wǎng)絡(luò)圖；

圖3是圖示根據(jù)一個示例實施例的在企業(yè)應用平臺中的企業(yè)應用和服務的框圖；

圖4是圖示根據(jù)一個示例實施例的動態(tài)路徑優(yōu)化系統(tǒng)的框圖；

圖5是圖示根據(jù)一個示例實施例的確定最優(yōu)路徑的方法的流程圖；

圖6是圖示根據(jù)一個示例實施例的確定最優(yōu)路徑的方法的流程圖；

圖7是圖示根據(jù)一個示例實施例的確定最優(yōu)路徑的方法的流程圖；

圖8A-8B圖示根據(jù)一個示例實施例的相鄰節(jié)點和對應子路徑的選擇；以及

圖9是根據(jù)一個示例實施例的、其上可以執(zhí)行在此所述的方法的示例計算機系統(tǒng)的框圖。

具體實施方式

公開了動態(tài)路徑優(yōu)化的示例方法和系統(tǒng)。在下面的說明中，為了說明的目的，闡述了多個具體細節(jié)，以便示例實施例的透徹理解。然而，對于本領(lǐng)域內(nèi)的技術(shù)人員顯然，可以在沒有這些具體細節(jié)的情況下實施本實施例。

在現(xiàn)實世界的路徑優(yōu)化中可能遇到幾個困難，包括但是不限于：交通流在所有道路上是動態(tài)的和變化的；交通阻塞是基于時間的；在規(guī)定區(qū)域中在確定的時間段期間存在交通限制；以及，在規(guī)定的路段中存在速度限制。

在涉及物流執(zhí)行的一個示例中，預期卡車快速向目的地運送貨物。圖1圖示根據(jù)一個示例實施例的物流執(zhí)行示例100，其反映在地圖110上的路徑優(yōu)化的現(xiàn)實世界復雜情況。在示例100中，在8:00am確定運輸卡車120從起始位置至目的地位置130行進的路徑140。如所示，當在8:00am確定路徑140時，該確定基于對于確定路徑140的時間特有的一個或多個交通狀況，諸如交通阻塞150的存在。然而，這些交通狀況可能到運輸卡車到達它們的出現(xiàn)位置的時間的時候已發(fā)生改變。例如，雖然當在運輸卡車EB-5仍在起始位置的同時在8:00am處確定路徑140時交通阻塞150可能在距離起始位置10公里的確定區(qū)域中出現(xiàn)，但是到卡車可能到達那個區(qū)域的時間（例如，在圖1中的8:30am）的時候，交通阻塞150可能已經(jīng)清除或已經(jīng)緩解。當前的路徑優(yōu)化解決方案不考慮在交通狀況中的該基于時間的改變的情況。

可以將路徑優(yōu)化的復雜問題分解為子問題。在每個子問題中，可以獲得用于反映車輛的預期到達數(shù)據(jù)的時間戳(timestamp)，由此將動態(tài)交通信息轉(zhuǎn)換為在對應路段處的靜態(tài)信息。動態(tài)規(guī)劃方法可以用于使用動態(tài)交通信息來優(yōu)化總體成本。該動態(tài)手段可以包括下面的特征的任何組合，稍后在本公開中更詳細地描述該下面的特征：

·數(shù)據(jù)收集：可以收集和向數(shù)據(jù)庫內(nèi)輸入交通流的歷史信息（例如，平均速度）、道路距離和交通限制。

·優(yōu)化：可以將問題劃分為幾個階段，在每個階段處需要策略決策。

·最優(yōu)策略：可以根據(jù)從源節(jié)點到當前節(jié)點的最小成本（即時成本）和最小的即將到來的成本（未來成本）來在每個階段處評估最小成本。可以以多種方式來設(shè)置該成本，包括但是不限于距離、行程時間、支付費用等。

·時間戳：可以使用相對于(from)源的最小成本向當前節(jié)點授予時間戳。

在一些實施例中，路徑優(yōu)化系統(tǒng)使用時間成本的動態(tài)評估。與傳統(tǒng)的靜態(tài)路徑優(yōu)化方法不同，本公開的技術(shù)可以根據(jù)實時交通信息來評估時間成本。

在一些實施例中，一種方法包括：接收確定從源地理位置至目的地地理位置的最優(yōu)路徑的指令；并且，使用多個子路徑的每個子路徑的對應歷史交通信息來確定從源地理位置至目的地地理位置的最優(yōu)路徑。每個子路徑的歷史交通信息可以對應于在對應子路徑的開始位置處的估計到達時間，并且用于從多個子路徑選擇子路徑。選擇的子路徑可以限定最優(yōu)路徑。

在一些實施例中，歷史交通信息包括對應子路徑的交通流的指示。在一些實施例中，交通流的指示包括交通流的平均速度。在一些實施例中，歷史交通信息進一步包括對應子路徑的可獲得性的指示。