别问，问就惜败。
1 总结
研一上学期就获悉了华为比赛的信息，笔者作为本科期间多次参加数学建模竞赛的老菜鸟，其实还是有点想法的，再加上实验室的小伙伴（C++同学）的“勾搭”，直接就上了“贼船”。
2019年3月10日至29日为练习阶段，30日9:00~17:00为初赛阶段。三只小菜鸡不停啄米，走了不少弯路，最后一周通宵了两次。最后由于时间紧张，棋差一招，很遗憾，很不甘，来年再战！
接下来说说一些关键的时间点：
- 10日，JAVA同学和C++同学分别开始构建底层数据结构。笔者开始读任务书，关注论坛。
- 17日，笔者写完调度系统的伪代码。
- 26日，JAVA同学实现了判题器，同时C++同学陷入调Bug自闭状态。
- 30日，最重要的优化没来得及实现，败北。
下面是比赛的思路：
2 调度系统
话不多说，直接上伪代码：
for(T){
// 对车进行标记，终止状态为0，等待状态为1，可入库状态为2。ASC表示升序。
for(EachRoad){
1StateCarQueue_EachRoad = queue[]
0StateCarQueue_EachRoad = queue[]
// 是否把终止状态的车也顺便放在一个队列里面，这样可以省去调度时遍历的时间。
AheadCar_EachChannel(1:NumberOfChannel) = 0 //对每个Channel设一个变量
for((i = LenOfRoad):1:1){
for(EachChannel_ASC){
if(Road_Record(i) != 0){
CarID = GetCarID()
AheadCar_EachChannel = CarID
V1 = min(Car_Speed, Road_Speed)
if(AheadCar_EachChannel == 0){
S1 = GetDistanceToAcrossRoad()
V2 = min(Car_Speed, NextRoad_Speed)
S2 = V2 - S1
if(S2 <= 0){
S2 = 0
Car_State = 0
BehindCarState_EachChannel = 0
if(S1 < V1 && RoadID == EndRoad){
Car_State = 1
}
}
else{
Car_State = 1
BehindCarState_EachChannel = 1
}
}
else{
S1 = GetDistanceToAheadCar()
GetCarChannel
if(BehindCarState_EachChannel == 1 && S1 < V1){
Car_State = 1
}
else{
Car_State = 0
BehindCarState_EachChannel = 0
/*
这里可能需要找出由于前面阻挡的车为终止状态，而导致无法过
路口的车。即 S2 > 0 但是被前车所阻挡。后面这些车需要封锁这
条路，然后更新一下地图，再算其最短路径。
*/
}
}
if(Car_State == 1){
1StateCarQueue_EachRoad = ArcossCarQueue_EachRoad.append(CarID)
}
else{
0StateCarQueue_EachRoad = ArcossCarQueue_EachRoad.append(CarID)
}
}
}
}
}
// 对道路内终止状态即Car_State == 0 的车进行调度。
for(EachRoad){
for(EachChannel){
for(LenOfRoad:1:1){
if(Car_State == 0){
CarRun
}
}
}
}
// 对路口车辆调度。ASC表示升序。 TODO:需要加入一个到达终点车的判定。
for(EachCrossRoad_ASC){
CarCanAcross = 1
while(CarCanAcross){
for(EachRoad_ASC){
for(AcrossCarQueue_EachRoad){
if(AcrossCarQueue_EachRoad == [] or CarCanAcross_EachRoad == 0){
// CarCanAcross_EachRoad = 0
break
}
CarID = GetCarID()
if(V1 - S1 > 0 && RoadID == EndRoad){
CarOffline
}
if(S2 <= 0){
// CarRun
// ChannelBlcok
// AcrossCarQueue_EachRoad.pop()
// 提取出被锁住的同channel的车，剩余队列继续进行路口调度
}
Car_Direction = GetCarDirection() // 1, 2, 3 分别表示 D, L, R
NextRoadID = GetNextRoadID()
if(NextRoadHaveSpace == 0){
CarCanAcross_EachRoad = 0
BlockedCar_EachRoad = AcrossCarQueue_EachRoad
break
}
if(Car_Direction == 1){
CarAcross // CarCanAcross需要从小号车道开始进入
AcrossCarQueue_EachRoad.pop()
// 更新Both Roads
}
elseif(Car_Direction == 2){
ConflictRoad = GetTurnLeftConflictRoad()
if(AcrossCarQueue_ConflictRoad_FirstCar_Dierection == 1){
break
}
CarAcross
AcrossCarQueue_EachRoad.pop()
/*
(100,21,30,9,55)表示的是第100号路口，按顺时针方向道路为21
, 30, 9, 55。此时本道路车辆左转前需要检查本道路的逆时针方向第
一条道路有无直行车辆。有直行车则冲突，暂时结束对本道路的调度，
转而调度下一道路。
*/
}
else{
ConflictRoad1 = GetTurnRightConflictRoad1()
ConflictRoad2 = GetTurnRightConflictRoad2()
if(ArocssCarQueue_ConflictRoad1_FirstCar_Direction != 1 && AcrossCarQueue_ConflictRoad2_FirstCar_Direction !=2){
CarAcross
AcrossCarQueue_EachRoad.pop()
}
/*
本道路车右转前需要先检查本道路的顺时针方向第一条道路有无直行
车辆，然后检查本道路顺时针方向第二条道路有无左转车辆。
*/
}
}
if(sum(CarCanAcross_EachRoad) == 0){
CarCanAcross = 0
break
}
}
}
}
// 对出车库的车进行调度，如果没有空位，则延迟一个单位时间出发。
for(EachCrossRoad){
if(GarageHaveCar){
GetCarID()
GetStarTime()
if(StartTime <= T && MaxCar < N && RoadLoad < n% ){
//若车辆达到计划出发时间，且所有道路总车辆小于N，且该道路负载程度小于n%。
//道路负载程度 = 道路车辆数/(道路长度*道路车道数)
if(RoadHaveSpace){
CarOut //检索出第一条道路的起始列有无空当。有空当的话优先进入小号Channel。
}
}
}
}
}
3 优化算法
笔者之前犯了一个严重的错误——没有分析地图数据，而这直接导致了优化算法的思路出现了问题。我们一直纠结于如何排除死锁、优化路径组合和道路负载均衡。然而真正重要的一点，也是能在简单分析地图数据后就知道的——车辆的速度问题。
就地图数据来看，车辆的计划出发时间都在100个时刻之内，而实际的出发时间需要人为设定，这正是判题器的作用之一（输出车辆的实际出发时间）。我们再来看看系统调度总时间的量级，其实是在千位的。换句话说，即使考虑最极端的情况，我们让所有车辆都在第100个时刻之后出发，也影响不了太多总时间。再看车辆的速度其实只有2，4，6，8，10，12，15，16这七种，那么我们为何不分批次把所有同速度的车来进行调度呢？这样无疑去除了慢车对快车速度限制，同时间接地减少了死锁和道路负载过大的问题。这是我们30日上午幡然醒悟，然而时间有限，确实来不及实现了。
那么解题流程应该是这样：
- 利用Floyd算法计算出每个路口节点的最短路径，并以此初始化所有车辆路径。
- 按照速度对所有车辆分批$P_1,\dots,P_7$。
- 对$P_1$车辆利用遗传算法优化调度系统的参数$MaxCar_1$和$RoadLoad_2$，并得到一个最优调度时间$T_1$。以此时间作为$P_2$车辆的计划出发时间。
- 依次对后续每批车辆进行第3步操作。
- 最终可以得到最优的系统总调度时间为$T = T_1 +\dots +T_7$，并输出每辆车的实际出发时间和最短路径。
