CodeCraft2019
华为软件精英挑战赛2019(https://codecraft.huawei.com)
复赛杭厦赛区第二，复赛未使用判题器
比赛的初赛，复赛和决赛均围绕智能交通中的车辆调度问题，即在给定地图（路口和道路）和车辆起始点的情况下，规划每辆车的路径和发车时间。
- 评价标准：
系统调度时间，从开始调度到所有车辆全部到达终点的时间
- 问题难点：
与实际交通场景类似，存在某些道路与路口在每辆车的路径规划中均处于高优先级，例如某道路车道宽限速高，又例如某路口在城市中心位置。这些道路和路口容易出现拥堵，由于系统调度是按照一定规则进行，拥堵的路口在某些条件下会出现死锁状态。问题的难点在于，如何保证不死锁的情况下，使得所有车都能尽早出发。
初赛
- 思路：
（1）按照车辆的预计发车时间升序排序，每个时间片发同样数量的车。在本步确定了每辆车的发车时间（保证实际发车时间晚于预计发车时间）。
（2）使用有向图表示整个地图，顶点为路口，边为道路。
（3）针对每一辆车，计算当前时刻的有向图每条边的权重，权重由道路长度、车辆速度、车道数和道路拥挤程度决定，使用dijkstra算法规划每辆车的路径。
（4）针对每辆车，当规划完其路径后，调高其行驶期间（人为设定此时长）沿途道路的拥挤程度，以达到后发车辆避开拥挤道路的目的。
（5）每规划一定数量的车之后，随机抽取一定比例的已经规划了路径的车重新规划路径。
- 遇到的问题：
正式赛比训练赛的地图大、待规划的车辆多（上升了一个数量级），线上运行一次需要十多分钟才能得到死锁与否及具体的系统调度时间。此外，我们的算法中设计的参数过多，比赛过程中时间紧张、调参困难。
复赛
增加预置车辆，预置车辆的实际发车时间与路径均事先给定且无法改变。增加优先车辆，优先车辆在调度中享有优先权，并且在最终计算成绩时，优先车辆的调度时间会加权重，加入到总时间中。
- 思路：
（1）确定每个时间片发的车辆数。由于预置车辆无法修改发车时间，如果某个时间的预置车辆数大于该时间片的发车数，则全部发预置车辆；如果预置车辆数不够该时间片的发车数，则先用可发的优先车辆填充，再用可发的普通车辆填充。
但训练赛的预置车辆分布类似于[0, 80, 0, 0, 0, 80, 0, 0, 0, 80, ...., 80(end), 0, 0, 0, 0, 0, 0, ...]（表示第1s有0辆预置车出发，第2秒有80辆预置车出发, 80(end)表示最后一批预置车，在前面一段时间内会隔几秒发出一大批预置车。但我们每秒发的车辆的上限为40，由于预置车的存在，在前面的一些秒内，会出现对路网的冲击，导致死锁。所以每个时间片的发车数按照以下规则计算：当预置车还没有发完，每秒发较少数量的车；当预置车辆发完之后，每秒发较多数量的车。
在正式赛中，预置车辆的分布类似，但尖峰变低，由80变成了20左右，这种低的尖峰对路网来说并不造成冲击，因为路网可以承受40辆/秒的发车辆。所以在正式赛中，每秒发车数量为一个定值。
（2）构建有向图和其它一些与有向图的边相对应的量（在计算有向图边的cost中使用）
（3）初始化路网的热度图heatmap
预置车辆的发车时间和行驶路径确定，考虑这些车辆对路网的热度影响初始化路网的热度图。
（4）使用dijkstra方法规划每辆车的路径，并且更新路网的热度。
（5）寻找开源判题器对初赛的比赛数据进行线下调度，统计分析每辆车实际运行时间，用以优化初赛时人为设定的每辆车的行驶时间。
开源判题器使用的是https://github.com/HgWe/codecraft2019 ，经过一些调整改为了加载规划好的路径信息进行调度（实际结果与官方似乎并非完全一致，但差得也不多），地图数据使用的是初赛的比赛图2，统计结果如下：
故采用了200作为复赛正式赛的实际参数。
- 正式赛的需求变更：
可以调整10%的预置车辆的路径（发车时间不能改）。
- 思路：
（1）先按训练赛的思路进行一次规划，获得所有道路在每个时刻的拥挤度数据。
（2）统计每一辆预置车辆发车时，其预置路径沿途的总cost值。
（3）挑选预置车辆中cost最高的前10%的车辆，对他们的路径进行一次重新规划。
- 比赛过程：
（1）正式赛和训练赛数据的难度不一样，正式赛地图更简单。表现为，训练赛的地图最高可承受43辆/s的发车数，而正式赛1图可以承受110辆/s、2图可承受?辆/s的发车数。而且正式赛和训练赛预置车辆规模不同，在总车辆均为约600,000辆的情况下，训练赛为20,000辆预置车辆，正式赛为3,000辆预置车辆。而且正式赛中两张地图的难度也相差很大。
（2）正式赛的预置车辆占总车辆的比例非常低，从而导致针对复赛的需求变更对最后的总时间提升效果不明显。
（3）由于没有预见到正式赛中两张地图难度差别大，在调整参数时，是对着图1进行优化，使得图1的调度时间较短，为复赛获得好名次奠定了基础。
决赛
增加车牌的字符检测需求。
- 思路：
因为之前接触的cv的东西，所以第一直觉就是使用目标检测的方法。但数据集只给了车牌对应的label，并没有给出对应字符的box，所以需要人工标框。
（1）车牌识别部分（a）使用传统cv方法，检测图片中的字符并生成框。
（b）人工核对框的位置和大小。
（c）由于比赛只能使用CPU，所以选择YOLOv3进行字符的检测。
（2）路径规划部分
（a）在复赛调开源判题器的过程中体会到了C++的优势，速度是真的比Python快到不知道哪里去了，不说别的，就是比赛现场调起参来迭代的速度都会快很多，有限的比赛时间内都人工梯度下降都能搜到比较好的参数，于是决赛一开始就果断换C++，整体思路不变，翻译成C++
（b）复赛中遇到一些特殊的地图，一些道路的拥挤度已经被设置得很高了，但还是有些车会去走这些路，这也许意味着在特殊的路网结构下，想从某个出发点到另外一些出发点，这些道路是必经之路。因此我们决定采用两次规划的方式（i）第一次按原思路规划，然后挑出拥挤度奇高的道路（用判题器导出数据，统计分析，人为选定阈值）。
（ii）第二次规划之前，在对路网拥挤度做初始化时，除了使用预置车的路径信息，同时使用前一步得到的结果，将那些拥挤度奇高（必经之路）的拥挤度事先调得很高，这样必经之类的车还是会选择这条路，但其他车能避开就避开了，起到分散车流的作用。
（c）整体框架使用迭代的方式，在每一轮迭代中先按上述思路规划路径，然后使用开源判题器（https://github.com/PokerM/CodeCraft2019 （康康看了都说叼的判题器，来自上交队伍））对规划结果进行判断，然后提高发车密度继续迭代，卡着时间限制的上限一直迭代，最后输出没有死锁的最好结果。
- 比赛过程：
（1）手工标框工作量太大，首先使用传统cv的方法生成大量的框减少了很多人力。
（2）在决定方法之前应该先调研，例如有CRNN的网络从图像中识别字符。咕咕咕队伍只是使用普通的分类网络就实现很高的准确率，也是值得学习的。
- 一些插曲
（1）一般来说，发车强度越高则最终调度时间越短，这也是我们所追求的目标，但是强度太高会导致死锁的几率增加，一旦死锁就没有成绩了，这是无法承受的。这两者是互相矛盾的。加上决赛的特殊机制：分几轮，仅第一轮公开地图数据，后几轮都使用不公开地图不断淘汰队伍，我们如果针对第一轮的数据进行激进的调参，也许可以增加进入后续轮的概率但后边地图一变翻车的几率就很高；如果调参时相对保守，则针对未知地图翻车的概率会低一些，但也许第一轮就被淘汰了（后来事实证明我们的确第一轮就被挤掉了233）。在算法确定的情况下，精确性与鲁棒性的选择从来都是一个无法逾越的trade off。
（2）训练阶段其实在决赛的训练阶段，路径规划部分的框架有过几种尝试。给定一个初始发车强度，若第1次迭代就死锁，则后续不断降低发车强度并规划、调度，直至出现第一个不死锁的情况，然后停止迭代并输出结果；若第1次迭代未死锁，则后续不断提高发车强度并规划、调度，直至出现第一个死锁的情况，然后停止迭代并输出最后一个不死锁的结果。这样的思路有两个问题：1.并不存在一个确定的发车强度分水岭，低于它一定不死锁而高于它一定死锁，其实经过我们测试发现在中间存在一个“过渡地带”，这附近的死锁与否挺随机的，而且调度时间也并非与发车强度呈绝对的单调关系；2.不同的地图数据，特性相差悬殊，最优的发车强度可能相差很远，而按这样的框架，搜索的起始点与搜索步长都是事先定好的，并不能保证在系统限制的运行时间内一定能结束迭代并输出结果，一旦超时直接没有成绩（我怀疑在决赛中有几个队伍被淘汰就是超时了而非死锁）。
（3）基于（2），考虑了变步长搜索、双向搜索等方式，对比之后觉得其实都不理想，最终比赛现场决定采用卡着时间上限、不管死锁与否只管一直搜的方案。
总结
（1）使用C++，python语言太慢。
（2）比赛总体的思路贯穿初赛预赛决赛，初始的起点决定最后的高度。正式赛中的需求变更不会太难，不对需求变更做处理也能跑的通。
（3）做好版本管理。
（4）训练赛和正式赛的数据特点可能不一样，需要现场做针对性的优化。要小心训练赛的方法过拟合。