TWI454662B - 路徑規劃系統及其方法 - Google Patents

Description

路徑規劃系統及其方法

本發明有關於一種規劃系統及其方法，且特別是有關於建議路徑的規劃系統及其方法。

市面上的導航系統都具備有根據使用者所指定的出發地與目的地規劃路徑的功能，使得現代人在行車或走路時對導航系統的依賴越來越深，平時不但依靠導航系統引導行車路徑以利使用者前往不同地點洽公、商辦，假日時更常依靠導航系統的指引前往旅遊景點休憩。

而已知的導航系統為使用者規劃路徑的方式，不外乎尋找出發地及目的地之間的最短路徑，以符合一般使用者想要儘快到達目的地的習慣。但根據最短距離所規劃出的建議路徑時常引導使用者走入狹小巷弄，在時間成本而言並不一定是最佳的選擇。

此外，由於在規劃過程中，可供選取的路段數量可能十分龐大，造成路網的交錯程度複雜，也可能產生在計算可能路徑時造成系統運算負擔過大的問題。

本發明實施例提供一種路徑規劃方法，用以規劃出發地到目的地之路徑，所述方法包括：提供多個道路圖層，每一道路圖層對應有道路等級及選取數量；自包含出發地的其中一個道路圖層搜尋連接出發地的路段，並分別計算所述路段的時間成本，其中，每一路段包括起始節點與終止節點；根據道路圖層對應的選取數量，依時間成本由低到高排序路段，以選取與選取數量相等的一或多個路段為候選路段，其中，自出發地開始依序相連接的候選路段組成候選路徑；判斷候選路徑的末端是否為對應目的地的終止節點；當候選路徑的末端為對應目的地的終止節點時，選取時間成本總和最小的候選路徑為出發地到目的地的建議路徑。當候選路徑的末端並非對應目的地的終止節點時，根據候選路徑末端的終止節點，分別再搜尋與各終止節點連接的一或多個路段，並分別計算時間成本，以及返回選取與選取數量相等的一或多個路段為候選路段的步驟。

除此之外，本發明實施例還提供一種路徑規劃系統，用以規劃出發地到目的地之路徑，包括圖層資料庫及處理單元。圖層資料庫記錄多個道路圖層，每一道路圖層對應有道路等級及選取數量。處理單元接收出發地及目的地，並讀取道路圖層其中之一以從出發地起搜尋相連接的路段，並計算每一路段的時間成本，以及根據所讀取的道路圖層對應的選取數量，依時間成本由低到高排序所述路段，以選取與選取數量相等的一或多個路段為候選路段。其中，自出發地起依序連接的一或多個候選路段組成候選路徑，處理單元用以持續選取候選路段以更新候選路徑，當候選路徑的末端對應的節點為該目的地時，選取時間成本總和最小的候選路徑為一建議路徑。

[路徑規劃系統實施例]

圖1繪示了本發明所提供的一種路徑規劃系統實施例的方塊圖。本例的路徑規劃系統1包括有輸入單元10、處理單元12、暫存單元14、圖層資料庫16及輸出單元18。輸入單元10、暫存單元14、圖層資料庫16及輸出單元18都連接於處理單元12，以接受處理單元12的控制而規劃出從某一出發地到目的地之間的建議路徑。

其中，路徑規劃系統1可設置於用以提供導航功能的電子裝置中，例如導航專用機、行動電話、個人數位助理或手提電腦等設備。輸入單元10可為滑鼠、鍵盤或觸控面板等周邊裝置，而輸出單元18則可以用以確認及辨識規劃後之路徑的顯示設備。處理單元12可為中央處理器、微處理器等運算設備，暫存單元14可為揮發性或非揮發性記憶體晶片，用以暫時記錄處理單元12所讀取及運算之資訊。

圖層資料庫16可記錄於非揮發性之記憶體單元，例如電子式可抹除可程式唯讀記憶體。圖層資料庫16中記錄了多個分別對應不同道路等級的道路圖層。所述的道路等級可由高到低分為高速公路、快速道路、省道、一般道路等道路類別的等級。除了底層的一般道路的道路圖層包括全部道路等級的路段及全部道路的起、迄節點之外，每一道路圖層包括所屬道路等級中的多個路段及每一路段的起、迄節點。例如：高速公路此一類別的道路等級可為最高等級，對應高速公路的道路圖層中僅包括高速公路的多個路段及節點。

其中，道路等級高的道路圖層中，包括的路段通常少於道路等級低的道路圖層，此外，道路等級高的道路圖層中，路段的時間成本相較於道路等級低的路段的時間成本亦會較低。例如：在路段的數量上，道路等級較高的高速公路少於道路等級較低的一般道路，且高速公路因速限較高、交通號誌少的緣故，其時間成本亦可低於一般道路。

因此，處理單元12可於接收到來自輸入單元10所輸入的出發地及目的地之後，選擇節點中包括有出發地的道路圖層開始搜尋可能的候選路徑(如圖2A所示)。包括有出發地的道路圖層通常為底層的道路圖層，也就是包含有一般道路及其他所有道路類型的圖層。各個圖層中所包括的多個路段皆包括有路段兩端的節點，分別為起始節點及終止節點。處理單元12可將出發地視為第一個起始節點，並搜尋與所述起始節點相連的一到多個路段及所述路段另一端的終止節點，並計算每個路段的時間成本。

由於與起始節點連接的路段可能數量眾多，為了能有效率地規劃路徑，處理單元12可對底層的道路圖層設置有限的選取數量，而非對將所有搜尋獲得的路段都納入規劃的範圍。例如將各個搜尋到的路段的時間成本由低到高排序後，選取時間成本最低的前5個路段做為候選路段，再從所述被選取的5個候選路段繼續搜尋後續的路段，至於超出選取數量之外的其他路徑則不再繼續進行規劃。

處理單元12可將被選取的5個候選路段的終端節點視為新的起始節點，分別再搜尋與起始節點連接的路段及各段路的終端節點。相同地，處理單元12可再從新搜尋到的多個路段中再計算及選取時間成本最低的前5個路段為候選路段。藉此使得從出發地開始所搜尋的路徑可維持在一定的數量範圍內，以增加路徑規劃的效率。

當處理單元12從出發地為第一個起始節點搜尋路徑，並且最終搜尋到以目的地為終止節點的一或多條由多個候選路段組成的候選路徑時，處理單元12計算連接出發地到目的地的候選路徑當中總時間成本最低的其中一條候選路徑為建議路徑。

其中，從出發地到目的地之間所經過的路徑可能包括有屬於不同道路等級的路段(如圖2B所示)，當處理單元12所選取的候選路段的終止節點為不同道路等級的路段之交界點時，處理單元12可從圖層資料庫16改為由不同道路等級的道路圖層進行後續的規劃。如前所述，由於不同道路等級的道路在數量上和需要花費的時間成本不盡相同，道路等級較高的路段的數量與時間成本會較道路等級較低的路段來得少，故處理單元12在遇到搜尋獲得的節點為不同道路等級之路段的交界點時，可優先採用道路等級較高的道路圖層進行搜尋。

當處理單元12在另一道路圖層進行搜尋時，同樣可限制在有限的搜尋範圍選取時間成本較低的數個路段續行規劃。在道路等級較高的道路圖層中選擇時間成本較低的數個候選路段時，所設定的選取數量可以少於道路等級低的道路圖層，例如只選取時間成本最低的前3個路段為候選路段，藉此以簡化計算量及更有效地淘汰時間成本過高的候選路徑。

以圖2A及圖2B所示之道路圖層的具體例示，將說明如後。

[路徑規劃方法實施例]

請參照圖3，圖3是本發明所提供的一種路徑規劃方法實施例的流程圖。本實施例所述的路徑規劃方法可利用多個不同的道路等級畫分搜尋的範圍及淘汰率，並且以時間成本的高低做為選擇路徑的判斷依據，藉以簡化道路網的複雜度，並提升搜尋路徑的效率。所述的方法可以利用圖1所示的系統施行，故請一併參照圖1所示的路徑規劃系統方塊圖以利理解。

處理單元12可接收使用者從輸入單元10輸入的出發地及目的地，並從圖層資料庫16讀取包含有全部道路等級及全部路段的道路圖層，以及將出發地視為第一個起始節點(S301)，開始於所述道路圖層中搜尋與所述第一個起始節點連接的一或多個路段，以及每一個所述路段另一端的終止節點(S303)。處理單元12尋獲與起始節點相連的一或多個路段後，計算每一路段所需的時間成本(S305)，再根據對應於所屬道路圖層而設定的選取數量，選取其中有限的路段作為候選路段(S307)。以圖2A所示的道路圖層示意圖為例，A節點為出發地、G節點為目的地時，以A節點為第一個起始節點，處理單元12從A點搜尋出共三段路徑：節點A到B所連接的路段、節點A到D所連接的路段、以及節點A到E連接的路段(以下簡稱AB路段、AD路段、AE路段，依此類推)，經處理單元12計算距離及根據道路等級加權後，三段路徑的時間成本分別為1、8、5單位。假設對應於本道路圖層所設定的選取數量為2個路段，亦即在搜尋到的全部路段中，以時間成本由小到大排序，僅選取前2個路段為候選路段。在本例中即為AB路段及AE路段兩段為候選路段，而排除AD路段。

從出發地開始，由各個候選路段依序連接而成的路徑為候選路徑，每一條候選路徑會因為處理單元12新選取的候選路段而延長，每一候選路徑的末端即為處理單元12最新選取的其中一個候選路段的終止節點。

處理單元12搜尋出候選路段而更新候選路徑的內容後，可判斷所述的一或多個候選路徑的末端是否為目的地(S309)，若被選取的一或多個候選路徑的末端為目的地，代表處理單元12已規劃出至少一條可由出發地連接到目的地的完整路徑，此時若有多條候選路徑皆為完整連接出發地到目的地的路徑時，處理單元12可從其中選取總時間成本最低的一條做為建議路徑，而若正好只有一條完整的候選路徑連接出發地到目的地，處理單元12可直接選取所述的候選路徑做為建議路徑(S311)。所述的總時間成本可指候選路徑當中一到多個候選路段的時間成本的總和。

然而，若處理單元12判斷出各候選路徑中的末端並非目的地，則繼續搜尋下一個路段以更新候選路徑並進一步接近目的地。在搜尋的過程中，處理單元12還可進一步判斷被選取的候選路段之終止節點是否與其他道路圖層的節點重疊(S313)。換言之，處理單元12可判斷候選路徑的末端接下來是否連接屬於不同道路等級的路段。若被選取的候選路段當中，並沒有終止節點與其他道路圖層的節點重疊，處理單元12可繼續在同一個道路圖層中，繼續以最後搜尋到的候選路段之終止節點(亦即候選路徑的末端)作為新的起始節點，繼續搜尋後續的一或多個路段(S315)，並且在搜尋出新的一或多個路段後，返回步驟S305以下，計算新搜尋到的候選路段的時間成本，再度根據預定的選取數量選取時間成本較低數個路段為候選路段，直到獲得可連接出發地到目的地的建議路徑(S311)為止。

例如在圖2A中，假設節點A到節點J所連接的各個路段皆屬於同一道路等級，處理單元12經選取AB路段及AE路段為候選路段後，判斷出節點B與節點E都沒有與其他道路等級的路段連接，處理單元12即可繼續在同一個道路圖層中以節點B和節點D分別做為新的起始端點，分別搜尋與節點B和節點D連接路段以更新候選路徑。如圖2A所示，從節點B和節點D可分別搜尋到BC路段、BD路段及EF路段，此三路段的時間成本分別為3、6、9單位，而在同樣的道路圖層僅取時間成本較小的前兩個，故而選取了連接於B節點的BC路段及BD路段，而排除EF路段。此時在圖2A所示的道路圖層上，分別包括AB路段連接BD路段，以及AB路段連接BC路段所形成的兩段候選路徑。

由於候選路徑的末端節點並非目的地所在的節點G，因此處理單元12可繼續以候選路徑的末端節點C及D為起始節點搜尋下一個路段。在圖2A所示的示意圖中，從節點C及D又分別搜尋到CJ路段、DH路段、DI路段及DC路段，各別的時間本成本分別為6、2、3、7單位。處理單元12根據預設的選取數量選取的候選路段為DH路段及DI路段兩段，以更新候選路徑。最後，再分別以節點H及節點I為新的起始節點，搜尋相連的路段，而分別獲得HG路段及IG路段。經計算後，HG路段及IG路段的時間成本分別為3及1單位。

處理單元12此時可判斷出HG路段及IG路段的終止節點G即為目的地，進一步判斷出已經規劃出兩條完整連接出發地A到目的地G的候選路徑，分別為經由節點A、B、D、H到G的第一候選路徑，以及經由節點A、B、D、I到G的第二候選路徑。第一候選路徑的總時間成本為9單位，第二候選路徑的總時間成本則為8單位，故而處理單元12計算出所述兩條候選路徑的總時間成本後，可選取總時間成本最小的候選路徑為建議路徑，也就是本例中的第二候選路徑。

回到圖3，若是在處理單元12判斷候選路徑的末端與另一道路等級的道路圖層之路段的節點重疊時(即S313的判斷結果為是時)，處理單元12可讀取包括所述重疊節點的另一道路圖層(S317)，例如為道路等級較高的道路圖層，並且在所述圖層上，以候選路徑末端的節點為起始節點，由處理單元12再度搜尋與所述起始節點連接的一或多個路段(S319)，並且返回步驟S305以下，分別計算各個路段的時間成本後，再根據對應於所述道路等級較高之道路圖層所設定的選取數量，選取時間成本較低的數個路段為候選路段，藉以更新候選路徑，直到獲得可連接出發地到目的地的建議路徑(S311)為止。

以圖2A及圖2B所繪示的道路圖層示意圖為例，圖2B所示的DH路段、DI路段、CD路段及CJ路段屬於同一道路等級的路段，並且，圖2B的道路圖層所對應的道路等級高於圖2A的道路圖層所對應的道路等級。

當處理單元12根據圖2A所示的道路圖層，從出發地A開始規劃路徑，而搜尋到包括AB路段及BD路段的候選路徑，以及包括AB路段與BC路段的另一候選路徑時，處理單元12可根據圖層資料庫16中對各個節點的記錄，判斷出候選路徑的末端，亦即節點C及D與圖2B所示之道路圖層中的節點重疊，故而可切換到圖2B所示的道路圖層，利用圖2B所示之道路圖層所包括的較高道路等級之路段繼續規劃候選路徑。

處理單元12在搜尋出連接節點C或節點D的路段後，可根據目前道路圖層所對應的選取數量選取其中一或多個路段為候選路段。由於圖2B所示的道路圖層對應於等級較高的道路，因此，為了搜尋的效率，選取數量可設置為少於道路等級較低之道路圖層所對應的數量。以本例而言，例如只選取時間成本最低的1個路段為候選路段。具體來說，如圖2B所示，處理單元12可搜尋出DH路段、DI路段、DC路段及CJ路段，時間成本分別為2、3、7及6單位。若根據時間成本的高低選取1個路段時，處理單元12將選取DH路段為新增的候選路段，並藉以更新由節點A、B、D到H所連接而成的候選路徑。

由於候選路徑末端的節點H尚非為目的地，故處理單元12尚需繼續搜尋下一個路段。處理單元12同樣可透過圖層資料庫16中對於節點的記錄，再判斷出節點H重疊於圖2A的道路圖層中，因此可切換回圖2A所對應的道路圖層搜尋與節點H相連接的路段。為了簡化說明之故，在圖2A當中，節點H所連接的路段僅有一段，即為HG路段，且GH路段的終止節點即為目的地。因此，處理單元12即已搜尋出完整連接出發地到目的地的一條候選路徑，即由節點A、B、D、H到G所組成的路徑，並將所述路徑指定為建議路徑。

上述說明僅用了兩層不同圖層，且二個道路圖層所對應的選取數量分別僅為時間成本最低的兩個及一個路段為候選路段，係為了便於說明之故，在實作上，根據不同的道路等級，通常可畫分為三層以上的道路圖層，而最底層的道路圖層所設定的選取數量可能超過數百。例如在包括一般道路的道路圖層中，每次選取時間成本最低的前500個路段為候選路段進行規劃，即使為道路等級較高的道路圖層，所對應的選取數量亦可能包括數十個，例如在包括快速道路的道路圖層中，每次選取時間成本最低的前60個路段為候選路段等，依此類推。藉此，既可利用底層道路圖層大範圍搜尋可能的連接到目的地的路段，又可利用逐漸隨著道路等級提高而減少搜尋範圍的方式簡化計算複雜度及增加計算效率，有利於迅速而準確地規劃出時間成本較低的建議路徑。

[實施例的可能功效]

根據本發明實施例，上述的路徑規劃系統及其方法，可提供一種由廣而深的搜尋手段，將各種道路路段依照道路等級畫分為不同的圖層，而由處理單元12根據規劃過程中所搜尋到的路段所屬等級，分別以不同的廣度選擇候選路段，而可將搜尋範圍限制在一定的數量內，提升路徑規劃的效率。

此外，上述實施例中用以選取候選路段的標準並非僅依照路段的距離來判斷，而是根據距離及路段所屬的道路等級等參數，綜合計算出所述的時間成本。相較於單純以最短距離為依據來規劃路徑的手段，本案實施例所獲得的建議路徑即使不是從出發地到目的地的最短路徑，但由於道路等級較高的路段所對應的時間成本較低，因此在建議路徑中有較大的機會包含屬於道路等級較高的路段。換言之，上述實施例所規劃出來的建議路徑能減少經過狹小巷弄並增加行走於平直大道的機率，使用的效益更甚於依照最短距離行走的路徑。

以上所述僅為本發明之實施例，其並非用以侷限本發明之專利範圍。

1．．．路徑規劃系統

10．．．輸入單元

12．．．處理單元

14．．．暫存單元

16．．．圖層資料庫

18．．．輸出單元

A-J．．．節點

S301-S319．．．流程步驟

圖1：本發明提供的一種路徑規劃系統實施例的方塊圖；

圖2A及2B：本發明提供的一種對應不同道路等級的道路圖層示意圖；及

圖3：本發明提供的一種路徑規劃方法實施例的流程圖。

S301-S319．．．流程步驟

Claims (11)

1. 一種路徑規劃方法，用以在一電子裝置規劃一出發地到一目的地之路徑，該電子裝置包括一處理單元及一圖層資料庫，所述方法包括：提供多個道路圖層，每一所述道路圖層對應一道路等級及一選取數量；自讀取出包含該出發地的其中一個所述道路圖層搜尋連接該出發地的一或多個路段，並分別計算該些路段的一時間成本，其中，每一所述路段包括一起始節點與一終止節點；依該時間成本由低到高排序該等路段，選取與所讀取的該道路圖層對應的該選取數量相等的其中一或多個路段為候選路段，其中，自該出發地開始依序相連接的該等候選路段組成一候選路徑；判斷該候選路徑的末端是否為對應該目的地的該終止節點；當該候選路徑的末端為對應該目的地的該終止節點時，選取該時間成本總和最小的該候選路徑為該出發地到該目的地的一建議路徑；及當該候選路徑的末端並非對應該目的地的該終止節點時，根據該等候選路徑末端的該等終止節點，分別再搜尋與各該等終止節點連接的一或多個路段，以該等候選路徑的該等終止節點作為新的該等起始節點，依據該等新的起始節點及與該等新的起始節點連接的該等路段分別對應的該道路圖層返回依該時間成本由低到高排序該等路段並選取與該道路圖層 對應的該選取數量相等的其中一或多個路段為該候選路段的步驟。
2. 如申請專利範圍第1項所述的路徑規劃方法，其中，對應的該道路等級高的該道路圖層所包括的該些路段的數量，少於對應的該道路等級低的該道路圖層所包括的該些路段。
3. 如申請專利範圍第2項所述的路徑規劃方法，其中，該些道路圖層中包括一最低圖層，該最低圖層包括所有道路等級的所有路段。
4. 如申請專利範圍第1項所述的路徑規劃方法，其中，當該候選路徑的末端並非對應該目的地的該終止節點時，根據該等候選路徑末端的該等終止節點，分別再搜尋與各該等終止節點連接的一或多個路段的步驟更包括：判斷該候選路徑的末端所對應的該終止節點是否與其他所述道路圖層中的節點重疊；若該候選路徑的末端所對應的該終止節點與其他所述道路圖層中的節點重疊，切換到包括該候選路徑末端的該終止節點的另一該道路圖層；於所述的另一該道路圖層搜尋連接於該候選路徑末端的該終止節點的一或多個路段。
5. 如申請專利範圍第4項所述的路徑規劃方法，其中，所切換的另一該道路圖層所對應的該道路等級高於切換前的該道路圖層，所切換的另一該道路圖層所對應的該選取數量少於切換前的該道路圖層所對應的該選取數量。
6. 如申請專利範圍第1項所述的路徑規劃方法，其中，每一所述路段的該時間成本係根據該路段的距離及該路段 所屬的該道路等級進行計算。
7. 一種路徑規劃系統，用以在一電子裝置規劃一出發地到一目的地之路徑，包括：一圖層資料庫，記錄多個道路圖層，每一所述道路圖層對應一道路等級及一選取數量；一處理單元，接收該出發地及該目的地，並讀取該等道路圖層其中之一以從該出發地起搜尋相連接的一或多個路段，並計算每一所述路段的一時間成本，以及依該時間成本由低到高排序該等路段，選取與所讀取的該道路圖層對應的該選取數量相等的其中一或多個路段為候選路段，其中每一所述路段包括一起始節點與一終止節點；其中，自該出發地起依序連接的一或多個候選路段組成一候選路徑，該處理單元用以持續選取該等候選路段以更新該等候選路徑，當該候選路徑的末端對應的該終止節點為該目的地時，選取該時間成本總和最小的該候選路徑為一建議路徑，當該候選路徑的末端對應的該終止節點並非對應該目的地時，以該等候選路段的該等終止節點作為新的該等起始節點繼續搜尋後續的一或多個該等路段，依據該等新的起始節點及與該等新的起始節點連接的該等路段分別對應的該道路圖層，依該時間成本由低到高排序該等路段並選取與所讀取的該道路圖層對應的該選取數量相等的其中一或多個路段為該等候選路段。
8. 如申請專利範圍第7項所述的路徑規劃系統，其中，對 應的該道路等級高的該道路圖層所包括的該些路段的數量，少於對應的該道路等級低的該道路圖層所包括的該些路段。
9. 如申請專利範圍第7項所述的路徑規劃系統，其中，該些道路圖層中包括一最低圖層，該最低圖層包括所有道路等級的所有路段。
10. 如申請專利範圍第7項所述的路徑規劃系統，其中，若該候選路徑的末端所對應的該終止節點與其他所述道路圖層中的節點重疊，切換到包括該候選路徑末端的該終止節點的另一該道路圖層以搜尋一或多個路段。
11. 如申請專利範圍第7項所述的路徑規劃系統，其中，該道路等級高的該道路圖層所對應的該選取數量，少於該道路等級低的該道路圖層所對應的該選取數量。