確定最優的會合點的方法和裝置製造方法

2024-03-31 16:21:05

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

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

【背景技術】
[0002] 作為一種群居動物，人類結伴而行的行為由來已久。換而言之，結伴而行可以理解 為共同出行，也就是多名在相同或不同地點的人員提前相遇，然後共同去往某個相同終點。
[0003]目前，在計算提前相遇點及相應的每個人員的路線時，人們普遍根據自身的經驗 來選擇提前相遇點，再使用網際網路上的路線規劃系統來計算。首先分別對每個人員的起始 點和選擇的提前相遇點進行路線規劃，然後再規劃從相遇點到終點的路線。但是，當對所 涉及的地理區域的交通出行情況不熟悉時，人們就很難根據自身經驗來選擇這個提前相遇 點，這樣可能導致所得出的結果和最佳的情形相差很大，而造成時間、金錢方面的損失。
[0004]在公知技術中，例如US5802492、EP1357357、EP2533013、EP1593938 等專利文獻均 提出了進行路線規劃的方法，每次對單一人員，從單一起始點到單一終點進行路線規劃。也 就是說，公知技術中，用戶在相應的界面輸入一個路線的起始點和一個路線的終點，系統獲 取用戶的搜索要求後，通過不同的方法計算出相應的從起始點到終點的路線規劃，可以包 括駕車路線規劃、公交路線規劃、步行路線規劃或者多模式交通路線規劃等。
[0005] 此外，現有公知技術也提出從一個起始點到多個目的地的路線規劃，也就是，一 個起始點經過一個或多個途經點到一個目的地的路線規劃。以作為公知技術的專利文獻 EP1193626為例，此公知技術提出了一種路線規劃系統，此系統可以計算從某一起始點出 發，經過多個途經點的路線規劃。用戶可以在該系統的用戶界面上輸入起始點、途經點或終 點，系統通過相應的方法計算出相應的路線，並將路線顯示在用戶界面的地圖上。


【發明內容】

[0006] 綜上所述，現有的公知技術僅提供人員從單一起始點到一個終點或者多個終點的 路線規劃。公知技術的缺點在於，當多名人員從多個不同的起始點到同一個終點時，公知技 術無法提供相應的路線規劃。特別在於，當用戶要求針對從多個人員從不同的起始點經過 一個未指定的提前相遇點到統一終點的路線規劃時，公知技術無法提供相應的路線規劃。
[0007] 特別地，針對不同地點的人員相約去往某個相同終點的情況，參與共同出行的人 員，或者選擇分別到達終點，或者在到達終點之前某個地點（以下稱為提前相遇點或會合 點）相遇後一起再前往終點。在這裡，前者可以簡單使用現有網際網路上的路線規劃系統來 對多人的路線進行分別規劃，也就是分別對每個人的起始點和終點進行路線規劃。
[0008] 相比之下，現有的公知技術無法針對後者進行路線規劃。在不同地點的多名人員 在到達終點之前的某個地點相遇後一起再前往終點的方式，首先可以減少人員的總交通費 用、降低二氧化碳排放，例如，人員可以分別駕車前往某個提前相遇點，然後乘坐同一輛車 前往終點。其次，人員通過與熟悉路線的其他人員同行（如一輛車引領另外一輛車），可減 少交通上花費的時間，更便捷地到達終點目的地。
[0009] 為了克服現有技術的上述缺陷提出了本發明。本發明的目的是提出一種為從不同 起始點前往相同的目的地且約定提前會合的多個移動體確定最優的會合點的方法和裝置， 不僅能夠通過為該多個移動體選擇會合點以使該多個移動體在該會合點會合後能夠方便 地前往目的地，而且能夠將多個移動體從不同起始點經由該會合點到達目的地的總代價最 小化或近似最小化。
[0010] 為了實現上述目的，提出了一種為從不同起始點前往相同的目的地且約定提前會 合的多個移動體確定最優的會合點的方法，包括：獲取步驟，獲取所述多個移動體各自的起 始點和目的地；以及確定步驟，利用地圖數據，根據所述多個移動體各自的起始點和目的地 進行路線搜索，按照各移動體經過會合點到達所述目的地的各路線的代價總和近似最小的 方式，來將該會合點確定為最優的會合點。
[0011] 優選地，所述代價是距離。
[0012] 優選地，所述確定步驟包括：利用地圖數據，以所述多個移動體各自的起始點和 所述目的地為出發點分別進行路線檢索，在檢測到所有這些路線檢索具有一個共同訪問點 時，將所述共同訪問點確定為所述最優的會合點。
[0013] 優選地，在以所述目的地為出發點進行路線檢索時，在進行路線檢索的過程中舍 棄回程無法通行的路段，並將回程單向的路段設置為雙向可通行路段。
[0014] 優選地，所述路線檢索採用迪科斯徹式搜索算法進行逐步檢索。
[0015] 優選地，所述會合點是用於所述多個移動體到達該會合點後再一同出發前往所述 目的地的點。
[0016] 優選地，所述會合點是用於所述多個移動體到達該會合點後合併為更少數量的移 動體再一同出發前往目的地的點。
[0017] 另外，根據本發明，提出了一種為從不同起始點前往相同的目的地且約定提前會 合的多個移動體確定最優的會合點的裝置，包括：獲取單元，獲取所述多個移動體各自的起 始點和目的地；以及確定單元，利用地圖數據，根據所述多個移動體各自的起始點和目的地 進行路線搜索，按照各移動體經過會合點到達所述目的地的各路線的代價總和近似最小的 方式，來將該會合點確定為最優的會合點。
[0018] 如上所述，本發明涉及一個針對多名人員出行進行路線規劃的系統，本發明所涉 及的系統針對共同出行的多名在不同起始點的人員，提供相應的路線規劃。本發明特別提 供了一種路線規劃方式，所規劃的路線可以指引多名人員，在前往終點的路途中的某地點 相遇後，再共同到達終點，而且通過確定最優的相遇點（會合點），能夠將多個移動體從不 同起始點經由該會合點到達目的地的總代價最小化或近似最小化。

【專利附圖】

【附圖說明】
[0019] 通過參考以下結合附圖對所採用的優選實施方式的詳細描述，本發明的上述目 的、優點和特徵將變得更顯而易見，其中：
[0020] 圖1是根據本發明的系統結構的示意圖。
[0021] 圖2是根據本發明的功能框圖。
[0022] 圖3是用於詳細描述本發明的用戶界面的圖。
[0023] 圖4是用於詳細描述本發明的系統如何獲得用戶輸入的相關搜索信息的過程的 流程圖。
[0024] 圖5是用於描述針對是否預先設定提前相遇點，系統做出相關計算的過程的流程 圖。
[0025] 圖6是用於詳細描述針對未預先設定提前相遇點時，系統計算相應提前相遇點和 相關路線規劃的過程的流程圖。
[0026] 圖7是以舉例方式解釋了圖6的計算方法的示意圖。
[0027] 圖8是舉例描述本發明在物流配送中的使用方法的圖。
[0028] 圖9是舉例描述本發明使用的現有技術"迪科斯徹搜索"的圖。

【具體實施方式】
[0029] 下面將參考附圖來詳細描述本發明的優選實施例。
[0030]〈實施方式1>
[0031] 圖1示出本發明的示例性實施方案的系統結構。其中，110為網際網路網絡；104為 含有用戶界面的計算機或其他可使用用戶界面的設備如行車導航儀或手機等，進行路線搜 索的用戶通過104設備的用戶界面來錄入搜索信息，並反饋顯示搜索結果；106代表此次共 同出行的其他人員的設備，可包括手機、計算機、行車導航儀等；102為進行路線規劃的服 務器。用戶通過104的用戶界面錄入本人信息與其他人員的信息，以便進行提前相遇點選 擇及路線規劃的搜索。104的用戶界面採集這些信息後，通過網際網路110發送到伺服器102。 伺服器102處理採集的信息，並生成相應的路線規劃。之後，伺服器102將規劃內容最終通 過網際網路110,發送並顯示到參與共同出行的人員設備104及106上。
[0032] 換一個角度說，參看圖2的功能模塊圖，本系統包括一個用戶需求輸入裝置210、 一個提前相遇點與路線規劃的計算裝置220和一個輸出模塊230。在用戶需求輸入裝置 210,用戶在相應設備的用戶界面上進行搜索需求錄入。220根據用戶的搜索需求計算出路 線規劃，並通過輸出模塊230顯示在用戶和其他參加共同出行的人員的設備上。
[0033] 圖3表示由某一個用戶在圖1的104上錄入搜索信息時所使用的用戶界面，也就 是圖2中的210。其中，用戶在301中指定搜索路線規劃所針對的具體時間，也就是最後一 個用戶到達目的地（終點）的時間，包括日期和時間；此用戶在302中直接填入指定的路線 終點；303,用戶可以輸入自己的起始點（起始位置）；在305中錄入其他每個參與共同出行 人員的起始點，按" + "按鈕（310)來添加每個人員的起始點地址，所添加的人員編號及地址 將被顯示在306中。當用戶不清楚自己出發起始點的位置時，可以在304中選擇電子日程 表（例如從OUTLOOKCALENDAR，GOOGLECALENDAR等之中選擇），系統可以根據用戶的電子 日程表來確定其在某個時間段的地理位置，作為其起始點；當此用戶不清楚其他參與共同 出行的人員在301中的時間點的位置時，可以按" + "(307)按鈕，將彈出對話框，要求用戶輸 入或從已有聯繫人中選擇將參與此次共同出行的其他人的日程信息、位置信息、聯繫信息、 出行交通模式偏好信息等；其中，當307添加某個參與共同出行的人後，此人的姓名圖標將 顯示在309中；之後，用戶可以將準備在同一個提前相遇點碰面的一組人用滑鼠從309拖入 310,按312按鈕來生成一組提前碰面的分組，生成的不同組別的人將以不同顏色或代號顯 示在314中，系統將根據每組人的起始點和終點來計算出相應的提前相遇點；最後，用戶可 以使用308 (確定按鈕），用戶按此按鈕時，以上輸入錄入的信息將被傳往伺服器102作為此 次共同出行的搜索需求。
[0034] 用戶在用戶界面輸入了搜索需求後，伺服器102中的生成路線規劃的系統首先分 析用戶的需求，如圖4所示。首先，系統確定路線規劃的終點（步驟410)和每個組別中人 員的起始點；當一個人員的起始點沒有指定時（步驟420的是），系統從該人員的電子日程 表得到相應時間段的該人員的起始點（步驟430)。當指定了一個人員的起始點時（步驟 420的否），系統從用戶的錄入中得到人員的參與提前碰面的分組（步驟425)。最後，系統 檢查是否所有參與提前碰面的人都進行了分組（步驟440)。
[0035] 圖5示出了根據當前人員組別是否指定了相應的提前見面點，系統進行相應的路 線規劃計算。具體地，在步驟500,判定是否對當前人員組別是否指定了相應的提前見面點。 在沒有指定相應的提前見面點時（步驟500的否），系統計算提前見面地點並進行路線規 劃（步驟600)。在指定了相應的提前見面點時（步驟500的是），系統針對已設定的提前 見面地點進行路線規劃（步驟520)。
[0036] 圖6解釋了圖5的步驟600的計算過程。在解釋此計算過程前，在這裡介紹一下 本發明要使用的一個現有技術，迪科斯徹式搜索。普通的迪科斯徹搜索是計算一個起始點S 到地圖上每個頂點v的最短路線。地圖上的頂點表示物理位置，頂點與頂點之間的路線表 示物理的路線。
[0037] 普通的迪科斯徹搜索包括以下步驟：（1)初始時，S只包含起始點，即S= {v}且v 至ljv的距離為0。U包含除v外的其他地圖上的頂點，U中頂點u距離為邊上的權重值（若 v與u有邊）（若u不是v的出邊鄰接點）。（2)從U中選取一個距離v最小的頂點k，把k， 加入S中（該選定的距離就是v到k的最短路徑長度）。（3)以k為新考慮的中間點，修改 U中各頂點的距離權重值；若從起始點v到頂點u(u為U集合中一個頂點）的距離（經過 頂點k)比原來距離（不經過頂點k)短，則修改起始點v到頂點u的路徑為經過頂點k的 路徑並修改相應的距離權重值。（4)重複步驟（2)和（3)直到所有頂點都包含在S中。圖 9的840列舉了迪科斯徹搜索算法的圖，其中，求A到其他各頂點（B、C、D、E)的最短路徑。 線上所標註為相鄰線段之間的距離，即權重值。在下表1中分步驟解釋了找到840中頂點 A到圖中所有頂點的最短路徑的過程。其中，下表1中的每一個步驟在本發明中被稱為"一 步迪科斯徹式搜索"。
[0038]

【權利要求】
1. 一種為從不同起始點前往相同的目的地且約定提前會合的多個移動體確定最優的 會合點的方法，包括： 獲取步驟，獲取所述多個移動體各自的起始點和目的地；以及 確定步驟，利用地圖數據，根據所述多個移動體各自的起始點和目的地進行路線搜索， 按照各移動體經過會合點到達所述目的地的各路線的代價總和近似最小的方式，來將該會 合點確定為最優的會合點。
2. 根據權利要求1所述的方法，其中， 所述代價是距離。
3. 根據權利要求1所述的方法，其中， 所述確定步驟包括： 利用地圖數據，以所述多個移動體各自的起始點和所述目的地為出發點分別進行路線 檢索，在檢測到所有這些路線檢索具有一個共同訪問點時，將所述共同訪問點確定為所述 最優的會合點。
4. 根據權利要求1所述的方法，其中， 在以所述目的地為出發點進行路線檢索時，在進行路線檢索的過程中捨棄回程無法通 行的路段，並將回程單向的路段設置為雙向可通行路段。
5. 根據權利要求1所述的方法，其中， 所述路線檢索採用迪科斯徹式搜索算法進行逐步檢索。
6. 根據權利要求1所述的方法，其中， 所述會合點是用於所述多個移動體到達該會合點後再一同出發前往所述目的地的點。
7. 根據權利要求1所述的方法，其中， 所述會合點是用於所述多個移動體到達該會合點後合併為更少數量的移動體再一同 出發前往目的地的點。
8. -種為從不同起始點前往相同的目的地且約定提前會合的多個移動體確定最優的 會合點的裝置，包括： 獲取單元，獲取所述多個移動體各自的起始點和目的地；以及 確定單元，利用地圖數據，根據所述多個移動體各自的起始點和目的地進行路線搜索， 按照各移動體經過會合點到達所述目的地的各路線的代價總和近似最小的方式，來將該會 合點確定為最優的會合點。
【文檔編號】G01C21/34GK104236569SQ201310250016
【公開日】2014年12月24日 申請日期:2013年6月21日 優先權日:2013年6月21日
【發明者】趙亮, 王文佳, 水谷美加 申請人:株式會社日立製作所