基于贪心算法的常态化防疫交通路线智能推荐系统

孔钦，刘晨，顾永鑫

（1.南京信息职业技术学院 人工智能学院，江苏 南京 210023；2.南京大学 软件学院，江苏 南京 210093；3.南京大学金陵学院信息科学与工程学院，江苏 南京 210089）

0 引 言

自新冠疫情发生以来，“健康码”“行程码”“核酸报告”等通行物逐渐成为人们日常出行必备。这些随社会发展所诞生的互联网产品正在逐步地改变着人们的生活方式。“大数据”“人工智能”等计算机技术在疫情防控中的成功应用，是国家能够控制疫情的重要原因之一。

每年春节期间，社会在应对庞大人口的“春节效应”的同时，地方政府也面对着数字化转型所带来巨大挑战。在符合我国巨大“人口移动”特点的春运时期，我国的交通管控、疫情防控面临着前所未有的压力。随着整体智能化汽车时代的到来，人们对于驾驶行程的安全性要求又提高到一个新的层次。目前行车搭载的“路线推荐”功能，虽然导航功能已经相当精确和完备，且提供较好的人机交互性体检。但针对疫情环境下的“安全性”却没有得到很好的保障，甚至出现推荐路线中包含高风险地区经过的现象，这对于没有及时关注到疫情城市信息的司机来讲，无疑会增加行车风险，政府管控疫情的难度也会大大增加。

在此前提下，一个基于实时城市疫情和基本路况信息的智能化路线推荐系统应运而生。该系统依靠国家城市发布的实时城市疫情信息作为数据源，借助大数据平台收集实时数据，结合先进的路线规划算法，实现疫情期间人们的日常出行路线推荐。平台实时提供最为安全的数据分析从而实现宏观的交通管控，出行的人们可以根据系统推荐出的路线，选择合适、安全、便捷的出行路线。

1 研究背景

为了满足用户的出行需求，用户可以根据导航路线的指引，从出发地到达目的地。服务器获取道路的相关情况（如：事故的发生地点，当前的拥堵路段），根据道路的相关情况检索导航路线，将最符合用户需求的路线提供给用户，使得用户出行时，可以有效地避免拥堵。

导航一般分为两类：（1）基于数字地图的导航；（2）基于轨迹数据的导航。基于数字地图的导航是最为传统的导航方式，其原理是基于最短路径或者最优路径的目标，应用动态规划原理计算路径，其中最常使用到的是以Dijkstra 算法为代表的贪心算法。这种算法的缺点是当路网比较大、路线图分支比较多时，使用该算法会大大浪费时间。因此贪心算法适合图网不是特别复杂的情况。另一种基于轨迹数据的导航大多把注意力放在轨迹挖掘上，更多的是利用机器学习的方法，对人们的出行数据进行挖掘、分析，再综合天气、路况等其他外界因素，形成一个最终的结果，找到与用户行驶更加匹配、合适的出行路线。

但是，上述两种方法中提供的导航路线只单纯考虑了道路的相关情况，没有结合近几年不断波动、实时变化的疫情发展情况。本系统在对比以上两种方法的基础上，依据目前省市之间的交通通行节点，参考“高德地图”数据库里的基础数据，利用贪心算法，将实时疫情信息纳入重要参数序列，形成一套适合都市圈城间交通的智能化路线推荐系统。

2 技术框架

2.1 高德地图开放平台API

高德地图是市面上优秀、专业的手机地图APP，它拥有国内全面的地图数据和精确的定位能力，为民众的出行提供了优秀的解决方案。它同时还提供开放平台API 服务，开发者可以通过调用API 快速构建处理地理信息的服务，如路线规划、导航、实时地图数据更新、获取精确坐标等。本项目运用其提供的数据，加上特定算法，以实现路线推荐。由于该API 由大型专业公司提供，因此稳定性、准确性有充分保障。

2.2 Python-Flask 框架

Flask 是使用Python 语言编写的开源Web 框架，相较于Python 下其他流行的Web 框架如Django，Flask 一个很大的特点就是“轻量”。它本身相当于一个“内核”，开发者可以基于这个“内核”开发程序扩展、中间件等，市面上有许多成熟的基于Flask 的程序增强扩展，它们可以大幅提升开发效率和程序稳定性。扩展插件在Flask 中“即插即用”，因此Flask 在保持轻量、快速开发的同时，也具备了极强的扩展与兼容性。综上所述，不论是开发还是维护，Flask 框架都能为开发者提供便利。

2.3 以贪心思想为核心的Dijkstra 算法

贪心算法又名为贪婪算法，它是一种抽象的算法思想，代表了一系列具体算法的集合。这类算法通常对问题进行分解，并在迭代过程中每次搜索局部最优解，并期望得到最终的最优解。贪心算法的优点是简单且高效，省去了不必要的枚举操作。

本项目应用Dijkstra 算法的核心在于实时获取地点位置信息之后，将其与疫情城市信息库数据进行对比，如果经过风险地区，路径置为一个最大阈值，这样在进行最短路径（或者其他需求路径比如红绿灯最少等）会将其放置末尾（因为我们知道对于最长路径极小概率成为人们的日常行程出行选择）。所以最终返回一个安全通畅的路径，并对于原本经过高风险地区的路径给出安全警示消息提示，具体算法流程图如图1所示。

图1 改进贪心算法流程图

3 系统架构

在知晓国家对于疫情的防控监管程度以及人们日常出行路线的需求时间节点范围后，再根据如今的一些地图导航功能和数据等综合情况，最后通过算法计算出系统的最终需求。

系统的整体目标为：（1）实现一个基于疫情城市数据的城市交通路线推荐系统；（2）用户可以根据实时疫情情况选择合适安全的路线；（3）政府机构可以通过系统实时了解人们的出行情况、给予出行者安全的建议，并实现系统端的宏观管控。应用系统架构图如图2所示。

图2 应用系统架构图

主要功能模块包括：（1）注册登录模块。用户可以注册登录系统，编辑个人信息；（2）引入健康码、行程码、核酸检查报告等同步信息库收录、查看功能；（3）自动同步个人位置信息功能；（4）实时重点疫情城市播报、显示、录入疫情城市数据库功能；（5）所有路线查看功能，其中由两部分组成，第一部分是根据传统算法计算出的推荐路线，第二部分是排除风险地区的推荐路线。软件功能模块图如图3所示。

图3 软件功能模块图

4 推荐路线具体详细设计

根据用户当前定位所在的城市，结合数据库里不断更新的实时城市疫情信息，推荐模块灵活设置途径城市的权重值，服务器利用贪心算法计算出优先级较高的几条路线，给予用户相应的出行建议，并将推荐信息同步至数据库中保存。如图4、图5、图6所示。

图4 路线推荐模块流程图

图5 用户行程上传界面图

图6 行程推荐展示图

城市道路信息由高德地图开放平台提供，服务器通过调用开放平台提供的API 获取地图信息。其地图数据约五分钟更新一次，保证数据的实时性、可靠性。为获取调用权限，需要申请高德开放平台的APP KEY 并下载官网提供的地图开发包，同时，根据开发环境的不同，需要使用不同的SHA1。调用流程如图7所示。

图7 服务器调用API 流程

为方便数据的传递和存储，开放平台提供的地图数据为JSON 或XML 格式。当用户确定始发地、目的地、交通方式时，系统将结合数据库存储的全国各地疫情信息，推荐安全系数较高的路线。推荐处理服务器首先会调用开放平台的路线规划接口，获取可能的出行路线（不包含疫情分析）。接着将所有路线进行以城市为单位的拆分（市内出行则以区/镇/街道为单位），得到可能途径的所有城市的非重复集合。再将其与数据库中的疫情信息进行比对，对有疫情/交通管制的城市按其风险程度进行加权，风险程度的评估包括该城市风险地区数量、城市交通管制措施、历史疫情数据等。

加权处理后形成由城市到城市的加权图，最后利用Dijkstra 算法找出总权重最小路径，此路径即为较安全的出行路线。除了安全层面的分析与加权计算，距离、时间、出行费用等常规策略选择也可以包含在推荐结果的算法当中。当用户选择其中一种策略时，路线推荐模块将按照加权图，以路径的安全程度进行分类，再对不同安全程度的路径进行策略加权，策略权重的大小与距离、时间、费用成正比。加权后形成以安全、策略为主的加权图，最后同样使用Dijkstra 算法找出总权重最小路径。

循环往复上述步骤得到路径集合后，其数据保存在一个整体的表中，接着该模块使用部分排序算法对所有路径按照安全/策略权重的高低进行升序排序。例如，从上述步骤的结果得到苏州到南京路径集合：A（中风险，10 千米）、B（低风险，5 千米）、C（中风险、5 千米）、D（低风险、10 千米），用户选择最短距离，则路线推荐模块首先依据安全程度将B、D（均为低风险）为一组，A、C（均为中风险）分为一组，再按照策略对其部分排序（路程升序），其推荐结果为B、D、C、A。

推荐结果内容包括系统推荐的始末地路径图、推荐路径上各个城市的详细疫情数据、交通情况、出行距离、出行费用、通行时间。其中，由于详细疫情数据为可选展示，因此路径图与详细疫情数据为不同的JSON 字符串。并且对于详细疫情数据进行懒加载处理，如用户不点击查看详细城市数据，则不会包含在推荐页面中。这样既能精简页面的信息量，提升用户的阅览、判断速度，也能减少大用户量情况下系统卡顿、崩溃的风险。上述处理流程如图8所示。

图8 推荐路线处理流程

5 获取疫情城市数据具体详细设计

爬虫模块会从国家卫建委官方网站请求疫情数据，通过上次保存的数据日期与当前获取的数据日期进行对比，筛选出最新的数据。为了防止频繁的调用爬虫模块而导致网站的崩溃，本项目使用每天定时获取数据的方式。这样既能减轻网站、数据处理服务器的负荷，也基本符合官方疫情数据的发布规律如图9所示。根据官方发布的数据类型，本项目将关键信息概括为：城市名称、该城市最新数据日期、该城市确诊病例统计、该城市无症状感染病例统计、该城市死亡病例统计、高风险地区统计及具体地区、中风险地区统计及具体地区、低风险地区统计及具体地区如图10所示。爬虫将从国家卫建委官网获取HTML 网页文件，在经过爬虫框架的预处理后得到具体的发布信息，此时将数据提交给数据处理模块。

图9 获取城市疫情数据模块图

图10 处理爬虫获取文件信息的模块图

数据处理模块将对爬虫模块提交的数据进一步提炼。该模块首先比对数据库中的各个城市的信息更新时间进而筛出过期的数据，然后将新发布的数据累加到原有的旧数据上形成最新数据，再根据城市名称，将最新数据分类，形成数据列表，最后提交给数据库将其持久化。处理爬虫数据的流程如图11所示。

图11 数据库表设计图

6 结 论

常态化防疫交通路线智能推荐系统，前端采用移动端比较流行的微信小程序以及方便办公人员操作Web 网页呈现，并且结合较为流行的前端开发流行框架，快速实现一个高响应的行程推荐系统。后端主要采用轻量级的Web 开发框架Flask，接收前端发送的数据，并配合擅长数据处理的Python语言，返回统一的响应格式数据给予前端相对应的响应，有效地实现推荐算法。服务器采用较为稳定的阿里云服务器，在能够保障安全性的同时给予整个项目最稳定、高效的运行模式。该系统的创新点在于能够实时根据疫情城市信息更新城市数据库、路线推荐方案，利用贪心算法，赋予不同城市权重值，从而给予用户最安全的行程路线和使用体验。