2019华为软件精英挑战赛

发表于 | 分类于 |

2019年3月参加了华为软件精英挑战赛，过程很刺激，西北赛区真的强，最后成绩：西北赛区初赛第四名，整理了比赛的过程跟代码，分享给大家~~

题目描述

背景信息

日常生活中，很多拥堵是由于车辆行驶路线规划失误，大批车辆集中选择主干道行驶导致通行效率下降。

如果车辆都由调度中心统一规划调度路线，拥堵问题将得到大大缓解甚至彻底解决。

实际上这一技术已经在工业领域如矿山车辆、无人货仓等得到广泛应用。

但道路上的私家车辆尚无法进行统一规划，未来，自动驾驶和物联网技术的结合，使得彻底解决这一难题出现了曙光。

请同学们提前出任“首席城市交通规划官”，为未来城市规划好每一辆车的行驶路线。

假设条件

  • 路口完全立交：假定在每一个路口交汇的所有道路都可以完全互连，且车辆通过路口时不考虑在路口的通行时间。

  • 无限神奇车库：我们认为，系统中的每个地点都有一个无限容量的“神奇车库”。车辆在未到既定出发时间前，或者到达目的后，就停放在“神奇车库”中，完全不影响其他车辆通过。但车辆一旦出发，在行驶过程中则不允许进入车库空间。

  • 不允许超车变道

  • 排队先到先行

  • 车道固定进入

题目输入

每一个测试用例都分为三部分：

road.txt/car.txt/cross.txt 

1
2
3
道路：(道路id，道路长度，最高限速，车道数目，起始点id，终点id，是否双向)  
车辆：(车辆id，始发地、目的地、最高速度、计划出发时间)  
路口：(路口id,道路id,道路id,道路id,道路id)

图形化实例：

答案提交

要求为每辆车规划最短路线，输出answer.txt 

1
(车辆id，实际出发时间，行驶路线序列)

评分标准

系统调度时间短者胜出。系统调度时间指，从系统调度开始时间（非第一辆车实际开始运行的时间），至所有车辆全部到达目的地的时间，两者之差作为系统调度时间。

若系统调度时间相同，则所有车辆的行驶用时总时间最少者胜出。

解决方法

建立一个矩阵，表示每条路的拥堵程度：

[道路长度]+[每条路当前时刻正在行驶的车辆数/车道数]，按照一定的权重比求和

矩阵的大小都是cross*cross

对新矩阵中的每个点做floyed，求出其最短路线。

其中，在计算每条路当前时刻正在行驶的车辆数时：

对已经规划好路线的车辆，每条路的长度/车辆速度（不能超过道路最大速度）=每条路上花费的时间

知道了出发时间，每条路上的时间，就可以计算出当前时刻所在的道路，在矩阵中该路线的位置加1

每秒发n（初赛62，复赛80多）辆车，这个n的值是调参调出来的不出现死锁的最大发车数量

Floyed最短路径算法

Floyd算法是解决任意两点间的最短路径的一种算法，是一个经典的动态规划算法。

上图表示是几个结点，以及结点之间的距离，上图的信息可以用一个矩阵来表示：

比如求取i到j之间的最短路线，找到i和j之间的结点k，判断 

1
2
3
4
for (i=1; i<=nv; i++)
      for (j=1; j<=nv; j++)
          for (k=1; k<=nv; k++)
              map[i][j] = min(map[i][j], map[i][k]+map[k][j]);

求i到j之间的距离，先找到第一个结点k，判断加入k之后距离会不会变小，如果变小，再求k到j之间的最小距离，在找到第二个结点k…依次循环

其他方法

  • 将速度大的车选出来，放在一个组，让他们先发车，因为速度大的车先发，就会先到终点，会减少后面道路的拥堵程度，但是效果并不好。
    分析原因：可能是让速度大的车先发了，后面的车都是速度慢的，整体来看，道路可能更容易堵。

  • 让速度大的那组，一次多发一些车

  • 行车方向相近的，分在不同的组，避免造成拥堵

复赛

复赛加上了优先车辆跟预置车辆的约束条件，优先车辆可以优先使用道路的路权并且先发车，预置车辆是指道路已经确定不能修改的车。

处理方式是：最终的评分标准中，总系统调度时间+优先车辆的时间

优先车辆：先发车，还是按之前的方法求出每辆车的最短路线

预置车辆（3000辆左右）：跟普通车辆一起发，在发车前进行一个if判断，如果是预置车辆，则按照其路线发，如果是普通车辆，就跟之前一样的处理方式。

遇到的问题

题目要求程序运行时间900s=15min，但是我们的python运行时间是半个多小时，最终翻译成c++程序就只要几分钟，时间大都浪费在floyed运算上面。

遇到瓶颈，无法继续优化路线，解决方法：多刷群消息，通过别人讨论的问题，寻找有用信息，线下交流会，多跟老师交流，多尝试。

附上求路线的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def process_10(car, road, cross):
    #method 10
    
    print('-------------------1')
    
    #create graph matrix
    numOfCross = len(cross.idList)
    #numOfRoad = len(road.idList)
    adjMatrix = np.zeros([numOfCross, numOfCross]) + sys.maxunicode
    roadMatrix = np.zeros([numOfCross, numOfCross],dtype = int)
    roadMatrixIndex = np.zeros([numOfCross, numOfCross],dtype = int)
    roadMatrixSpeed = np.zeros([numOfCross, numOfCross],dtype = int)
    roadMatrixChannel = np.zeros([numOfCross, numOfCross],dtype = int)
    for i in range(len(road.idList)):
        adjMatrix[road.fromList[i]-1, road.toList[i]-1] = road.lengthList[i]
        roadMatrix[road.fromList[i]-1, road.toList[i]-1] = road.idList[i]
        roadMatrixIndex[road.fromList[i]-1, road.toList[i]-1] = i
        roadMatrixSpeed[road.fromList[i]-1, road.toList[i]-1] = road.speedList[i]
        roadMatrixChannel[road.fromList[i]-1, road.toList[i]-1] = road.channelList[i]
        if(road.isDuplexList[i] == 1):
            adjMatrix[road.toList[i]-1, road.fromList[i]-1] = road.lengthList[i]
            roadMatrix[road.toList[i]-1, road.fromList[i]-1] = road.idList[i]
            roadMatrixIndex[road.toList[i]-1, road.fromList[i]-1] = i
            roadMatrixSpeed[road.toList[i]-1, road.fromList[i]-1] = road.speedList[i]
            roadMatrixChannel[road.toList[i]-1, road.fromList[i]-1] = road.channelList[i]
    for i in range(numOfCross):
        adjMatrix[i,i] = 0
    print('-------------------2')
        
    #compute the min distance by floyd
    distanceMin, routeMin = floyd(adjMatrix, numOfCross)
    
    print('-------------------3')
    #sum Of the routes
    sumRoutesMat = np.zeros([numOfCross, numOfCross],dtype = int)
    
    #compute the time of the routes
    #sumCrossMat =  np.zeros([numOfCross,numOfCross])
    #sumCrossList = [[car.fromList[i],car.toList[i]] for i in range(len(car.idList))]
    #for i in range(len(sumCrossList)):
        #sumCrossMat[sumCrossList[i][0] - 1,sumCrossList[i][1] - 1] += 1
    #[([np.empty([0],dtype=int)] * numOfCross) for i in range(numOfCross)]
    #routeCrossMatCode = [[np.zeros([numOfCross,numOfCross],dtype=int) for i0 in range(numOfCross)] for i1 in range(numOfCross)]
    #routeCrossList = [[np.empty([0],dtype=int) for i0 in range(numOfCross)] for i1 in range(numOfCross)]
    #routeCrossListCode = [[np.zeros([1,numOfRoad],dtype=int) for i0 in range(numOfCross)] for i1 in range(numOfCross)]
    
    #for i in range(numOfCross):
        #for j in range(numOfCross):
            #if sumCrossMat[i][j] > 0:
                #routeCrossList[i][j] = [[routeMin[i][j][i0]-1,routeMin[i][j][i0+1]-1] for i0 in range(len(routeMin[i][j])-1)]
                #routeCrossListCode[i][j] = [roadMatrixIndex[i0,j0] for i0,j0 in routeCrossList[i][j]]
                #for i0,j0 in routeCrossList[i][j]:
                    #routeCrossMatCode[i][j][i0,j0] = 1
    
    #answer
    numOfCar = len(car.idList)
    planTimeList = np.zeros(numOfCar, dtype = int)
    print('-------------------4')
    costTimeList = np.zeros(1, dtype = int)
    endTimeList = np.zeros(numOfCar, dtype = int)
    answer = [[''] for i in range(numOfCar)]
    timeOfNow = 0
    carInRoutesIndex = np.arange(numOfCar)
    print('-------------------5')
    carRouteCrossMatCode = [[np.zeros([numOfCross, numOfCross],dtype=int)] for i0 in range(len(car.idList))]
    print('-------------------6')
    for i in range(numOfCar):
        if i%600 ==0:
            print(i)
            #distanceMin, routeMin = floyd(adjMatrix + sumRoutesMat * 300, numOfCross)
        i0 = car.fromList[i] - 1
        j0 = car.toList[i] - 1
        routeCrossListCode_0 = [roadMatrixIndex[routeMin[i0][j0][i]-1,routeMin[i0][j0][i+1]-1] for i in range(len(routeMin[i0][j0])-1)]
        roadIdList = [road.idList[i] for i in routeCrossListCode_0]
        for j1 in range(len(routeMin[i0][j0])-1):
            carRouteCrossMatCode[i][0][routeMin[i0][j0][j1]-1,routeMin[i0][j0][j1+1]-1] += 1
        if i>1000:
            timeOfNow = math.floor((i-1000) / 28)
        else:
            timeOfNow = car.planTimeList[i]
        planTimeList[i] = max(timeOfNow,car.planTimeList[i])
        costTime_tmp = [road.lengthList[i] for i in routeCrossListCode_0]
        costTime_tmp2 = [road.speedList[i] for i in routeCrossListCode_0]
        costTime_tmp3 = np.vstack((costTime_tmp2,car.speedList[i] * np.ones([1,len(routeCrossListCode_0)]))).min(0)
        costTimeList = sum(costTime_tmp / costTime_tmp3)
        endTimeList[i] =  planTimeList[i] + costTimeList
        answer[i] = str(car.idList[i]) + ', ' + str(planTimeList[i]) + ', ' + str(roadIdList)[1 : -1]
        carInRoutes = carInRoutesIndex[endTimeList >= timeOfNow]
        #print('i:'+str(i)+'--------'+'timeOfNow:'+str(timeOfNow))
        #print(sum(endTimeList >= timeOfNow))
        sumRoutesMat = sumRoutesMat * 0
        for j2 in carInRoutes:
            sumRoutesMat += carRouteCrossMatCode[j2][0]
        sumRoutesMat[roadMatrix > 0] = sumRoutesMat[roadMatrix > 0] / roadMatrixChannel[roadMatrix > 0]

    return answer