专利名称：一种满足活动需求和路径最优的出行导航方法
技术领域：
本发明涉及出行导航领域，尤其涉及同时满足活动需求和路径最优的出行导航方法。
背景技术：
伴随着我国城市化进程的推进，城市交通工具数量和城市交通需求都急剧增长，随之而来的是有限的交通资源供不应求，出现了城市交通拥堵等问题。缓解城市交通问题 的两种交通管理模式是交通需求管理和交通系统管理。出行导航作为交通系统管理的一种 重要手段，是将交通信息传递给出行者，从而引导出行者选择出行路径，改善交通系统的性 能。然而传统的出行导航方法存在一些不足1)传统的出行导航仅针对出行本身，只考虑了帮助出行者寻找要到达的目的地的 路径，是一种仅对出行过程的导航。传统导航有片面性和局限性，出行只是手段，活动才是 目的，传统的导航没能考虑到出行产生的根源，即出行源于个体活动的需要。出行的产生是 源于活动的参与，传统出行导航不一定满足个体活动的需求，也无法为出行者的活动提供 个性化的服务。2)传统导航只是对单次出行选择最优出行路径，没有考虑到出行者一天中多次出 行之间存在的关联性。出行者的许多活动之间是既相互关联又彼此限制，而传统导航没能 将这些活动约束考虑进去，没有从活动_出行链的角度对出行路径进行整体导航。

发明内容
技术问题本发明的目的是提供一种同时满足活动需求和路径最优的出行导航方法，在满足 活动需求的所有出行路径基础上，从活动_出行链整体的角度，选定出行时间最小的路径 作为最优路径，并利用GIS (地理信息系统)作为技术平台对出行者进行最优活动地点和出 行路径的导航。技术方案为达到上述目的，本发明的具体方法如下步骤1 普通个体出行者根据自己出行的实际需要建立初始活动安排，列出出行 的具体活动、活动地点限制条件和时间约束条件。所述的活动地点限制条件是出行者根据 自身的实际需求对活动的地点属性进行的组合，包括(1)活动地点的地理位置符合出行者 的要求，⑵活动地点的等级和规模达到出行者的规定水平，(3)活动地点周围Ikm范围内 有出行者指定的设施。所述的时间约束条件是指出行者根据自身的实际需求对活动的时间 属性进行的组合，包括(1)活动的起始时间，(2)活动的终止时间。步骤2 结合当天的活动和地点限制条件，寻找到能够满足出行者活动需要的活 动地点，从中提取出可供选择的活动地点集合。步骤3 确定定点活动对数目，结合时间约束条件，利用启发式搜索算法得到每个定点活动对内的最优地点，并将所述的最优地点作为非定点活动地点，同时得到每个定点 活动对内各活动对的最优出行路径，从而确定出行者当天所有的活动地点和出行路径。步骤4 利用地理信息系统GIS作为技术平台，根据步骤3中得到的最优活动地点 和最优出行路径对个体出行者进行导航。有益效果同时满足活动需求和路径最优的出行导航方法考虑到出行只是手段，活动才是目 的，出行者对于活动的参与才是出行产生的根源，该导航方法将传统的交通导航由出行本 身拓展到活动_出行系统，并利用GIS作为技术平台实现此方法的导航。该方法的有益效 果具体包括1.同时满足活动需求和路径最优的出行导航方法不仅针对出行本身，而且允许出 行者根据自身的实际需要建立活动地点限制条件和时间约束条件。地点约束条件的建立为 出行者提供了多个活动地点的集合，克服了传统方法只能针对固定出行起点和出行终点进 行导航的缺陷。2、同时满足活动需求和路径最优的出行导航方法在具体路径搜索过程中将非定 点活动放在定点活动对中进行整体搜索，对多个可选非定点活动地点与定点活动地点之间 的出行时间进行了比对，将传统方法中仅针对单次出行的导航拓展到从活动_出行链的角 度对出行路径进行整体导航，同时考虑了活动_出行链中的各个活动所受到的时间约束， 使得导航选择所选择的活动地点和出行路径更为贴近出行者实际需要。


图1为满足活动需求和路径最优的出行导航方法的示意图。图2为步骤2中确定可供选择的活动地点集合的示意图。图3为步骤3中确定最优活动地点和出行路径的示意图。图4为算例中初始路网和活动地点状况的示意图。图5为算例中以家和上班地点组成的定点活动对为例确定最优活动地点和出行 路径的示意图。图6为算例中出行者当天的整个最优活动地点和出行路径的示意图。
具体实施例方式下面结合附图，对本发明作详细说明，如图所示。1.个体出行者建立初始活动安排普通个体出行者均可以结合自身当天的实际情况，随意选择出行活动地点和时 间，确定总的活动数目。与此同时，还可以自主灵活的调整活动安排，包括更改活动次序，增 加删除活动，修改活动的名称、类型、持续时间、出行方式等。其中活动分为定点活动和非定 点活动，定点活动是出行者指定活动地点的活动，非定点活动是出行者在活动安排中确定 具体活动类型而不确定活动地点的活动。一般而言，定点活动包括上班、上学、回家等刚性 活动，非定点活动较多的是娱乐、休闲等弹性活动。出行者还需列出地点限制条件和时间约束条件。活动地点限制条件是出行者可以 根据自身的实际需求对活动的地点属性进行的组合，包括(1)活动地点的地理位置符合出行者的要求，(2)活动地点的等级和规模达到出行者的规定水平，(3)活动地点周围Ikm范 围内有出行者指定的设施。活动时间约束条件是指出行者根据自身的实际需求对活动的时 间属性进行的组合，包括(1)活动的起始时间，(2)活动的终止时间。2.确定可供选择的活动地点集合将出行者活动安排的活动数目m作为循环总次数，对出行者当天安排的活动做时 间排序并标号，用i表示活动的序号，其中1 < i < m，假定出行起点和终点均为定点，依次 对已做好排序标号的活动进行活动地点的提取，具体措施如下(1)选择出行起始点作为第一个定点，选取第一个活动，即令i = 1，转入(2)。(2)判断活动的活动地点类型，如果活动是定点活动，选取下一个活动，即i = i+Ι，转入(4)；如果是非定点活动，则转入(3)。(3)用j表示非定点活动i的活动地点，将出行者规定的非定点活动的活动地点提 取数η作为每个非定点活动的循环总次数，选取活动i的第一个活动地点，即j = 1，判断 是否满足活动的地点限制条件，如果不满足地点限制条件，则继续选择下一个活动地点，即 j = j+1 ；如果满足地点限制条件，则将活动地点j加入活动i的可选活动地点集合，并继续 选择下一个活动地点，即j = j+1,当活动地点数目达到了 η时，活动i的活动地点提取完 成，令i = i+Ι，转入(4)。(4)当活动i的序号值达到了出行者活动安排的活动数目m时，循环结束，表示整 个可供选择的活动地点集合提取完毕；否则，返回(2)。3.确定最优活动地点和出行路径将出行者活动安排的活动数目m作为循环总次数，对出行者当天安排的活动做时 间排序并标号，用i表示活动的序号，其中1 < i < m，假定出行起点和终点均为定点，将相 邻两个活动组成活动对，并将出行起点和第一个活动作为活动对处理，将相邻两个定点活 动组成至少包括一个活动对的定点活动对，用f(k)表示定点活动对的最小出行时间，其中 k为定点活动对中的后一个活动的标号，用F表示定点活动对中后一个活动k之前的所有定 点活动对的最小出行时间的总和，具体措施如下(1)令F初始值为0，选择出行起点，将出行起点作为第一个定点，判断第一个活动 是否为定点活动，即i = 1。如果是定点活动，则转入(3)；如果是非定点活动，将该非定点 活动与第一个定点当作活动对，确定该非定点活动的可选活动地点集合中的地点与出行起 点间的出行时间，转入(5)。(2)如果当前活动对中的后一个活动是定点活动，则转入(3)；如果当前活动对中 的后一个活动是非定点活动，确定该非定点活动与前一个活动组成的活动对中各活动地点 间的出行时间，转入(5)。(3)结合活动的时间约束条件，利用启发式搜索算法得到这个定点活动与前面最 近的一个定点间的最优出行路径，此时f(k)为最小值，在F值中加入f(k)的值，转入(4)。(3)所述的启发式搜索算法具体实现过程如下(3. 1)建立两个表，Open表用于存放非定点活动地点和当前定点活动对的后一个 定点活动地点，Close表用于存放当前定点活动对的前一个定点活动地点。(3. 2)将出行起点和第一个活动作为活动对处理，如果第一个活动是定点活动，则 转入(3.4)；如果第一个活动是非定点活动，则对第一个活动中各个可选活动地点做标记，标记值为各个活动地点与出行起点间的出行时间，标记完成后，将第一个活动的活动地点 从Open表放入Close表中，并将第一个活动作为下一个活动对的前一个非定点活动，并找 出下一个活动对的后一个活动，如果后一个活动是定点活动，则转入(3.4)；如果后一个活 动是非定点活动，则将后一个活动作为当前非定点活动，转入(3.3a)。(3.3a)从当前非定 点活动的可选活动地点集合中任选一个地点作为当前活动地点并对当前活动地点进行标 记，再从前一个非定点活动的可选活动地点集合中任选一个活动地点作为前一活动地点， 将当前活动地点与前一活动地点之间的出行时间与前一活动地点的标记值的和作为当前 活动地点的一个候选标记值，(3.3b)重复(3. 3a)，得到当前活动地点的第二个候选标记 值、第三个候选标记值、……，直到得到当前活动地点的所有候选标记值，再从所有候选标 记值选择出最小的候选标记值，并将所选的最小的候选标记值作为当前活动地点的标记 值，将所选的最小的候选标记值所对应的活动地点的前一个活动标记为最优地点，标记完 成后，将当前非定点活动的可选活动集合的地点从Open表放入Close表中，并将当前非定 点活动转化为前一个非定点活动，同时也作为下一个活动对的前一个活动，并找出下一个 活动对的后一个活动，如果后一个活动是定点活动，则转入(3.4)；如果后一个活动是非定 点活动，则将后一个活动作为当前非定点活动，转入(3.3a)，(3.4)将定点活动对的后一个 定点活动的标记值定为定点活动对的出行时间的最小值，并将定点活动对的后一个定点活 动的前面一个活动中所有候选标记值里取最小值的地点作为最优地点，将定点活动从Open 表放入Close表中，此时，Open表为空，标记全部完成。从定点活动对的后一个活动反向追 踪定点活动对中的前一定点活动与后一定点活动之间的每一个非定点活动的最优地点，最 优地点间取出行时间最短的路径作为最优出行路径。(4)如果当前活动i是出行终点，则循环结束，得到当前出行路径最优的一组活 动地点，此时的F值为最优出行路径对应的出行时间；如果当前活动i不是出行终点，转入 (5)。(5)将当前活动作为下一个活动对的前一个活动，令i = i+Ι，转入(2)。4.利用上述方法得到的最优活动地点和最优出行路径对出行者进行导航上述方法最终确定了出行者当天的最优活动地点和最优出行路径。此时可以结合 GIS (地理信息系统)以友好的交互方式对出行者进行导航，传达给出行者在目前的交通状 况下，到达所有活动地点的预估实施时间和相应的路径指示，使其始终行驶在最优出行路 径上。实际算例此导航方法针对的是普通个体出行者，现以下面的道路网络图作为实例，简述具 体实现过程。步骤1该出行者结合了自身的实际情况，建立了当天的活动安排和地点限制条件 和时间约束条件，具体的路网状况如图4。该出行者早上8:00从家里出发前，先安排好当天的活动顺序为家一寄包裹一上班一看电影一购物一家再列出地点限制条件和时间约束条件假定出行者根据当天自身的实际情况列出地点限制条件和时间约束条件为
权利要求
1. 一种满足活动需求和路径最优的出行导航方法，其特征在于 步骤1 普通个体出行者根据自己出行的实际需要建立初始活动安排，列出出行的具 体活动、活动地点限制条件和时间约束条件，所述的活动地点限制条件是出行者根据自身 的实际需求对活动的地点属性进行的组合，包括(1)活动地点的地理位置符合出行者的要 求，(2)活动地点的等级和规模达到出行者的规定水平，(3)活动地点周围Ikm范围内有出 行者指定的设施，所述的时间约束条件是指出行者根据自身的实际需求对活动的时间属性 进行的组合，包括(1)活动的起始时间，(2)活动的终止时间，步骤2 结合当天的活动和地点限制条件，寻找到能够满足出行者活动需要的活动地 点，从中提取出可供选择的活动地点集合，步骤3 确定定点活动对数目，结合时间约束条件，利用启发式搜索算法得到每个定点 活动对内的最优地点，并将所述的最优地点作为非定点活动地点，同时得到每个定点活动 对内各活动对的最优出行路径，从而确定出行者当天所有的活动地点和出行路径，步骤4 利用地理信息系统GIS作为技术平台，根据步骤3中得到的最优活动地点和最 优出行路径对个体出行者进行导航；可供选择的活动地点集合采用如下方法来确定将出行者活动安排的活动数目m作为循环总次数，对出行者当天安排的活动做时间排 序并标号，用i表示活动的序号，其中1 < i < m，假定出行起点和终点均为定点，依次对已 做好排序标号的活动进行活动地点的提取，具体措施如下步骤Al)选择出行起始点作为第一个定点，选取第一个活动，即令i = 1，转入步骤A2)；步骤A2)判断活动的活动地点类型，如果活动是定点活动，选取下一个活动，即i = i+Ι，转入步骤A4)；如果是非定点活动，则转入步骤A3)；步骤A3)用j表示非定点活动i的活动地点，将出行者规定的非定点活动的活动地点 提取数η作为每个非定点活动的循环总次数，选取活动i的第一个活动地点，即j = 1，判断 是否满足活动的地点限制条件，如果不满足地点限制条件，则继续选择下一个活动地点，即 j = j+1 ；如果满足地点限制条件，则将活动地点j加入活动i的可选活动地点集合，并继续 选择下一个活动地点，即j = j+1,当活动地点数目达到了 η时，活动i的活动地点提取完 成，令i = i+Ι，转入步骤A4)；步骤A4)当活动i的序号值达到了出行者活动安排的活动数目m时，循环结束，表示整 个可供选择的活动地点集合提取完毕；否则，返回步骤A2)； 确定最优活动地点和出行路径采用如下方法将出行者活动安排的活动数目m作为循环总次数，对出行者当天安排的活动做时间排 序并标号，用i表示活动的序号，其中1 < i < m，假定出行起点和终点均为定点，将相邻两 个活动组成活动对，并将出行起点和第一个活动作为活动对处理，将相邻两个定点活动组 成至少包括一个活动对的定点活动对，用f (k)表示定点活动对的最小出行时间，其中k为 定点活动对中的后一个活动的标号，用F表示定点活动对中后一个活动k之前的所有定点 活动对的最小出行时间的总和，具体措施如下步骤Bi)令F初始值为0，选择出行起点，将出行起点作为第一个定点，判断第一个活动 是否为定点活动，即i = 1。如果是定点活动，则转入步骤B3)；如果是非定点活动，将该非定点活动与第一个定点当作活动对，确定该非定点活动的可选活动地点集合中的地点与出 行起点间的出行时间，转入步骤B5)，步骤B2)如果当前活动对中的后一个活动是定点活动，则转入步骤B3)；如果当前活动 对中的后一个活动是非定点活动，确定该非定点活动与前一个活动组成的活动对中各活动 地点间的出行时间，转入步骤B5)，步骤B3)结合活动的时间约束条件，利用启发式搜索算法得到这个定点活动与前面最 近的一个定点间的最优出行路径，此时f(k)为最小值，在F值中加入f(k)的值，转入步骤 B4)，步骤B4)如果当前活动i是出行终点，则循环结束，得到当前出行路径最优的一组活动 地点，此时的F值为最优出行路径对应的出行时间；如果当前活动i不是出行终点，转入步 骤 B5)，步骤B5)将当前活动作为下一个活动对的前一个活动，令i = i+Ι，转入步骤B2)。
2.根据权利要求1所述的满足活动需求和路径最优的出行导航方法，其特征在于，步 骤B3)所述的启发式搜索算法的具体实现过程如下步骤B3. 1)建立两个表，Open表用于存放非定点活动地点和当前定点活动对的后一个 定点活动地点，Close表用于存放当前定点活动对的前一个定点活动地点，步骤B3. 2)将出行起点和第一个活动作为活动对处理，如果第一个活动是定点活动， 则转入步骤B3. 4)；如果第一个活动是非定点活动，则对第一个活动中各个可选活动地点 做标记，标记值为各个活动地点与出行起点间的出行时间，标记完成后，将第一个活动的活 动地点从Open表放入Close表中，并将第一个活动作为下一个活动对的前一个非定点活 动，并找出下一个活动对的后一个活动，如果后一个活动是定点活动，则转入步骤B3. 4)； 如果后一个活动是非定点活动，则将后一个活动作为当前非定点活动，转入步骤B3. 3a),步骤B3. 3a)从当前非定点活动的可选活动地点集合中任选一个地点作为当前活动地 点并对当前活动地点进行标记，再从前一个非定点活动的可选活动地点集合中任选一个活 动地点作为前一活动地点，将当前活动地点与前一活动地点之间的出行时间与前一活动地 点的标记值的和作为当前活动地点的一个候选标记值，步骤B3. 3b)重复步骤B3. 3a)，得到当前活动地点的第二个候选标记值、第三个候选标 记值、……，直到得到当前活动地点的所有候选标记值，再从所有候选标记值选择出最小的 候选标记值，并将所选的最小的候选标记值作为当前活动地点的标记值，将所选的最小的 候选标记值所对应的活动地点的前一个活动标记为最优地点，标记完成后，将当前非定点 活动的可选活动集合的地点从Open表放入Close表中，并将当前非定点活动转化为前一个 非定点活动，同时也作为下一个活动对的前一个活动，并找出下一个活动对的后一个活动， 如果后一个活动是定点活动，则转入步骤B3. 4)；如果后一个活动是非定点活动，则将后一 个活动作为当前非定点活动，转入步骤B3. 3a)，步骤B3. 4)将定点活动对的后一个定点活动的标记值定为定点活动对的出行时间的 最小值，并将定点活动对的后一个定点活动的前面一个活动中所有候选标记值里取最小值 的地点作为最优地点，将定点活动从Open表放入Close表中，此时，Open表为空，标记全部 完成。从定点活动对的后一个活动反向追踪定点活动对中的前一定点活动与后一定点活动之 间的每一个非定点活动的最优地点，最优地点间取出行时间最短的路径作为最优出行路径。
全文摘要
一种满足活动需求和路径最优的出行导航方法普通个体出行者根据自己出行的实际需要建立初始活动安排，列出出行的具体活动、活动地点限制条件和时间约束条件。结合当天的活动和地点限制条件，寻找到能够满足出行者活动需要的活动地点，从中提取出可供选择的活动地点集合。确定定点活动对数目，结合时间约束条件，利用启发式搜索算法得到每个定点活动对内的最优地点，并将所述的最优地点作为非定点活动地点，同时得到每个定点活动对内各活动对的最优出行路径，确定出行者当天所有的活动地点和出行路径。利用地理信息系统GIS作为技术平台，根据步骤3中得到的最优活动地点和最优出行路径对个体出行者进行导航。
文档编号G01C21/34GK101995255SQ20101025979
公开日2011年3月30日 申请日期2010年8月20日 优先权日2010年8月20日
发明者杨敏, 王炜, 范会川, 陈学武, 陈景旭 申请人:东南大学