评分模型在路网通勤习惯分析中的应用——提出问题（1）

1、问题的由来、目标和意义

最近一段时间和公司其它业务部门讨论时，发现一个有趣的交通路网问题，车辆从S点行驶到V点共用时40分钟，这段时间内路网中的卡口摄像头识别到了车辆通过的信息。如下图所示：

设计师需要通过这些有限的路网数据，分析出当前车辆最可能的行驶路径，并且基于一段时间（1个月、2个月甚至3个月）内某车辆多个行驶路径样本，分析后得到车辆A的通勤习惯数据。能够支持解决这个问题的基础数据是有限的，它们包括：

• 相对静态的数据：地图交通网数据（没有结构化，需研发团队自行结构化）、道路级别数据、卡口位置数据等

• 相对动态的数据：从外部得到的周期更新的交通网拥堵、卡口摄像数据（最关键的数据）、交通事故数据等

解决这个问题，在业务层面还需要注意以下几个关键点：

1、数据的采集主要通过设置在主道上的卡口摄像头，或者设置在路口的卡口摄像头完成。两者的区别主要在于，前者只能提供车辆车牌信息和行驶方向信息，而后者由于是安装在路口，所以不止可以提供车牌信息，还能提供车辆在路口可能的转向信息。

2、由于技术问题、采光问题、清晰度问题，卡口摄像头做不到100%正确识别车辆车牌信息，也就是说如果卡口摄像头在一段时间内没有拍摄到某个车辆的车牌信息，也不能代表这辆车在这段时间内一定没有行驶过这段道路。

3、根据车辆某一天最可能的行驶轨迹情况，是不能得到车辆一段时间的通勤习惯的，需要多个分析样本，再利用回归分析的方式，才能得出车辆在一段时间内的通勤习惯。

车辆可能的行驶路径信息、通勤习惯信息至少能够为城市的智慧交通领域提供以下业务支持：

• **优化交通流量‌：**通过分析通勤习惯数据，交通部门可以识别交通高峰时段和瓶颈路段，从而采取措施进行改善，如调整交通信号灯、增加公交线路或建设新的交通基础设施，以优化交通流量和提高道路利用效率。

• 提升公共交通系统效率‌：公共交通运营商可以利用通勤习惯数据来优化公交线路和时间表，提高公共交通的准点率和便捷性。例如，通过分析通勤者的出发时间和到达时间，可以调整公交和地铁的发车频率和运营时间，以满足乘客的需求‌。

• 改善城市规划‌：城市规划者可以基于通勤习惯数据进行更合理的城市布局和基础设施建设。例如，通过分析通勤路线和交通状况，可以确定哪些区域需要更多的公共交通设施或道路改善，以减轻交通拥堵和提高居民的生活质量‌。

• 提高通勤者生活质量‌：通过减少通勤时间和改善通勤体验，可以显著提升通勤者的生活质量和工作效率。例如，通过分析通勤者的出行习惯，可以提供个性化的出行建议和路线规划，减少通勤时间和疲劳‌。

所以通勤习惯分析属于智慧交通业务中的基础分析，其分析的结果可以用于支撑智慧交通业务的上层能力。实际上通勤习惯分析属于OD（Origin-Destination，起止点）分析中的一种具体形式，OD分析主要通过收集和分析数据，识别出行起点和终点之间的车辆流动情况。在交通规划中，OD分析可以帮助了解交通流量、识别高峰期和瓶颈区，优化交通网络设计和管理。此外，OD分析也广泛应用于物流、零售等领域，通过分析货物流动和顾客行为，提高资源配置和运营效率‌。

2、解决问题需要具备的知识结构

2.1、OD分析可能的解决方案剖析

上图将整个问题可能的解决方案剖析成三个部分，第一个部分主要是拍照数据的采集和数据清洗。这个阶段要解决的主要问题是，不同型号、不同通讯方式的卡扣摄像头，如何汇聚数据并初步检测出错误数据。例如一些较新型号的卡口摄像头自带5G通讯模块，可以直接连接到数据采集系统/数据集中平台，通过MQTT等标准协议传输数据。有的卡口摄像头虽然不具备5G通讯模块，但是可以统一接入到IoT网关或者集中管控终端上，再由IoT网关或者终端完成数据传输。空间路网数据亦是采用类似的思路进行数据采集。

这些原始数据都将在数据采集系统/物联数据集中平台进行归集，后者显然需要兼容各种数据传输方式，并完成初步的数据清洗操作。从本文描述的需要解决的问题来说，这些原始数据主要就是各个交通卡口的车牌数据、时间数据、车辆行驶方向数据，等等。显然数据采集系统并不负责完成OD轨迹实时分析，也并不是本文讨论的重点。（如果需要详细了解这部分内容，可以参考《软件设计不是CRUD（21）：在流式数据处理系统中进行业务抽象落地——需求分析》等文章）

基础数据准备完毕后，会在湖仓一体化的数据存储平台进行存储，以便支持后续的数据分析过程。数据分析的关键过程在流式分析平台上完成，也就是说讨论如何分析得到更匹配真实情况的OD轨迹，甚至如何基于多份OD轨迹样本分析得到单台车辆在一个较长时间段内的通勤习惯，就是讨论在流式分析平台上对数据分析的详细设计。这是解决问题的关键设计部分，也是本文（和后续几篇文章）的重点内容。

整个问题可能的解决方案，还有第三个结构部分，就是基于已分析数据向外提供数据应用能力的平台。数据应用平台至少可以基于轨迹数据、出行习惯数据，以及自身AI分析后得到的其它扩充数据，向上层业务系统/第三方系统提供诸如城市路网规划、拥堵预测与缓解、高峰管制优化、路口信号优化等多种多样的业务支持。虽然这也不是本文讨论的重点，但读者可以明确知道OD分析在智慧交通应用中的意义和重要程度。

2.2、知识准备

本文不讨论技术选型本身，技术选型仅是表象，不同技术经历、技术背景的工程师对于技术选型都有自己的理解，在选型要点和细节上都会有所区别。所以读者进需要知晓上图中涉及的中间件即可：

• Kafka：Kafka作为在数据分析场景下，在多个中间件之间实时传输数据的消息队列，相信大家不会陌生。在解决本问题的技术架构中，Kafka负责多个任务，包括作为摄像头向数据采集平台/物联数据集中平台传输卡口监控数据的一种渠道、作为数据采集和清洗后，向湖仓一体化的存储方案传输数据的一种渠道。

• Flink：Flink是一款开源流式数据处理框架，主要用于实时数据流的处理和分析。Flink的核心是用Java和Scala编写的分布式数据流引擎，旨在实现数据流上的有状态计算‌。Flink大量应用在对数据分析有较强实时性要求、较大数据量要求的分析场景。除了本身提供的流式分析特性外，Flink也支持数据的批处理，这也是为什么上图中所示的技术方案中，类似通勤习惯这样的周期性批处理分析，我们也放到了Flink中。

• StarRocks：StarRocks内部通过MPP计算框架完成SQL的具体执行工作。MPP框架本身能够充分的利用多节点的计算能力，整个查询并行执行，从而实现很好的交互式分析体验。 StarRocks作为一款湖仓一体化的数据存储和计算平台，可以支持与Hive，MySQL，Elastic serach存储方案无缝构建外表。

本文的重点是介绍启发式搜索在交通通勤领域的应用，更具体的说，是解决启发式搜索如何有效降低遍历搜索算法的计算成本，提高问题的解决效率。所以以下“图”结构中的基础算法知识，需要读者掌握（本文不会讲解这些基础知识，会直接认为读者已掌握）：

• 加权有向图：‌加权有向图‌是一种图论中的数据结构，它是在有向图的基础上，每条边都赋予了一个权重值。这个权重值，一般和应用场景有关。在交通应用场景中每个顶点代表两个或者多个路段的交汇点（可能是十字路口、丁字路口、匝道、隧道出入口、高速出入口等），每条边代表一个独立的路段，每条边越高的权重，代表出于主观或客观的原因车辆行驶时对路段越高的选择度。

• 图的最小搜索树：在一个加权有向图中，如果存在一棵各边权重和最小的生成树，那么这棵树就被称为最小生成树。生成树是原图的一个子集，包含图中所有顶点，但仅有n-1条边（n为顶点数），这些边构成了一棵无环的树。

• 两个顶点的所有路径：既是通过一种算法，找到图结构中两个顶点间所有的联通路径。这种算法一般是某种遍历算法，因为只有了解了图中每个顶点的具体联通情况，才能找出所有联通路径，这就导致要找到两个顶点所有路径的算法时间复杂度一般会比较高——O(N²)

• 两个顶点的加权最短路径：在加权有向图中，从顶点s到顶点t的最短路径是所有从s到t的路径中权重最小的那条路径。

• 遍历搜索：遍历搜索，也称为暴力搜索，是一种简单但全面的搜索策略。它不考虑任何智能或优化，只是逐个访问数据结构中的每个节点，直到找到目标值或遍历完所有节点。这种搜索策略适用于没有任何特殊性质的数据结构，如普通的树或图。在遍历搜索中，常见的两种方法是深度优先搜索（DFS）和广度优先搜索（BFS）。

• 启发式搜索：是一种更智能、更高效的搜索策略。它使用问题相关业务知识来指导搜索过程，以提高搜索效率。具体到图的交通应用场景中，启发式搜索考虑的就是交通常识、驾驶习惯等因素。这种策略在现实业务场景和深度学习中更为适用，常见于最优解、可能性等问题的处理。

3、问题概要分析

3.1、可能性问题与最优解问题的区别

有的读者会疑问，本文开头提出的问题和目前导航服务厂商提供的多途径点规划功能类似，为什么不直接使用地图厂商提供的相关服务，而要作为一个基础问题自己解决呢？这里暂时不分析业务、安全等层面的考虑，单从问题本身的性质来说，这两个问题就存在较大区别：

多途经点规划和可能的OD轨迹分析，两个问题的研究场景不一样。前者是在交通行为还没有发生的情况，在满足多个途径点位的要求下，寻找一个最优解；后者是在交通行为已经发生的情况下，基于交通网的各种历史状态和经过的点位，推导出多种可能性作为分析样本。再基于一段较长时间后，对足够多的样本进行多次回归等方式，找到可能性中的最可能得情况。前者属于单纯的最优解问题，后者属于可能性问题。

可能性问题：可能性问题关注的是某个事件或情况发生的概率或存在的程度。这通常涉及到对不确定性的评估和预测。很明显通过有限的数据在交通路网上还原点位A到点位B可能的路径，就属于可能性问题。可能性问题得到的解并不是最优解，而是根据目前现状后得到最有可能的情况。

最优解问题：最优解是指在问题或情境中能找到的最佳或最理想的解决方案。这个定义涵盖了在一定条件下，没有任何其他解能比这个解更优越，即达到了问题解决的极限状态。

3.2、对问题进行分析

推测可能的行驶轨迹，并最终得出驾驶习惯，可以通过以下步骤，结合流处理过程和批处理过程进行问题的解决：

1. 对交通地图进行结构化处理

   地图的数据结构本质上是一种加权有向图，且图中存在环状结构。要解决地图上的问题，首先需要将地图进行结构化。实际工作中，这个步骤可以由技术团队自行完成——描述成二维矩阵或者二维表（邻接表），也可以借助市场上成熟的中间件产品，例如PostgreSQL with PostGIS 、Neo4j、Cassandra等数据库都对地理空间数据有专门的存储格式和能力支持。作为后续的技术方案演练，本文将自行构建邻接表来进行空间数据的结构化描述。

2. 利用具有通勤业务特点的DFS/BFS算法，求A点到B点权值较大的多条可能路径

   这是非常关键的步骤，也是本文讨论的技术核心之一。由于上文已经描述了可能性问题和最优解问题的区别，所以后续内容不再解释为什么核心算法不是诸如Dijkstra这样的最优解算法，而重点放在讨论如何结合启发式信息对常规DFS/BFS算法进行优化，以寻求各种可能的结果。

   
   （导航软件中，这条红色的目标方向辅助线，到底有什么作用？仅仅是为了识别方向吗？）

   另外，在寻找可能路径的过程中，由于路径权重涉及多个领域的基础数据，且这些基础数据并没有一个规范的评分方式，所以确认路径的过程中，就可能使用熵权法对每条路径进行确权，并且需要保证这些评分维度，可以进行扩展。

3. 利用模糊综合评价法，对路径进行打分，分数最高者为最可能路径

   由上一步骤得到的可能路径如果只有一条，那么就不需要进行本步骤。如果存在多条可能路径，则需要利用综合评分法，找到其中评分最高的一条路径，作为最可能路径。综合评分涉及的评分维度至少包括实际时间和线路预计时间的差异，因为不同的业务场景可能存在的差异，参与综合评分的维度允许进行扩展。

4. 通过以上分析方式，积累一定规模的路径样本（例如1个月、2个月），通过线性回归方式，求得车辆A在一定时间周期内的通勤习惯。

   通过以上3个步骤，可以得到特定车辆某一次的可能行驶轨迹，但是仅仅一次或者有限的几次行驶轨迹是无法确认车辆驾驶者的驾驶习惯的，需要一个较长时间段的多个轨迹作为分析样本，分析后才能得出驾驶习惯。

下面，我们就对以上解决问题的步骤逐一进行详细讨论。讨论将基于以下的示意性路网结构（片段）进行：