# SDK_python

**Repository Path**: YanMingBo/SDK_python

## Basic Information

- **Project Name**: SDK_python
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2019-03-18
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 华为软件精英挑战赛 CodeCraft-2019 小结
在小结开始之前，需要特别感谢[GitHub判决器](https://github.com/AkatsukiCC/huawei2019-with-visualization)开源的大佬。我们很多想法都是在次基础上去完成实现的。
### 初赛赛题简介：
1. 背景信息
l 道路交通是城市的核心要素之一。  
l 随着社会经济的发展，中国城市的车辆保有量已经越来越多，大都市慢慢变成了“堵”市。如何在出行时避免拥堵，是每一个人的目标。  
l 日常生活中，很多拥堵是由于车辆行驶路线规划失误，大批车辆集中选择主干道行驶导致通行效率下降。  
l 如果车辆都由调度中心统一规划调度路线，拥堵问题将得到大大缓解甚至彻底解决。  
l 实际上这一技术已经在工业领域如矿山车辆、无人货仓等得到广泛应用。  
l 但道路上的私家车辆尚无法进行统一规划，未来，自动驾驶和物联网技术的结合，使得彻底解决这一难题出现了曙光。  
l 请同学们提前出任“首席城市交通规划官”，为未来城市规划好每一辆车的行驶路线。  
2. 题目定义  
l 在模拟的道路图上为每一辆车规划行驶路线，系统会自动根据规划路线运行。  
l 在路线合法的前提下，最终所有车辆按照规划的路线到达目的地。  
3. 系统假定  
l 路口完全立交：假定在每一个路口交汇的所有道路都可以完全互连，且车辆通过路口时不考虑在路口的通行时间。  
l 无限神奇车库：我们认为，系统中的每个地点都有一个无限容量的“神奇车库”。车辆在未到既定出发时间前，或者到达目的后，就停放在“神奇车库”中，完全不影响其他车辆通过。但车辆一旦出发，在行驶过程中则不允许进入车库空间。
4. 约束条件 ...

### 比赛成绩：
比赛成绩并不是很理想，在初赛练习赛最后一天，联系地图达到每张500+s，排名20。  
初赛比赛当天，由于路口顺序并不是北、东、南、西的顺序，而是顺时针的方式。并且路口号、车辆号、道路号都不连续，导致花费了很长时间去修改代码。最后剩余调餐时间不足，以一张图2600+s完成比赛，遗憾未进复赛。
### 题目思路：
1. 首先考虑车辆的路径规划，由于没有很好的想法，于是采用Floyd的最短路算法，给车辆进行路径规划。（貌似A星算法对此题可能有所帮助，但是没有进一步深入研究）
2. 考虑慢车对快车速度的影响，将车辆发车顺序，按照速度降序，发车时间升序。
3. 通过实时更新地图，来规划车辆后续的行进方式。地图的更新参数有：某一道路上的车辆数、车道限速、车道长度、车道个数。
4. 对于路口循环死锁问题的解决：
   1. 当所以路口遍历后，路口不再发生更新，且路口未完成调度，则认为死锁
   2. 记录上一时刻的地图状态
   3. 改变发生死锁的路口的第一优先级车辆的行驶方向（选择非车辆来时路段，非原计划行驶路段，选择改变后路径长度最短路段。若无该路段，则选择不进行更改）。所以这个解锁方式也是概率解锁的，不是很理想～
   4. 改变车辆行驶路径后，回溯上一地图状态后，重新进行路口调度。
   
（路口循环死锁的问题解决解决的非常不理想，首先需要与官方完全一样的判决器，但是我们采用的是Github上大佬的一个并不完全准确的判决器，其二路况信息的记录与回溯占用大量的内存和时间资源，在限时内，无法完成。）

### 判决器思路的简单介绍：

```python
def simulate(self, graph, epoch):
        visualize = visualization()
        visualize.crossLocGen()
        while True:
            self.step(graph)
            #visualize.drawMap()
            if CARDISTRIBUTION[2] == CARNAMESPACE.__len__():
                print(CARDISTRIBUTION[2])
                break
            if self.dead:
                break
            TIME[0] += 1
            # adjust graph with epoch
            if TIME[0] % epoch == 0:
                graph.rebuild_adj_matrix()
                graph.floyd_algorithm()
```
其中`visualize.drawMap()`函数能够绘制路况图 

调度的函数是`self.step(graph)`：

```python
def step(self, graph):
        print("time:%d" % TIME[0])
        for crossId in CROSSNAMESPACE:
            CROSSDICT[crossId].setDone(False)
        print("pre-movement...")
        for road in ROADNAMESPACE:
            ROADDICT[road].stepInit()
        print("while loop...")
        # =========================
        unfinishedCross = CROSSNAMESPACE
        while unfinishedCross.__len__() > 0:
            self.dead = True
            nextCross = []
            for crossId in unfinishedCross:
                cross = CROSSDICT[crossId]
                cross.step(graph)
                if not cross.__done__():
                    nextCross.append(crossId)
                if cross.__update__() or cross.__done__():
                    self.dead = False
            unfinishedCross = nextCross
            if self.dead:
                print("dead lock in", unfinishedCross)
                return
        # caculate car num in road
        SUM = 0
        for roadId in ROADNAMESPACE:
            road = ROADDICT[roadId]
            SUM = SUM + road.__forwardNum__() + road.__backwardNum__()
        print(SUM)
        print("car pulling away from carport")
        for i in range(CROSSNAMESPACE.__len__()):
            crossId = CROSSNAMESPACE[i]
            for roadId in CROSSDICT[crossId].__validRoad__():
                ROADDICT[roadId].setBucket(crossId)
            CROSSDICT[crossId].outOfCarport(graph)
```
首先通过`CROSSDICT[crossId].setDone(False)`语句对所有路口初始化。   
然后通过`ROADDICT[road].stepInit()`对道路上的车辆进行行驶。  
之后通过`cross.step(graph)`对过路口对车辆进行调度。  
最后通过`CROSSDICT[crossId].outOfCarport(graph)`对等待的车辆进行发车。

### 在判决器的基础上完成我们的车辆路径规划：

```python
# 在CROSS类的step函数中添加下列代码，完成路口调度时的路径实时更新
# ==========实时调整车辆路径代码==========
carId = nextCarId[index]
car = CARDICT[carId]
toCross = CROSSINDEX[car.__to__()]
curRoad = car.__curRoad__()
nRoad = car.__nextRoad__()
#curCross = 0
curCross = CROSSINDEX[car.__nextCrossId__()]
if nRoad != -1: # 车辆不到终点
    addRoute = graph.floyd_min_route[curCross][toCross]
    oldRoute = car.__route__()
    old_Route = oldRoute[0:car.__routeIndex__()]
    if old_Route != None or addRoute != None:
        newRoute = old_Route + addRoute
        if addRoute[0] != curRoad:   # 车辆不回开，
            car.reRoute(newRoute)

nextCar.append(car)
nextRoad.append(car.__nextRoad__())
```


```python
#新建GRAPH类，利用Floyd算法，进行最短路规划。
class GRAPH(object):
    def __init__(self):
    def establish_adjmatrix(self):
    def rebuild_adj_matrix(self):
    def floyd_algorithm(self):
    def init_plantime_route(self):
    def replan_route(self, carId):
    def __minRoute__(self, i, j):
```


```python
#在outOfCarport函数中，添加这两段代码，实现发车时的路径更新和车道拥堵时的延缓发车


# 出库时，从新的graph中读取新的route
graph.replan_route(carId)

# 加上当前道路车辆数占总容量数比值，若超过一定值，则延缓发车
curCarNum = 0
if self.id_ == road.__from__():
    curCarNum = road.__forwardNum__()
else:
    curCarNum = road.__backwardNum__()
if (curCarNum*1.0 / road.__carCapcity__()) > 1:
    CARDICT[carId].__rePlanTime__(TIME[0]+1)
    self.resetCarport(TIME[0]+1, carId)
    continue
```

```python
# 将原本写在main里的文件系统，单独写成一个类。包含文件的读入、写出、车辆的按车速时间排序、发车顺序的打乱等。
class FILESYSTEM(object):
    def __init__(self, argv1, argv2, argv3, argv4, epoch):
    #sort car max v and start time
    def sort_car(self,car=[]):
    def start_time_modify(self,carsort=[],epoch=15):
    def randomcar(self,carsort=[]):
    def loadfile(self, epoch):
    def answer_print(self, carId, graph):
    def __CarSort__(self):
```

```python
# 通过递归调用crossCorrtion，修正cross的道路链接顺序
def crossCorrction(crossId, roadId, face):
    cross = CROSSDICT[crossId]
    if cross.corrct == True:
        return
    cross.faceCorrction(roadId, face)
    cross.corrct = True
    for index in range(len(cross.roadIds)):
        roadId = cross.roadIds[index]
        nextCross = -1
        nextface = None
        if roadId != -1:
            road = ROADDICT[roadId]
            if road.__to__() == crossId:
                nextCross = road.__to__()
            else:
                nextCross = road.__from__()
            if index == 0:
                nextface = 2
            elif index == 1:
                nextface = 3
            elif index == 2:
                nextface =0
            elif index == 3:
                nextface = 1
            else:
                print("error happend in crossCorrction, nextface not exist")
            crossCorrction(nextCross, roadId, nextface)

# 在CROSS类中添加faceCorrction函数，face的实际朝向，修正现有朝向
class CROSS(object):
    def faceCorrction(self, roadId, face):
        if self.corrct == False:
            index = 0
            for i in range(len(self.temp)):
                if self.temp[i] == roadId:
                    index = i
                    break
            for i in range(len(self.roadIds)):
                ii = face % 4
                jj = (i+index) % 4
                face += 1
                self.roadIds[ii] = self.temp[jj]
            
# 修正cross
CROSSNAMESPACE.sort()
crossId = CROSSNAMESPACE[0]
i = 0 
for roadId  in CROSSDICT[crossId].temp:
    if roadId != -1:
        crossCorrction(crossId, roadId, i)
        i += 1
```

### 总结：
在初赛练习赛中，通过利用还算相近的判决器，去实时更新路况，更改车辆路径，较好的实现了车辆的路径分配问题。但在仅1w辆车、100个路口的情况下，依旧需要将120s的程序运行时间。以至于在实际比赛地图中6w辆车、140+路口的情况下，难以实现车辆的实时调度。以至于滞后的地图更新带来了车辆运行不通，甚至死锁的情况。  
死锁问题没有有效解决：一、判决器的不准确。二、地图回溯的资源占用。  
车辆路径没有更有效的规划，仅依据最短路，显然并不是很合适。  

**比赛就这样告一段落了，虽然没能获得好成绩，但也有所收获。之后就需要去实习面试，小论文的撰写等一系列工作。最近被焦狗优美的C++代码看尿了，才发觉原来这样才叫做写代码，之后要进一步完善代码的书写习惯**

最后的最后，放一张比赛用图，镇楼
![image](https://gitee.com/YanMingBo/SDK_python/raw/master/MapPicture.jpg)