前言：又到春招季！作为国民级出行服务平台，高德业务疾速倒退，大量校招 / 社招名额凋谢，欢送大家投递简历，详情见文末。为帮忙大家更理解高德技术，咱们策动了 # 春招专栏 # 的系列文章，组织各业务团队的高年级同学以 科普 + 利用实际 为次要内容为大家做相干介绍。
本文是 # 春招专栏 # 系列的第 1 篇，依据 高德机器学习研发部 负责人 damon 在 AT 技术讲坛所分享的 《AI 在出行畛域的利用实际》 的内容整顿而成。在不影响原意的状况下对内容略作删节。
AT 技术讲坛 (Amap Technology Tribune) 是高德发动的一档技术交流活动，每期围绕一个主题，咱们会邀请阿里团体内外的专家以演讲、QA、凋谢探讨的形式，与大家做技术交换。
damon 依据用户在出行前，出行中和出行后如何应用导航服务，别离选取了几个典型的业务场景来介绍 AI 算法在其中的利用，最初对将来做了一些瞻望。
以某位同学周末和敌人相约去“木屋烧烤”店撸串为例，假如这位同学抉择驾车返回目的地，咱们来看下 AI 算法是如何在导航过程中起到作用的。
出行前，先做路线布局，ETA（预估达到工夫），不要早退；出行中，最怕的就是遇到突发动静事件而影响到出行工夫；出行后（到目的地），餐馆是否还在失常营业，也须要通过技术开掘，帮忙用户提前躲避白跑一趟的危险。
上面别离介绍。
出行前 - 路线布局
路线布局，和网页搜寻，商品搜寻的举荐算法很类似，为用户举荐一条合乎集体爱好的优质路线。举荐的路线要合乎以下几个条件：
- 能走：此路能通，依照路线能够达到起点。
- 好走：路线品质在以后地点工夫下确保优质。
- 千人千面：不同用户在保障路线优质的前提下，个性化调整更合乎用户偏好。
同时，在不对用户产生误导的前提下，提供更多的比照参考给用户来抉择：
- 优质：相比首路线 / 主路线，有肯定的、用户可感触到的劣势。
- 多样：相比首路线 / 主路线，尽可能有本人的专长。
路线布局算法的特点
从用户产生出行需要，到需要失去满足。在用户搜寻的时候，上传的 Query 除了有起起点和导航策略，也会像其余搜寻一样，有隐含的需要，比方 个性化和场景化 。在导航业务外面，个性化能够拆分成 熟路 和偏好 两个维度，熟路比拟容易了解，偏好是指用户对 工夫、间隔、红绿灯、免费 等不同维度上的偏好。
那么，对应的解决方案，咱们引入 用户 ID，存储记忆了用户的起起点对应的熟路信息。对用户的偏好，相似 DIN 的网络结构，对用户历史导航序列进行建模，获取用户偏好信息。
在用户提交搜寻需要之后，对导航引擎来说，也分为 召回 ， 排序 和过滤 几局部。
对于导航的召回，对性能要求比拟高，所以目前召回的后果较少。对排序来说，同样是多指标，而且多指标之间要进行均衡的业务。类比到电商举荐畛域，不仅心愿用户更多地对商品进行点击浏览，还心愿用户在看完商品介绍之后进行购买，进步 GMV。
对于地图出行，不仅心愿用户更多的应用导航且依照举荐的路线走，还心愿实走工夫要尽可能短，用户反馈尽量好。
而且，和其余畛域相似，多个指标之间会存在抵触，比方电商 CTR 和 GMV。在导航畛域，让用户尽可能的走关闭路线，没有进口，那必定实走覆盖率就回升了，然而这样布局的路线会绕远，工夫和间隔都变差。
多指标的均衡，如何在“帕累托最优”的状况下，进行多个指标之间的取舍、均衡，是大家始终在摸索的问题，咱们目前采纳的是 带束缚的最优化问题来进行建模，就是保障其余指标不变差的状况下，把某个指标最优化。
最初，用户拿到导航引擎返回的路线后果，特点是信息少，用户只能看到整条路线的总工夫、总间隔和免费等统计信息，对于这条路好不好走，能不能走很难晓得。
而且，大部分用户是在生疏场景下用导航，对导航依赖很重，很难决策走哪条路更好，这就导致 排序在首条的计划选择率很高 ，达到 90% 以上，这个偏置是很重大的，在训练实走覆盖率的时候，咱们设计了 偏置网络，来排汇用户这种偏向。
导航还有一个特点，一旦出错，对用户挫伤特地大，比方遇到小路，用户的车可能会呈现刮蹭；遇到封路，用户可能就得绕路，付出相当的工夫和金钱老本。这往往会比信息搜寻给用户带来的影响和挫伤更大。所以，咱们在过滤阶段，对 Badcase 的过滤也是严格作为束缚要求的。
路线布局召回算法
路线布局算法，经典的是教科书上的 Dijkstra 算法，存在的问题就是性能比拟差，线上理论利用都做了优化，这里就不开展介绍了。
当起起点间隔超过 500 公里，性能根本就不可承受了，尽管有启发式 A star 算法，然而 A star 算法有可能丢最优解，并不是完满解决性能问题的办法。
解决性能问题的思路，一个是分布式，一个是 Cache，而最短路线搜寻并不像网页搜寻，分布式并不能很好的解决性能问题，所以目前工业界理论应用的算法都是基于 Cache 的办法。
Cache 的办法就是 提前把一些起起点对之间的最短路线计算好（Shortcuts），在用户申请过去的时候，利用好这些 Shortcuts，达到放慢求路的目标（简略举例子，比方从北京到广州，如果提前计算好了从北京到济南，济南到南京，南京到广州的最短门路，那就能够在计算北京到广州的时候，利用这些提前计算好的最短路线）。
其中最为经典的一个算法就是CH 算法(Contraction Hierarchies)，在预处理阶段，对所有节点进行了重要性排序，逐步把不重要的点去掉，而后减少 Shortcuts；Query 查问阶段，从终点和起点别离开始双向求路，只找重要性高的点，来达到减速的目标。
既然是 Cache，就会面临一个更新的问题，比方原始路网的路况变动了，或者原始路网某条路封路了，那么提前缓存好的 Shortcuts 也须要更新。
这个时候 CH 的算法，因为 Shortcuts 结构设计不够法则，更新就很慢，无奈响应实时路况的变动。于是，路线布局算法推动到了下一代，CBR 算法（Cell based Routing），这个算法通过分而治之的思维，在预处理阶段，把全国路网切分成 n 个子图，切分的要求是子图之间连贯的边（边界边）尽可能的少。
在每个子图内，再持续往下切分，进而造成金字塔构造，预处理阶段就是把边界边之间的最短门路都提前算好，Cache 下来求路的时候，就能够利用这些 Shortcuts 了。
CBR 的长处是，在预处理阶段，路网的切分是分层的，每一层都足够小，在更新这一层的 Shortcuts 的时候，能够把数据都放到 CPU 的 L1 Cache 里去，所以计算速度特地快。
总结一下 CBR 和 CH 的区别：
- Query 查问性能，CH 更快，CH 是 0.1ms 级别，CBR 是 1 -2ms 级别。
- Shortcuts 更新性能，CH 全国路网更新最快能做到 10 分钟，而 CBR 能做到 15 秒更新全国，能够满足实时路况变动和路网实时更新的需要。
- CH 的 Shortcuts 不法则，导致不同策略之间（规避拥挤，高速优先等）不能很好的复用 Shortscuts 的起起点构造，所以不同策略须要独自重建 Shortcuts，内存占用十分大。
这是咱们排序的网络结构，右边是用户偏置网络，把路线排序的程序，以及疏导路线之间的类似度信息输出进去，冀望尽可能打消掉偏置带来的影响。两头输出的用户历史统计信息和用户导航序列信息，用来提取用户的个性化偏好。优化的次要指标是实走覆盖率。
新一代的路线布局算法，要求提供 随工夫推演的能力。比方 8:00 从终点登程，前面要走 1 2 3 ..n 条路达到目的地，假如 8:10 走到第 2 条路线，8:20 走到第 3 条路线，那么咱们在 8:00 计算 Shortcuts 的时候，就不能只用到 8:00 的路况，须要把后续进入某个路线的时刻思考进来，用那个时刻的路况来计算，这就是 TDR 求路算法，目前是高德独创的，能真正实现规避将来的拥挤，并利用将来的畅通来布局门路。
出行前 -ETA（预估达到工夫）
下面三幅图，选取的是北京西单金融街左近的区域，展现了在三个相邻工夫点上的交通状况。其中绿色、黄色、红色代表交通路况不同的状态。
假如当初是 18 点整，路况预测的指标就是预估将来时刻的交通状况，须要依赖每条路线的历史信息，以及周边街坊的路线拥挤信息，对时空两个维度进行建模。
对工夫序列的建模，用 RNN，LSTM 等 SEQ2SEQ 的序列，也有采纳 CNN，TCN 等。对空间信息的建模，目前支流的办法是用 GRAPH.
只管模型在一直降级，越来越简单，然而对于突发事件导致的拥挤，依据历史统计信息，很难预测精准，比方去年 9 月份在上海世博园区举办外滩大会，世博园平时很少有人去，历史路况都是畅通，而在散会期间，车很多导致很堵。
这个时候靠历史信息是很难预测精确，咱们须要一个能代表将来的信号，能力预测，这就是路线布局的信息，如果想去世博园的人很多，那么布局的量就会很多，咱们依据布局的量，就能晓得将来有很多人想要去世博园，就会导致世博园拥挤。
所以，咱们把布局的量，通过一个流量往工夫域的转换，引入到路况预测模型，成果获得显著晋升，尤其是在突发拥挤的时候，高德的这个研究成果被 KDD2020 收录，并且曾经在业务场景中失去了利用，有趣味的同学能够具体查看咱们的论文。
行中 - 用文本数据挖掘动静交通事件
持续向餐馆后退，导航途中，最怕遇到拥挤，封路等事件，所以高德会想尽一切办法开掘这些动静事件，帮忙用户躲避开。当初高德用到了多个维度的数据源，其中的行业和互联网情报都是文本数据，要用到 NLP 的技术来开掘。
介绍一下怎么用 AI 算法来开掘动静事件。
上面一段文本就是典型的来自于网络媒体的信息：
G0612（西和）高速南绕城路段西山隧道 ZK33+844（兰州方向）应急车道停一辆故障大客车临时关闭，行车道和超车道失常通行，请车辆留神避让、减速慢行。
这段信息是非结构化的，须要咱们做预处理，因素提取，再进行事件的组织，组织成架构化的信息，能力自动化的利用。
很天然的，针对因素提取，咱们用 BERT 模型建模，然而 BERT 模型太简单，性能比拟差，线上理论利用带来很大的挑战。
咱们采取了 常识蒸馏 的办法，训练一个简略的 Student 的网络，来解决性能问题。常识蒸馏最次要的是如何捕获潜在语义信息。高德 在业界率先提出了用比照学习框架进行常识蒸馏，同时，在计算样本之间间隔的时候，提出 COS- 间隔代替欧氏间隔的办法，可能让模型无效的学习到潜在语义表白信息。
对于 Student 表白的特征向量与 Teacher 特征向量间隔凑近，而要远离负例。应用余弦间隔，比方欧式间隔，可能更好适应 Teacher 网络和 Student 网络，输入的特征向量长度散布不统一的问题，这个工作成绩发表在了 AAAI2021 上。
出行后 -POI 数据过期（加强现势性）的问题
人们在高德地图上会看到很多地理位置趣味点（Point of Interest，缩写为 POI），例如餐厅、超市、景点、酒店、车站、停车场等。对 POI 数据的评估维度包含现势性、准确性、齐备性和丰富性。
其中，现势性就是地图所提供的天文空间信息反映以后最新状况的水平，简而言之，加强现势性就是指尽可能疾速地发现已开业、搬迁、更名、拆迁的过期冗余 POI 数据，并将其解决成下线状态的过程。这部分能够参考咱们之前公布的文章《高德地理位置趣味点现势性加强演进之路》。
以上仅是 AI 算法在出行场景利用的一些举例，更多的技术计划欢送大家来和咱们一起探讨。
出行前景 - 全局调度
对网页搜寻来说，后果是信息，能够有限复制，互不影响；对电商搜寻来说，后果是商品，能够认为商品足够多，不够再生产，所以也能够认为互不影响。
不同的是，导航搜寻进去的路线资源是无限的，你用的多了，我就用的少。比方，一条路畅通，咱们把人导过来，那么这条路就堵死了，所以咱们要做全局调度，进步路线资源的使用率。
咱们心愿全局调度零碎能和交通信号灯买通，在一个交通仿真的环境下，用多智能体强化学习的办法，学习到更大规模的交通系统上如何兼顾协调车辆、交通灯，充分利用路线资源，进一步缓解拥挤。咱们一起来摸索！
春招炽热进行中，2022 届毕业生看过去！
春招炽热进行中，2022 届毕业生看过去！
春招炽热进行中，2022 届毕业生看过去！