路径搜索方法

摘要

本发明具有：计算机从地图数据中提取在包含出发地和目的地的地图区域中包含的节点和链路的步骤；针对这些链路计算与能量消耗或能量再生相关的链路成本的步骤；针对提取出的各个节点和链路，分别生成多个副本，生成第1网络的步骤；对第1网络追加第1以及第2追加链路，生成第2网络的步骤；使用第2网络搜索从与出发地对应的节点的副本到与目的地对应的节点的副本的路径的步骤。第1追加链路是设定有预定的非负的链路成本，将链路的副本的终点的节点变更为该链路的其它副本的终点的节点的链路。第2追加链路设定有预定的非负的链路成本，将与目的地对应的节点的副本之间连接。

主权项

一种路径搜索方法，其特征在于，具有：提取步骤，计算机从包含与节点相关的节点数据以及与链路相关的链路数据的地图数据中，提取在包含出发地和目的地的地图区域中包含的节点和链路；链路成本计算步骤，所述计算机针对通过所述提取步骤提取出的链路，计算与能量消耗相关的非负的链路成本或者与能量再生相关的非正的链路成本；第1网络生成步骤，所述计算机针对通过所述提取步骤提取出的各个节点和链路，分别生成多个副本，来生成第1道路网络；第2网络生成步骤，所述计算机对所述第1道路网络追加第1追加链路和第2追加链路，来生成第2道路网络；以及路径搜索步骤，所述计算机使用通过所述链路成本计算步骤计算出的链路成本和通过所述第2网络生成步骤生成的所述第2道路网络，搜索从与所述出发地对应的节点的副本到与所述目的地对应的节点的副本的路径，所述第1追加链路，作为设定有预定的非负的链路成本的链路，是将通过所述第1网络生成步骤生成的链路的副本的终点的节点变更为该链路的其它副本的终点的节点的链路，所述第2追加链路，作为设定有预定的非负的链路成本的链路，是将与所述目的地对应的节点的副本之间分别连接的链路。