一种满足活动需求和路径最优的出行导航方法

摘要

一种满足活动需求和路径最优的出行导航方法：普通个体出行者根据自己出行的实际需要建立初始活动安排，列出出行的具体活动、活动地点限制条件和时间约束条件。结合当天的活动和地点限制条件，寻找到能够满足出行者活动需要的活动地点，从中提取出可供选择的活动地点集合。确定定点活动对数目，结合时间约束条件，利用启发式搜索算法得到每个定点活动对内的最优地点，并将所述的最优地点作为非定点活动地点，同时得到每个定点活动对内各活动对的最优出行路径，确定出行者当天所有的活动地点和出行路径。利用地理信息系统GIS作为技术平台，根据步骤3中得到的最优活动地点和最优出行路径对个体出行者进行导航。

说明书

技术领域

本发明涉及出行导航领域，尤其涉及同时满足活动需求和路径最优的出行导航方法。

背景技术

伴随着我国城市化进程的推进，城市交通工具数量和城市交通需求都急剧增长，随之而来的是有限的交通资源供不应求，出现了城市交通拥堵等问题。缓解城市交通问题的两种交通管理模式是交通需求管理和交通系统管理。出行导航作为交通系统管理的一种重要手段，是将交通信息传递给出行者，从而引导出行者选择出行路径，改善交通系统的性能。

然而传统的出行导航方法存在一些不足：

1)传统的出行导航仅针对出行本身，只考虑了帮助出行者寻找要到达的目的地的路径，是一种仅对出行过程的导航。传统导航有片面性和局限性，出行只是手段，活动才是目的，传统的导航没能考虑到出行产生的根源，即出行源于个体活动的需要。出行的产生是源于活动的参与，传统出行导航不一定满足个体活动的需求，也无法为出行者的活动提供个性化的服务。

2)传统导航只是对单次出行选择最优出行路径，没有考虑到出行者一天中多次出行之间存在的关联性。出行者的许多活动之间是既相互关联又彼此限制，而传统导航没能将这些活动约束考虑进去，没有从活动-出行链的角度对出行路径进行整体导航。

发明内容

技术问题：

本发明的目的是提供一种同时满足活动需求和路径最优的出行导航方法，在满足活动需求的所有出行路径基础上，从活动-出行链整体的角度，选定出行时间最小的路径作为最优路径，并利用GIS(地理信息系统)作为技术平台对出行者进行最优活动地点和出行路径的导航。

技术方案：为达到上述目的，本发明的具体方法如下：

步骤1：普通个体出行者根据自己出行的实际需要建立初始活动安排，列出出行的具体活动、活动地点限制条件和时间约束条件。所述的活动地点限制条件是出行者根据自身的实际需求对活动的地点属性进行的组合，包括(1)活动地点的地理位置符合出行者的要求，(2)活动地点的等级和规模达到出行者的规定水平，(3)活动地点周围1km范围内有出行者指定的设施。所述的时间约束条件是指出行者根据自身的实际需求对活动的时间属性进行的组合，包括(1)活动的起始时间，(2)活动的终止时间。

步骤2：结合当天的活动和地点限制条件，寻找到能够满足出行者活动需要的活动地点，从中提取出可供选择的活动地点集合。

步骤3：确定定点活动对数目，结合时间约束条件，利用启发式搜索算法得到每个定点活动对内的最优地点，并将所述的最优地点作为非定点活动地点，同时得到每个定点活动对内各活动对的最优出行路径，从而确定出行者当天所有的活动地点和出行路径。

步骤4：利用地理信息系统GIS作为技术平台，根据步骤3中得到的最优活动地点和最优出行路径对个体出行者进行导航。

有益效果

同时满足活动需求和路径最优的出行导航方法考虑到出行只是手段，活动才是目的，出行者对于活动的参与才是出行产生的根源，该导航方法将传统的交通导航由出行本身拓展到活动-出行系统，并利用GIS作为技术平台实现此方法的导航。该方法的有益效果具体包括：

1.同时满足活动需求和路径最优的出行导航方法不仅针对出行本身，而且允许出行者根据自身的实际需要建立活动地点限制条件和时间约束条件。地点约束条件的建立为出行者提供了多个活动地点的集合，克服了传统方法只能针对固定出行起点和出行终点进行导航的缺陷。

2、同时满足活动需求和路径最优的出行导航方法在具体路径搜索过程中将非定点活动放在定点活动对中进行整体搜索，对多个可选非定点活动地点与定点活动地点之间的出行时间进行了比对，将传统方法中仅针对单次出行的导航拓展到从活动-出行链的角度对出行路径进行整体导航，同时考虑了活动-出行链中的各个活动所受到的时间约束，使得导航选择所选择的活动地点和出行路径更为贴近出行者实际需要。

附图说明

图1为满足活动需求和路径最优的出行导航方法的示意图。

图2为步骤2中确定可供选择的活动地点集合的示意图。

图3为步骤3中确定最优活动地点和出行路径的示意图。

图4为算例中初始路网和活动地点状况的示意图。

图5为算例中以家和上班地点组成的定点活动对为例确定最优活动地点和出行路径的示意图。

图6为算例中出行者当天的整个最优活动地点和出行路径的示意图。

具体实施方式

下面结合附图，对本发明作详细说明，如图所示。

1.个体出行者建立初始活动安排

普通个体出行者均可以结合自身当天的实际情况，随意选择出行活动地点和时间，确定总的活动数目。与此同时，还可以自主灵活的调整活动安排，包括更改活动次序，增加删除活动，修改活动的名称、类型、持续时间、出行方式等。其中活动分为定点活动和非定点活动，定点活动是出行者指定活动地点的活动，非定点活动是出行者在活动安排中确定具体活动类型而不确定活动地点的活动。一般而言，定点活动包括上班、上学、回家等刚性活动，非定点活动较多的是娱乐、休闲等弹性活动。

出行者还需列出地点限制条件和时间约束条件。活动地点限制条件是出行者可以根据自身的实际需求对活动的地点属性进行的组合，包括(1)活动地点的地理位置符合出行者的要求，(2)活动地点的等级和规模达到出行者的规定水平，(3)活动地点周围1km范围内有出行者指定的设施。活动时间约束条件是指出行者根据自身的实际需求对活动的时间属性进行的组合，包括(1)活动的起始时间，(2)活动的终止时间。

2.确定可供选择的活动地点集合

将出行者活动安排的活动数目m作为循环总次数，对出行者当天安排的活动做时间排序并标号，用i表示活动的序号，其中1≤i≤m，假定出行起点和终点均为定点，依次对已做好排序标号的活动进行活动地点的提取，具体措施如下：

(1)选择出行起始点作为第一个定点，选取第一个活动，即令i＝1，转入(2)。

(2)判断活动的活动地点类型，如果活动是定点活动，选取下一个活动，即i＝i+1，转入(4)；如果是非定点活动，则转入(3)。

(3)用j表示非定点活动i的活动地点，将出行者规定的非定点活动的活动地点提取数n作为每个非定点活动的循环总次数，选取活动i的第一个活动地点，即j＝1，判断是否满足活动的地点限制条件，如果不满足地点限制条件，则继续选择下一个活动地点，即j＝j+1；如果满足地点限制条件，则将活动地点j加入活动i的可选活动地点集合，并继续选择下一个活动地点，即j＝j+1，当活动地点数目达到了n时，活动i的活动地点提取完成，令i＝i+1，转入(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+1，转入(2)。

4.利用上述方法得到的最优活动地点和最优出行路径对出行者进行导航

上述方法最终确定了出行者当天的最优活动地点和最优出行路径。此时可以结合GIS(地理信息系统)以友好的交互方式对出行者进行导航，传达给出行者在目前的交通状况下，到达所有活动地点的预估实施时间和相应的路径指示，使其始终行驶在最优出行路径上。

实际算例

此导航方法针对的是普通个体出行者，现以下面的道路网络图作为实例，简述具体实现过程。

步骤1 该出行者结合了自身的实际情况，建立了当天的活动安排和地点限制条件和时间约束条件，具体的路网状况如图4。

该出行者早上8:00从家里出发前，先安排好当天的活动顺序为：

家→寄包裹→上班→看电影→购物→家

再列出地点限制条件和时间约束条件

假定出行者根据当天自身的实际情况列出地点限制条件和时间约束条件为

步骤2 确定可供选择的活动地点集合

该出行者当天共有5个活动，作为循环的总次数。其中家、工作地点都属于定点活动地点，其余活动都为非定点活动。依次对各个活动地点数目根据地点限制条件进行提取，本例中出行者规定的非定点活动的活动地点提取数为5个。第一个活动是寄包裹，图示路网中寄包裹的4个地点都满足地点限制条件，将这些地点放入寄包裹这个活动的可选活动地点集合。下一个活动是工作地点，由于是定点就直接选择下一个活动看电影，图示路网中有1个电影院附近没有西餐厅，则满足地点限制条件的电影院数目是3个，转入下一个活动购物，图示路网中购物的5个地点都满足地点限制条件，将这些地点放入购物这个活动的可选活动集合，转入下一个活动回家，家是定点，且总活动数目达到出行者当天活动安排的活动数目，整个可供选择的活动地点集合提取完毕。

对非定点活动的活动地点提取数目如下：

  非定点活动类型  满足地点限制条件个数  寄包裹  4  看电影  3  购物  5

步骤3 确定最优活动地点和出行路径

出行者从家出发，先是去寄包裹，寄包裹是非定点活动，有4个地点供选择，将家与这4个地点组成可选活动对，算出每个活动对的出行时间。再去判断下个活动，上班是定点活动，这时家和工作地点就组成了一个定点活动对。用启发式搜索方法找出一条家与上班地点组成的定点活动对的最优路径方案1，以下数字表示途经的交叉口，从家出发→16→11→6→1→2→3→4→工作地点，F值为57min。结合寄包裹的时间约束条件要在8:30之前完成，而方案1不满足时间约束条件。对出行方案进行调整，重新搜索路径得到方案2，以下数字表示途经的交叉口，从家出发→21→22→23→18→13→14→9→4→工作地点，满足寄包裹和工作地点的时间约束条件的要求，即第一个定点活动对路径方案已经完成，如图5。

将工作地点作为下一个定点活动对的前一个活动，寻找下一个定点活动对的后一个定点活动，找到下一个定点活动对的后一个活动是回家，用启发式搜索方法找出工作地点到家的定点活动对的最优路径方案，以下数字表示途经的交叉口，从工作地点出发→5→9→8→13→12→17→16→家。由于家是出行者当天的出行终点，所有活动对应的出现最优地点和最优路径都找出。

最终得到的出行者一天的出行方案如图6。以下数字表示途经的交叉口，出行路径为从家出发→21→22→23→18→13→14→9→4→工作地点→5→9→8→13→12→17→16→家为终点。

步骤4 上述方法最终确定了出行者当天的最优活动地点和最优出行路径。此时可以结合GIS(地理信息系统)以友好的交互方式对出行者进行导航，传达给该出行者在目前的交通状况下，到达所有活动地点的预估实施时间和相应的路径指示，使其始终行驶在最优出行路径上。