一种夜班公交车站点及路径选择方法
一种夜班公交车站点及路径选择方法
【技术领域】
[0001] 本发明属于交通技术领域，涉及数据挖掘中热点的定义和图论领域中最优路径的 选择。 技术背景
[0002] 公共汽车往往是城市生活中最流行的交通工具，它不仅能减少交通拥堵，此外也 能降低尾气的排放。在大多数城市中，白天的公交车设施已经做到非常完善了，但是在晚 间，大部分城市都没有相对完整的公交车系统，这也导致了出租车成为晚间人们出行的最 佳选择。基于此，我们可以利用出租车行驶的信息来帮助我们设计晚间公交系统。
[0003] 使用出租车行驶信息有两大好处:首先由于成熟的GPS技术，我们可以获得大量的 出租车行驶信息，包括行驶时间，行驶速度，行驶地点，车载的人数，上下车地点等待，通过 挖掘出租车信息，进而获得晚间人们出行规律。此外出租车数据是实时更新的，当城市不断 发展变化，出租车数据也会发生相应的变化，这样我们就可以更有针对性的做出动态调整。
[0004] 基于出租车数据挖掘往往可以分为3类，社会动态挖掘，交通动态挖掘以及行为动 态挖掘。其中社会动态挖掘主要是研究城市人口的集体行为并观察人们的行为规律，可以 协助城市管理员更好的管理、设计、维护以及更新城市的基础设施。目前的研究包括:人们 的出行区域，城市的热点区域，热点区域的功能分类以及城市不同区域关联度等等。交通动 态挖掘就是分析城市交通道路网的流量变化。目前的研究包括交通流的离散点，实时的交 通路况预测以及估计出行时间等等。行为动态挖掘主要是基于出租车司机对城市的经验来 分析出不正常或者高效的出行行为。目前的研究包括最快找到乘客或者出租车，推荐最快 到达目的地的行驶路线，规划公交车路线以及监测不正常行驶行为等等。
[0005] 城市交通网设计也是城市规划和交通领域中的一个研究热门领域。公交网设计问 题是一个复杂的，非线性的，非凸的，多目标的NP-hard问题。设计目标多种多样，常见的有 如何在时间，容量以及资源的限制条件下，追求最短路径，最短行驶时间，最低操作代价，最 大客流，最大的区域覆盖面积以及最大的安全系数等等。这些目标和用户需求之间往往都 存在一定的冲突，因此需要在这些目标之间找到一个平衡点而不是单一的寻求最优值。早 期的公交车系统设计往往是在分析乘客的流动数量以及乘客的需求的基础上，根据设计者 自己的经验和直觉发展起来的。近来的相关工作同样假设乘客的流量可以由用户调查以及 人口估计计算得到，基于此，提出了很多复杂的优化算法，其中启发式的设计思想往往能够 得到近似最优解决方案。
【发明内容】
[0006] 本发明的目的在于利用城市出租车轨迹数据建立夜班公交车双向站点，并在考虑 公交车站点建造成本的情况下，能在一定的时间限制内使该路线搭载的乘客数量最大化。
[0007] 现代社会的城市公交车路网设计实际上已经发展得很完善了，但夜班公交车路线 规划是城市公交路网设计中容易忽略的一点。由于夜晚乘客需求量相对于白天而言要少很 多，因此很多公交车晚上会停运。另外城市公交车路网中几乎没有专门为夜班公交车设计 的站点或路线，夜晚运行的公交车往往也是沿着白天的路线运行的;但实际上，晚上公交车 的乘客需求跟白天公交车的乘客需求会有很大的差异。因此，本发明着眼于在夜班公交车 站点的建立以及夜班公交车路线的选择，其特点在于：
[0008] 1)从夜晚乘客乘坐的出租车的上下车点位置来挑选出可能的候选公交车站点。
[0009] 2)在一定的时间限度内使能搭载的乘客数量最大化。
[0010] 3)在公交车站点建设成本和搭载最多乘客这两者之间取均衡的结果。
[0011] 4)由于乘客流量是随着时间不断变化的，因此本发明将考虑夜晚不同时间槽内的 乘客流量变化。
[0012]为达到上述目的，本发明通过以下技术方案来加以实现：
[0013] -种基于出租车轨迹的夜班公交车路径选择方法，该方法包括了一种快速的候选 公交站点设定的方法和一种公交车最优路径的选择办法;最终目的是为城市的晚归人群提 供安全便利的公共交通服务，使得城市生活更加方便快捷。
[0014] 所述的城市分割方法，将泰森多边形分割法运用到了城市区域分割中，该方法将 城市的大量的重要路口作为初始离散点，然后将城市分为若干个泰森多边形。且这些泰森 多边形离城市中心越近，则面积越小，反之则越大。
[0015] 所述的高效率的合并和分割方法，在用泰森多边形分割法将城市分割成若干个泰 森多边形后，为了保证其形成的类的面积大小和上下车点数量的一致性，对这些泰森多边 形进行合并和分割。合并的方法为仅通过简单的邻接规则以及出租车上下车点数量排序而 进行，即由上下车数量最大的泰森多边形开始按照排序顺序合并与之相邻的其余泰森多边 形，直至整个城市初步形成若干个区域;然后再对其中面积大小以及乘客流量数过大的区 域进行重新分割，在分割的时候主要考虑到该区域自身的特点，如当该区域自身长大于宽 时，对其进行纵向分割，反之，则进行横向切割;通过合并和分割后，得到面积大小以及乘客 流量均适合的热点区域。
[0016] 由泰森多边形分割法形成的泰森多边形本身具有面积特征，并且这些特征具有现 实世界中城市的区域特点；即在同一城市区域的泰森多边形，它的邻接泰森多边形面积大 小与其相近；因此，我们在选取候选站点时，站点之间的距离也不是一成不变的，而是根据 其所处的区域特色进行调整，即城市中心区域的公交站点数量多，且间距短；反之，则数量 少，间距长。
[0017] 定义了泰森多边形的关联度;根据同一热点区域内每个泰森多边形的关联度的值 和上车点的数量定义了其成为候选站点的可能性；因此，挑选可能性最大的泰森多边形作 为候选公交站点;每个热点区域有且仅有一个候选公交站点。
[0018] 清晰的定义了任意源点终点对之间的匹配度，该匹配度主要由任意源点终点对之 间路径的支持度以及乘客流量比例组成。
[0019] 在给定路径源点和终点的情况下，我们将该两点之间的所有获选公交站点建造了 一个初始有向图；其中每个结点代表一个候选公交站点，每条有向边，代表一条有方向的路 径。
[0020] 提出了四个在给定源终点的情况下能得到所有可能路径的约束条件;根据约束条 件，我们可以初步去除那些不可能的候选公交车站点，简化初步有向图。
[0021] 提出了两个规则来去除无效的路径，一个是不曲折规则，另一个是出入度值规则， 从而得到了源点终点之间的所有有效路径。
[0022] 提出了一种基于概率的扩散算法以及一种基于概率的双向扩散算法;前者能挑选 出单向的公交车最优路径，后者能挑选出双向的公交最优车路径。
[0023]进一步，从另外一个角度而言:该技术方案可以分为两个部分，一个是候选公交车 站点的设定，另一个是公交车最优路径的选择。第一部分又可以分为四个部分:泰森多边形 分割；热点泰森多边形选择;热点区域建立;候选公交站点设定。同时第二部分也可分为四 个部分:源点终点定义;有向图构建;有效路径选择;最优路径生成。具体而言：
[0024]所述的泰森多边形分割，是指同一平面上的N个离散点按照最邻近原则将该平面 划分为N个大小不一的泰森多边形。每个泰森多边形中间有且仅有一个离散点，且该泰森多 边形内所有的点都距该离散点最近。因此，本发明将城市交通路网中的关键路口作为泰森 多边形的离散点，将整个城市分成了若干泰森多边形。城市中心的泰森多边形面积小，而郊 区则面积大。运用泰森多边形分割法的优势是考虑到了城市交通路网的拓扑结构，该拓扑 结构对于建立城市公交车网至关重要。因此，该分割法能使城市的初步划分更为合理。
[0025 ]所述的热点泰森多边形选择，是指从上述初步 生成的泰森多边形中挑选出热点泰 森多边形。先分别统计了每个泰森多边形中的出租车上下车点的数量。由于地理因素限制， 大多数泰森多边形中出租车上下车点的数量为零，比如河流，山川等等。然后将出租车上下 车点数量不为零的泰森多边形挑选出来，计算了其每小时上下车点数量的累积分布概率， 将超过某个阈值的泰森多边形定义为热点泰森多边形。
[0026] 所述的热点区域建立，是指将上述热点泰森多边形经过合并和分离后，生成若干 个热点区域;该热点区域中包含着数量相近的出租车上下车点。首先，分别统计上述的热点 泰森多边形中的出租车上下车点的数量，并对其进行降序排序。然后选择排在第一位的泰 森多边形去合并与其地理位置上相邻的所有其它泰森多边形;然后再选择下一个泰森多边 形重复上述过程。通过此方法，初步可以得到若干个热点区域。但是由于有些热点区域中包 含的上下车点的数量太多，即该区域中的乘客需求太大，在该区域中仅仅设立一个公交站 点根本满足不了需求，这样就会造成公交站点设定的不合理。因此，必须将这些初步获得的 热点区域进行分割，以保证每个区域拥有相近的上下车点数量。其次考虑到地理因素，将长 度大于宽度的区域进行纵向切割，反之则进行横向切割;长度和宽度相近的则先随机进行 分割一次，然后再按上述方法进行分割。通过此方法，获得了上下车点数量在某个范围内的 若干热点区域;该范围由城市中每个时段具体的公交车乘客需求量决定。
[0027] 所述的候选公交站点设定，即从上述获得的热点区域中选定候选公交站点，每个 热点区域中有且仅有一个候选公交站点。首先，定义了泰森多边形的密度D(V 1)，该值表示 第i个热点泰森多边形Vi的邻接热点泰森多边形的数量。对于一个有k边泰森多边形而言， 其密度D(V 1)的值为Ο-k。然后，将热点区域中每个泰森多边形V1成为候选公交站点的可能性 定义为P(V 1)I(V1)是根据一定的权值比重综合每个泰森多边形的密度D(V1)的比值以及它 们的上下车点数量N(V 1)的比值而得到的值，可用以下公式计算：
[0029] 奶和《2分别为每个泰森多边形的密度D(Vi)的比值的权重以及它们的上下车点数 量比值的权重。ZiUiV(A)则表示η个泰森多边形的上下车点数量的累加和，即总的上下车 点数量。该权重的值可由多次实验结果得到。最后，选择P(V 1)值最大的泰森多边形中的关 键路口作为候选的公交站点。
[0030] 所述的源点终点定义，即在上述候选公交站点之间挑选出公交车路径的源点和终 点。公交车站点源点和终点的选择对公交车网的设计十分重要，也是公交车路径选择问题 的基础步骤。结合实际情况，城市中的公交车路线一般具有区域特色，即城市的公交车一般 会在特定的区域行驶。而泰森多边形的面积大小是与交通路口的密集程度具有直接关联 的。因此，根据泰森多边形的面积特色将相邻的面积大小相近的泰森多边形进行合并，形成 一定大小的区域。这样，得到了若干个区域。而公交车源点终点的则在位于上述这些区域的 边界地带的候选公交车站点之间挑选。边界地带指的是与其他区域相邻的泰森多边形组成 的地带。接着，分别计算这些处于边界地带的候选公交车站点的出度和入度的值。将其中入 度为零的候选公交车站点设为源点，出度为零的候选公交车站点设为终点。用此种方法，定 义出了公交车路线的源点和终点。
[0031] 所述的有向图构建，即将上述挑选出的候选公交站点构建成一个有向图，从而进 行公交车最优路径的选择。在该有向图中，每个结点代表一个候选公交车站点，每条有向边 代表一条带有方向的路径。即在两个相邻的候选站点之间如果存在乘客流量，则用一条边 将其连接起来，否则没有边;该边的方向则根据乘客流量的方向确定，即出租车行驶的方 向。因此，在上述一个区域间的所有源点终点之间构建有向图，同时计算从第i个源点到第j 个终点路径的支持度以及该路径的乘客流量数占总的乘客流量数的比例，将这两项进 行累加则得到该路径的源点和终点的匹配值M(r^)，可用以下公式计算：
[0033] 其中，R表示同一区域中从任意源点到任意终点的所有路径集合，I R|则表示该集 合的数量，而如叩&七1^^，1〇|则表示路径^,座集合1?中出租车行驶的次数。即该公式表 示从某个源点到某个终点的路径行驶次数占总数的比例，即为该路径的支持度。pf(r^)为 路径ru的乘客流量数，
则为该区域总的乘客流量数。根据源点的密度进行 排序，从密度值最大的源点开始，分别计算该源点到其它终点匹配度，选择与该源点匹配值 最大的终点。用此种方法，得出了源点终点之间的对应关系。然后，在源点终点对关系确定 的情况下，将其中没有对应终点的源点和没有对应源点的终点去除。在得到源点终点对之 后，重新构建有向图；首先，去除不在给定源点终点对之间的候选公交站点，接着去除不符 合该源点到终点行驶方向的结点和路径;因此，构建成初始有向图。
[0034] 所述的有效路径选择，是在上述初步有向图的基础下，根据四个约束条件和两个 规则去除掉给定源点终点对之间的所有无效路径，从而得到所有有效路径。所述的这四个 约束条件用于从给定源点终点对之间的所有候选公交车站点之间挑选出有效的候选公交 站点;而两个规则用于在上述有效候选公交车站点之间挑选出有效路径。
[0035] 其中，所述的这四个约束条件为:每一个挑选的节点都应该远离起始点，不断的接 近终点，同时远离在此之前的节点，并且每个站点之间必须保持一定的合适的距离。即候选 站点在源点到终点方向上的映射值是不断增长的。因此，我们去除不满足这四个约束条件 的候选公交站点，从而得到了所有有效的候选公交站点。
[0036] 所述的两个规则为不曲折规则和出入度规则。具体而言，第一个规则为去掉在源 点终点间曲折反复的路径，即保证该源点终点间所有路径的平滑性。第二个规则为计算每 个结点的出入度，将出度和入度任意一个为零或者都为零的值去掉。从而保证在给定源点 终点的一个有向图中，只有一个入度为零的结点，即为源点；和一个出度为零的结点，即为 终点。通过上述方法，去掉了给定源点终点的路径中的无效路径，从而得到了有效路径。
[0037] 所述的最优路径生成，则是在上述有效路径中生成最优路径。最优路径是指能在 更少的行驶时间内能搭载更多乘客的路径。基于这个目的，我们提出两个算法，一个是单向 最优路径选择算法，另一个是双向路径选择算法。
[0038] 单向最优路径选择算法，其核心思想是根据所有候选的公交站点被设为公交站点 的概率值来选择公交站点。因此，根据每个候选站点之间的乘客流量数用以下公式定义了 该条件概率：
[0040]其中，是指第i个可能的候选站点，而ni，n2，···，nj表示的是丨之前的所有历史站 点；//(/?,"乂)是结点nm到候选结点《之间的乘客流量，
I.则是指<之前所有 历史站点到某个候选站点4的乘客流量之和。#是结点如的所有可能的下一个站点的集合， 即是结点W在图中所有的孩子结点，而|Nl则指的是所有可能站点的数量。则
则表示所有历史站点到所有获选站点η丨的乘客流量之和。因此上述 公式表示的是某个获选站点与历史轨迹的乘客流量之和在所有获选站点与历史轨迹站点 的全部乘客流量之和所占的比例，该值越大，则表明某个候选站点成为下一个候选站点的 概率越大。并且，运用这个方法，下一个站点的确立不仅仅由当前站点决定，而是由所有的 同一条路径中的历史站点决定的。另外，每次都挑选概率排在前m的候选站点作为下一个站 点。因此，对于要经过η个站点的路径来说，该算法总共会产生m n条路径。最后，再通过计算 每条路径的运行时间以及总的最大载客数，在一定的时间限度内，挑选出乘客流量最大的 路径，即该路径为最优路径。
[0041]双向最优路径选择算法，其思想是在两个 相反的方向上分别运行上述单向最优路 径选择算法，从而得到两个方向上所有可能的路径，即能得到2mn条候选路径;然后计算这 些候选路径的运行时间和最大载客数，从而挑选出最优路径。该算法主要是考虑到双向路 径上的乘客需求的差异性，因为乘客需求是随着时间不断的在变化的。而实际生活中，公交 车都是沿着相同的路径来回行驶的，因此，必须综合考虑到两个方向上的情况，从而能生成 对双向路线而言最优的路径。
[0042]由于采用了上述技术方案，本发明提出的基于出租车轨迹的夜班公交车路径选择 方法，具有以下有益效果：
[0043] 1)将城市的出租车GPS数据用于公交车站点的设计，出租车和公交车均为城市中 两种主流的公共交通工具，它们之间具有一定程度上的相似性和共通性。并且，出租车相对 于公交车而言，更加能直观的反应城市居民的出行需求。再者，出租车乘客通常会在城市的 公交路线或者地铁路线不能直接或者不能到达其目的地时才选择乘坐出租车。因此，用出 租车数据来设计公交车站点更能满足城市居民的需求。
[0044] 2)采用了泰森多边形分割法来对城市进行分割，并将城市交通路网中的重要路口 作为泰森多边形的离散点。用此种方法，充分考虑到了城市交通路网的实际情况，并能通过 泰森多边形的面积很直观的反映城市中心和城郊的区别。因此在选择路径的源点和终点的 时候，能根据区域特色划分，使公交车站点的设计更加人性化。
[0045] 3)设计了一种新的方法去定义城市中的热点区域，从而能从中挑选出候选公交车 站点。该方法根据每个泰森多边形中出租车上下乘客的数量从城市中定义出若干个大小合 适的热点区域，每个热点区域具有相近的出租车上下乘客的数量。用这种方法，保证了每个 候选公交站点的乘客数量的合理性。
[0046] 4)提出了一种新的方法去选择公交车最佳行驶路径，使得公交车能在一定的时间 限度内搭载更多的乘客，以满足更多人的需求。该方法不同于最短路径的选择，因为不仅仅 考虑行驶的时间，同时还考虑乘客需求量、公交车站点建造成本等等因素。因此，本发明的 方法更加符合实际情况。
[0047] 5)提出了一种新的准确定义公交车路线源点终点对的方法，该方法充分考虑到了 公交车行驶路线的区域特性，以及源点终点对之间路径的支持度和乘客流量数，即前文中 定义的源点终点的匹配度。用这种方法选出的源点终点对既符合城市中实际的交通路况， 也能更加满足乘客的需求。
[0048] 6)分别提出了单向和双向公交车最优路线规划的方法。大多数公交车路线设计方 案都仅仅考虑单向的行驶路线，另外一个方向通常都只是简单的反向行驶而已。但实际上， 乘客需求是随着时间以及目的地的变化而变化的，并不能一概而论。因此，本发明综合考虑 了公交车的双向行驶路线，从而使得公交车双向行驶过程中搭载的乘客数量最大。
【附图说明】
[0049] 图1为本发明的系统架构图。
[0050] 图2A为本发明方法的区域分割示例图（合并后的大区域）。
[0051] 图2B为本发明方法的区域分割示例图（分割成四个子区域）。
[0052]图3为泰森多边形关联度计算示例图。
[0053]图4为四个约束条件示例图。
[0054] 图5A为源点终点对匹配示例图（源点终点匹配前）。
[0055] 图5B为源点终点对匹配示例图（源点终点匹配后）。
[0056] 图6 A为在给定源点终点的情况下有向图生成和有效路径选择示例图（初始有向 图）。
[0057] 图6B为在给定源点终点的情况下有向图生成和有效路径选择示例图（修剪后的有 向图）。
【具体实施方式】
[0058] 下面结合附图所示实施例对本发明做进一步说明。
[0059] 请参阅图I，本发明的系统架构图，本发明可分为两个子部分:候选公交站点设定 以及最优公交路线选择。
[0060] 每个子部分又分为四个子部分:候选公交站点设定部分包括泰森多边形分割、热 点泰森多边形选择、热点区域建立和候选公交站点设定;最优公交路线选择部分包括源点 终点定义、有向图构建、有效路径选择和最优路径生成。
[0061] 图2A为上述热点区域建立过程中热点泰森多边形形成的初步热点区域，该热点区 域面积较大，因此对其进行分割，如图2B所示。按照前文所述方法，将其分割成四个大小合 适，且乘客流量数相近的四个子区域。
[0062] 请参阅图3,为泰森多边形关联度计算示例图。
[0063] 其中编号为1的泰森多边形为七边形，则它有七个邻接泰森多边形编号分别为2， 3，4，5，6，7，8。根据上述关联度的定义，该泰森多边形的关联度的值在0-7之间。而在其七个 邻接泰森多边形中，为邻接泰森多边形有三个，分别是编号为3，5，6的泰森多边形;编号2， 4,7,8的泰森多边形则为普通的泰森多边形。因此，根据定义，编号1的泰森多边形的关联度 值为3。
[0064] 请参阅图4,为四个约束条件示例图。
[0065] 其中圆圈S代表该路径源点，圆圈D则代表终点；圆圈1，2，3，4代表中间的候选公交 站点。满足四个约束条件即如图所示，后一个候选公交站点坐标在S-D方向的映射值大于前 一个候选公交站点。
[0066] 请参阅图5A和图5B，为源点终点对匹配示例图。
[0067]其中左图为源点终点匹配前的图，右图为源点终点匹配后图；左图中有三个源点 S1,&，&，两个源点D1, D2,在它们之间有很多候选公交车站点。在上述匹配过程结束后，产生 了两个源点终点对S1-D 2，S2-D2，如右图所示。
[0068] 请参阅图6A和图6B，为在给定源点终点的情况下有向图生成和有效路径选择示例 图。
[0069] 在源点终点已经确定的情况下，图中圆圈S和D分别代表某路径的源点和终点，中 间其它的点代表它们之间存在的所有的候选公交站点。图6A为初步建成的有向图，而图6B 则为经过前文所述的挑选过程后，得到的所有有效路径。
[0070] 本实施例1中，所述的候选公交车站点的设定中，用泰森多边形分割法对城市进行 分割。其中，要以城市重要的路口作为泰森多边形的离散点。根据我国的《公路工程技术标 准》所述，公路可分为高速公路、一级公路、二级公路、三级公路、四级公路五个等级。而本发 明中所述的重要路口至少为二级公路及以上的公路所形成的路口。具体而言，可根据公路 等级对其进行赋值，如高速公路赋值为5,然后依次递减，四级公路为1。然后将组成某个路 口的平均公路等级作为该路口的等级，例如由高速公路和一级公路组成的二叉路，则路口 的等级戈
接下来，我们再统计出各个路口每天的平均车流量，可以以一年的观 察时间为标准计算平均车流量。将某个路口的等级值与其每天平均车流量值进行相乘得到 该路口的重要值，并对重要值进行排序。最后，根据实际情况，选择排名前N个路口作为重要 路口，将城市分为若干个泰森多边形。
[0071] 本实施例1中，所述的候选公交车站点的设定中，关于热点泰森多边形的选择中涉 及到阈值的设定。该阈值的大小决定了热点泰森多边形的数量，从而间接影响了热点区域 的数量，也就是候选公交车站点的数量。而在实际情况中，由于存在着湖，山，建筑群等，几 乎90%以上的热点泰森多边形中上下车数量是为零的。为了保证公交车路线几乎可以覆盖 整座城市，我们选取的热点泰森多边形应该足够多，至少占所有有上下车数量的泰森多边 形总数的90%，全部泰森多边形数量的0.5%以上。因此，该阈值要根据该城市的实际情况， 并在保证热点泰森多边形占上下车点数量不为0的全部泰森多边形的90%的情况下选取。
[0072] 本实施例1中，所述的 候选公交车站点的设定中，关于热点区域的建立问题，其中 涉及到热点区域的面积和乘客流量数的设定。本发明中，热点区域的大小并不是固定的，而 是根据实际情况中该城市的区域特点决定的。这也同样是所述的候选公交车站点的设定 中，采用泰森多边形分割法的优势之一。因为泰森多边形的面积本身就是大小不一的，且越 靠近城市中心面积越小，反之则越大。这一特点也符合城市公交运输规则，城市中心地带公 交站点相隔距离短，且站点多；而城郊地带公交站点之间距离相对长，且站点少。因此，本发 明在保证每个站点的乘客流量数相近的情况下，根据泰森多边形的面积大小大致的确定该 区域的人口密度。在人口密度大小差不多的区域内，热点区域的面积大小一致，则公交站点 之间的距离相等。即公交站点之间的距离并不是一成不变的；人口越密集，热点区域面积越 小，则该区域的公交站点之间的距离越近;反之，则面积越小，公交站点之间的距离越远。则 热点区域的面积要根据城客流量数进行合并和分割等调整。
[0073] 本实施例1中，所述的候选公交车站点的设定中，在选取候选公交车站点时权值Wi 和W2设定并不能对候选公交车站点的数量造成影响，仅仅能影响到候选公交车站点的经炜 度。而候选公交站点的地理位置选择，首先要考虑的是该区域人口密度的分布情况。我们应 该尽量选择人口密度相对集中的位置，因为人对到站点的步行距离有一定的容忍值。根据 调查，该值大致在500m左右。其次要考虑到的是与其它站点之间的距离，如前述所说，我们 要保证人口密度大小相等时站点之间的距离相等。然后，在多次反复试验中，选取满足上述 两个条件的最优权值。
[0074] 本实施例2中，所述的公交车最优路径的选择，在建立源点和终点的映射时，我们 应该考虑到公交车的行驶时间。在实际生活中，公交车的行驶时间一般在半个小时到一个 半小时的范围内。因此，源点终点对之间的距离既不能太远，也不能太近。本发明用的是出 租车的数据，在进行公交车行驶时间估算的时候要注意进行速度转化。一般而言，出租车的 行驶速度是公交车的1.5倍。
[0075] 本实施例2中，所述的公交车最优路径的选择，在生成最优路径的生成过程中，对 中间站点数量的选择需要考虑到站点之间的距离以及站点建造成本。为了满足更多乘客的 需求，原则上我们应该使中间站点数量更多。但是中间站点的增加会增加整体的行驶时间， 同时也会增加建造成本。因此，我们应该结合实际情况，在保证整体行驶时间的情况下，在 中间站点数量选择和站点建造成本之间找到一个平衡点。该平衡点可通过反复实验得到。
[0076] 本实施例2中，所述的公交车最优路径的选择，在实际建造公交车站点的时，由于 本发明采用的是出租车的GPS数据，因此得考虑到出租车与公交车之间的差别。在很多城市 的道路规划中，出租车与公交车行驶的路线与允许停靠的位置是不同的。因此，得结合具体 城市的实际情况建造公交车站点。在本方案中得出的公交站点建造地点不能用时，应该选 择与该地点相近的地点，且不能对路线的规划造成影响。
[0077]上述的对实施例的描述是为便于该技术领域的普通技术人员能理解和应用本发 明。熟悉本领域技术的人员显然可以容易地对这些实施例做出各种修改，并把在此说明的 一般原理应用到其他实施例中而不必经过创造性的劳动。因此，本发明不限于这里的实施 例，本领域技术人员根据本发明的揭示，不脱离本发明范畴所做出的改进和修改都应该在 本发明的保护范围之内。
【主权项】
1. 一种夜班公交车站点及路径选择方法，其特征在于:包括候选公交站点设定的方法 和公交车最优路径的选择方法； 所述候选公交站点设定的方法是指利用出租车的上下车的位置信息来定义城市中的 热点区域，然后从每个热点区域中挑出一个候选公交车站点；所述公交车最优路径的选择 办法是指将候选站点和行驶路径的方向和距离构建成有向图，然后通过单向最优路径算法 和双向路径选择算法，分别得出单向和双向的公交车行驶的最优路径。2. 根据权利要求1所述的夜班公交车站点及路径选择方法，其特征在于： 将泰森多边形分割法运用到城市区域分割中，该方法将城市的大量的重要路口作为初 始离散点，然后将城市分为若干个泰森多边形;且这些泰森多边形离城市中心越近，则面积 越小，反之则越大； 优选的，关于合并和分割方法:在合并时仅通过简单的邻接规则以及出租车上下车点 数量排序而进行，即由上下车数量最大的泰森多边形开始按照排序顺序合并与之相邻的其 余泰森多边形，直至整个城市初步形成若干个区域;然后再对其中面积大小以及乘客流量 数过大的区域进行重新分割，在重新分割的时候主要考虑到该区域自身的特点，；通过合并 和分割后，得到面积大小以及乘客流量均适合的热点区域； 优选的，在重新分割的时候，当该区域自身长大于宽时，对其进行纵向分割，反之，则进 行横向切割。3. 根据权利要求2所述的夜班公交车站点及路径选择方法，其特征在于： 选取候选站点时，站点之间的距离不是一成不变的，而是根据其所处的区域特色进行 调整； 优选的，城市中心区域的公交站点数量多，且间距短;反之，则数量少，间距长。4. 根据权利要求2所述的夜班公交车站点及路径选择方法，其特征在于： 定义泰森多边形的关联度;根据同一热点区域内每个泰森多边形的关联度的值和上车 点的数量定义其成为候选站点的可能性;优选的，挑选可能性最大的泰森多边形作为候选 公交站点;优选的，每个热点区域有且仅有一个候选公交站点。5. 根据权利要求2所述的夜班公交车站点及路径选择方法，其特征在于： 定义任意源点终点对之间的匹配度，该匹配度主要由任意源点终点对之间路径的支持 度以及乘客流量比例组成； 优选的，在给定路径源点和终点的情况下，将该两点之间的所有获选公交站点建造了 一个初始有向图；其中每个结点代表一个候选公交站点，每条有向边，代表一条有方向的路 径； 优选的，提出四个在给定源终点的情况下能得到所有可能路径的约束条件;根据约束 条件，初步去除那些不可能的候选公交车站点，简化初步有向图； 优选的，提出两个规则来去除无效的路径，一个是不曲折规则，另一个是出入度值规 贝IJ，从而得到了源点终点之间的所有有效路径； 优选的，提出一种基于概率的扩散算法以及一种基于概率的双向扩散算法;通过前者 挑选出单向的公交车最优路径，通过后者挑选出双向的公交最优车路径。6. 根据权利要求1所述的夜班公交车站点及路径选择方法，其特征在于： 所述候选公交站点设定的方法包括四个部分:泰森多边形分割、热点泰森多边形选择、 热点区域建立、候选公交站点设定;所述公交车最优路径的选择办法包括四个部分:源点终 点定义、有向图构建、有效路径选择、最优路径生成。7. 根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的泰森多边形分割，是指同一平面上的N个离散点按照最邻近原则将该平面划分 为N个大小不一的泰森多边形;每个泰森多边形中间有且仅有一个离散点，且该泰森多边形 内所有的点都距该离散点最近； 优选的，将城市交通路网中的关键路口作为泰森多边形的离散点，将整个城市分成了 若干泰森多边形;优选的，城市中心的泰森多边形面积相对小，而郊区则面积相对大； 优选的，所述的热点泰森多边形选择，是指从上述初步生成的泰森多边形中挑选出热 点泰森多边形;先分别统计了每个泰森多边形中的出租车上下车点的数量;然后将出租车 上下车点数量不为零的泰森多边形挑选出来，计算其每小时上下车点数量的累积分布概 率，将超过某个阈值的泰森多边形定义为热点泰森多边形。8. 根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的热点区域建立，是指将上述热点泰森多边形经过合并和分离后，生成若干个热 点区域;该热点区域中包含着数量相近的出租车上下车点；首先，分别统计上述的热点泰森 多边形中的出租车上下车点的数量，并对其进行降序排序;然后选择排在第一位的泰森 多 边形去合并与其地理位置上相邻的所有其它泰森多边形;然后再选择下一个泰森多边形重 复上述过程，通过此方法，初步得到若干个热点区域； 优选的，由于有些热点区域中包含的上下车点的数量太多，即该区域中的乘客需求太 大，在该区域中仅仅设立一个公交站点根本满足不了需求，这样就会造成公交站点设定的 不合理；需要将这些初步获得的热点区域进行分割，以保证每个区域拥有相近的上下车点 数量;其次考虑到地理因素，将长度大于宽度的区域进行纵向切割，反之则进行横向切割； 长度和宽度相近的则先随机进行分割一次，然后再按上述方法进行分割;通过此方法，获得 了上下车点数量在某个范围内的若干热点区域;该范围由城市中每个时段具体的公交车乘 客需求量决定； 优选的，所述的候选公交站点设定，即从上述获得的热点区域中选定候选公交站点，每 个热点区域中有且仅有一个候选公交站点；首先，定义了泰森多边形的密度D(Vi)，该值表 示第i个热点泰森多边形V i的邻接热点泰森多边形的数量;对于一个有k边泰森多边形而 言，其密度D(V1)的值为Ο-k;然后，将热点区域中每个泰森多边形^成为候选公交站点的可 能性定义为P(V 1) ;P(Vl)是根据一定的权值比重综合每个泰森多边形的密度D(V1)的比值以 及它们的上下车点数量N(V 1)的比值而得到的值，采用以下公式计算：?:和抑分别为每个泰森多边形的密度D(V1)的比值的权重以及它们的上下车点数量比 值的权重。则表示η个泰森多边形的上下车点数量的累加和，即总的上下车点数 量;该权重的值可由多次实验结果得到；最后，选择P(V1)值最大的泰森多边形中的关键路 口作为候选的公交站点。9. 根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的源点终点定义，即在上述候选公交站点之间挑选出公交车路径的源点和终点； 根据泰森多边形的面积特色将相邻的面积大小相近的泰森多边形进行合并，形成一定大小 的区域;得到了若干个区域;公交车源点终点则在位于上述这些区域的边界地带的候选公 交车站点之间挑选;边界地带指的是与其它区域相邻的泰森多边形组成的地带;接着，分别 计算这些处于边界地带的候选公交车站点的出度和入度的值;将其中入度为零的候选公交 车站点设为源点，出度为零的候选公交车站点设为终点，用此种方法定义出公交车路线的 源点和终点； 优选的，所述的有向图构建，即将上述挑选出的候选公交站点构建成一个有向图，从而 进行公交车最优路径的选择;在该有向图中，每个结点代表一个候选公交车站点，每条有向 边代表一条带有方向的路径；即在两个相邻的候选站点之间如果存在乘客流量，则用一条 边将其连接起来，否则没有边;该边的方向则根据乘客流量的方向确定，即出租车行驶的方 向； 优选的，在上述一个区域间的所有源点终点之间构建有向图，同时计算从第i个源点到 第j个终点路径的支持度以及该路径的乘客流量数占总的乘客流量数的比例，将这两项 进行累加则得到该路径的源点和终点的匹配值M(r^)，采用以下公式计算：其中，R表示同一区域中从任意源点到任意终点的所有路径集合，I Rl则表示该集合的 数量，而|1^叩&让(^^，1〇|则表示路径以^在集合1?中出租车行驶的次数；即该公式表示从 某个源点到某个终点的路径行驶次数占总数的比例，即为该路径的支持度;pf(r^)为路径 r i, j的乘客流量数，则为该区域总的乘客流量数； 优选的，根据源点的密度进行排序，从密度值最大的源点开始，分别计算该源点到其它 终点匹配度，选择与该源点匹配值最大的终点；用此种方法，得出了源点终点之间的对应关 系;然后，在源点终点对关系确定的情况下，将其中没有对应终点的源点和没有对应源点的 终点去除；在得到源点终点对之后，重新构建有向图；首先，去除不在给定源点终点对之间 的候选公交站点，接着去除不符合该源点到终点行驶方向的结点和路径;构建成初始有向 图。10.根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的有效路径选择，是在上述初步有向图的基础下，根据四个约束条件和两个规则 去除掉给定源点终点对之间的所有无效路径，从而得到所有有效路径;所述的这四个约束 条件用于从给定源点终点对之间的所有候选公交车站点之间挑选出有效的候选公交站点； 而两个规则用于在上述有效候选公交车站点之间挑选出有效路径； 优选的，所述的这四个约束条件为:每一个挑选的节点都应该远离起始点，不断的接近 终点，同时远离在此之前的节点，并且每个站点之间必须保持一定的合适的距离；即候选站 点在源点到终点方向上的映射值是不断增长的;去除不满足这四个约束条件的候选公交站 点，从而得到了所有有效的候选公交站点； 优选的，所述的两个规则为不曲折规则和出入度规则；第一个规则为去掉在源点终点 间曲折反复的路径，即保证该源点终点间所有路径的平滑性;第二个规则为计算每个结点 的出入度，将出度和入度任意一个为零或者都为零的值去掉;从而保证在给定源点终点的 一个有向图中，只有一个入度为零的结点，即为源点；和一个出度为零的结点，即为终点;通 过上述方法，去掉了给定源点终点的路径中的无效路径，从而得到了有效路径； 优选的，所述的最优路径生成，则是在上述有效路径中生成最优路径;最优路径是指能 在更少的行驶时间内能搭载更多乘客的路径;基于这个目的，通过以下两个算法来加以解 决:一个是单向最优路径选择算法，另一个是双向路径选择算法； 优选的，所述单向最优路径选择算法，是根据所有候选的公交站点被设为公交站点的 概率值来选择公交站点;根据每个候选站点之间的乘客流量数用以下公式定义了该条件概 率：其中，W是指第i个可能的候选站点，而ni，n2,. . .，nj表示的是W〖.之前的所有历史站点； #(?",,<)是结点nm到候选结点/{之间的乘客流量，则是指 之前所有历 史站点到某个候选站点nf啲乘客流量之和;#是结点的所有可能的下一个站点的集合， 即是结点W在图中所有的孩子结点，而|Nl则指的是所有可能站点的数量。则.则表示所有历史站点到所有获选站点的乘客流量之和；因此上述 公式表示的是某个获选站点与历史轨迹的乘客流量之和在所有获选站点与历史轨迹站点 的全部乘客流量之和所占的比例，该值越大，则表明某个候选站点成为下一个候选站点的 概率越大;并且，运用这个方法，下一个站点的确立不仅仅由当前站点决定，而是由所有的 同一条路径中的历史站点决定的；另外，每次都挑选概率排在前m的候选站点作为下一个站 点;对于要经过η个站点的路径来说，该算法总共会产生#条路径;最后，再通过计算每条路 径的运行时间以及总的最大载客数，在一定的时间限度内，挑选出乘客流量最大的路径，即 该路径为最优路径； 优选的，所述双向最优路径选择算法，是在两个相反的方向上分别运行上述单向最优 路径选择算法，从而得到两个方向上所有可能的路径，即能得到2mn条候选路径;然后计算 这些候选路径的运行时间和最大载客数，从而挑选出最优路径。
【专利摘要】一种夜班公交车站点及路径选择方法，包括候选公交站点设定的方法和公交车最优路径的选择方法；所述候选公交站点设定的方法是指利用出租车的上下车的位置信息来定义城市中的热点区域，然后从每个热点区域中挑出一个候选公交车站点；所述公交车最优路径的选择办法是指将候选站点和行驶路径的方向和距离构建成有向图，然后通过单向最优路径算法和双向路径选择算法，分别得出单向和双向的公交车行驶的最优路径。本发明可以协助完善城市公交车服务系统，给相关人群提供更多便利，同时也能提高效率。
【IPC分类】G06Q10/04, G08G1/00
【公开号】CN105489000
【申请号】CN201510897666
【发明人】张大强, 范珂
【申请人】同济大学
【公开日】2016年4月13日
【申请日】2015年12月8日
【技术领域】
[0001] 本发明属于交通技术领域，涉及数据挖掘中热点的定义和图论领域中最优路径的 选择。 技术背景
[0002] 公共汽车往往是城市生活中最流行的交通工具，它不仅能减少交通拥堵，此外也 能降低尾气的排放。在大多数城市中，白天的公交车设施已经做到非常完善了，但是在晚 间，大部分城市都没有相对完整的公交车系统，这也导致了出租车成为晚间人们出行的最 佳选择。基于此，我们可以利用出租车行驶的信息来帮助我们设计晚间公交系统。
[0003] 使用出租车行驶信息有两大好处:首先由于成熟的GPS技术，我们可以获得大量的 出租车行驶信息，包括行驶时间，行驶速度，行驶地点，车载的人数，上下车地点等待，通过 挖掘出租车信息，进而获得晚间人们出行规律。此外出租车数据是实时更新的，当城市不断 发展变化，出租车数据也会发生相应的变化，这样我们就可以更有针对性的做出动态调整。
[0004] 基于出租车数据挖掘往往可以分为3类，社会动态挖掘，交通动态挖掘以及行为动 态挖掘。其中社会动态挖掘主要是研究城市人口的集体行为并观察人们的行为规律，可以 协助城市管理员更好的管理、设计、维护以及更新城市的基础设施。目前的研究包括:人们 的出行区域，城市的热点区域，热点区域的功能分类以及城市不同区域关联度等等。交通动 态挖掘就是分析城市交通道路网的流量变化。目前的研究包括交通流的离散点，实时的交 通路况预测以及估计出行时间等等。行为动态挖掘主要是基于出租车司机对城市的经验来 分析出不正常或者高效的出行行为。目前的研究包括最快找到乘客或者出租车，推荐最快 到达目的地的行驶路线，规划公交车路线以及监测不正常行驶行为等等。
[0005] 城市交通网设计也是城市规划和交通领域中的一个研究热门领域。公交网设计问 题是一个复杂的，非线性的，非凸的，多目标的NP-hard问题。设计目标多种多样，常见的有 如何在时间，容量以及资源的限制条件下，追求最短路径，最短行驶时间，最低操作代价，最 大客流，最大的区域覆盖面积以及最大的安全系数等等。这些目标和用户需求之间往往都 存在一定的冲突，因此需要在这些目标之间找到一个平衡点而不是单一的寻求最优值。早 期的公交车系统设计往往是在分析乘客的流动数量以及乘客的需求的基础上，根据设计者 自己的经验和直觉发展起来的。近来的相关工作同样假设乘客的流量可以由用户调查以及 人口估计计算得到，基于此，提出了很多复杂的优化算法，其中启发式的设计思想往往能够 得到近似最优解决方案。
【发明内容】
[0006] 本发明的目的在于利用城市出租车轨迹数据建立夜班公交车双向站点，并在考虑 公交车站点建造成本的情况下，能在一定的时间限制内使该路线搭载的乘客数量最大化。
[0007] 现代社会的城市公交车路网设计实际上已经发展得很完善了，但夜班公交车路线 规划是城市公交路网设计中容易忽略的一点。由于夜晚乘客需求量相对于白天而言要少很 多，因此很多公交车晚上会停运。另外城市公交车路网中几乎没有专门为夜班公交车设计 的站点或路线，夜晚运行的公交车往往也是沿着白天的路线运行的;但实际上，晚上公交车 的乘客需求跟白天公交车的乘客需求会有很大的差异。因此，本发明着眼于在夜班公交车 站点的建立以及夜班公交车路线的选择，其特点在于：
[0008] 1)从夜晚乘客乘坐的出租车的上下车点位置来挑选出可能的候选公交车站点。
[0009] 2)在一定的时间限度内使能搭载的乘客数量最大化。
[0010] 3)在公交车站点建设成本和搭载最多乘客这两者之间取均衡的结果。
[0011] 4)由于乘客流量是随着时间不断变化的，因此本发明将考虑夜晚不同时间槽内的 乘客流量变化。
[0012]为达到上述目的，本发明通过以下技术方案来加以实现：
[0013] -种基于出租车轨迹的夜班公交车路径选择方法，该方法包括了一种快速的候选 公交站点设定的方法和一种公交车最优路径的选择办法;最终目的是为城市的晚归人群提 供安全便利的公共交通服务，使得城市生活更加方便快捷。
[0014] 所述的城市分割方法，将泰森多边形分割法运用到了城市区域分割中，该方法将 城市的大量的重要路口作为初始离散点，然后将城市分为若干个泰森多边形。且这些泰森 多边形离城市中心越近，则面积越小，反之则越大。
[0015] 所述的高效率的合并和分割方法，在用泰森多边形分割法将城市分割成若干个泰 森多边形后，为了保证其形成的类的面积大小和上下车点数量的一致性，对这些泰森多边 形进行合并和分割。合并的方法为仅通过简单的邻接规则以及出租车上下车点数量排序而 进行，即由上下车数量最大的泰森多边形开始按照排序顺序合并与之相邻的其余泰森多边 形，直至整个城市初步形成若干个区域;然后再对其中面积大小以及乘客流量数过大的区 域进行重新分割，在分割的时候主要考虑到该区域自身的特点，如当该区域自身长大于宽 时，对其进行纵向分割，反之，则进行横向切割;通过合并和分割后，得到面积大小以及乘客 流量均适合的热点区域。
[0016] 由泰森多边形分割法形成的泰森多边形本身具有面积特征，并且这些特征具有现 实世界中城市的区域特点；即在同一城市区域的泰森多边形，它的邻接泰森多边形面积大 小与其相近；因此，我们在选取候选站点时，站点之间的距离也不是一成不变的，而是根据 其所处的区域特色进行调整，即城市中心区域的公交站点数量多，且间距短；反之，则数量 少，间距长。
[0017] 定义了泰森多边形的关联度;根据同一热点区域内每个泰森多边形的关联度的值 和上车点的数量定义了其成为候选站点的可能性；因此，挑选可能性最大的泰森多边形作 为候选公交站点;每个热点区域有且仅有一个候选公交站点。
[0018] 清晰的定义了任意源点终点对之间的匹配度，该匹配度主要由任意源点终点对之 间路径的支持度以及乘客流量比例组成。
[0019] 在给定路径源点和终点的情况下，我们将该两点之间的所有获选公交站点建造了 一个初始有向图；其中每个结点代表一个候选公交站点，每条有向边，代表一条有方向的路 径。
[0020] 提出了四个在给定源终点的情况下能得到所有可能路径的约束条件;根据约束条 件，我们可以初步去除那些不可能的候选公交车站点，简化初步有向图。
[0021] 提出了两个规则来去除无效的路径，一个是不曲折规则，另一个是出入度值规则， 从而得到了源点终点之间的所有有效路径。
[0022] 提出了一种基于概率的扩散算法以及一种基于概率的双向扩散算法;前者能挑选 出单向的公交车最优路径，后者能挑选出双向的公交最优车路径。
[0023]进一步，从另外一个角度而言:该技术方案可以分为两个部分，一个是候选公交车 站点的设定，另一个是公交车最优路径的选择。第一部分又可以分为四个部分:泰森多边形 分割；热点泰森多边形选择;热点区域建立;候选公交站点设定。同时第二部分也可分为四 个部分:源点终点定义;有向图构建;有效路径选择;最优路径生成。具体而言：
[0024]所述的泰森多边形分割，是指同一平面上的N个离散点按照最邻近原则将该平面 划分为N个大小不一的泰森多边形。每个泰森多边形中间有且仅有一个离散点，且该泰森多 边形内所有的点都距该离散点最近。因此，本发明将城市交通路网中的关键路口作为泰森 多边形的离散点，将整个城市分成了若干泰森多边形。城市中心的泰森多边形面积小，而郊 区则面积大。运用泰森多边形分割法的优势是考虑到了城市交通路网的拓扑结构，该拓扑 结构对于建立城市公交车网至关重要。因此，该分割法能使城市的初步划分更为合理。
[0025 ]所述的热点泰森多边形选择，是指从上述初步 生成的泰森多边形中挑选出热点泰 森多边形。先分别统计了每个泰森多边形中的出租车上下车点的数量。由于地理因素限制， 大多数泰森多边形中出租车上下车点的数量为零，比如河流，山川等等。然后将出租车上下 车点数量不为零的泰森多边形挑选出来，计算了其每小时上下车点数量的累积分布概率， 将超过某个阈值的泰森多边形定义为热点泰森多边形。
[0026] 所述的热点区域建立，是指将上述热点泰森多边形经过合并和分离后，生成若干 个热点区域;该热点区域中包含着数量相近的出租车上下车点。首先，分别统计上述的热点 泰森多边形中的出租车上下车点的数量，并对其进行降序排序。然后选择排在第一位的泰 森多边形去合并与其地理位置上相邻的所有其它泰森多边形;然后再选择下一个泰森多边 形重复上述过程。通过此方法，初步可以得到若干个热点区域。但是由于有些热点区域中包 含的上下车点的数量太多，即该区域中的乘客需求太大，在该区域中仅仅设立一个公交站 点根本满足不了需求，这样就会造成公交站点设定的不合理。因此，必须将这些初步获得的 热点区域进行分割，以保证每个区域拥有相近的上下车点数量。其次考虑到地理因素，将长 度大于宽度的区域进行纵向切割，反之则进行横向切割;长度和宽度相近的则先随机进行 分割一次，然后再按上述方法进行分割。通过此方法，获得了上下车点数量在某个范围内的 若干热点区域;该范围由城市中每个时段具体的公交车乘客需求量决定。
[0027] 所述的候选公交站点设定，即从上述获得的热点区域中选定候选公交站点，每个 热点区域中有且仅有一个候选公交站点。首先，定义了泰森多边形的密度D(V 1)，该值表示 第i个热点泰森多边形Vi的邻接热点泰森多边形的数量。对于一个有k边泰森多边形而言， 其密度D(V 1)的值为Ο-k。然后，将热点区域中每个泰森多边形V1成为候选公交站点的可能性 定义为P(V 1)I(V1)是根据一定的权值比重综合每个泰森多边形的密度D(V1)的比值以及它 们的上下车点数量N(V 1)的比值而得到的值，可用以下公式计算：
[0029] 奶和《2分别为每个泰森多边形的密度D(Vi)的比值的权重以及它们的上下车点数 量比值的权重。ZiUiV(A)则表示η个泰森多边形的上下车点数量的累加和，即总的上下车 点数量。该权重的值可由多次实验结果得到。最后，选择P(V 1)值最大的泰森多边形中的关 键路口作为候选的公交站点。
[0030] 所述的源点终点定义，即在上述候选公交站点之间挑选出公交车路径的源点和终 点。公交车站点源点和终点的选择对公交车网的设计十分重要，也是公交车路径选择问题 的基础步骤。结合实际情况，城市中的公交车路线一般具有区域特色，即城市的公交车一般 会在特定的区域行驶。而泰森多边形的面积大小是与交通路口的密集程度具有直接关联 的。因此，根据泰森多边形的面积特色将相邻的面积大小相近的泰森多边形进行合并，形成 一定大小的区域。这样，得到了若干个区域。而公交车源点终点的则在位于上述这些区域的 边界地带的候选公交车站点之间挑选。边界地带指的是与其他区域相邻的泰森多边形组成 的地带。接着，分别计算这些处于边界地带的候选公交车站点的出度和入度的值。将其中入 度为零的候选公交车站点设为源点，出度为零的候选公交车站点设为终点。用此种方法，定 义出了公交车路线的源点和终点。
[0031] 所述的有向图构建，即将上述挑选出的候选公交站点构建成一个有向图，从而进 行公交车最优路径的选择。在该有向图中，每个结点代表一个候选公交车站点，每条有向边 代表一条带有方向的路径。即在两个相邻的候选站点之间如果存在乘客流量，则用一条边 将其连接起来，否则没有边;该边的方向则根据乘客流量的方向确定，即出租车行驶的方 向。因此，在上述一个区域间的所有源点终点之间构建有向图，同时计算从第i个源点到第j 个终点路径的支持度以及该路径的乘客流量数占总的乘客流量数的比例，将这两项进 行累加则得到该路径的源点和终点的匹配值M(r^)，可用以下公式计算：
[0033] 其中，R表示同一区域中从任意源点到任意终点的所有路径集合，I R|则表示该集 合的数量，而如叩&七1^^，1〇|则表示路径^,座集合1?中出租车行驶的次数。即该公式表 示从某个源点到某个终点的路径行驶次数占总数的比例，即为该路径的支持度。pf(r^)为 路径ru的乘客流量数，
则为该区域总的乘客流量数。根据源点的密度进行 排序，从密度值最大的源点开始，分别计算该源点到其它终点匹配度，选择与该源点匹配值 最大的终点。用此种方法，得出了源点终点之间的对应关系。然后，在源点终点对关系确定 的情况下，将其中没有对应终点的源点和没有对应源点的终点去除。在得到源点终点对之 后，重新构建有向图；首先，去除不在给定源点终点对之间的候选公交站点，接着去除不符 合该源点到终点行驶方向的结点和路径;因此，构建成初始有向图。
[0034] 所述的有效路径选择，是在上述初步有向图的基础下，根据四个约束条件和两个 规则去除掉给定源点终点对之间的所有无效路径，从而得到所有有效路径。所述的这四个 约束条件用于从给定源点终点对之间的所有候选公交车站点之间挑选出有效的候选公交 站点;而两个规则用于在上述有效候选公交车站点之间挑选出有效路径。
[0035] 其中，所述的这四个约束条件为:每一个挑选的节点都应该远离起始点，不断的接 近终点，同时远离在此之前的节点，并且每个站点之间必须保持一定的合适的距离。即候选 站点在源点到终点方向上的映射值是不断增长的。因此，我们去除不满足这四个约束条件 的候选公交站点，从而得到了所有有效的候选公交站点。
[0036] 所述的两个规则为不曲折规则和出入度规则。具体而言，第一个规则为去掉在源 点终点间曲折反复的路径，即保证该源点终点间所有路径的平滑性。第二个规则为计算每 个结点的出入度，将出度和入度任意一个为零或者都为零的值去掉。从而保证在给定源点 终点的一个有向图中，只有一个入度为零的结点，即为源点；和一个出度为零的结点，即为 终点。通过上述方法，去掉了给定源点终点的路径中的无效路径，从而得到了有效路径。
[0037] 所述的最优路径生成，则是在上述有效路径中生成最优路径。最优路径是指能在 更少的行驶时间内能搭载更多乘客的路径。基于这个目的，我们提出两个算法，一个是单向 最优路径选择算法，另一个是双向路径选择算法。
[0038] 单向最优路径选择算法，其核心思想是根据所有候选的公交站点被设为公交站点 的概率值来选择公交站点。因此，根据每个候选站点之间的乘客流量数用以下公式定义了 该条件概率：
[0040]其中，是指第i个可能的候选站点，而ni，n2，···，nj表示的是丨之前的所有历史站 点；//(/?,"乂)是结点nm到候选结点《之间的乘客流量，
I.则是指<之前所有 历史站点到某个候选站点4的乘客流量之和。#是结点如的所有可能的下一个站点的集合， 即是结点W在图中所有的孩子结点，而|Nl则指的是所有可能站点的数量。则
则表示所有历史站点到所有获选站点η丨的乘客流量之和。因此上述 公式表示的是某个获选站点与历史轨迹的乘客流量之和在所有获选站点与历史轨迹站点 的全部乘客流量之和所占的比例，该值越大，则表明某个候选站点成为下一个候选站点的 概率越大。并且，运用这个方法，下一个站点的确立不仅仅由当前站点决定，而是由所有的 同一条路径中的历史站点决定的。另外，每次都挑选概率排在前m的候选站点作为下一个站 点。因此，对于要经过η个站点的路径来说，该算法总共会产生m n条路径。最后，再通过计算 每条路径的运行时间以及总的最大载客数，在一定的时间限度内，挑选出乘客流量最大的 路径，即该路径为最优路径。
[0041]双向最优路径选择算法，其思想是在两个 相反的方向上分别运行上述单向最优路 径选择算法，从而得到两个方向上所有可能的路径，即能得到2mn条候选路径;然后计算这 些候选路径的运行时间和最大载客数，从而挑选出最优路径。该算法主要是考虑到双向路 径上的乘客需求的差异性，因为乘客需求是随着时间不断的在变化的。而实际生活中，公交 车都是沿着相同的路径来回行驶的，因此，必须综合考虑到两个方向上的情况，从而能生成 对双向路线而言最优的路径。
[0042]由于采用了上述技术方案，本发明提出的基于出租车轨迹的夜班公交车路径选择 方法，具有以下有益效果：
[0043] 1)将城市的出租车GPS数据用于公交车站点的设计，出租车和公交车均为城市中 两种主流的公共交通工具，它们之间具有一定程度上的相似性和共通性。并且，出租车相对 于公交车而言，更加能直观的反应城市居民的出行需求。再者，出租车乘客通常会在城市的 公交路线或者地铁路线不能直接或者不能到达其目的地时才选择乘坐出租车。因此，用出 租车数据来设计公交车站点更能满足城市居民的需求。
[0044] 2)采用了泰森多边形分割法来对城市进行分割，并将城市交通路网中的重要路口 作为泰森多边形的离散点。用此种方法，充分考虑到了城市交通路网的实际情况，并能通过 泰森多边形的面积很直观的反映城市中心和城郊的区别。因此在选择路径的源点和终点的 时候，能根据区域特色划分，使公交车站点的设计更加人性化。
[0045] 3)设计了一种新的方法去定义城市中的热点区域，从而能从中挑选出候选公交车 站点。该方法根据每个泰森多边形中出租车上下乘客的数量从城市中定义出若干个大小合 适的热点区域，每个热点区域具有相近的出租车上下乘客的数量。用这种方法，保证了每个 候选公交站点的乘客数量的合理性。
[0046] 4)提出了一种新的方法去选择公交车最佳行驶路径，使得公交车能在一定的时间 限度内搭载更多的乘客，以满足更多人的需求。该方法不同于最短路径的选择，因为不仅仅 考虑行驶的时间，同时还考虑乘客需求量、公交车站点建造成本等等因素。因此，本发明的 方法更加符合实际情况。
[0047] 5)提出了一种新的准确定义公交车路线源点终点对的方法，该方法充分考虑到了 公交车行驶路线的区域特性，以及源点终点对之间路径的支持度和乘客流量数，即前文中 定义的源点终点的匹配度。用这种方法选出的源点终点对既符合城市中实际的交通路况， 也能更加满足乘客的需求。
[0048] 6)分别提出了单向和双向公交车最优路线规划的方法。大多数公交车路线设计方 案都仅仅考虑单向的行驶路线，另外一个方向通常都只是简单的反向行驶而已。但实际上， 乘客需求是随着时间以及目的地的变化而变化的，并不能一概而论。因此，本发明综合考虑 了公交车的双向行驶路线，从而使得公交车双向行驶过程中搭载的乘客数量最大。
【附图说明】
[0049] 图1为本发明的系统架构图。
[0050] 图2A为本发明方法的区域分割示例图（合并后的大区域）。
[0051] 图2B为本发明方法的区域分割示例图（分割成四个子区域）。
[0052]图3为泰森多边形关联度计算示例图。
[0053]图4为四个约束条件示例图。
[0054] 图5A为源点终点对匹配示例图（源点终点匹配前）。
[0055] 图5B为源点终点对匹配示例图（源点终点匹配后）。
[0056] 图6 A为在给定源点终点的情况下有向图生成和有效路径选择示例图（初始有向 图）。
[0057] 图6B为在给定源点终点的情况下有向图生成和有效路径选择示例图（修剪后的有 向图）。
【具体实施方式】
[0058] 下面结合附图所示实施例对本发明做进一步说明。
[0059] 请参阅图I，本发明的系统架构图，本发明可分为两个子部分:候选公交站点设定 以及最优公交路线选择。
[0060] 每个子部分又分为四个子部分:候选公交站点设定部分包括泰森多边形分割、热 点泰森多边形选择、热点区域建立和候选公交站点设定;最优公交路线选择部分包括源点 终点定义、有向图构建、有效路径选择和最优路径生成。
[0061] 图2A为上述热点区域建立过程中热点泰森多边形形成的初步热点区域，该热点区 域面积较大，因此对其进行分割，如图2B所示。按照前文所述方法，将其分割成四个大小合 适，且乘客流量数相近的四个子区域。
[0062] 请参阅图3,为泰森多边形关联度计算示例图。
[0063] 其中编号为1的泰森多边形为七边形，则它有七个邻接泰森多边形编号分别为2， 3，4，5，6，7，8。根据上述关联度的定义，该泰森多边形的关联度的值在0-7之间。而在其七个 邻接泰森多边形中，为邻接泰森多边形有三个，分别是编号为3，5，6的泰森多边形;编号2， 4,7,8的泰森多边形则为普通的泰森多边形。因此，根据定义，编号1的泰森多边形的关联度 值为3。
[0064] 请参阅图4,为四个约束条件示例图。
[0065] 其中圆圈S代表该路径源点，圆圈D则代表终点；圆圈1，2，3，4代表中间的候选公交 站点。满足四个约束条件即如图所示，后一个候选公交站点坐标在S-D方向的映射值大于前 一个候选公交站点。
[0066] 请参阅图5A和图5B，为源点终点对匹配示例图。
[0067]其中左图为源点终点匹配前的图，右图为源点终点匹配后图；左图中有三个源点 S1,&，&，两个源点D1, D2,在它们之间有很多候选公交车站点。在上述匹配过程结束后，产生 了两个源点终点对S1-D 2，S2-D2，如右图所示。
[0068] 请参阅图6A和图6B，为在给定源点终点的情况下有向图生成和有效路径选择示例 图。
[0069] 在源点终点已经确定的情况下，图中圆圈S和D分别代表某路径的源点和终点，中 间其它的点代表它们之间存在的所有的候选公交站点。图6A为初步建成的有向图，而图6B 则为经过前文所述的挑选过程后，得到的所有有效路径。
[0070] 本实施例1中，所述的候选公交车站点的设定中，用泰森多边形分割法对城市进行 分割。其中，要以城市重要的路口作为泰森多边形的离散点。根据我国的《公路工程技术标 准》所述，公路可分为高速公路、一级公路、二级公路、三级公路、四级公路五个等级。而本发 明中所述的重要路口至少为二级公路及以上的公路所形成的路口。具体而言，可根据公路 等级对其进行赋值，如高速公路赋值为5,然后依次递减，四级公路为1。然后将组成某个路 口的平均公路等级作为该路口的等级，例如由高速公路和一级公路组成的二叉路，则路口 的等级戈
接下来，我们再统计出各个路口每天的平均车流量，可以以一年的观 察时间为标准计算平均车流量。将某个路口的等级值与其每天平均车流量值进行相乘得到 该路口的重要值，并对重要值进行排序。最后，根据实际情况，选择排名前N个路口作为重要 路口，将城市分为若干个泰森多边形。
[0071] 本实施例1中，所述的候选公交车站点的设定中，关于热点泰森多边形的选择中涉 及到阈值的设定。该阈值的大小决定了热点泰森多边形的数量，从而间接影响了热点区域 的数量，也就是候选公交车站点的数量。而在实际情况中，由于存在着湖，山，建筑群等，几 乎90%以上的热点泰森多边形中上下车数量是为零的。为了保证公交车路线几乎可以覆盖 整座城市，我们选取的热点泰森多边形应该足够多，至少占所有有上下车数量的泰森多边 形总数的90%，全部泰森多边形数量的0.5%以上。因此，该阈值要根据该城市的实际情况， 并在保证热点泰森多边形占上下车点数量不为0的全部泰森多边形的90%的情况下选取。
[0072] 本实施例1中，所述的 候选公交车站点的设定中，关于热点区域的建立问题，其中 涉及到热点区域的面积和乘客流量数的设定。本发明中，热点区域的大小并不是固定的，而 是根据实际情况中该城市的区域特点决定的。这也同样是所述的候选公交车站点的设定 中，采用泰森多边形分割法的优势之一。因为泰森多边形的面积本身就是大小不一的，且越 靠近城市中心面积越小，反之则越大。这一特点也符合城市公交运输规则，城市中心地带公 交站点相隔距离短，且站点多；而城郊地带公交站点之间距离相对长，且站点少。因此，本发 明在保证每个站点的乘客流量数相近的情况下，根据泰森多边形的面积大小大致的确定该 区域的人口密度。在人口密度大小差不多的区域内，热点区域的面积大小一致，则公交站点 之间的距离相等。即公交站点之间的距离并不是一成不变的；人口越密集，热点区域面积越 小，则该区域的公交站点之间的距离越近;反之，则面积越小，公交站点之间的距离越远。则 热点区域的面积要根据城客流量数进行合并和分割等调整。
[0073] 本实施例1中，所述的候选公交车站点的设定中，在选取候选公交车站点时权值Wi 和W2设定并不能对候选公交车站点的数量造成影响，仅仅能影响到候选公交车站点的经炜 度。而候选公交站点的地理位置选择，首先要考虑的是该区域人口密度的分布情况。我们应 该尽量选择人口密度相对集中的位置，因为人对到站点的步行距离有一定的容忍值。根据 调查，该值大致在500m左右。其次要考虑到的是与其它站点之间的距离，如前述所说，我们 要保证人口密度大小相等时站点之间的距离相等。然后，在多次反复试验中，选取满足上述 两个条件的最优权值。
[0074] 本实施例2中，所述的公交车最优路径的选择，在建立源点和终点的映射时，我们 应该考虑到公交车的行驶时间。在实际生活中，公交车的行驶时间一般在半个小时到一个 半小时的范围内。因此，源点终点对之间的距离既不能太远，也不能太近。本发明用的是出 租车的数据，在进行公交车行驶时间估算的时候要注意进行速度转化。一般而言，出租车的 行驶速度是公交车的1.5倍。
[0075] 本实施例2中，所述的公交车最优路径的选择，在生成最优路径的生成过程中，对 中间站点数量的选择需要考虑到站点之间的距离以及站点建造成本。为了满足更多乘客的 需求，原则上我们应该使中间站点数量更多。但是中间站点的增加会增加整体的行驶时间， 同时也会增加建造成本。因此，我们应该结合实际情况，在保证整体行驶时间的情况下，在 中间站点数量选择和站点建造成本之间找到一个平衡点。该平衡点可通过反复实验得到。
[0076] 本实施例2中，所述的公交车最优路径的选择，在实际建造公交车站点的时，由于 本发明采用的是出租车的GPS数据，因此得考虑到出租车与公交车之间的差别。在很多城市 的道路规划中，出租车与公交车行驶的路线与允许停靠的位置是不同的。因此，得结合具体 城市的实际情况建造公交车站点。在本方案中得出的公交站点建造地点不能用时，应该选 择与该地点相近的地点，且不能对路线的规划造成影响。
[0077]上述的对实施例的描述是为便于该技术领域的普通技术人员能理解和应用本发 明。熟悉本领域技术的人员显然可以容易地对这些实施例做出各种修改，并把在此说明的 一般原理应用到其他实施例中而不必经过创造性的劳动。因此，本发明不限于这里的实施 例，本领域技术人员根据本发明的揭示，不脱离本发明范畴所做出的改进和修改都应该在 本发明的保护范围之内。
【主权项】
1. 一种夜班公交车站点及路径选择方法，其特征在于:包括候选公交站点设定的方法 和公交车最优路径的选择方法； 所述候选公交站点设定的方法是指利用出租车的上下车的位置信息来定义城市中的 热点区域，然后从每个热点区域中挑出一个候选公交车站点；所述公交车最优路径的选择 办法是指将候选站点和行驶路径的方向和距离构建成有向图，然后通过单向最优路径算法 和双向路径选择算法，分别得出单向和双向的公交车行驶的最优路径。2. 根据权利要求1所述的夜班公交车站点及路径选择方法，其特征在于： 将泰森多边形分割法运用到城市区域分割中，该方法将城市的大量的重要路口作为初 始离散点，然后将城市分为若干个泰森多边形;且这些泰森多边形离城市中心越近，则面积 越小，反之则越大； 优选的，关于合并和分割方法:在合并时仅通过简单的邻接规则以及出租车上下车点 数量排序而进行，即由上下车数量最大的泰森多边形开始按照排序顺序合并与之相邻的其 余泰森多边形，直至整个城市初步形成若干个区域;然后再对其中面积大小以及乘客流量 数过大的区域进行重新分割，在重新分割的时候主要考虑到该区域自身的特点，；通过合并 和分割后，得到面积大小以及乘客流量均适合的热点区域； 优选的，在重新分割的时候，当该区域自身长大于宽时，对其进行纵向分割，反之，则进 行横向切割。3. 根据权利要求2所述的夜班公交车站点及路径选择方法，其特征在于： 选取候选站点时，站点之间的距离不是一成不变的，而是根据其所处的区域特色进行 调整； 优选的，城市中心区域的公交站点数量多，且间距短;反之，则数量少，间距长。4. 根据权利要求2所述的夜班公交车站点及路径选择方法，其特征在于： 定义泰森多边形的关联度;根据同一热点区域内每个泰森多边形的关联度的值和上车 点的数量定义其成为候选站点的可能性;优选的，挑选可能性最大的泰森多边形作为候选 公交站点;优选的，每个热点区域有且仅有一个候选公交站点。5. 根据权利要求2所述的夜班公交车站点及路径选择方法，其特征在于： 定义任意源点终点对之间的匹配度，该匹配度主要由任意源点终点对之间路径的支持 度以及乘客流量比例组成； 优选的，在给定路径源点和终点的情况下，将该两点之间的所有获选公交站点建造了 一个初始有向图；其中每个结点代表一个候选公交站点，每条有向边，代表一条有方向的路 径； 优选的，提出四个在给定源终点的情况下能得到所有可能路径的约束条件;根据约束 条件，初步去除那些不可能的候选公交车站点，简化初步有向图； 优选的，提出两个规则来去除无效的路径，一个是不曲折规则，另一个是出入度值规 贝IJ，从而得到了源点终点之间的所有有效路径； 优选的，提出一种基于概率的扩散算法以及一种基于概率的双向扩散算法;通过前者 挑选出单向的公交车最优路径，通过后者挑选出双向的公交最优车路径。6. 根据权利要求1所述的夜班公交车站点及路径选择方法，其特征在于： 所述候选公交站点设定的方法包括四个部分:泰森多边形分割、热点泰森多边形选择、 热点区域建立、候选公交站点设定;所述公交车最优路径的选择办法包括四个部分:源点终 点定义、有向图构建、有效路径选择、最优路径生成。7. 根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的泰森多边形分割，是指同一平面上的N个离散点按照最邻近原则将该平面划分 为N个大小不一的泰森多边形;每个泰森多边形中间有且仅有一个离散点，且该泰森多边形 内所有的点都距该离散点最近； 优选的，将城市交通路网中的关键路口作为泰森多边形的离散点，将整个城市分成了 若干泰森多边形;优选的，城市中心的泰森多边形面积相对小，而郊区则面积相对大； 优选的，所述的热点泰森多边形选择，是指从上述初步生成的泰森多边形中挑选出热 点泰森多边形;先分别统计了每个泰森多边形中的出租车上下车点的数量;然后将出租车 上下车点数量不为零的泰森多边形挑选出来，计算其每小时上下车点数量的累积分布概 率，将超过某个阈值的泰森多边形定义为热点泰森多边形。8. 根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的热点区域建立，是指将上述热点泰森多边形经过合并和分离后，生成若干个热 点区域;该热点区域中包含着数量相近的出租车上下车点；首先，分别统计上述的热点泰森 多边形中的出租车上下车点的数量，并对其进行降序排序;然后选择排在第一位的泰森 多 边形去合并与其地理位置上相邻的所有其它泰森多边形;然后再选择下一个泰森多边形重 复上述过程，通过此方法，初步得到若干个热点区域； 优选的，由于有些热点区域中包含的上下车点的数量太多，即该区域中的乘客需求太 大，在该区域中仅仅设立一个公交站点根本满足不了需求，这样就会造成公交站点设定的 不合理；需要将这些初步获得的热点区域进行分割，以保证每个区域拥有相近的上下车点 数量;其次考虑到地理因素，将长度大于宽度的区域进行纵向切割，反之则进行横向切割； 长度和宽度相近的则先随机进行分割一次，然后再按上述方法进行分割;通过此方法，获得 了上下车点数量在某个范围内的若干热点区域;该范围由城市中每个时段具体的公交车乘 客需求量决定； 优选的，所述的候选公交站点设定，即从上述获得的热点区域中选定候选公交站点，每 个热点区域中有且仅有一个候选公交站点；首先，定义了泰森多边形的密度D(Vi)，该值表 示第i个热点泰森多边形V i的邻接热点泰森多边形的数量;对于一个有k边泰森多边形而 言，其密度D(V1)的值为Ο-k;然后，将热点区域中每个泰森多边形^成为候选公交站点的可 能性定义为P(V 1) ;P(Vl)是根据一定的权值比重综合每个泰森多边形的密度D(V1)的比值以 及它们的上下车点数量N(V 1)的比值而得到的值，采用以下公式计算：?:和抑分别为每个泰森多边形的密度D(V1)的比值的权重以及它们的上下车点数量比 值的权重。则表示η个泰森多边形的上下车点数量的累加和，即总的上下车点数 量;该权重的值可由多次实验结果得到；最后，选择P(V1)值最大的泰森多边形中的关键路 口作为候选的公交站点。9. 根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的源点终点定义，即在上述候选公交站点之间挑选出公交车路径的源点和终点； 根据泰森多边形的面积特色将相邻的面积大小相近的泰森多边形进行合并，形成一定大小 的区域;得到了若干个区域;公交车源点终点则在位于上述这些区域的边界地带的候选公 交车站点之间挑选;边界地带指的是与其它区域相邻的泰森多边形组成的地带;接着，分别 计算这些处于边界地带的候选公交车站点的出度和入度的值;将其中入度为零的候选公交 车站点设为源点，出度为零的候选公交车站点设为终点，用此种方法定义出公交车路线的 源点和终点； 优选的，所述的有向图构建，即将上述挑选出的候选公交站点构建成一个有向图，从而 进行公交车最优路径的选择;在该有向图中，每个结点代表一个候选公交车站点，每条有向 边代表一条带有方向的路径；即在两个相邻的候选站点之间如果存在乘客流量，则用一条 边将其连接起来，否则没有边;该边的方向则根据乘客流量的方向确定，即出租车行驶的方 向； 优选的，在上述一个区域间的所有源点终点之间构建有向图，同时计算从第i个源点到 第j个终点路径的支持度以及该路径的乘客流量数占总的乘客流量数的比例，将这两项 进行累加则得到该路径的源点和终点的匹配值M(r^)，采用以下公式计算：其中，R表示同一区域中从任意源点到任意终点的所有路径集合，I Rl则表示该集合的 数量，而|1^叩&让(^^，1〇|则表示路径以^在集合1?中出租车行驶的次数；即该公式表示从 某个源点到某个终点的路径行驶次数占总数的比例，即为该路径的支持度;pf(r^)为路径 r i, j的乘客流量数，则为该区域总的乘客流量数； 优选的，根据源点的密度进行排序，从密度值最大的源点开始，分别计算该源点到其它 终点匹配度，选择与该源点匹配值最大的终点；用此种方法，得出了源点终点之间的对应关 系;然后，在源点终点对关系确定的情况下，将其中没有对应终点的源点和没有对应源点的 终点去除；在得到源点终点对之后，重新构建有向图；首先，去除不在给定源点终点对之间 的候选公交站点，接着去除不符合该源点到终点行驶方向的结点和路径;构建成初始有向 图。10.根据权利要求6所述的夜班公交车站点及路径选择方法，其特征在于： 所述的有效路径选择，是在上述初步有向图的基础下，根据四个约束条件和两个规则 去除掉给定源点终点对之间的所有无效路径，从而得到所有有效路径;所述的这四个约束 条件用于从给定源点终点对之间的所有候选公交车站点之间挑选出有效的候选公交站点； 而两个规则用于在上述有效候选公交车站点之间挑选出有效路径； 优选的，所述的这四个约束条件为:每一个挑选的节点都应该远离起始点，不断的接近 终点，同时远离在此之前的节点，并且每个站点之间必须保持一定的合适的距离；即候选站 点在源点到终点方向上的映射值是不断增长的;去除不满足这四个约束条件的候选公交站 点，从而得到了所有有效的候选公交站点； 优选的，所述的两个规则为不曲折规则和出入度规则；第一个规则为去掉在源点终点 间曲折反复的路径，即保证该源点终点间所有路径的平滑性;第二个规则为计算每个结点 的出入度，将出度和入度任意一个为零或者都为零的值去掉;从而保证在给定源点终点的 一个有向图中，只有一个入度为零的结点，即为源点；和一个出度为零的结点，即为终点;通 过上述方法，去掉了给定源点终点的路径中的无效路径，从而得到了有效路径； 优选的，所述的最优路径生成，则是在上述有效路径中生成最优路径;最优路径是指能 在更少的行驶时间内能搭载更多乘客的路径;基于这个目的，通过以下两个算法来加以解 决:一个是单向最优路径选择算法，另一个是双向路径选择算法； 优选的，所述单向最优路径选择算法，是根据所有候选的公交站点被设为公交站点的 概率值来选择公交站点;根据每个候选站点之间的乘客流量数用以下公式定义了该条件概 率：其中，W是指第i个可能的候选站点，而ni，n2,. . .，nj表示的是W〖.之前的所有历史站点； #(?",,<)是结点nm到候选结点/{之间的乘客流量，则是指 之前所有历 史站点到某个候选站点nf啲乘客流量之和;#是结点的所有可能的下一个站点的集合， 即是结点W在图中所有的孩子结点，而|Nl则指的是所有可能站点的数量。则.则表示所有历史站点到所有获选站点的乘客流量之和；因此上述 公式表示的是某个获选站点与历史轨迹的乘客流量之和在所有获选站点与历史轨迹站点 的全部乘客流量之和所占的比例，该值越大，则表明某个候选站点成为下一个候选站点的 概率越大;并且，运用这个方法，下一个站点的确立不仅仅由当前站点决定，而是由所有的 同一条路径中的历史站点决定的；另外，每次都挑选概率排在前m的候选站点作为下一个站 点;对于要经过η个站点的路径来说，该算法总共会产生#条路径;最后，再通过计算每条路 径的运行时间以及总的最大载客数，在一定的时间限度内，挑选出乘客流量最大的路径，即 该路径为最优路径； 优选的，所述双向最优路径选择算法，是在两个相反的方向上分别运行上述单向最优 路径选择算法，从而得到两个方向上所有可能的路径，即能得到2mn条候选路径;然后计算 这些候选路径的运行时间和最大载客数，从而挑选出最优路径。
【专利摘要】一种夜班公交车站点及路径选择方法，包括候选公交站点设定的方法和公交车最优路径的选择方法；所述候选公交站点设定的方法是指利用出租车的上下车的位置信息来定义城市中的热点区域，然后从每个热点区域中挑出一个候选公交车站点；所述公交车最优路径的选择办法是指将候选站点和行驶路径的方向和距离构建成有向图，然后通过单向最优路径算法和双向路径选择算法，分别得出单向和双向的公交车行驶的最优路径。本发明可以协助完善城市公交车服务系统，给相关人群提供更多便利，同时也能提高效率。
【IPC分类】G06Q10/04, G08G1/00
【公开号】CN105489000
【申请号】CN201510897666
【发明人】张大强, 范珂
【申请人】同济大学
【公开日】2016年4月13日
【申请日】2015年12月8日
最新回复(0)