文件列表:

CodeCraft2019 (0, 2019-11-10)
... ...

# CodeCraft2019 2019年华为软件精英挑战赛,京津东北赛区初赛第四,复赛第三,决赛全国32强,珞珈山丶陈小帅。 历时将近两个月的比赛终于落下帷幕,从初赛到决赛一共写过五个大版本,六十个小版本,初赛及复赛时设计过很多不同的车辆排序方式,权重函数,发车方式等,针对不同地图进行调参,决赛时由于不公开地图,且练习赛时已基本将不同的设计定型,因此决赛时仅有发车数辆一个参数,也有利于使用判题器快速自动调参,此开源版本为最终决赛用代码。 ## 调度策略 1、车辆调度基于每秒发车,假设参数设定每秒发m辆车,该时刻已有n辆预置车辆,则理论该时刻发车数为m - n辆,同时考虑该时刻预置车辆对后续时间片的影响,如取影响时间段为n / 20,时间段内假设每秒都有20辆预置车辆出发,同时当某时刻预置车辆过大时,下一时间片暂停发车,因此实际每秒的发车数量并没有达到m - n辆,而是受之前及当前时间片的预置车辆的影响,自适应确定发车数量。 2、将车辆分为优先级车辆和普通车辆,将两种车辆集合分别进行排序,首先将车辆按计划出发时间排序,计划出发时间相同的车辆按照起点均匀分布排序,以保证地图各道路负载均衡。如有10辆车,起点分别为{1, 1, 2, 2, 2, 3, 3, 4, 4, 5},则将车辆排序为{1, 2, 3, 4, 5, 1, 2, 3, 4, 2},代码中有不同排序方式选择,其中引入按车辆理论行驶时间排序,用于确定改变哪些预置优先级车辆的出发时间,总体调度基于上述的计划出发时间及出发地均匀分布排序。 3、发车顺序优先发优先级车辆,该时刻可发的优先级车辆发车数小于该时刻发车数时,发普通车进行补充,如该时刻由调度策略确定发车数为m,而该时刻可发的优先级车辆数为n,则该时刻发n辆优先级车,m - n辆普通车,当优先级车及预置车均调度完成后,普通车辆按间隔时间为4秒发车。(间隔4秒发车效果比每秒发车效果更好,可能因为道路权重和权重刷新方式不同,部分队伍采用每秒发车效果优于间隔4秒发车。) 4、道路初始权重为:长度 / 速度,其中当道路限速小于所有车辆最大速度时,速度为道路限速,否则为所有车辆最大速度,权重增加部分为:该道路历史车辆总数 / 车道数,即权重函数为:length / speed + carsNumber / channel,对车辆进行路径规划时,将车辆经过的所有道路按照此函数更改权重。 5、路径规划采用Floyd算法,每辆车路径规划完道路权重都会发生改变,但此时并不更新权重矩阵,该时刻所有车辆调度完成后再更新权重矩阵,即每秒更新一次(间隔4秒发车时每4秒更新一次),并非每辆车更新一次,因此选择Floyd算法。算法,每辆车路径规划完道路权重都会发生改变,但此时并不更新权重矩阵,该时刻所有车辆调度完成后再更新权重矩阵,即每秒更新一次(间隔4秒发车时每4秒更新一次),并非每辆车更新一次,因此选择Floyd算法。

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：