专利名称：路线选择系统、路线选择方法和路线选择程序的制作方法
技术领域：
本发明涉及一种用于选择路线、比如交通路线的系统、方法和程序。
背景技术：
汽车导航系统具有搜寻和显示交通路线的功能。在这一过程中的算法例如将十字路口视为节点而路段视为边，并且在其中对路线长度加权的加权图中搜寻最短路线。然而这时大量汽车具有用来同时搜寻路线的汽车导航系统，并且每个汽车独立确定最短路线。在这引起用于多个汽车的交通路线重叠时，特定路线或者边的使用频率增加，并且拥堵出现于这些路线中的一些路线中。这时如图1中所示，认为用于每个路线的时间随着交通量增加而迅速增加。在汽车中引用车辆信息和通信系统(VICS)提供的交通信息，使得汽车导航系统可以计算备选路线。然而在大量车辆引用相同交通信息时，最终选择相似备选路线，并且这引起如图2中所示进一步拥堵。因此需要中心服务器考虑由于车辆集中而出现拥堵，并且如图3中所示执行多对多路线安排以缓解拥堵。换而言之，如果可以相互避免拥堵，则存在减少所需时间的可能性。然而在多对多路线安排中执行的计算通常经历困难，并且难以在合理数量的时间内提出求解。在公开号为2001-331564的待审日本专利中公开一种用于通过使用针对每个计划的必需精确度和计算时间而优化的手段来计算用于运输计划中的每个运输手段的路线，来实现有效计划的系统。至少具有输入/输出设备、处理器和存储设备并且创建分布计划的这一系统包括:基本信息注册步骤，用于输入用于基地、比如工厂、中继基地和供应商的位置信息；运输服务信息注册步骤，用于输入包括每个运输服务拜访的基地和负荷数量的运输递送信息；条件注册步骤，用于输入包括运输计划的必需准确度和限制时间的目标信息；算法选择步骤，用于选择用于路线预备的算法；路线预备步骤，用于根据这一信息预备用于递送服务的路线；以及输出步骤，用于输出结果。公开号为2004-12312的待审专利公开一种路线搜索设备，该设备包括:第一搜索装置，用于搜寻最小成本路线，沿着该最小成本路线的伴随路线的参数在从起点到目的地的伴随路线的参数之中变成最小；加权装置，用于对构成第一最短路线的每个路段的参数进行加权；以及区域限制装置，用于基于第一搜索装置的计算的数据发现具体地图区域作为限制区域。这一设备还包括:第二搜索装置，用于通过将借助区域限制装置发现的限制区域视为待搜索对象仅在该区域中搜寻路线。通过利用在先前搜索期间获得的信息限制搜索范围来缩短随后搜索所需要的时间。公开号为2009-19932的待审专利公开一种用于为从移动起点到达移动终点的自治移动体搜寻移动路线的路线搜索系统，该系统包括:区域划分部分，用于将移动区域划分成多个区域；与区域划分部分划分的多个区域对应的多个评估值计算部分，用于计算每个区域的评估值；以及路线确 定部分，用于基于评估值计算部分计算的评估值来确定路线。评估值计算部分具有:评估值处理部分，用于基于附近存在的区域的评估值和从附近区域到它自己的区域的移动成本来计算评估值。第0073段声明“被指示为移动起点和移动终点的区域数目无论它是多对一、一对多或者多对多都可以适用于本发明。”然而即使简单求解也需要大量计算，现有技术文献均未公开一种用于以合理计算量获得多对多路线搜索处理的技术。引用列表专利文献专利文献I公开号为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位架构并且可以是来自InterCorporation 的 Pentinm 4、Core 2Duo 或者Xeon 或者来自 AdvancedMicroDevices Inc.的Atllkm 。^存储器406优选地具有4GB或者更多的容量。硬盘驱动408优选地具有500GB或者更多的容量以便存储大量数据。这样的硬件配置的优选例子是IBM System X系列。然而本发明不限于此。它甚至可以实现于个人计算机中。尽管在任何附图中未示出，但是硬盘驱动408包括预装操作系统。操作系统可以是与CPU404兼容的任何操作系统。例子包括Linux 、来自Microsoft Corporation的Windows χρ 、Windows 2000 和 Windows2008 Server 0硬盘驱动408存储下文描述的主例程502、交通路线图数据504、请求数据506、求解器508、路线搜索模块510和路线更新模决512。用现有编程语言、比如C、C++、C#或者Java 创建主例程502、求解器508、路线搜索模块510和路线更新模块512并且如果必要则在系统启动时并且通过操作系统的作用向存储器406中加载主例程502、求解器508、路线搜索模块510和路线更新模块512。显示器414优选地是液晶显示器。可以使用包括XGA(分辨率:1024X768)或者UXGA(分辨率=1600X1200)的任何分辨率。尽管在附图中未示出，但是显示器414用来显示用于开始和停止本发明的处理程序以及用于显示交通路线数据的操作屏幕。
下文参照图5的功能框图说明用来实现本发明的逻辑功能结构。在图5中，主例程502是管理整个过程、在显示器414上显示操作屏幕(未示出)并且响应于使用键盘410和鼠标412而录入的用户操作来开始和停止过程的程序。交通图数据504是加权图数据，在该加权图数据中以图的形式描述路线而将道路表达为边并且将十字路口表达为节点，并且在该加权图数据中通过单调增加逐段线性函数逼近每条道路的权值以对由于交通量增加所致的拥堵出现建模。通常表达图为矩阵或者列表以使它计算机可读和可存储于介质、比如硬盘中。然而图可以采用能够实现本发明的目的的任何形式。图6是示出边和所需时间的逐段线性的图。这里X是用每小时通过的车辆数目表达的交通量。这是图1中所示图的逐段线性逼近。如附图中所示，使用的逐段线性函数是所需时间t = ap+h,其中O彡X < X1、所需时间t = a2x+b2,其中X1彡x < X2和所需时间t = a3x+b3,其中X2 ( X，其中Si > 0(i = 1,2,3)。这里仅示出三段,但是这仅为一个实施例。如果必要，则可以使用任何数目和宽度的段。逐段线性函数不限于此。例如可以实施它为由每个边指示的并且引用存储器中的表的线性函数。换而言之，准备一个表使得响应于用于交通量的值彡X1而返回{a1; bj并且响应于用于交通量的值X1彡X < X2而返回{a2,
b2} ο 根据道路的实际条件确定用于执行每边的逐段线性逼近的系数组、比如{a1; bj、{a2, b2}。换而言之,优选地与边的实际长度成比例地确定系数、比如Ia1, bj (i = 1,2,3等)。然而对于上坡道路使{apbj更大，并且对于下坡道路使{ai，bJ更小。还对于具有大弯曲的道路使k，bj更大，对于具有许多车道的道路使{ai; bj更小，并且对于窄道路使{ai; bj更大。此外，对于具有良好人行道的道路使{ai; bj更小，并且对于无人行道的道路使Iai, bj更大。在优选例子中，用于每边的所需时间是t = maxj {ajX+bJ。这里Si > O。提供请求数据506为集合{出发点，目的地点，需求水平}。可以例如使用探测汽车数据来收集这一请求数据。使用探测汽车数据的交通数据收集技术在本领域中是公知的。例如参见公开号为2004-110458的待审专利公开、公开号为2004-156982的待审专利公开、公开号为2007-193705的待审专利公开和公开号为2004-241987的待审专利公开。由于在每对{出发点，目的地点}之间行进的车辆数目在给定的时间段内已知，所以这些技术可以用来预备请求数据506，使得车辆数目被设置为需求水平，按照需求水平降序对集合{出发点，目的地点，需求水平}排序，并且向硬盘驱动408从最高保存预定数目的对。求解器508使用通过将用于所有请求的实际所需时间除以最短所需时间而获得的所有值的最小化的最大值作为目标函数，并且求解混合整数规划(MIP)问题从而向每个请求提供多个路线及其利用率(实数)作为输出。不存在关于求解器的限制，但是优选例子是IBM ILOG CPLEXo下文更具体说明MIP公式表达。路线搜索模块510使用任何公知算法、比如Dijkstra算法或者A*搜索技术来执行加权图路线搜索。算法也可以是在公开号为2008-157698的待审专利公开中描述的修正的A*搜索技术。路线更新模块512任意消除路线，以便减少计算量或者添加有用路线。下文参照图8中的流程图更具体说明路线更新模块512执行的过程。
下文参照图7和图8说明本发明的路线选择过程。在图7的步骤702中，主例程502调用路线搜索模块510，并且针对请求数据506中的{出发点，目的地点}对搜寻从出发点到目的地点的最低成本路线或者最短路线，其中X = O置于用于t = maxj {ajX+bJ的公式中。在步骤704中，主例程502调用求解器508，并且用当前时间的候选路线求解混合整数规划(MIP)问题。在由步骤704、步骤706和步骤708构成的循环中，可以通过使用先前解作为第二和后续迭代中的初始值来减少计算时间。下文说明MIP公式表达。公式表达旨在于使用其中使通过将用于所有请求的实际所需时间除以最短所需时间而获得的所有值中的最大值最小化的目标函数。这表达为图G=(V, E)，其中V是交通图数据504中的节点集合并且E是边集合。参考图6中的逐段线性逼近，用于沿着边e e E移动的行进时间由以下等式表达，其中交通量为X:te (X) = Iiiaxi (aeix+bei)这里aei>0。请求i (i = I,..., k)具有以下属性。出发点的节点:Si e V目的地点的节点:gie V需求水平:屯G R, Cli > O也令Pi*为未包括从节点Si到节点gi的路线的所有路线的集合。然后表达为P e Pi*为连接边的排列。P = (e1； e2,..., θ|ρ|)这里I ρ I是连接到P的边数。因此令Ti*为在交通量X为O时从节点Si到节点gi的最小所需时间。换而言之，Ti*由以下等式表达。等式I
权利要求
1.一种计算机实施的用于选择路线的方法，所述方法包括以下步骤: 预备将路段表达为边并且将路线十字路口表达为节点的图，每个路段的权值由单调增加逐段线性函数逼近； 响应于多个请求是出发点和目的地点的集合在所述图中搜寻最短路线，并且将所述获得的路线建立为待处理路线集合； 求解目标函数，以便最小化关于多个出发点和目的地点的所述集合通过将从每个出发点到每个目的地点的所需时间除以最短所需时间而获得的最大值；以及 在重复所述目标函数的求解的过程中，去除其最小成本大于或者等于当前最佳解的成本的那些路线和在先前迭代中添加的任何未用路线。
2.根据权利要求1所述的用于选择路线的方法，其中所述加权是所述路线的行进时间。
3.根据权利要求2所述的用于选择路线的方法，还包括以下步骤:在重复所述目标函数的求解的过程中向所述待处理路线集合添加在添加时降低所述目标函数的任何路线。
4.根据权利要求3所述的用于选择路线的方法，其中所述添加步骤还包括以下步骤:在“实际所需时间/最短所需时间”被最大化、具有与所有候选路线相同的实际所需时间的请求是瓶颈请求并且在用于这些瓶颈请求的候选路线集合中包括的边是瓶颈边时，搜寻使用当前成本并且未使用所述瓶颈边的任何路线。
5.根据权利要求4所述的用于选择路线的方法，还包括以下步骤:响应于在所述搜寻使用当前成本并且未使用瓶颈边的任何路线的步骤中未发现路线，包括和搜寻使用所述瓶颈边的任何路线。·
6.根据权利要求5所述的用于选择路线的方法，还包括以下步骤:响应于在所述搜寻使用当前成本并且未使用所述瓶颈边的任何路线的步骤中未发现路线，在不存在关于每个非瓶颈边恶化当前解并且增加流量的路线时，搜寻使用当前成本并且未使用所述瓶颈边的任何路线。
7.根据权利要求6所述的用于选择路线的方法，还包括以下步骤:响应于在所述搜寻使用当前成本并且未使用所述瓶颈边的任何路线的步骤中未发现路线，包括和搜寻使用所述瓶颈边的任何路线。
8.根据权利要求1所述的用于选择路线的方法，其中所述目标函数由求解器求解。
9.根据权利要求8所述的用于选择路线的方法，其中所述请求是出发点、目的地点和需求水平的集合，并且所述求解器输出用于从所述出发点到所述目的地点的多个路线的所述需求水平的百分比。
10.一种计算机执行的用于选择路线的程序，所述程序包括以下步骤: 预备将路线表达为边并且将路线十字路口表达为节点的图，每个路线的权值由单调增加逐段线性函数逼近； 响应于多个请求是出发点和目的地点的集合在所述图中搜寻最短路线，并且将所述获得的路线建立作为待处理路线集合； 求解目标函数，以便最小化关于多个出发点和目的地点的所述集合通过将从每个出发点到每个目的地点的所需时间除以最短所需时间而获得的最大值；以及 重复所述目标函数的求解，同时从所述待处理路线集合作为无希望路线去除具有比当前最佳解更大的最小成本的任何路线和在先前迭代中添加的任何未用路线。
11.根据权利要求10所述的用于选择路线的程序，其中所述加权是所述路线的通过时间。
12.根据权利要求11所述的用于选择路线的程序，还包括以下步骤:在重复所述目标函数的求解的过程中向所述待处理路线集合添加在添加时降低所述目标函数的任何路线。
13.根据权利要求12所述的用于选择路线的程序，其中所述添加步骤还包括以下步骤:在“实际所需时间/最短所需时间”被最大化、具有与所有候选路线相同的实际所需时间的请求是瓶颈请求并且在用于这些的候选路线集合中包括的边是瓶颈边时，搜寻使用当前成本并且未使用所述瓶颈边的任何路线。
14.根据权利要求13所述的用于选择路线的程序，还包括以下步骤:响应于在所述搜寻使用当前成本并且未使用所述瓶颈边的任何路线的步骤中未发现路线，包括和搜寻使用所述瓶颈边的任何路线。
15.根据权利要求10所述的用于选择路线的程序，其中所述目标函数由求解器求解。
16.根据权利要求15所述的用于选择路线的程序，其中所述请求是出发点、目的地点和需求水平的集合，并且所述求解器输出用于从所述出发点到所述目的地点的多个路线的所述需求水平的百分比。
17.一种计算机实施的用于选择路线的系统，所述系统包括: 存储装置；以及在所述存储装置中存储: 用于预备将路段表达为边并且将路线十字路口表达为节点的图的装置，每个路段的权值由单调增加逐段线性函数逼近； 用于响应于多个请求是出发点和目的地点的集合在所述图中搜寻最短路线并且将所述获得的路线建立为待处理路线集合的装置； 用于求解目标函数、以便最小化关于多个出发点和目的地点的所述集合通过将从每个出发点到每个目的地点的所需时间除以最短所需时间而获得的最大值的装置；以及 用于在重复所述目标函数的求解的过程中、去除其最小成本大于或者等于当前最佳解的成本的那些路线和在先前迭代中添加的任何未用路线的装置。
18.根据权利要求17所述的用于选择路线的系统，其中还包括以下步骤:在重复所述目标函数的求解的过程中，向所述待处理路线集合添加在添加时降低所述目标函数的任何路线。
19.根据权利要求18所述的用于选择路线的系统，其中所述添加步骤还包括以下步骤:在“实际所需时间/最短所需时间”被最大化、具有与所有候选路线相同的实际所需时间的请求是瓶颈请求并且在用于这些的候选路线集合中包括的边是所述瓶颈边时，搜寻使用当前成本并且未使用所述瓶颈边的任何路线。
20.根据权利要求19所述的用于选择路线的系统，还包括以下步骤:响应于在所述搜寻使用当前成本并且未使用所述瓶颈边的任何路线的步骤中未发现路线，包括和搜寻使用所述瓶颈边的任何路线。
21.根据权利要求20所述的用于选择路线的系统，其中所述请求是出发点、目的地点和需求水平的集合，并且所述求解器输出用于从所述出发点到所述目的地点的多个路线的所述需求水平的百分比。
全文摘要
提供一种用于用合理计算量获得多对到路线搜索过程的技术。在使用指示出发点和目的地点的信息作为请求时，公式表达为混合整数规划(MIP)问题，其中目标函数是“使通过将用于所有请求的实际所需时间除以最短所需时间而获得的所有值中的最大值最小”。通过在从初始状态逐渐和反复添加有希望路线的过程中，求解MIP问题来阻止候选路线数目的激增。也通过使用在迭代结束时的实际路线来搜寻新路线，优先搜寻具有高效用值的路线作为备选路线。这时去除具有比当前最佳解更大的最小成本的任何路线和在先前迭代中添加的任何未用路线作为无希望路线。通过在更新路线候选时保持在先前迭代期间使用的路线，先前迭代的解可以用作MIP问题中的初始值，并且减少计算时间。
文档编号G01C21/34GK103250031SQ20118005578
公开日2013年8月14日 申请日期2011年11月8日 优先权日2010年11月26日
发明者吉住贵幸 申请人:国际商业机器公司