[發明專利]確定最優的會合點的方法和裝置

在審

• 申請號: 201310250016.3
• 申請日: 2013-06-21
• 公開（公告）號: CN104236569A
• 公開（公告）日: 2014-12-24
• 發明（設計）人: 趙亮;王文佳;水谷美加
• 申請（專利權）人: 株式會社日立制作所
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 吳秋明

技術領域

本發明涉及一種為從不同起始點前往相同的目的地且約定提前會合的多個移動體確定最優的會合點的方法和裝置，不僅能夠通過為該多個移動體選擇會合點以使該多個移動體在該會合點會合后能夠方便地前往目的地，而且能夠將多個移動體從不同起始點經由該會合點到達目的地的總代價最小化或近似最小化。

背景技術

作為一種群居動物，人類結伴而行的行為由來已久。換而言之，結伴而行可以理解為共同出行，也就是多名在相同或不同地點的人員提前相遇，然后共同去往某個相同終點。

目前，在計算提前相遇點及相應的每個人員的路線時，人們普遍根據自身的經驗來選擇提前相遇點，再使用互聯網上的路線規劃系統來計算。首先分別對每個人員的起始點和選擇的提前相遇點進行路線規劃，然后再規劃從相遇點到終點的路線。但是，當對所涉及的地理區域的交通出行情況不熟悉時，人們就很難根據自身經驗來選擇這個提前相遇點，這樣可能導致所得出的結果和最佳的情形相差很大，而造成時間、金錢方面的損失。

在公知技術中，例如US5802492、EP1357357、EP2533013、EP1593938等專利文獻均提出了進行路線規劃的方法，每次對單一人員，從單一起始點到單一終點進行路線規劃。也就是說，公知技術中，用戶在相應的界面輸入一個路線的起始點和一個路線的終點，系統獲取用戶的搜索要求后，通過不同的方法計算出相應的從起始點到終點的路線規劃，可以包括駕車路線規劃、公交路線規劃、步行路線規劃或者多模式交通路線規劃等。

此外，現有公知技術也提出從一個起始點到多個目的地的路線規劃，也就是，一個起始點經過一個或多個途經點到一個目的地的路線規劃。以作為公知技術的專利文獻EP1193626為例，此公知技術提出了一種路線規劃系統，此系統可以計算從某一起始點出發，經過多個途經點的路線規劃。用戶可以在該系統的用戶界面上輸入起始點、途經點或終點，系統通過相應的方法計算出相應的路線，并將路線顯示在用戶界面的地圖上。

發明內容

綜上所述，現有的公知技術僅提供人員從單一起始點到一個終點或者多個終點的路線規劃。公知技術的缺點在于，當多名人員從多個不同的起始點到同一個終點時，公知技術無法提供相應的路線規劃。特別在于，當用戶要求針對從多個人員從不同的起始點經過一個未指定的提前相遇點到統一終點的路線規劃時，公知技術無法提供相應的路線規劃。

特別地，針對不同地點的人員相約去往某個相同終點的情況，參與共同出行的人員，或者選擇分別到達終點，或者在到達終點之前某個地點(以下稱為提前相遇點或會合點)相遇后一起再前往終點。在這里，前者可以簡單使用現有互聯網上的路線規劃系統來對多人的路線進行分別規劃，也就是分別對每個人的起始點和終點進行路線規劃。

相比之下，現有的公知技術無法針對后者進行路線規劃。在不同地點的多名人員在到達終點之前的某個地點相遇后一起再前往終點的方式，首先可以減少人員的總交通費用、降低二氧化碳排放，例如，人員可以分別駕車前往某個提前相遇點，然后乘坐同一輛車前往終點。其次，人員通過與熟悉路線的其他人員同行(如一輛車引領另外一輛車)，可減少交通上花費的時間，更便捷地到達終點目的地。

為了克服現有技術的上述缺陷提出了本發明。本發明的目的是提出一種為從不同起始點前往相同的目的地且約定提前會合的多個移動體確定最優的會合點的方法和裝置，不僅能夠通過為該多個移動體選擇會合點以使該多個移動體在該會合點會合后能夠方便地前往目的地，而且能夠將多個移動體從不同起始點經由該會合點到達目的地的總代價最小化或近似最小化。

為了實現上述目的，提出了一種為從不同起始點前往相同的目的地且約定提前會合的多個移動體確定最優的會合點的方法，包括：獲取步驟，獲取所述多個移動體各自的起始點和目的地；以及確定步驟，利用地圖數據，根據所述多個移動體各自的起始點和目的地進行路線搜索，按照各移動體經過會合點到達所述目的地的各路線的代價總和近似最小的方式，來將該會合點確定為最優的會合點。

優選地，所述代價是距離。

優選地，所述確定步驟包括：利用地圖數據，以所述多個移動體各自的起始點和所述目的地為出發點分別進行路線檢索，在檢測到所有這些路線檢索具有一個共同訪問點時，將所述共同訪問點確定為所述最優的會合點。

優選地，在以所述目的地為出發點進行路線檢索時，在進行路線檢索的過程中舍棄回程無法通行的路段，并將回程單向的路段設置為雙向可通行路段。

優選地，所述路線檢索采用迪科斯徹式搜索算法進行逐步檢索。