路线选择系统、路线选择方法和路线选择程序

摘要

提供一种用于用合理计算量获得多对到路线搜索过程的技术。在使用指示出发点和目的地点的信息作为请求时，公式表达为混合整数规划(MIP)问题，其中目标函数是“使通过将用于所有请求的实际所需时间除以最短所需时间而获得的所有值中的最大值最小”。通过在从初始状态逐渐和反复添加有希望路线的过程中，求解MIP问题来阻止候选路线数目的激增。也通过使用在迭代结束时的实际路线来搜寻新路线，优先搜寻具有高效用值的路线作为备选路线。这时去除具有比当前最佳解更大的最小成本的任何路线和在先前迭代中添加的任何未用路线作为无希望路线。通过在更新路线候选时保持在先前迭代期间使用的路线，先前迭代的解可以用作MIP问题中的初始值，并且减少计算时间。

说明书

技术领域

本发明涉及一种用于选择路线、比如交通路线的系统、方法和 程序。

背景技术

汽车导航系统具有搜寻和显示交通路线的功能。在这一过程中 的算法例如将十字路口视为节点而路段视为边，并且在其中对路线 长度加权的加权图中搜寻最短路线。

然而这时大量汽车具有用来同时搜寻路线的汽车导航系统，并 且每个汽车独立确定最短路线。在这引起用于多个汽车的交通路线 重叠时，特定路线或者边的使用频率增加，并且拥堵出现于这些路 线中的一些路线中。这时如图1中所示，认为用于每个路线的时间 随着交通量增加而迅速增加。

在汽车中引用车辆信息和通信系统(VICS)提供的交通信息， 使得汽车导航系统可以计算备选路线。然而在大量车辆引用相同交 通信息时，最终选择相似备选路线，并且这引起如图2中所示进一 步拥堵。

因此需要中心服务器考虑由于车辆集中而出现拥堵，并且如图 3中所示执行多对多路线安排以缓解拥堵。换而言之，如果可以相互 避免拥堵，则存在减少所需时间的可能性。然而在多对多路线安排 中执行的计算通常经历困难，并且难以在合理数量的时间内提出求 解。

在公开号为2001-331564的待审日本专利中公开一种用于通过 使用针对每个计划的必需精确度和计算时间而优化的手段来计算用 于运输计划中的每个运输手段的路线，来实现有效计划的系统。至 少具有输入/输出设备、处理器和存储设备并且创建分布计划的这一 系统包括：基本信息注册步骤，用于输入用于基地、比如工厂、中 继基地和供应商的位置信息；运输服务信息注册步骤，用于输入包 括每个运输服务拜访的基地和负荷数量的运输递送信息；条件注册 步骤，用于输入包括运输计划的必需准确度和限制时间的目标信息； 算法选择步骤，用于选择用于路线预备的算法；路线预备步骤，用 于根据这一信息预备用于递送服务的路线；以及输出步骤，用于输 出结果。

公开号为2004-12312的待审专利公开一种路线搜索设备，该 设备包括：第一搜索装置，用于搜寻最小成本路线，沿着该最小成 本路线的伴随路线的参数在从起点到目的地的伴随路线的参数之中 变成最小；加权装置，用于对构成第一最短路线的每个路段的参数 进行加权；以及区域限制装置，用于基于第一搜索装置的计算的数 据发现具体地图区域作为限制区域。这一设备还包括：第二搜索装 置，用于通过将借助区域限制装置发现的限制区域视为待搜索对象 仅在该区域中搜寻路线。通过利用在先前搜索期间获得的信息限制 搜索范围来缩短随后搜索所需要的时间。

公开号为2009-19932的待审专利公开一种用于为从移动起点 到达移动终点的自治移动体搜寻移动路线的路线搜索系统，该系统 包括：区域划分部分，用于将移动区域划分成多个区域；与区域划 分部分划分的多个区域对应的多个评估值计算部分，用于计算每个 区域的评估值；以及路线确定部分，用于基于评估值计算部分计算 的评估值来确定路线。评估值计算部分具有：评估值处理部分，用 于基于附近存在的区域的评估值和从附近区域到它自己的区域的移 动成本来计算评估值。第0073段声明“被指示为移动起点和移动终 点的区域数目无论它是多对一、一对多或者多对多都可以适用于本 发明。”

然而即使简单求解也需要大量计算，现有技术文献均未公开一 种用于以合理计算量获得多对多路线搜索处理的技术。

引用列表

专利文献

专利文献1公开号为2001-331564的待审专利公开

专利文献2公开号为2004-12312的待审专利公开

专利文献3公开号为2009-19932的待审专利公开

发明内容

技术问题

因此，本发明的一个目的是提供一种用于以合理计算量获得多 对多路线搜索过程的技术。

本发明的另一目的是提供一种用于以合理计算量并且在考虑 由于多个车辆的通过所致的拥堵水平的同时获得路线搜索过程的技 术。

对问题的解决方案

在本发明中，通过将交通路线描述为图并且使用单调增加逐段 线性函数逼近每边的所需时间来对由于交通量增加所致的拥堵出现 进行建模。这一模型逼近图1中所示在拥堵水平与所需时间之间的 关系曲线。

在汽车导航系统请求指示出发点和目的地点的信息时，可以公 平对待所有车辆，并且可以使用其中“使通过将用于所有请求的实际 所需时间除以最短所需时间而获得的所有值中的最大值最小”的目 标函数来实现完全合理路线安排。可以描述本发明的这一发现为混 合整数规划(MIP)问题并且使用预定求解器来求解该问题。

然而MIP描述需要对所有可能路线的显式枚举，并且候选路 线数目可能根据图的大小呈指数。这意味着这一问题是NP难度问题 并且难以在现实中求解。

在本发明的一个特征中，候选路线数目可以呈指数，但是通过 在从初始状态逐渐和反复添加有希望路线的同时求解MIP问题来抑 制候选路线数目的激增。

在本发明的另一特征中，通过使用在迭代结束时的实际路线来 搜寻新路线，优选地搜寻具有高效用值的路线作为备选路线。这时， 具有比当前最佳解更大的最小成本的任何路线和在先前迭代中添加 的任何未用路线被作为无希望路线而去除。

在本发明的另一特征中，获得从出发点到目的地点的多个路线 以及连同它们的利用率一起作为MIP计算的结果。这些结果可以用 来优化路线以便缓解拥堵。

在本发明的又一特征中，通过在更新路线候选时保持在先前迭 代期间使用的路线，先前迭代的解可以用作MIP问题中的初始值， 并且可以大量减少计算时间。

本发明的效果

在本发明中，可以通过使用混合整数规划问题并且通过去除无 希望路线并且保持在先前迭代中使用的路线以便从有希望值开始迭 代计算，来以合理计算量计算多对多路线。

在本发明中，可以获得通过使用单调增加逐段线性函数逼近每 边的所需时间使用合理计算量，来获得缓解拥堵的所需路线安排。

附图说明

图1是示出在交通量与所需时间之间的关系的图。

图2是示出车辆如何使用拥堵信息来避免某一路线的图。

图3是示出如何以适当方式将车辆引向一路线的图。

图4是用来实现本发明的硬件配置的例子的框图。

图5是用来实现本发明的功能配置的例子的框图。

图6是示出如何使用单调增加逐段线性函数来逼近的图。

图7是示出本发明的路线选择过程的流程图的图。

图8是示出本发明的路线选择过程的流程图的图。

图9是示出本发明的处理的输出例子的图。

具体实施方式

下文参照附图说明本发明的例子。除了另有指示之外，所有附 图中相同标号用来表示相同对象。下文说明本发明的实施例，并且 本发明决不旨在于限于在例子中说明的内容。

图4是用来实现本发明的例子中的系统配置和处理的计算机 硬件的框图。在图1中，CPU404、主存储器(RAM)406、硬盘驱 动(HDD)408、键盘410、鼠标412和显示器414连接到系统总线 402。CPU404优选地基于32位或者64位架构并且可以是来自Inter Corporation的4、2Duo或者或者来自Advanced Micro Devices Inc.的主存储器406优选地具有4GB或者更 多的容量。硬盘驱动408优选地具有500GB或者更多的容量以便存 储大量数据。

这样的硬件配置的优选例子是System X系列。然而本发 明不限于此。它甚至可以实现于个人计算机中。

尽管在任何附图中未示出，但是硬盘驱动408包括预装操作系 统。操作系统可以是与CPU404兼容的任何操作系统。例子包括 来自Microsoft Corporation的WindowsWindows和Windows2008

硬盘驱动408存储下文描述的主例程502、交通路线图数据 504、请求数据506、求解器508、路线搜索模块510和路线更新模 决512。

用现有编程语言、比如C、C++、C#或者Java^TM创建主例程 502、求解器508、路线搜索模块510和路线更新模块512并且如果 必要则在系统启动时并且通过操作系统的作用向存储器406中加载 主例程502、求解器508、路线搜索模块510和路线更新模块512。

显示器414优选地是液晶显示器。可以使用包括XGA(分辨 率：1024×768)或者UXGA(分辨率：1600×1200)的任何分辨率。 尽管在附图中未示出，但是显示器414用来显示用于开始和停止本 发明的处理程序以及用于显示交通路线数据的操作屏幕。

下文参照图5的功能框图说明用来实现本发明的逻辑功能结 构。在图5中，主例程502是管理整个过程、在显示器414上显示 操作屏幕(未示出)并且响应于使用键盘410和鼠标412而录入的 用户操作来开始和停止过程的程序。

交通图数据504是加权图数据，在该加权图数据中以图的形式 描述路线而将道路表达为边并且将十字路口表达为节点，并且在该 加权图数据中通过单调增加逐段线性函数逼近每条道路的权值以对 由于交通量增加所致的拥堵出现建模。通常表达图为矩阵或者列表 以使它计算机可读和可存储于介质、比如硬盘中。然而图可以采用 能够实现本发明的目的的任何形式。

图6是示出边和所需时间的逐段线性的图。这里x是用每小时 通过的车辆数目表达的交通量。这是图1中所示图的逐段线性逼近。 如附图中所示，使用的逐段线性函数是所需时间t＝a₁x+b₁，其中 0≤x＜x₁、所需时间t＝a₂x+b₂，其中x₁≤x＜x₂和所需时间 t＝a₃x+b₃，其中x₂≤x，其中a_i＞0(i＝1，2，3)。这里仅示出三 段，但是这仅为一个实施例。如果必要，则可以使用任何数目和宽 度的段。逐段线性函数不限于此。例如可以实施它为由每个边指示 的并且引用存储器中的表的线性函数。换而言之，准备一个表使得 响应于用于交通量的值≤x₁而返回{a₁，b₁}并且响应于用于交通量的 值x₁≤x＜x₂而返回{a₂，b₂}。

根据道路的实际条件确定用于执行每边的逐段线性逼近的系 数组、比如{a₁，b₁}、{a₂，b₂}。换而言之，优选地与边的实际长度 成比例地确定系数、比如{a_i，b_i}(i＝1，2，3等)。然而对于上坡 道路使{a_i，b_i}更大，并且对于下坡道路使{a_i，b_i}更小。还对于具有 大弯曲的道路使{a_i，b_i}更大，对于具有许多车道的道路使{a_i，b_i}更 小，并且对于窄道路使{a_i，b_i}更大。此外，对于具有良好人行道的 道路使{a_i，b_i}更小，并且对于无人行道的道路使{a_i，b_i}更大。

在优选例子中，用于每边的所需时间是t＝max_i{a_ix+b_i}。这 里a_i＞0。

提供请求数据506为集合{出发点，目的地点，需求水平}。可 以例如使用探测汽车数据来收集这一请求数据。使用探测汽车数据 的交通数据收集技术在本领域中是公知的。例如参见公开号为 2004-110458的待审专利公开、公开号为2004-156982的待审专利公 开、公开号为2007-193705的待审专利公开和公开号为2004-241987 的待审专利公开。由于在每对{出发点，目的地点}之间行进的车辆 数目在给定的时间段内已知，所以这些技术可以用来预备请求数据 506，使得车辆数目被设置为需求水平，按照需求水平降序对集合{出 发点，目的地点，需求水平}排序，并且向硬盘驱动408从最高保存 预定数目的对。

求解器508使用通过将用于所有请求的实际所需时间除以最 短所需时间而获得的所有值的最小化的最大值作为目标函数，并且 求解混合整数规划(MIP)问题从而向每个请求提供多个路线及其利 用率(实数)作为输出。不存在关于求解器的限制，但是优选例子 是ILOG CPLEX。下文更具体说明MIP公式表达。

路线搜索模块510使用任何公知算法、比如Dijkstra算法或者 A*搜索技术来执行加权图路线搜索。算法也可以是在公开号为 2008-157698的待审专利公开中描述的修正的A*搜索技术。

路线更新模块512任意消除路线，以便减少计算量或者添加有 用路线。下文参照图8中的流程图更具体说明路线更新模块512执 行的过程。

下文参照图7和图8说明本发明的路线选择过程。

在图7的步骤702中，主例程502调用路线搜索模块510，并 且针对请求数据506中的{出发点，目的地点}对搜寻从出发点到目 的地点的最低成本路线或者最短路线，其中x＝0置于用于t＝max_i{a_ix+b_i}的公式中。

在步骤704中，主例程502调用求解器508，并且用当前时间 的候选路线求解混合整数规划(MIP)问题。在由步骤704、步骤706 和步骤708构成的循环中，可以通过使用先前解作为第二和后续迭 代中的初始值来减少计算时间。

下文说明MIP公式表达。公式表达旨在于使用其中使通过将 用于所有请求的实际所需时间除以最短所需时间而获得的所有值中 的最大值最小化的目标函数。这表达为图G＝(V，E)，其中V是 交通图数据504中的节点集合并且E是边集合。参考图6中的逐段 线性逼近，用于沿着边e∈E移动的行进时间由以下等式表达，其 中交通量为x：

t_e(X)＝max_i(a_eix+b_ei)

这里a_ei＞0。

请求i(i＝1，...，k)具有以下属性。

出发点的节点：s_i∈V

目的地点的节点：g_i∈V

需求水平：d_i∈R，d_i＞0

也令P_i*为未包括从节点s_i到节点g_i的路线的所有路线的集合。 然后表达为p∈P_i*为连接边的排列。

p＝(e_l，e₂，...，e_|p|)

这里|p|是连接到p的边数。

因此令T_i*为在交通量x为0时从节点s_i到节点g_i的最小所需 时间。换而言之，T_i*由以下等式表达。

等式1

$T_i^{*}=\underset{p\in P_i^{*}}{\min }\underset{e\in p}{\Sigma }{t}_e\left(0\right)$

这时令每边的成本e∈E为t_e(0)，并且可以例如通过调用路线 搜索模块510并且执行最短路线搜索算法来确定T_i*，即使未显式枚 举P_i*的所有元素。

也向用于请求i的候选路线集合P_i*的元素给予序号，并且P_i* 的第j个路线(j＝1，...，|P_i*|)由p_ij表达。此外，L是充分大的正 常数，并且y_ij是取值0或者1的整数变量，0或者1表达是否使用 用于请求i的候选路线j。这些定义用来以如下方式公式表达混合整 数规划问题。

等式2

min λ

s.t.

$x_e=\underset{(i,j)=\{i,j|e\in p_{\mathrm{ij}}\}}{\Sigma }{x}_{\mathrm{ij}}$for e∈E

$\underset{j}{\Sigma }{x}_{\mathrm{ij}}=d_i$for i＝1，...，k

x_ij≤d_iy_ij

x_ij≥0，x_ij∈R

y_ij∈{0，1}

其中在s.t.(使得)以下的表达式代表约束。

因此，混合整数规划问题的求解所产生的x_ij表达了请求i中的 第j个路线的交通量。换而言之，x_ij/d_i是请求i中的第j个路线的利 用率。在图9中表达这一利用率为与从出发点1到目的地点1的多 个路线中的每个路线关联的百分比。

接着在步骤706中，主例程502确定是否已经满足终止条件。 例如在计算时间超过预先设置的时间或者迭代数目已经超过预定数 目时已经满足终止条件。

在主例程502已经确定已经满足终止条件时，过程被终止。这 时，获得从每个请求的出发点到目的地点的多个路线并且获得每个 路线的利用率。

在主例程502在步骤706中确定尚未满足终止条件时，过程继 续步骤708，其中主例程502调用路线更新模块512并且更新候选路 线。通过删除未用路线和无希望路线并且添加有希望路线，来更新 候选路线。下文参照图8中的流程图更具体说明这一过程。

在已经在步骤708中更新候选路线之后，求解器508再次在步 骤704中基于更新的候选路线求解MIP。

下文参照图8中的流程图说明在路线更新模块512中执行的处 理。换而言之，在步骤802中，路线更新模块512消除每个请求中 的以下路线作为无希望路线。

·其最低成本等于或者大于当前最佳解的成本的那些路线。这 里最低成本是在交通量x＝0时的成本。

·在先前迭代中添加、但是未用的那些路线。用于变量y_ij的值 0在步骤704中在求解器508的计算结果中确定未用路线。

通过消除这些路线来抑制候选路线数目的激增。

在步骤804中，路线更新模块512设置其“实际所需时间/最短 所需时间”最大并且用于所有候选的“实际所需时间”相同的那些请求 为瓶颈请求并且设置在候选路线中包括的那些边为瓶颈边。换而言 之，路线更新模块512在每个迭代的结果中标识瓶颈请求和瓶颈边 集合。确定目标函数值的那些请求被定义为瓶颈该请求，并且在请 求的候选路线中包括的那些边被定义为瓶颈边。

在步骤806中，路线更新模块512在瓶颈请求中搜寻其成本比 满足以下条件的当前最佳解更少的路线。

·将用当前成本搜索未使用瓶颈边的那些路线。

·如果未发现，则将用当前成本搜索可能使用瓶颈边的那些路 线。

添加以这一方式发现的任何路线。换而言之，能够有效地添加 在添加时降低目标函数值的路线或者具有降低目标函数值的高概率 的路线。

在步骤808中，路线更新模块512确定是否在步骤806中发现 候选路线。如果发现，则从图8中所示子例程返回，过程回到图7 中的步骤704。

在路线更新模块512在步骤808中确定未发现候选路线时，如 果不存在关于每个非瓶颈边恶化当前解并且增加流量、也就是交通 量的路线，则路线更新模块512在步骤810中搜寻满足以下条件的 路线。

·将用当前成本搜索使用瓶颈边的那些路线。

·如果未发现，则将搜索可以使用瓶颈边的那些路线。

如果发现路线，则添加它。从图8中所示子例程返回，过程回 到图7中的步骤704。

执行步骤810中的过程的原因在于即使并非瓶颈的那些请求 也可以通过添加候选路线来提高目标函数值。这时对于具有满足以 下条件的候选路线的那些请求，无论针对这样的请求添加哪个路线 都不能提高目标函数值。

·候选路线的边都不是瓶颈边，并且路线本身不是用于确定当 前目标函数值的路线。

这些条件假设边的成本函数是严格单调增加的成本函数。换而 言之，对于所需时间函数“ax+b”，应当使用“a＞0”而不是“a≥0”。

回到图7中的流程图，在步骤704中已经计算MIP并且已经 在步骤706中确定已经满足终止条件时，针对每个请求返回多个路 线，并且针对每个路线返回利用率。

在已经以这一方式获得在多对多出发点与目的地点之间的所 需路线并且已经获得所需路线的利用率时，可以将它们应用于交通 路线安排，以便缓解比如在高峰时间期间的持续或者持久拥堵和在 某些设施周围的规律拥堵。

它也可以应用于人群控制，以便计划用于在活动地点的人群移 动的高效路线并且计划在火灾情况下的有效撤退路线。

参照具体实施例说明本发明，并且图示一个硬件配置类型。然 而本发明也可以使用于任何其它硬件环境、比如多处理器环境或者 网络连接的群计算环境中。

标号列表

402：系统总线

404：CPU

406：存储器

406：主存储装置

408：硬盘驱动

410：键盘

412：鼠标

414：显示器

502：主例程

504：交通路线图数据

506：请求数据

508：求解器

510：路线搜索模块

512：路线更新模块