2019华为软件精英挑战赛

我们是成渝赛区   火炎焱燚龘 小队 很遗憾最终止步于复赛圈，虽然知道在复赛前也还调侃自己是成都3日游，但是在最终出来竞赛结果的时候也还是或多或少有一些失落。不过也感谢我的队友小炎子和小健，他们在竞赛中也付出了很多也给予了很多支持。

开始比赛时候，没有调度器，使用的是deep Q-Learning 规划路径，根据道路的长度与速度设置Q-Table.发车时间通过设置随机数来避免锁死，能够跑通，但是有太大的随机性，而且随机数越小时间越短但是容易死锁，随机时间越大不容易锁死，但是运行的时间就较长。
在寻找改进方案的过程中也查阅了很多资料，其中发现纳什均衡QLearning 是融合了博弈论，其实题目中的车子最终达到调度时间最短也就是一个博弈论的问题。但是由于相关资料比较少，没能够在短时间完成。因此提出的改进思路就是写调度器，根据调度器来规划发车的时间。

然而调度器之路却是漫长而艰难的，竞赛中所描述的规则比较多，所以调度器存写出来也是bug 重重，最开始的基本的思路为：
使用CAR ROAD CROSS 三个类分别记录车子，道路，节点的信息，在ROAD中使用向量记录车道里面的车子的信息，vector里面存放的信息为车辆的ID号。由于在不同的端点调度时候，对于同一个道路他对应的出路口不同（左右车道），因此使用两个指针，分别指向对于某个特定的CROSS的ROAD中的左右车道，一个是驶入方向 一个是驶出方向。调度器的主要流程根据官方的调度器伪代码

 在有了初步的调度器以后，虽然bug 重重，但是开始根据调度器结果来实时的调度车子运行。
解题主要思路

1. 读入数据后，使用dijkstra规划一次路径，将所有的规划的车子放置到对应的道路所在的车库（放置在道路里面车库不是节点，有点是可以方便区分出接下来要上的是哪一条道路）。
2. 设置每个时间片允许发车的最大数目，依次轮询各个路口的各条道路，先计算道路的拥挤情况，我们称之为道路占用率（占用率 = 道路上的车子数目/总共可以容纳的车子数目。 其中 总共可以容纳的车子数目 = 车道数*车道长度）。设置有一个阈值，占用率没超过阈值就允许发车，并且发车的数目和阈值相关，对应的函数逻辑是占用越少发车数目越多。
3. 实时的更新路权，每个时间片重新计算道路权重，在发车之前重新规划一遍路径，路权函数的设置就比较玄学了，主要还是调试出来的，我们的路权函数是考虑了道路长度和道路拥挤情况两个因素。我们采用分段函数，在车辆比较少的时候关注的是距离，所以此时关于长度的权重要大，而在中期道路上有很多的车辆时候，拥挤情况（道路占用率）更重要，因此占用率权重更大。
4. 每个时间片在路口对能够出路口的车辆重新进行规划路径，在规划路径之前需要先将本条道路的权重修改为最大，防止车辆回头，这个方法很有效，通过实时的规划车辆路径使得出路口的车辆能够及时规避拥堵的道路，因此采用这个方法以后道路出现死锁的几率情况明显下降。

在后期的修改中也曾尝试，使用回溯，当每次都尽可能多的放置车辆上路，然后采用等比步进保存一些时间片的道路现场信息，发现死锁以后回退到以前时间片，修改发车数目，不过时间比较紧张，存在一些BUG，就没能发挥出效果，不过这也是以后可以优化的一个方案。

最后，感谢华为给我们提供了一个锻炼的平台，让我们认识到自己的不足也让我们认识到很多大佬。同时也感谢我的两个队友，也祝你们能够再接再厉勇攀高峰。

本人的github地址为：https://github.com/DeamonYang/
后期整理好代码后将上传到github.