序言：又到春招季！
作为国民级出行做事平台，高德业务快速发展，大量校招/社招名额开放，欢迎大家投递简历，详情见文末。为帮助大家更理解高德技能，我们策划了#春招专栏#的系列文章，组织各业务团队的高年级同学以科普+运用实践为紧张内容为大家做干系先容。
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算法在出行场景运用的一些举例，更多的技能方案欢迎大家来和我们一起磋商。
出行前景-全局调度
对网页搜索来说，结果是信息，可以无限复制，互不影响；对电商搜索来说，结果是商品，可以认为商品足够多，不足再生产，以是也可以认为互不影响。
不同的是，导航搜索出来的道路资源是有限的，你用的多了，我就用的少。比如，一条路畅通，我们把人导过去，那么这条路就堵去世了，以是我们要做全局调度，提高道路资源的利用率。
我们希望全局调度系统能和交通信号灯打通，在一个交通仿真的环境下，用多智能体强化学习的方法，学习到更大规模的交通系统上如何统筹折衷车辆、交通灯，充分利用道路资源，进一步缓解拥堵。我们一起来探索！
作者：高德技能小哥
本文为阿里云原创内容，未经许可不得转载