路径搜索装置、路径搜索方法、路径搜索程序以及记录介质

摘要

路径搜索装置(100)具备提取部(101)、取得部(102)、确定部(103)、和搜索部(104)。提取部(101)提取地图数据上的道口。取得部(102)取得由提取部(101)提取出的道口在每个时间段阻断交通的台数(交通阻断量)。确定部(103)基于由取得部(102)取得的交通阻断量，确定发生了一定程度以上的拥堵的道口(拥堵道口)。搜索部(104)对包含由确定部(103)确定的拥堵道口的环节乘以预定的环节成本值，搜索至目的地的路径。

说明书

技术领域

本发明涉及安装在移动体上的路径搜索装置、路径搜索方法、路径搜索程序以及记录介质。但是，本发明的应用不限于上述的路径搜索装置、路径搜索方法、路径搜索程序以及记录介质。

背景技术

近年来，在车辆等移动体中安装有基于地图数据搜索至目的地的路径的路径搜索装置。例如，在搜索到至目的地的路径时，存在设定有经由所谓很少打开的道口(開かずの踏切)的路径的情况。在这种情况下，有时在很少打开的道口中，通过该道口花费了不少时间，与搜索出的预定时间大不相同。

因此，提出了如下技术：预先存储各个道口在每个时间段的开闭时间，基于该存储数据，考虑与该时刻对应的道口数据来进行路径搜索(例如，参照下面的专利文献1)。

专利文献1：日本特开2001-304887号公报

但是，在上述专利文献1的技术中，例如，当相邻道口的开闭时间相同时，即使一个道口是拥挤道路的道口、另一个道口是交通量闲散的道路的道口，由于仅仅考虑道口的开闭时间来设定路径，因此，有时会将拥挤道路的道口用于路径。也就是说，不考虑虽然开闭时间相同但该道路的通过时间由于交通量的不同而不同的情况，却仅仅考虑开闭时间，因此，存在不能设定合适的路径的问题。

发明内容

为了解决上述问题而达到目的，第一方面的发明涉及的路径搜索装置，其特征在于，该路径搜索装置具有：提取单元，其提取地图数据上的道口；取得单元，其取得由所述提取单元提取出的道口在每个时间段阻断交通的台数(下面，称作“交通阻断量”)；确定单元，其基于由所述取得单元取得的所述交通阻断量，确定发生了一定程度以上的拥堵的道口(下面，称作“拥堵道口”)；以及搜索单元，其对包含由所述确定单元确定的所述拥堵道口的环节乘以预定的环节成本值，搜索至目的地的路径。

此外，第二方面的发明涉及的路径搜索方法，其特征在于，该路径搜索方法包括如下步骤：提取步骤，提取地图数据上的道口；取得步骤，取得通过所述提取步骤提取出的道口在每个时间段阻断交通的台数(下面，称作“交通阻断量”)；确定步骤，基于通过所述取得步骤取得的所述交通阻断量，确定发生了一定程度以上的拥堵的道口(下面，称作“拥堵道口”)；以及搜索步骤，对包含通过所述确定步骤确定的所述拥堵道口的环节乘以预定的环节成本值，搜索至目的地的路径。

此外，第三方面的发明涉及的路径搜索程序，其特征在于，该路径搜索程序使计算机执行第二方面所述的路径搜索方法。

此外，第四方面的发明涉及的计算机能够读取的记录介质，其特征在于，所述记录介质记录有第三方面所述的路径搜索程序。

附图说明

图1是示出实施方式的路径搜索装置的功能结构的一例的框图。

图2是示出实施方式的路径搜索装置的路径搜索处理顺序的一例的流程图。

图3是示出本实施例的导航装置的硬件结构的一例的框图。

图4是示出本实施例的导航装置的路径搜索处理的一例的流程图。

图5是示出本实施例的导航装置的路径搜索处理的另一个例子的流程图。

图6-1是示出在本实施例中路径搜索时使用的环节成本(link cost)的计算处理的一例的流程图。

图6-2是示出本实施例的导航装置的路径搜索处理的另一个例子的流程图。

图7是示出在本实施例中道口属性的赋予处理的一例的流程图。

图8是示出在本实施例中，当没有正在进行道口等待的车辆时的车辆平均等待时间的一例的曲线图。

图9是示出在本实施例中，当存在正在进行道口等待的车辆时的车辆平均等待时间的一例的曲线图。

图10是示出本实施例的道口显示的一例的说明图。

图11是示出本实施例的道口记号的显示形式的一例的说明图。

图12是示出本实施例的立体交叉记号的显示形式的一例的说明图。

标号说明

100：路径搜索装置；101：提取部；102：取得部；103：确定部；104：搜索部；105：所需时间计算部；106：取入部；107：阻断量计算部；108：通知部；109：显示控制部；110：显示部；300：导航装置；1030：道口；1030a：拥堵道口；1030b：拥堵道口；1031：立体交叉道路；1100：道口记号；1110：标记；1120：外周；1200：立体交叉记号；1210：标记；1220：外周。

具体实施方式

下面，参照附图详细说明本发明的路径搜索装置、路径搜索方法、路径搜索程序以及记录介质的优选实施方式。

(实施方式)

(路径搜索装置的功能构成)

说明本发明的实施方式的路径搜索装置100的功能结构。图1是示出实施方式的路径搜索装置的功能结构的一例的框图。在图1中，路径搜索装置100构成为具有提取部101、取得部102、确定部103、搜索部104、所需时间计算部105、取入部106、阻断量计算部107、通知部108、显示控制部109以及显示部110。

提取部101提取地图数据上的道口。取得部102取得由提取部101提取出的道口在每个时间段阻断交通的台数(以下，称作“交通阻断量”)。具体而言，交通阻断量是每预定时间阻断交通的台数，例如，可以列举在各个道口中实测的台数。每个时间段，有代表性地可以列举每1小时、每2小时的期间(span)，也可以是每天、每早晨、每白天、每下午、每晚上。交通阻断量可以是通过有线或无线等方式接收的实时信息，还可以是预先记录的信息。

确定部103根据由取得部102取得的交通阻断量，确定发生了一定程度以上的拥堵的道口(以下，称作“拥堵道口”)。一定程度以上的拥堵是指以道口地点为起始一定距离以上的拥堵、存在一定台数以上的车辆的拥堵、进行道口等待的车辆的台数每隔一定时间达到一定台数以上的拥堵、通过该道口需要的时间为一定时间以上的拥堵等。即，通过道口需要的时间与其他道口相比长的道口相当于拥堵道口。另外，这里所说的“一定”不必是所有道口共同的一定值，也可以是按照每个道口而设定的值。

具体而言，例如，在取得部102取得了交通阻断量的情况下，确定部103对照该交通阻断量和预先记录的针对每个道口按照每个时间段设定的阈值，当交通阻断量在阈值以上时，将该道口确定为拥堵道口。

当搜索部104通过例如最短路径法等进行路径搜索时，计算各环节的环节成本。搜索部104计算包含由确定部103确定的拥堵道口在内的环节的预定的环节成本值。环节成本值是环节计算时使用的加权，例如，可以是根据实时的交通阻断量每次计算的值，也可以是与预先记录的每个时间段的交通阻断量对应地预先设定的值。

此外，也可以是，搜索部104根据由取得部102取得的交通阻断量，对包含上述拥堵道口的环节乘以预定的环节成本值，搜索至目的地的路径。此外，也可以具备所需时间计算部105。所需时间计算部105根据由搜索部104搜索到的路径，计算至目的地的所需时间。具体而言，在至目的地的路径中包含拥堵道口时，搜索部104加上与环节成本值对应的预定时间，计算至目的地所需要的时间。

此外，在本实施方式中，取入部106和阻断量计算部107是任意的结构元素。取入部106取入在各个时间段中存在道口的道路每预定时间的交通量、和道口每预定时间中能够使车辆通行的车辆转出量。阻断量计算部107根据由取入部106取入的每预定时间的交通量和车辆转出量，计算交通阻断量。存在道口的道路每预定时间的交通量例如是指，一般根据干线道路或车道数量等而增加的量。车辆转出量也是一般根据干线道路或车道数量等而增加的量。此外，车辆转出量是根据道口的开闭时间而变化的量，阻断机开放的时间越长，则车辆转出量越大。

也可以是，确定部103基于根据地图数据上的道口位置而确定的拥堵道口的位置，确定绕过拥堵道口的道口(以下，称作“绕弯道口”)、或者绕过拥堵路口且与线路立体交叉的道路(以下，称作“立体交叉道路”)。此时，搜索部104根据已设定的搜索条件，在通过拥堵道口、绕弯道口、或立体交叉道路的路径中，选择最合适的路径即可。具体而言，立体交叉道路是指跨过线路的跨线桥、或在线路下方通过的地下通道等。此外，搜索部104搜索时的搜索条件是时间优先、距离优先等条件。此外，最合适的路径是指最符合搜索条件的路径。

此外，在本实施方式中，通知部108是任意的构成元素。通知部108在搜索部104搜索到经由绕弯道口或立体交叉道路的至目的地的路径时，通知已绕过拥堵道口的情况。通知部108例如可以生成通过文字显示已绕过的情况的图像，也可以用虚线等表示经由拥堵道口的路径，通知已绕过拥堵道口的情况。

此外，也可以是，取得部102取得在当前时刻出发时拥堵道口的交通阻断量、和在经过预定时间后的时刻出发时拥堵道口的交通阻断量。此时，搜索部104基于由取得部102取得的在当前时刻出发时拥堵道口的交通阻断量、和在经过预定时间后的时刻出发时拥堵道口的交通阻断量，搜索各个出发时刻的路径即可。此外，所需时间计算部105计算各个出发时刻的所需时间即可。

此外，在本实施方式中，显示控制部109和显示部110是任意的构成元素。显示控制部109将由确定部103确定的拥堵道口的显示控制成与通常的显示不同的显示。显示部110显示由显示控制部109显示控制后的拥堵道口。显示控制部109的与通常的显示不同的显示例如是指，对发生了拥堵的道路进行带颜色显示、闪烁显示、叉显示等利用者能够识别拥堵的显示。显示部110只要是显示器等能够显示拥堵道口的部件即可。因此，显示部110使包含拥堵道口在内的发生了一定程度以上的拥堵的道口为与通常的显示不同的显示。

也可以是，显示控制部109对拥堵道口进行记号显示，并且，根据由取得部102取得的交通阻断量，使记号显示的拥堵道口的显示形式变化。记号显示例如可以列举表示道口的标记。根据交通阻断量使显示形式变化是指，例如根据拥堵的长度、通过道口花费的时间，使标记闪烁或者使标记的颜色变化即可。具体而言，例如，在通过道口花费的时间大于等于预定时间的情况下，加速标记的闪烁或者将标记的颜色显示成红色等，进行督促绕过该拥堵道口的显示即可。

也可以是，显示控制部109对绕弯道口或立体交叉道路进行记号显示。记号显示例如可以列举表示道口的标记。此外，在这种情况下，也可以是，显示控制部109根据拥堵道口的交通阻断量，使绕弯道口或立体交叉道路的显示形式变化。即，在拥堵道口的拥挤在预定程度以上的情况下，只要显示督促向该绕弯道口或立体交叉道路通行的颜色即可，例如将标记的颜色显示成蓝色并使之闪烁等。

(路径搜索装置100的路径搜索处理顺序)

接着，利用图2说明路径搜索装置100的路径搜索处理顺序。图2是示出实施方式的路径搜索装置的路径搜索处理顺序的一例的流程图。

在图2的流程图中，路径搜索装置100等待路径搜索开始的输入(步骤S201：否的环路)，在有路径搜索开始的输入时(步骤S201：是)，提取部101提取地图数据上的道口(步骤S202)。然后，取得部102取得由提取部101提取出的道口的交通阻断量(步骤S203)。

然后，确定部103根据由取得部102取得的交通阻断量，确定拥堵道口(步骤S204)。然后，搜索部104对包含拥堵道口的环节乘以预定的环节成本值，搜索至目的地的路径(步骤S205)，结束一连串的处理。

如以上说明的那样，本实施方式的路径搜索装置100根据道口在每个时间段阻断交通的台数(交通阻断量)确定拥堵道口，并且，对包含该拥堵道口的环节乘以预定的环节成本值进行路径搜索。根据这样的路径搜索装置100，能够进行与各道口的交通量对应的路径搜索。因此，利用者能够探索回避了通过时间长的拥堵道口的行走路线。此外，如果大多数的车辆回避了拥堵道口，则能够使拥堵得到缓解。

此外，本实施方式的路径搜索装置100还可以具备取入每预定时间的交通量和道口中车辆转出量的取入部，并且，具备基于由取入部106取入的每预定时间的交通量和车辆转出量，计算交通阻断量的阻断量计算部107。也就是说，也可以根据交通量和车辆转出量，计算每个道口的交通阻断量。根据这样的结构，能够简单并且正确地计算交通阻断量。

此外，本实施方式的路径搜索装置100还可以除了拥堵道口之外还确定绕弯道口或立体交叉道路，并基于已设定的搜索条件，在通过拥堵道口、绕弯道口或立体交叉道路的路径中选择最合适的路径。根据这样的结构，能够进行与时间优先、距离优先等检索条件对应的路径搜索。

此外，本实施方式的路径搜索装置100还可以具备在搜索部104搜索到经由绕弯道口或立体交叉道路的至目的地的路径时，通知已绕过拥堵道口的情况的通知部108。根据这样的结构，利用者能够了解所显示的路径不是绕道的路径而是已绕过拥堵道口的路径的情况，并且能够了解缩短了至目的地的所需时间的情况。

此外，本实施方式的路径搜索装置100的取得部102还可以取得在当前时刻出发时的拥堵道口的交通阻断量和在经过预定时间后的时刻出发时的拥堵道口的交通阻断量。此外，搜索部104还可以基于由取得部102取得的在当前时刻出发时的拥堵道口的交通阻断量、和在经过预定时间后的时刻出发时的拥堵道口的交通阻断量，搜索各个出发时刻的路径。根据这样的结构，利用者能够了解推迟出发时刻时的到达时刻和所需时间，因此在时间有富裕的情况下，能够稳定地推迟出发时刻。

此外，本实施方式的路径搜索装置100还可以具备显示控制部109和显示部110，该显示控制部109将拥堵道口的显示控制成与通常的显示不同的显示，该显示部110显示由显示控制部109进行了显示控制后的拥堵道口。根据这样的结构，利用者能够在显示画面上确认通过时间长的道口。

此外，本实施方式的路径搜索装置100中的显示控制部109还可以在对拥堵道口进行记号显示的同时，根据由取得部102取得的交通阻断量，使记号显示的拥堵道口的显示形式变化。根据这样的结构，利用者能够看一眼就掌握拥堵道口，并且还能够看一眼就掌握拥挤的程度。

此外，本实施方式的路径搜索装置100中的显示控制部109还可以对绕弯道口或立体交叉道路进行记号显示。根据这样的结构，利用者能够看一眼就掌握绕弯道口或立体交叉道路，并能够简单地找到该绕弯道口或立体交叉道路。

实施例

下面，说明本发明的实施例。在本实施例中，说明通过安装在车辆中的导航装置来实施本发明的路径搜索装置100时的一例。

(导航装置300的硬件结构)

利用图3说明本实施例的导航装置300的硬件结构。图3是示出本实施例的导航装置的硬件结构的一例的框图。在图3中，导航装置300安装在车辆等移动体中，具备CPU 301、ROM 302、RAM 303、磁盘驱动器304、磁盘305、光盘驱动器306、光盘307、语音I/F(接口)308、扬声器309、输入设备310、影像I/F 311、显示器312、通信I/F 313、GPS单元314、和各种传感器315。此外，各构成部301～315通过总线320分别连接。

CPU301控制导航装置300的整体。ROM 302记录有引导程序、当前地点计算程序、导航程序、路径引导程序、语音生成程序、地图数据显示程序、记号显示程序等各种程序。此外，RAM 303用作CPU301的工作区域。

当前地点计算程序例如基于后述的GPS单元314和各种传感器315的输出信息，计算车辆的当前地点(导航装置300的当前地点)。

导航程序利用记录在后述的磁盘305中的地图数据等，搜索从出发地点至目的地点的最佳路径。这里，最佳路径是指至目的地点的最短(或最快)的路径或最符合利用者指定的条件的路径等。此外，不仅搜索目的地点，还可以搜索至顺路地点或休息地点的路径。搜索到的引导路径经由CPU 301向语音I/F 308或影像I/F 311输出。

路径引导程序基于通过执行导航程序而搜索到的引导路径信息、通过执行当前地点计算程序而计算出的车辆当前地点信息、和从磁盘305读出的地图数据，生成实时的路径引导信息。所生成的路径引导信息经由CPU 301向语音I/F308或影像I/F311输出。

语音生成程序生成与模式对应的音调和语音的信息。即，基于通过执行路径引导程序而生成的路径引导信息，设定与导向点对应的虚拟声源并生成语音指导信息，经由CPU 301向语音I/F308输出。

地图数据显示程序通过影像I/F311在显示器312上显示记录在磁盘305或光盘307上的地图数据。

记号显示程序显示记录在磁盘305或光盘307上的、记号显示的地图数据上的道口位置，并且基于道口的交通阻断量改变显示形式。

磁盘驱动器304通过CPU301的控制来控制对磁盘305的数据的读取/写入。磁盘305在磁盘驱动器304的控制下记录已写入的数据。作为磁盘305，例如可以使用HD(硬盘)或FD(软盘)。

光盘驱动器306通过CPU301的控制来控制对光盘307的数据的读取/写入。光盘307是通过光盘驱动器306的控制而读出数据的可拆卸的记录介质。光盘307还能够利用可以写入的记录介质。此外，作为这种可拆卸的记录介质，除了光盘307之外还可以是MO、存储卡等。

语音I/F308与语音输出用的扬声器309连接。输入设备310可以列举具备用于输入文字、数值、各种指示等的多个键的遥控器、键盘、鼠标、触摸面板等。输入设备310可以通过遥控器、键盘、鼠标、触摸面板中的任意一个方式来实现，还可以通过其中的多个方式来实现。

影像I/F 311与显示器312连接。具体而言，影像I/F 311例如由控制IC等构成，所述控制IC基于控制显示器312整体的图形控制器、临时记录能够即时显示的图像信息的VRAM(Video RAM)等缓冲器存储器、和从图形控制器输出的图像数据，对显示器312进行显示控制。

在显示器312上显示有图标、光标、菜单、窗口、或文字和图像等的各种数据。在显示器312上以二维或三维的方式描绘有上述地图数据。显示在显示器312上的地图数据中，能够重叠显示表示安装有导航装置300的车辆的当前地点的标记等。通过CPU301计算车辆的当前地点。

这种显示器312例如可以采用CRT、TFT液晶显示器、等离子体显示器等。显示器312例如设置在车辆的仪表板附近。除了车辆的仪表板附近之外，显示器312还可以设置在车辆的后部座椅周围等，从而在车辆内设置多个。

通信I/F 313通过无线的方式连接到网络，发挥导航装置300与CPU301的接口的功能。通信I/F 313还通过无线的方式连接到互联网等通信网，还发挥该通信网与CPU301的接口的功能。

通信网包括LAN、WAN、共用线路网或移动电话网等。具体而言，通信I/F313由例如FM调谐器、VICS(Vehicle Information andCommunication System：道路交通信息通信系统)/信标接收器、无线导航装置和其他导航装置构成，取得从VICS中心发送的拥堵或交通管制等的道路信息。另外，VICS是注册商标。

GPS单元314接收来自GPS卫星的电波，输出表示车辆当前地点的信息。GPS单元314的输出信息与后述的各种传感器315的输出值一起用于由CPU301计算车辆的当前地点。表示当前地点的信息例如是纬度/经度、高度等确定地图数据上的一点的信息。

各种传感器315输出车速传感器、加速度传感器、角速度传感器等的能够判断车辆的位置或举动的信息。各种传感器315的输出值用于由CPU 301计算车辆的当前地点或测定速度或方位的变化量等。

图1中示出的路径搜索装置100具备的提取部101、取得部102、确定部103、搜索部104、所需时间计算部105、取入部106、阻断量计算部107、通知部108、显示控制部109、显示部110通过如下方式来实现其功能：CPU301利用记录在图3所示的导航装置300中的ROM 302、RAM303、磁盘305、光盘307等上的程序或数据，执行预定的程序，控制导航装置300中的各个部分。

即，本实施例的导航装置300能够通过执行记录在导航装置300中的作为记录介质的ROM302中的各种程序，按照图2所示的路径搜索处理顺序，执行图1所示的路径搜索装置100具备的功能。

(导航装置300的路径搜索处理的一例)

接着，利用图4说明本实施例的导航装置300进行的路径搜索处理的一例。图4是示出本实施例的导航装置的路径搜索处理的一例的流程图。

在图4的流程图中，导航装置300处于待机状态，直到接收到路径搜索开始的指示为止(步骤S401：否的环路)，如果接收到路径搜索开始的指示(步骤S401：是)，则例如在时间优先的搜索条件下，不对包含有道口的环节乘以环节成本值而进行路径搜索(步骤S402)。然后，对包含有道口的环节乘以环节成本值而进行路径搜索(步骤S403)。在计算所需时间时，当路径中包含有拥堵道口时，加上与环节成本值对应的预定时间来计算即可。另外，有关环节成本值的计算将在后面叙述。

然后，判断上述两条路径是否不同(步骤S404)。在步骤S404中，当判断为两条路径不同时(步骤S404：是)，从地图数据上确定拥堵道口(步骤S405)。具体而言，两条路径不同是指对环节乘以环节成本值而搜索到的路径是绕过拥堵道口的路径，所需时间比经由拥堵道口的路径更短的路径。

然后，根据各个时间阻断交通的台数即交通阻断量，变更拥堵道口的显示形式(步骤S406)。显示形式的变更将在后面详细介绍，例如，是指使拥堵道口以红色闪烁。然后，确定绕过拥堵道口的绕弯道口(步骤S407)。绕弯道口的确定例如是指，沿着与该拥堵道口相同的线路而存在的其他道口，也可以将不是拥堵道口的道口作为绕弯道口。然后，根据拥堵道口的拥挤程度，例如变更使绕弯道口以蓝色闪烁等绕弯道口的显示形式(步骤S408)。

然后，生成显示出是绕过了拥堵道口的路径的图像(步骤S409)。此时的图像例如是指后述的“绕过了拥堵的道口”等的文字图像。然后，显示变更了显示形式的拥堵道口、绕弯道口、经由绕弯道口的路径(步骤S410)，结束一连串的处理。另一方面，在步骤S404中，当不对包含有道口的环节乘以环节成本值而搜索到的路径、和对包含有道口的环节乘以环节成本值而搜索到的路径这两条路径没有不同时(步骤S404：否)，即，判断为环节上没有拥堵道口时，结束一连串的处理。

在上述的说明中，在步骤S404中，当两条路径不同时，即，存在绕过拥堵道口的路径时，自动地选择绕弯的路径，但也可以接收来自利用者的选择。具体而言，也可以显示“绕过拥堵的道口吗？”等，当从利用者接收到“是”的输入时，显示经由绕弯道口的路径，当接收到“否”的输入时，显示经由拥堵道口的路径。

此外，在本实施例中，当绕过拥堵道口时，不仅可以是绕弯道口，也可以是相对于线路进行立体交叉的立体交叉道路。当是选择了立体交叉道路的路径时，例如，变更使立体交叉道路的显示以蓝色闪烁等的显示形式即可。此外，在步骤S409中生成文字图像，但是，与此同时，例如也可以用虚线来显示经由拥堵道口的路径。

此外，当拥堵道口的邻近道口全部拥挤时，即，当无法确定绕弯道口时，是经由拥堵道口的路径。此时，显示通过拥堵道口的路径的情况，并且，例如使地图显示的道口全部以红色闪烁即可。

(导航装置300的路径搜索处理的另一个例子)

接着，利用图5说明本实施例的导航装置300进行的路径搜索处理的另一个例子。图5是示出本实施例的导航装置的路径搜索处理的另一个例子的流程图。图5所示的流程图是如下的处理：搜索在当前时刻出发时的路径和在经过预定时间后的时刻出发时的路径。

在图5的流程图中，导航装置300处于待机状态，直到接收到路径搜索开始的指示为止(步骤S501：否的环路)，如果接收到路径搜索开始的指示(步骤S501：是)，则例如在时间优先的搜索条件下，不对包含有道口的环节乘以环节成本值而进行路径搜索(步骤S502)。在计算所需时间时，当在路径中包含有拥堵道口时，加上与环节成本值对应的预定时间来进行计算即可。然后，对包含有道口的环节乘以在当前时刻出发时的环节成本值来进行路径搜索(步骤S503)。另外，在当前时刻出发时的环节成本值是指在当前时刻出发到达道口时的时间段内的环节成本值。

然后，判断上述两条路径是否不同(步骤S504)。在步骤S504中，当判断为两条路径不同时(步骤S504：是)，乘以在经过预定时间之后的时刻出发时的环节成本值来进行环节搜索(步骤S505)。另外，在经过预定时间之后的时刻出发时的环节成本值，是指在经过预定时间之后的时刻出发到达道口时的时间段内的环节成本值。然后，显示乘以环节成本值后的各个出发时刻的路径和所需时间(步骤S506)，结束一连串的处理。

另一方面，在步骤S504中，当不对包含有道口的环节乘以环节成本值而搜索到的路径、和对包含有道口的环节乘以环节成本值而搜索到的路径这两条路径没有不同时(步骤S504：否)，即，判断为环节上没有拥堵道口时，结束一连串的处理。

在上述的路径搜索处理中，关于各个出发时刻的路径搜索，列举具体的时间段进行补充。例如，设当前时刻为上午8点。设在上午8点出发时到达目的地的预定到达时刻为9点30分。此外，当在经过1小时之后的时刻、即上午9点出发时，由于过了高峰时间，道口的拥堵得到缓解，所以设到达目的地的预定到达时刻为9点50分。在这种情况下，通过显示各个出发时刻的路径和所需时间，利用者能够选择最合适的出发时刻。此外，在这样的路径搜索处理中，通过利用者指定到达目的地的到达时刻，还能够进行逆算出可最迟出发的时间的路径搜索。

另外，在上述的路径搜索处理中，关于各个出发时刻的路径上的道口，对拥堵道口或绕弯道口进行记号显示即可。此外，关于各个出发时刻的路径，也可以显示绕过了拥堵道口的路径的情况。

(路径搜索时使用的环节成本的计算处理的一例)

接着，利用图6-1来说明在本实施例中，路径搜索时使用的环节成本的计算处理的一例。图6-1是示出在本实施例中路径搜索时使用的环节成本的计算处理的一例的流程图。

在图6-1的流程图中，导航装置300根据环节的长度、宽度、车道数量、信号机的数量等计算环节成本(步骤S601)。然后，取得环节的道口属性(步骤S602)。然后，判断所取得的道口属性中是否存在拥堵道口的道口属性(步骤S603)。另外，关于拥堵道口的道口属性的赋予方法将在后面叙述。在步骤S603中，当判断为所取得的道口属性中存在拥堵道口的道口属性时(步骤S603：是)，判断到达环节的时刻是否在拥堵道口的时刻内(步骤S604)。

在步骤S604中，当判断为到达环节的时刻在拥堵道口的时刻内时(步骤S604：是)，将环节成本增加α(步骤S605)，结束一连串的处理。另外，α是按照每个拥堵道口设定的加权值。另一方面，在步骤S603中，当判断为所取得的道口属性中不存在拥堵道口的道口属性时(步骤S603：否)，结束一连串的处理。此外，在步骤S604中，当判断为到达环节的时刻不在拥堵道口的时刻内时(步骤S604：否)，结束一连串的处理。另外，步骤S603和步骤S604的处理顺序是任意的，也可以先进行步骤S604的处理。

(本实施例的导航装置的路径搜索处理的另一个例子)

接着，利用图6-2来说明本实施例的导航装置的路径搜索处理的另一个例子。图6-2是示出本实施例的导航装置的路径搜索处理的另一个例子的流程图。

在图6-2的流程图中，导航装置300处于待机状态，直到接收到路径搜索开始的指示为止(步骤S611：否)，如果接收到路径搜索开始的输入(步骤S611：是)，则提取地图数据上的道口(步骤S612)。然后，取得所提取的各道口的平均等待时间(步骤S613)。另外，对于平均等待时间，预先按照时间进行存储即可。此外，具体的平均等待时间的计算方法将在后面叙述。

然后，计算相当于平均等待时间的环节成本α(步骤S614)。然后，对包含道口的环节乘以预定的环节成本α，搜索至目的地的路径(步骤S615)，结束一连串的处理。具体而言，例如，如果是平均等待时间为10分钟的道口，则乘以相当于10分钟的环节成本，如果是非拥堵道口的平均等待时间为10秒的道口，则乘以相当于10秒的环节成本即可。此外，在这样的处理中，当进行在经过预定时间之后的时刻出发时的路经搜索时，利用预先存储的经过预定时间之后的平均等待时间或交通阻断量，进行路径搜索即可。

(道口属性的赋予处理的一例)

接着，利用图7，说明本实施例中道口属性的赋予处理的一例。图7是示出在本实施例中道口属性的赋予处理的一例的流程图。

在图7的流程图中，导航装置300取得在某个道口中，每一定时间阻断交通的台数(交通阻断量N)(步骤S701)。交通阻断量N的具体情况将在后面叙述。然后，判断是否存在所取得的交通阻断量N超过预定值β的时间段(步骤S702)。预定值β是按照每个道口设定的阈值。此外，此时的时间段是指通过时间长的时间段，例如，高峰时的上午7点～9点等的时间段。

在步骤S702中，当判断为存在交通阻断量N超过预定值β的时间段时(步骤S702：是)，对包含该道口的环节赋予拥堵道口的道口属性(步骤S703)。然后，存储交通阻断量N超过预定值β的时间段(步骤S704)，结束一连串的处理。此外，在步骤S702中，当判断为不存在交通阻断量N超过预定值β的时间段时(步骤S702：否)，结束一连串的处理。这里，在步骤S704中，对N超过β的时间段进行存储，但是并非一定要存储时间段，只要至少生成表示该道口是否是拥堵道口的信息作为属性信息即可。这样，通过赋予拥堵道口的属性信息，并预先存储交通阻断量N超过预定值β的时间段，能够在显示画面上显示道口附近的拥堵信息。

(没有正在等待道口的车辆时的车辆的平均等待时间的一例)

接着，利用图8和图9，说明计算交通阻断量的一例。首先，利用图8说明没有正在等待道口的车辆时的车辆的平均等待时间。图8是示出在本实施例中，没有正在等待道口的车辆时的车辆的平均等待时间的一例的曲线图。

在图8中，曲线图800的横轴801表示道口开放之后的经过时间(秒)，纵轴802表示车辆的等待时间(秒)。图8所示的曲线图的道口是关闭60秒钟、开放60秒钟的道口。即，在图8中，横轴801为0～60秒的期间道口开放，横轴801为60～120秒的期间道口关闭。例如，在道口开放后0～60秒的期间，到达该道口的车辆(图8中的A点)的等待时间为0，表示无需等待时间就能够通行。

另一方面，如果横轴801为60秒，则本次道口关闭。因此，在道口开放后60秒的时候，表示到达该道口的车辆(图8中的B点)等待60秒钟。此外，例如当横轴801为90秒时，表示到达该道口的车辆(图8中的C点)等待30秒钟。然后，当横轴801为120秒时，表示到达该道口的车辆(图8中的D点)无需等待时间就能够通行。

根据该曲线图800，计算该道口的车辆的平均等待时间。首先，计算120秒钟的等待时间的累计。120秒钟的车辆的等待时间的累计是由直线811和直线812和横轴801围成的三角形的面积820。即，面积820为(120-60)×60÷2＝1800。接着，计算每120秒的车辆的平均等待时间。车辆的平均等待时间是将面积820除以120秒而得到的值(1800÷120)＝15秒。因此，这样的没有道口等待的道口的平均等待时间是每120秒为15秒的等待时间。

(计算交通阻断量的一例)

接着，利用图9说明计算交通阻断量的一例。图9是示出在本实施例中，当存在正在道口等待的车辆时计算交通阻断量的一例的曲线图。利用图9所示的曲线图，说明当车辆到达道口时，存在正在道口等待的车辆的情况。

在图9中，曲线图900的横轴901表示道口开放之后的经过时间(秒)，纵轴902表示车辆的等待时间。图9所示的曲线图900与图8所示的曲线图800同样，是关闭60秒钟、开放60秒钟的道口。假设在该道口中道路的交通量为6台/60秒。因此，在道口关闭60秒钟的期间，有6台车辆在道口等待。此外，在该道口中，设当道口开放时车辆能够通行的交通量(相当于车辆转出量)为12台/60秒。

在图9中，当横轴901为0秒时，即，道口开放时，到达该道口的车辆(图9中的E点)的等待时间为30秒。这意味着等待正在道口等待的6台车辆通过。具体说明是，由于道口开放时车辆能够通行的交通量(车辆转出量)为12台/60秒，因此，每一台通过所需时间是车辆转出量的倒数，即5秒/台。因此，意味着6台车辆通过需要将5秒/1台设为6台(6倍)而得到的30秒。

此外，例如当横轴901为30秒时，即，当从道口开放经过30秒之后，到达该道口的车辆(图9中的F点)的等待时间为15秒。对此进行说明。由于每一台通过所需时间为5秒/1台，因此，从道口开放经过30秒期间的车辆转出台数根据30秒÷(5秒/1台)为6台。另一方面，道路的交通量为6台/60秒，一台间隔的时间是交通量的倒数，即10秒/1台。

因此，从道口开放经过30秒期间到达道口的车辆根据30秒÷(10秒/1台)为3台。即，道口开放经过30秒后到达的车辆将要等待3台道口开放后到达的车辆的通过。因此，3台车辆通过需要使每一台通过所需时间即5秒/1台为3台而得到的15秒。同样，在横轴901经过60秒时，到达该道口的车辆(图9中的G点)的等待时间为0。

另一方面，在经过60秒时，到达该道口的车辆(图9中的H点)是道口等待的起始，其等待时间为60秒。同样，例如经过90秒后到达该道口的车辆(图9中的I点)的等待时间为45秒。所述等待时间是将道口开放之前剩余的时间30秒与道口关闭后到达的3台车辆通过所需的时间15秒相加而得到的值，在此省略计算的详细描述。

根据该曲线图900，计算该道口的车辆的平均等待时间。首先，计算120秒钟的等待时间的累计。120秒钟的车辆的等待时间的累计是由横轴901和纵轴902和直线911围成的三角形的面积920加上由横轴901、直线912、直线913和波浪线914围成的梯形的面积921而得到的总面积。具体而言，面积920为60×30÷2＝900。此外，面积921是(30+60)×(120-60)÷2＝2700。因此，总面积为面积920加上面积921而得到的3600。

接着，计算每120秒的车辆的平均等待时间。车辆的平均等待时间是将总面积除以120秒而得到的值(3600÷120)即30秒。因此，这样的道口平均等待时间是30秒/120秒的等待时间。接着，计算交通阻断量。交通阻断量是每预定时间无法通行的车辆的台数，是将平均等待时间除以每一台通过所需时间而得到的。在该道口中，每一台通过所需时间是5秒/1台。因此，交通阻断量根据(30秒/120秒)÷(5秒/1台)为6台/120秒。即，该道口的交通阻断量为每120秒6台。另外，例如如果将该交通阻断量换算为每1小时，则为180台。

如使用图7说明的那样，这样计算出的交通阻断量用于与作为在不同道口按照时间段设定的阈值的预定交通量(预定值β)进行比较，当大于等于预定值β时，将该道口确定为拥堵道口。

(道口显示的一例)

接着，利用图10，说明本实施例的道口显示的一例。图10是示出本实施例的道口显示的一例的说明图。

在图10中，显示在显示器312上的显示画面1000是北面向上(northup)显示，将显示画面1000的上方设定为北方进行显示。显示画面1000显示有线路1010、道路1020、道口1030(1030a～1030c)、立体交叉道路1031、当前位置1040、目的地1050、文字显示1060。各道口1030被记号显示。道口1030a、1030b是拥堵道口。此外，道口1030c是绕弯道口。立体交叉道口1031被记号显示。立体交叉道路1031是相对于线路立体交叉的道路。

如后所述，道口1030基于交通阻断量，根据拥堵的长度或该道口1030的等待时间等，变更显示形式。在本实施例中，例如，东侧的拥堵道口1030a和西侧的拥堵道口1030b离车站1032较近，阻断器下降的时间最长，因此道路拥挤，标记的外周显示红色。另外，后面将详细叙述道口记号外周的颜色。此外，绕弯道口1030c不拥挤，道口记号的外周显示蓝色。此外，立体交叉道路1031的道口记号的外周显示黄色。

当显示有这样的显示画面1000时，假设利用者位于当前位置1040，进行至目的地1050的路径搜索。在通常的路径搜索中，例如寻找探索最短路径的路径，即，寻找经由东侧的拥堵道口1030a或西侧的拥堵道口1030b的路径，但是，在本实施例中，搜索经由道口1030c的路径或经由立体交叉道路1031的路径。然后，在文字显示1060中显示“绕过了拥堵的道口”的文字图像。

(道口记号的显示形式的一例)

接着，利用图11说明本实施例的道口记号的显示形式的一例。图11是示出本实施例的道口记号的显示形式的一例的说明图。

在图11中，道口记号1100是显示在图10所示的道口1030中的记号。在图11中，道口记号1100由表示电车的标记1110和外周1120构成。外周1120根据交通阻断量来改变颜色。例如，当通过道口所需时间非常长时，具体而言，当通过该道口需要30分钟以上的时间时亮红灯。此外，当通过该道口需要例如10分钟以上30分钟以下的时间时亮黄灯。此外，当通过该道口需要的时间例如在10分钟以下时，即，没有拥挤时亮蓝灯。另外，外周1120的亮灯不限于采用上述的3种颜色以3个阶段来显示拥堵的方式，也可以任意地设定。

(立体交叉记号的显示形式的一例)

接着，利用图12说明本实施例的立体交叉记号的显示形式的一例。图12是示出本实施例的立体交叉记号的显示形式的一例的说明图。

在图12中，立体交叉记号1200是显示在图10所示的立体交叉道路1031上的记号。在图12中，立体交叉记号1200由表示立体交叉道路的标记1210和外周1220构成。立体交叉记号1200可以始终显示，也可以仅在附近存在拥堵道口的情况下显示。此外，在附近存在拥堵道口的情况下，也可以改变外周1220的颜色而引人注目。例如，在附近存在拥堵道口的情况下，通过使外周1220亮蓝灯，能够督促利用者通行该立体交叉道路。

如以上说明的那样，本实施例的导航装置300基于道口中每个时间段阻断交通的台数(交通阻断量)来确定拥堵道口，并且对包含该拥堵道口的环节乘以预定的环节成本值，进行路径搜索。根据这样的导航装置300，能够进行与各道口的交通量对应的路径搜索。因此，利用者能够探索回避了通过时间长的拥堵道口的路线。此外，如果大多数的车辆回避了拥堵道口，则能够使拥堵得到缓解。

此外，本实施例的导航装置300基于每预定时间的交通量和道口的车辆转出量计算交通阻断量。即，基于交通量和车辆转出量，计算各道口的交通阻断量。根据这样的结构，能够简单且正确地计算交通阻断量。

此外，除了拥堵道口以外，本实施例的导航装置300还确定绕弯道口或立体交叉道路，并根据已设定的搜索条件，从通过拥堵道口、绕弯道口、或立体交叉道路的路径中，选择最合适的路径。根据这种结构，能够进行与时间优先、距离优先等检索条件对应的路径搜索。

此外，本实施例的导航装置300在搜索经由绕弯道口或立体交叉道路的至目的地的路径时通知绕过了拥堵道口的情况。根据这样的结构，利用者能够了解所显示的路径不是绕远的路径而是绕过了拥堵道口的路径，并且，能够了解缩短了至目的地的所需时间的情况。

此外，本实施例的导航装置300还可以取得在当前时刻出发时的拥堵道口的交通阻断量和在经过预定时间后的时刻出发时的拥堵道口的交通阻断量，并基于在当前时刻出发时的拥堵道口的交通阻断量和在经过预定时间后的时刻出发时的拥堵道口的交通阻断量，搜索各个出发时刻的路径。根据这样的结构，利用者能够了解在推迟了出发时间时的到达时刻和所需时间，因此在时间有富裕的情况下，能够稳定地推迟出发时刻。

此外，本实施方式的路径搜索装置300将拥堵道口的显示控制成与通常的显示不同的显示。根据这样的结构，利用者能够在显示画面上确认通过时间长的道口。

此外，本实施方式的路径搜索装置300对拥堵道口进行记号显示，并且，根据交通阻断量使记号显示的拥堵道口的显示形式变化。根据这样的结构，利用者能够看一眼就掌握拥堵道口，还能够看一眼就掌握拥挤的程度。

此外，使本实施方式的路径搜索装置300对绕弯道口或立体交叉道路进行记号显示。根据这样的结构，利用者能够看一眼就掌握绕弯道口或立体交叉道路，能够简单地找到该绕弯道口或立体交叉道路。

如以上说明的那样，本发明的路径搜索装置、路径搜索方法、路径搜索程序和记录介质根据道口中每个时间段的阻断交通的台数(交通阻断量)，确定拥堵道口，并且对包含该拥堵道口的环节乘以预定的环节成本值进行路径搜索。即，能够进行与各道口的交通量对应的路径搜索。因此，利用者能够探索回避了通过时间长的拥堵道口的路线。此外，如果大多数的车辆回避了拥堵道口，则能够使拥堵得到缓解。

另外，本实施例中说明的路径搜索方法可以通过由个人计算机或工作站等计算机执行预先准备的程序来实现。该程序记录在硬盘、软盘、CD-ROM、MO、DVD等计算机能够读取的记录介质中，通过计算机从记录介质中读出而执行该程序。此外，该程序也可以是能够经由互联网等网络而分发的传输介质。