路径搜索装置和路径搜索方法

1.一种能使用多个路径搜索算法的路径搜索装置，其包括：
旅行路径累积单元，其用于获取并累积已旅行过的路径；
算法选择单元，其用于基于在所述旅行路径累积单元中所累积的旅行路径而选择满足用户偏好的路径搜索算法；以及
路径搜索单元，其用于通过使用由所述算法选择单元所选择的算法进行直至目的地的路径搜索，
其中，所述算法选择单元
借助于所述多个路径搜索算法，搜索从累积于所述旅行路径累积单元中的每个所述旅行路径的起点至目的地的路径，
为每个算法计算路径匹配率，所述路径匹配率是作为搜索结果而得到的路径和实际旅行路径之间的匹配率，
基于每个路径的所述路径匹配率为每个算法计算所述用户的路径选择倾向和所述算法之间的匹配率，并且
选择匹配率相对于所述用户的路径选择倾向为最高的算法作为满足所述用户偏好的算法。
2.如权利要求1所述的路径搜索装置，其中
所述算法选择单元搜索失配点，所述失配点是作为所述搜索的结果而得到的路径和所述实际旅行路径彼此分叉处的点，当存在失配点时，所述算法选择单元从所述失配点向前进行新的路径搜索，并且还通过使用该搜索结果而计算所述路径匹配率。
3.如权利要求1或2所述的路径搜索装置，其中
所述算法选择单元搜索失配点，所述失配点是作为所述搜索的结果而得到的路径和所述实际旅行路径彼此分叉处的点，并且为从多个搜索结果中得到的多个失配点提取公共点；并且
当使用所述选择的算法进行路径搜索时，所述路径搜索单元通过提高与所述公共点匹配的路段的成本而进行所述路径搜索。
4.如权利要求3所述的路径搜索装置，其中
所述路径搜索单元通过使用所述选择的算法以进行所述搜索，并且当在搜索到的路径上存在与所述公共点匹配的路段时，在提高所述路段的成本之后再次进行路径搜索。
5.一种路径搜索方法，其包括：
旅行路径累积步骤，该步骤用于获取并累积已经旅行过的路径；
算法选择步骤，该步骤用于基于所述累积的旅行路径而选择满足用户偏好的路径搜索算法；以及
路径搜索步骤，该步骤用于通过使用所述选择的算法进行直至目的地的路径搜索，其中，所述算法选择步骤包括：
借助于多个算法以搜索从在所述旅行路径累积步骤中所累积的每个所述旅行路径的起点至目的地的路径，
为每个算法计算路径匹配率，所述路径匹配率是作为所述搜索的结果而得到的路径和实际旅行路径之间的匹配率，
基于每个路径的所述路径匹配率为每个算法计算所述用户的路径选择倾向和所述算法之间的匹配率，以及
选择匹配率相对于所述用户的路径选择倾向为最高的算法作为满足所述用户的偏好的算法。
6.如权利要求5所述的路径搜索方法，其中
在所述算法选择步骤中搜索失配点，所述失配点是所述搜索的结果而得到的所述路径和所述实际旅行路径彼此分叉处的点，并且当存在失配点时，从所述失配点向前进行新的路径搜索，并且还通过使用该搜索结果而计算所述路径匹配率。
7.如权利要求5或6所述的路径搜索方法，其中
在所述算法选择步骤中，搜索作为所述搜索的结果而得到的所述路径和所述实际旅行路径彼此分叉处的点的失配点，并且为从多个搜索结果中得到的多个失配点提取公共点；
并且
在所述路径搜索步骤中，当借助于所述选择的算法进行路径搜索时，通过提高与所述公共点匹配的路段的成本而进行所述路径搜索。
8.如权利要求7所述的路径搜索方法，其中
在所述路径搜索步骤中，通过使用所述选择的算法进行所述搜索，并且当在搜索到的路径上存在与所述公共点匹配的路段时，在提高所述路段的成本之后再次进行路径搜索。

路径搜索装置和路径搜索方法\n技术领域\n[0001] 本发明涉及一种用于搜索直至目的地的路径的路径搜索技术，更具体地，本发明涉及一种通过使用满足用户偏好的路径搜索算法而进行路径搜索的技术。\n背景技术\n[0002] 过去，已经广泛使用能够以顺畅的方式在不熟悉的道路上驾驶的路径搜索装置(导航装置)。在路径搜索中存在多个路径搜索算法，例如最短旅行路径算法、最短旅行时间算法、收费道路优先级算法、使用不收费道路的算法等。因此采用了下列技术。即，在需要用户预先指定路径搜索算法之后进行路径搜索，或通过使用多个算法进行路径搜索，并且将多个搜索到的路径提供给用户。\n[0003] 而且，提出了下列技术进行更满足用户的偏好的路径选择。在第一专利文件中提出了一种技术，其中，将基于地图数据而计算出的路径与已旅行路径的数据作比较，并且基于比较的结果改变搜索成本以计算直至目的地的路径。此外，在第二专利文件中提出了一种技术，其中，根据多个搜索条件而得到路径和接合点或分支点，并且需要用户设置他或她喜好的导航路径。\n[0004] 专利文件1：日本专利3596704号\n[0005] 专利文件2：日本专利申请公布2007-240400号\n发明内容\n[0006] 然而，在上述现有技术中存在下列问题。通常，用户的路径选择的倾向(偏好)不是必然满足预定的路径搜索算法。因此，即使用户想从根据多个路径搜索算法而作出的搜索结果中搜索满足他或她的喜好的路径，但是在未知的或不熟悉的地方，用户难以确定哪条路径适合于他或她的目的。\n[0007] 因为改变了不同于实际的已旅行路径(已旅行路径的数据)的路径的搜索成本，故第一专利文件中所述的技术仅在已知的或熟悉的地方可以有效工作。此外，第二专利文件的技术需要用户在每个接合点或分支点处自己操作以选择导航路径，因而麻烦。\n[0008] 考虑到上述情况而作出本发明，并且本发明的目的是即使在用户之前尚未旅行过的地方也能提供满足用户的偏好的路径。\n[0009] 为达到上述目的，根据下列单元或处理而进行路径搜索。\n[0010] 根据本发明的路径搜索装置能使用多个路径搜索算法，并且所述路径搜索装置包括旅行路径累积单元，其用于获取并累积已经旅行过的路径，算法选择单元，其用于基于所累积的旅行路径而选择满足用户偏好的路径搜索算法，以及路径搜索单元，其用于通过使用所选择的算法进行直至目的地的路径搜索。\n[0011] 此处，算法选择单元首先通过使用多个路径搜索算法，分别搜索从每个所累积的旅行路径的起点至目的地的路径。然后，算法选择单元为每个算法计算作为搜索结果而得到的路径和实际旅行路径之间的匹配率(路径匹配率)。之后，算法选择单元为每个算法计算用户的路径选择倾向和所述算法(算法的偏好度)之间的匹配率。可为每个路径基于其路径匹配率而计算用户的路径选择倾向和所述算法之间的该匹配率。例如，优选的是通过对各个所累积的路径的路径匹配率取平均值(这也可通过加权平均来实现)以得到算法的匹配率。然后，算法选择单元选择匹配率相对于用户的路径选择倾向为最高的算法作为满足用户的偏好的算法。\n[0012] 于是，通过从用户的过去的旅行路径中确定用户的路径选择偏好，即使在不熟悉的地方也可为用户提供合适的路径。\n[0013] 而且，本发明中的算法选择单元优选地搜索失配点，所述失配点是作为搜索结果而得到的路径和实际旅行路径彼此分叉处的点，并且当存在失配点时，从失配点向前进行新的路径搜索，并且还通过使用该搜索结果而计算路径匹配率。\n[0014] 在这一点上，例如，当来自搜索的路径和实际路径在起点附近的点上彼此不同时，那么在整个范围内余下的所有路径不同，但是这不必然意味着用户不喜好该路径搜索算法。因此，通过从失配点向前进行新的路径搜索，从而得到新的路径相对于实际路径的匹配率，可作出关于用户是否喜好该路径搜索算法的更准确的判断。\n[0015] 而且，本发明中的算法选择单元可为从多个搜索结果中得到的多个失配点提取公共点(失配公共点)。然后，当使用所选择的算法进行路径搜索时，路径搜索单元优选地通过提高与该失配公共点匹配的路段的选择成本(使得该路段不易于被选中)而进行路径搜索。注意作为公共点或特点，这里例如列出交通信息(存在或不存在交通信号、存在或不存在拥堵、单行道交通状况等)、周边POI(兴趣点)信息、(诸如商店、学校等的设施)等。\n[0016] 如果对于很多路径存在不同于其搜索结果的路段(路段的类型)，那么可确定这样的路径不满足用户的偏好。因此，通过搜索公共失配点并提高这样的路段中的选择成本，可进行更满足用户的偏好的路径选择。\n[0017] 此处注意，在使用如上所述的失配公共点的情况下，优选地，路径搜索单元通过使用所选择的算法进行搜索，并且当在搜索路径上存在与公共点匹配的路段时，在提高该路段的成本之后再次进行路径搜索。\n[0018] 为了在直至目的地的所有路段中的失配公共点改变成本，这会提高处理负荷，因此首先不考虑任何失配公共点而作出路径搜索，并且仅当在搜索到的路径上存在失配公共点时，执行成本的改变，借以可以有效的方式进行所述处理。\n[0019] 此处注意，通过将路径再搜索的执行限制于当在作为搜索结果而得到的路径上不存在避让点的时间，或限制于当选择同样的路径的时间，可得到满足用户的偏好的路径。然而，可以考虑处理时间而设置再搜索的频率的上限。\n[0020] 此处注意，可将本发明理解为一种具有上述单元的至少部分的路径搜索装置。而且，可将本发明理解为一种包括上述处理的至少部分的路径搜索方法或一种能实现这种方法的程序。可将本发明的上述各个单元和处理以任何可能的方式任意地彼此组合以构成本发明。\n[0021] 根据本发明，即使在用户之前还未旅行过的地方，仍可提供满足用户偏好的路径。\n附图说明\n[0022] [图1]图1是图示根据本发明的第一实施例的汽车导航装置的功能性构造的视图。\n[0023] [图2]图2A～2D是分别图示旅行历史表、路径表、OD表和POI表的构造的视图。\n[0024] [图3]图3是图示算法偏好度计算处理的流程的流程图。\n[0025] [图4]图4A是说明在路径搜索中的失配点的视图，并且图4B是说明当存在这样的失配点时的再搜索处理的视图。\n[0026] [图5]图5是图示路径匹配率表的构造的视图。\n[0027] [图6]图6是图示算法偏好度表的构造的视图。\n[0028] [图7]图7是图示路径搜索处理的流程的流程图。\n[0029] [图8]图8是图示根据本发明的第二实施例的汽车导航装置的功能性构造的视图。\n[0030] [图9]图9是图示失配点表的构造的视图。\n[0031] [图10]图10是图示提取避让点的处理流程的流程图，所述避让点是对于失配点的公共条件。\n[0032] [图11]图11是图示避让点表的构造的视图。\n[0033] [图12]图12是图示路径搜索处理的流程的流程图。\n具体实施方式\n[0034] 现在，下面参照附图通过示例详述本发明的优选的实施例。\n[0035] (第一实施例)\n[0036] 根据本实施例的汽车导航装置通过分析用户迄今所旅行过的路径以确定用户喜好怎样的路径选择，并且在刚进行了路径搜索的情况下，使用满足用户偏好的路径搜索算法。图1是图示根据本发明的汽车导航装置(路径搜索装置)的功能性构造的示意图。\n[0037] 该汽车导航装置基本上配备了旅行路径累积部3、算法选择部5和路径搜索部6，其中，算法选择部5用于通过分析由旅行路径累积部3所累积的旅行路径而选择满足用户偏好的路径搜索算法，并且路径搜索部6通过使用由此选择出的算法以进行路径搜索。\n[0038] 此处应当注意，作为这种路径搜索算法的示例而列举了最短距离(距离优先级)算法、最少时间(时间优先级)算法、收费道路优先级算法、右转避让算法等，但是本发明不限于这些算法，并且可使用任何的任意路径搜索算法。\n[0039] <路径累积处理>\n[0040] 旅行路径累积部3通过将从GPS装置1中得到的位置数据和包含路段信息的地图数据2匹配而得到旅行路径(旅行路段)，并将旅行路径存储在旅行历史表4中。在本实施例中，得到了满足每个用户的偏好的搜索算法，因此期望的是为每个用户存储旅行路径的历史数据。为此目的，优选的是当用户操作该装置时识别用户。\n[0041] 图2A～2D图示了旅行历史表4的具体结构。如图2A所示，旅行历史表4具有用于用户ID412、OD(初始点/目的地：起点/终点)-ID413、路径ID414的每个组合的路径设置ID411，并且将其旅行频率415和其最后更新日期416存储于旅行历史表4中。\n[0042] 路径表(图2B)、OD表(图2C)和POI(兴趣点)表(图2D)被用作用于辅助旅行历史表4的其他表。\n[0043] 路径表中存储有路径ID421、OD-ID422和路段序列423。路段序列423是构成路径的路段的ID被以路径的顺序排列。从附图中可见，在即使各路径的起点和终点相同而各路径仍分别彼此不同的情况下，这些路径被存储为具有不同路径ID的记录。OD表中存储有OD数据，即存储有OD-ID431、起点(初始点)432和终点(目的地)433。对于起点和终点，它们的位置被存储为POI-ID。POI表中存储有POI数据，即存储有POI-ID441、纬度442、经度443和位置444。\n[0044] <算法选择处理>\n[0045] 算法选择部5从由旅行路径累积部3所准备的旅行历史表4中得到满足用户的偏好的路径搜索算法。算法选择部5基本上具有路径匹配率计算部51和算法偏好度计算部\n56。路径匹配率计算部51计算用户实际旅行的路径(存储在路径表中的路径)和根据每个搜索算法而得到的路径搜索结果在多大程度上彼此匹配，并且将所得到的结果存储在匹配率表55中。算法偏好度计算部56从每个用户过去旅行的各路径的旅行历史和路径匹配率表55中来计算算法偏好度，所述算法偏好度表明每个用户喜好哪种路径选择算法的倾向，并且将所述路径选择算法的倾向存储在算法偏好度表57中。\n[0046] 更具体地，在算法选择部5中的路径匹配率计算部51设置有路径搜索部52、失配点提取部53和路径匹配率计算部54。下面连同图3中所示的流程图说明各个功能部的详细工作原理。图3是图示由算法选择部5进行的算法偏好度计算处理的整个流程的流程图。\n[0047] 路径搜索部52对存储在旅行历史表4中的每个路径，根据预定的路径搜索算法而从其起点(初始点)至其终点(目的地)搜索路径。具体地，在步骤S31中，首先输入存储在旅行历史表4中的路径的起点和终点以作为用于路径搜索的目的地条件。然后，在步骤S32中，选择一个预定的路径搜索算法，并且在步骤S33中，通过使用由此选择的算法以进行路径搜索。\n[0048] 在步骤S34中，失配点提取部53提取在实际旅行路径和作为搜索结果而得到的路径之间的失配点。例如，如图4A所示，当实际旅行路径的路段序列是1、2、3、4和5，并且作为搜索结果而得到的旅行路径的路段序列是1、6、7和8的情况下，可判断或确定出失配发生在节点N1处。在此情况下，路径搜索部52返回步骤S33，在步骤S33中，路径搜索部52通过将节点N2设置为起点以再次进行路径搜索，其中节点N2是失配所发生的路段(即路段2)的终端节点。可认为只要在其搜索结果中存在失配，则连续地进行这种再搜索处理。\n在图4B的示例中，作为搜索结果的路径的路段序列变成1、6、3、4和5。此处，注意路段6和路段3彼此不连接，但是目的是得到搜索到的路径的匹配率，于是在这样的结果中不存在问题。此外，通过进行如上所述的再搜索，当计算用户的路径选择倾向和路径搜索算法在多大程度上彼此满足时，可以尽可能地反映出用户的实际旅行历史。\n[0049] 然后，在步骤S35中，路径匹配率计算部54计算用户实际旅行的路径和根据特定路径搜索算法而作出的搜索的路径之间的匹配率，并且将所述匹配率存储在路径匹配率表\n55中。路径的匹配率是表示用户的实际旅行路径和根据特定路径搜索算法而搜索出的路径之间彼此在多大程度上匹配的值。路径的匹配率例如可以获得为(匹配路段数)/(实际旅行路径的路段数)，或(匹配路段的总距离)/(实际旅行路径的总计距离)。此外，路径的匹配率还可以获得为(匹配节点数)/(实际旅行路径的节点数)，或者路径的匹配率可以仅针对将各种道路的路段互相连接的节点而获得为(匹配节点数)/(实际旅行路径的节点数)。\n[0050] 根据用于每个路径的所有预定的路径搜索算法以进行路径匹配率的计算。因此，在步骤中S36中，确定是否已使用所有算法而计算出匹配率，并且当存在借此尚未计算出匹配率的任何算法时，则返回至步骤S32以计算用于该算法的匹配率。\n[0051] 另一方面，当已根据所有算法计算出特定路径的匹配率时(S36：是)，然后，在步骤中S37中确定是否存在还未得到匹配率的任何路径，并且当在旅行路径或历史表4中存在未经处理或未完成的路径时，则返回至步骤S31以计算该路径的匹配率。\n[0052] 将以上述方式得到的各匹配率存储于路径匹配率表55中。图5中图示了路径匹配率表55的示例。路径匹配率表55中存储有搜索ID551、路径ID552、OD-ID553、搜索算法\n554、路段序列555和匹配率556。如该图所示，为每个路径的每个搜索算法554而存储搜索到的路径(路段序列555)和实际旅行路径(路径ID552)之间的匹配率556。\n[0053] 当为每个路径而已经得到根据每个搜索算法的搜索到的路径的匹配率时，则算法偏好度计算部56计算每个算法的算法偏好度，所述算法偏好度是用户的路径搜索倾向和路径搜索算法彼此匹配的程度，并且算法偏好度计算部56将该算法偏好度存储于算法偏好度表57中。基于用户实际旅行的各个路径和根据待检查的搜索算法的搜索结果之间的匹配率而计算特定搜索算法的算法偏好度。例如，可通过对用于用户实际旅行的各个路径的匹配率取平均值而得到该算法偏好度，所述匹配率根据每个路径的旅行的频率或数量而被加权。该权重可以是与旅行频率成比例而变大的值。然而，为了防止用户经常旅行的那些路径的路径选择倾向被过度地反映出来，优选的是使用随着旅行频率而增大但是随着增大的速率而逐渐地降低的权重。此外，为了更多地反映出最近的路径选择倾向，同样优选的是从最后更新日期开始随着时间的推移而降低权重。\n[0054] 图6图示了算法偏好度表57的示例。如图6所示，算法偏好度表57中存储有用户ID571、搜索算法572和匹配率(偏好度)573。以此方式，关于每个用户的路径搜索倾向的每个搜索算法的匹配率，即每个用户的搜索算法的偏好度被存储于算法偏好度表中。\n[0055] 此处注意，在合适的时间，例如当用户停止驾驶操作(即在关掉发动机时)或当用户开始驾驶操作(即在启动发动机时)时，对于直到那时的旅行历史，仅需执行根据算法选择部5的算法偏好度的上述计算处理。在这一点上，不需要每次对所有路径进行上述处理，但是反而仅需要对于从其最后的执行中已被新加入的那些路径执行上述处理。此外，当用户从操作起始位置直到操作终止位置而旅行时，用户的旅行路径可包含中继或中间点(中途停留点)，从而在请求用户确认是否存在任何中继点之后进行该处理。而且，虽然在以上描述中说明对于所有旅行路径而得到匹配率，但可从匹配率计算处理中排除部分旅行路径。\n[0056] <路径搜索处理>\n[0057] 当用户提供了初始点(通常为当前位置点)和目的地时，路径搜索部6搜索直到其目的地的路径。当进行该路径搜索时，通过参照算法偏好度表57，通过使用满足用户偏好的最合适的算法以进行路径选择。\n[0058] 图7是图示路径搜索处理的流程的流程图。首先，路径搜索部6从用户那里接收目的地的输入(步骤S71)。此时，从GPS装置1中得到的当前位置用作路径搜索的初始点。\n然后，通过参照算法偏好度表57以选择最满足用户的路径选择偏好的路径选择算法(步骤S72)。之后，路径搜索部6通过使用如此选择的路径搜索算法以进行路径搜索(步骤S73)，并且通过将所述路径显示在显示器等上而给用户提供搜索结果(步骤S74)。\n[0059] <本实施例的效果>\n[0060] 根据本实施例，从用户迄今所旅行过的路径的历史中，可确定最满足或匹配用户的路径选择偏好的路径选择算法。于是，当刚进行路径搜索时，可提供通过最匹配用户偏好的路径选择算法而搜索到的路径。\n[0061] 根据这种方法，即使在用户还未旅行过且不熟悉的地方，可搜索类似于用户日常使用路径的路径并将所述路径提供给用户。\n[0062] 通常，仅使用几种路径搜索算法，因为算法的增加使得用户难以决定选择何种算法。然而，根据本实施例，即使在使用大量的搜索算法的情况下，也不需要用户明确地指定使用何种搜索算法。于是，可从大量的搜索算法中选择最合适的一个以满足用户的偏好，而无需给用户施加负担。\n[0063] (第二实施例)\n[0064] 根据本发明的第二实施例的汽车导航装置，其不仅具有第一实施例的功能，还可以提取用户避让经过的点(路段)，并且使得更加难以选择包括这样的点的路径，从而提供更满足用户的路径搜索倾向的路径。\n[0065] 图8图示根据本发明的第二实施例的汽车导航装置的功能性构造。不同于第一实施例的是提供失配点表7、避让点提取部8和避让点表9。\n[0066] <避让点提取处理>\n[0067] 当在路径匹配率计算部51中的实际旅行路径和搜索结果路径存在失配点的情况下，将该失配点存储于失配点表7中。如图9所示，失配点表7中存储有用户ID701和失配路段对702。失配路段对是发生失配的一对路段，并且如图4A所示，在节点N1处，实际旅行的为路段2但搜索算法选择路段6的情况下，失配路段对变成2和6。失配点是每个用户所特有的信息，因此为每个用户ID存储该失配点。\n[0068] 在图9中，仅存储发生失配的路段对，但是可分别存储所述路段对所产生的失配的频率，以及存储当根据搜索算法所选择的路径和实际旅行路径彼此匹配的次数的频率。\n即，可存储失配发生的比率(概率)。这是因为对于特定路段对不会每次都产生失配，并且在很多情况下，当旅行通过搜索算法所选择的路段时，用户不必避让该路段。于是，通过存储避让路段的比率，可以更充分的方式确定被用户避让的路段。\n[0069] 避让点提取部8从失配点表7中提取被用户避让的路段(避让点)。通过得到存在于失配点表7中所包含的失配点中的公共点而进行避让点的提取。例如，建立了被认为是失配原因的一些条件(例如拥堵、右转、校舍等)，并且判断包含在失配点表中的每个失配点是否满足这些条件。当预定的条件表现为超过预定次数的失配点时，可确定用户避让了这种条件下的点。不仅如此，还可通过使用神经网络技术等提取各避让点。\n[0070] 图10作为流程图图示了由避让点提取部8所执行的避让点提取处理的流程的一个示例。在该示例中，避让点提取部8预先收集原因(失配条件)，这些原因被认为是由用户所避让的那些点的原因。例如可将学校路径、交通信号、右转、拥堵等列为失配条件。\n[0071] 避让点提取部8从失配点表7中提取失配点(步骤S101)。然后，确定以此方式提取的失配点是否满足预先收集在避让点提取部中的失配条件(步骤S102)。例如，通过使用搜索算法所选择的路段是学校路径，并且用户实际旅行的路段不是学校路径的情况下，可满足失配条件“学校路径”。在此情况下，用于被满足的失配条件的计数值(步骤S103)递增。此处，注意一个失配点可满足多个失配条件。对于所有失配点进行这种失配条件的计数(步骤S104)。\n[0072] 随后，当用于失配条件的计数值等于或大于预定值时，具有这种条件的路段被提取为避让点，并且将所述路段存储在避让点表9中(步骤S105)。例如，如果用于失配条件“学校路径”的计数值等于或大于阈值，那么可确定用户倾向于避让学校路径，因此学校路径被提取为避让点。\n[0073] 在图11中图示了避让点表9的构造。避让点表9包括用户ID901和避让点902，并且为每个用户存储该用户避让哪类点。\n[0074] <路径选择处理>\n[0075] 接下来，当参照图12的流程图时，说明通过使用以此方式提取的避让点，根据路径搜索部6所执行的路径搜索处理。首先，路径搜索部6从用户那里接收目的地输入(步骤S121)，从算法偏好度表57中选择满足用户的路径选择偏好的路径选择算法(步骤S122)，并且通过使用以此方式选择的算法而进行路径搜索(步骤S123)。然后，在作为搜索的结果而得到的路径中，确定是否存在与存储在避让点表9中的避让点匹配的路段(步骤S124)。\n当在搜索到的路径上存在避让点时进行调整，使得对于该路段的搜索成本增加，这样使得该路段不易于被选中(步骤S125)。此后，基于已经被调整的搜索成本再次进行路径搜索处理。即使调整了搜索成本，仍执行这样的处理，直到在作为搜索的结果而得到的路径上不存在避让点，或直到搜索到或得到同样的路径为止，但是可为再搜索的频率设置上限值。然后，将由此得到的路径作为来自于搜索的路径结果提供给用户(步骤S126)。\n[0076] <本实施例的效果>\n[0077] 根据本实施例，不仅可从预定的路径搜索算法中使用最满足用户的路径选择偏好的算法，而且可以这样的方式进行路径搜索，即用户倾向于避让的道路被设定为不易于被选中。即，可以更灵活的方式进行能够反映用户的路径选择倾向的路径搜索。\n[0078] 附图标记列表\n[0079] 3 旅行路径累积部\n[0080] 4 旅行历史表\n[0081] 5 算法选择部\n[0082] 51 路径匹配率计算部\n[0083] 55 匹配率表\n[0084] 56 算法偏好度计算部\n[0085] 57 算法偏好度表\n[0086] 6 路径搜索部\n[0087] 7 失配点表\n[0088] 8 避让点提取部\n[0089] 9 避让点表