标签 Traffic-Network-Model 下的文章

目前,我采用的是迪杰斯特拉算法计算所有点的最短路径(感觉弗洛伊德算法会更好些?)。迪杰斯特拉算法算的是单源(V_begin)到所有点的最短距离,也就是说需要遍历一次所有的点。

遍历V_begin

for (int V_begin = 0; V_begin < G->m_CrossRoad_v.size(); V_begin++) {
}
下面是迪杰斯特拉算法的流程

1. 声明dist数组

vector<double> Determined_dist(G->m_CrossRoad_v.size(), 0.0);

2. 初始化顶点集

void calcShortestPath(Graph *G) {
    int currentPointSite,nextPointSite;
    ofstream PointPathFile(DIR_RES"PointPath.txt"),RoadPathFile(DIR_RES"RoadPath.txt");
    //对点进行的一级遍历
    for (int V_begin = 0; V_begin < G->m_CrossRoad_v.size(); V_begin++) {
        // =================== 迪杰斯特拉算法开始 ===============================
        vector<bool> S(G->m_CrossRoad_v.size(), false); //判断是否选中
        vector<double> dist(G->m_CrossRoad_v.size(), DBL_MAX/2);// dist
        vector<double> compare_dist(G->m_CrossRoad_v.size(), DBL_MAX/2);// 辅助dist用来取最短距离点
        vector<int> path(G->m_CrossRoad_v.size(),-2); // path
        S[V_begin] = true;
        path[V_begin] = -1;
        for(auto crossroad : G->m_CrossRoad_v[V_begin].JunctionRoad){
            nextPointSite = G->m_Road_v[crossroad.outRoadID].m_CrossRoadToSite;
            dist[nextPointSite] = G->m_Road_v[crossroad.outRoadID].m_dLength;
            compare_dist[nextPointSite] = dist[nextPointSite];
        }
        auto min = min_element(compare_dist.begin(), compare_dist.end());
        int min_element_index = distance(compare_dist.begin(), min);
        compare_dist[min_element_index] = DBL_MAX/2;
        // 循环size-1次
        for(int i = 0; i < G->m_CrossRoad_v.size()-1; i++){
            for(auto crossroad : G->m_CrossRoad_v[min_element_index].JunctionRoad){
                currentPointSite = min_element_index;
                nextPointSite = G->m_Road_v[crossroad.outRoadID].m_CrossRoadToSite;
                if(S[nextPointSite]){
                    continue;
                }
                if(dist[nextPointSite] > dist[currentPointSite] + G->m_Road_v[crossroad.outRoadID].m_dLength) {
                    dist[nextPointSite] = dist[currentPointSite] + G->m_Road_v[crossroad.outRoadID].m_dLength;
                    compare_dist[nextPointSite] = dist[nextPointSite];
                    path[nextPointSite] = currentPointSite;
                }
            }
            min = min_element(compare_dist.begin(), compare_dist.end());
            min_element_index = distance(compare_dist.begin(), min);
            S[min_element_index] = true;
            compare_dist[min_element_index] = DBL_MAX/2;
        }
        for(int i = 0;i<path.size();i++){
            int j = i;
            bool flag = false;
            while( path[j] >= 0) {
                flag = true;
                PointPathFile << path[j] << " ";
                for(auto node:G->m_CrossRoad_v[j].JunctionRoad){
                    if(G->m_Road_v[node.outRoadID].m_CrossRoadToSite == path[j]){
                        RoadPathFile << node.outRoadID << " ";
                    }
                }
                j = path[j];
            }
            if(flag){RoadPathFile << endl;PointPathFile << endl ;}
        }
    }
}

runSimulation(Graph &G)

1. 遍历每条道路

2. 遍历该道路的车辆

a. 计算特定时间间隔后的位置

b. 若应行驶至其他道路

进入对应的路口缓冲区,根据路口类的红绿灯对象判断是否能通行。

若能通行,则填至目标道路

若不能,则继续停留在路口缓冲区

c. 若仍停留在原道路

改变该车在当前道路的位置。

  for (auto &road:G.m_Road_v) {
        auto src = road.m_queVehicle;
        decltype(road.m_queVehicle) obj;
        //路内车的遍历
        while (!src.empty()) {
            //弹出一辆车
            auto it = src.front();
            src.pop_front();
            // 当车的时间戳小于实际时间时,才模拟运行
            if (it.time < SYSTEM_TIME) {
                it.fSpec = (100 - road.get_Congestion() - 20) / 3.6;
                dist = it.dDistance + it.fSpec * 10;
                it.time++;

                it.showself();
                //如果车十秒后不在此路
                if (dist >= road.m_dLength) {
                    //路径擦除
                    auto route = it.queRoute;
                    int site = it.m_nSiteRoadID;
                    route.pop();
                    //如果抵达终点
                    if (route.empty()) {
                        cout << "it is be shutdown" << endl;
                        exit(0);
                        // 否侧没有抵达终点
                    } else {
                        //获取所在路和下一条路的ID
                        int next = route.front();
                        //判断红绿灯情况
                        cout << site << endl;
                        G.m_CrossRoad_v[site].m_CTrafficLight_Light.clock(SYSTEM_TIME);
                        //如果可以通行
                        if (G.m_CrossRoad_v[site].m_CTrafficLight_Light.getStatus(it.m_nSiteRoadID, next)) {
                            cout << GREEN << "绿灯通行:" << endl;
                            it.queRoute = route;
                            it.dDistance = 0;
                            it.m_nSiteRoadID = next;
                            auto *site_road = &G.m_Road_v[next].m_queVehicle;
                            site_road->push_back(it);
                            //如果不能通行
                        } else {
                            //将距离置为道路长度,表示正在等候红灯
                            it.dDistance = G.m_Road_v[it.m_nSiteRoadID].m_dLength;
                            cout << YELLOW << "等待红灯" << endl;
                            //车辆塞回去
                            obj.push_back(it);
                        }
                    }
                    //否则,当车十秒后还在此路时
                } else {
                    it.dDistance = dist;
                    obj.push_back(it);
                }
                //否则直接填入
            } else {
                obj.push_back(it);
            }
        }
        road.m_queVehicle = obj;
    }

generateVehicle(Map_Graph);

1. 随机车辆总数

  • [ ] 此处未随机,待完善
std::random_device rd;
std::mt19937 mt(rd());

2. 遍历车辆,为车辆设立起点和路线

a. 在道路向量中随机选一条路径

-[ ] 此处未随机,待完善

auto route = v_Route[3];

b. 以该路径的首序列为起点

Vehicle car(n_VehicleNum, route, 0, 0, route.front());
G.m_Road_v[route.front()].m_queVehicle.push_back(car);

1. 从文件(route.txt)中读取路径

形如以下格式

0 1 
0 1 2 
0 1 2 3 
0 1 2 3 4 
0 1 2 3 4 5 
0 1 2 3 4 5 6 
0 1 2 3 4 5 6 7 

其中,一行表示一条可完全畅通的道路编号序列。将所有道路存入v_Route

vector<queue<int>> v_Route;

/**
 * load route from route file
 * @param Map_graph
 */
void loadRoute(Graph &Map_graph) {
    string str_Path;
    ifstream fin_Route(DIR_RES"route.txt");
    while (getline(fin_Route, str_Path)) {
        stringstream ss_Temp(str_Path);
        queue<int> q_Path_Temp;
        int n_Temp;
        while (ss_Temp >> n_Temp) {
            q_Path_Temp.push(n_Temp);
        }
        v_Route.push_back(q_Path_Temp);
    }
}

道路类型的设置

it->m_CTrafficLight_Light.setType(it->JunctionRoad.size());

根据路口道路条数, 设置路灯类型(是T字路口还是+字路口)

/**
 * 交通灯类
 */
class TrafficLight {
public:
    TrafficLight() {
        for (int i = 0; i < 8; i++) {
            roadID[i] = -1;
        }

    };
    void changeStatus();

    void clock(int time);

    void setAllRed();

    void setAllGreen();

    bool getStatus(int from, int to);
    /**
     * 设置灯的类型, 是T字路口还是+字路口
     * @param type 
     */
    void setType(int type) { this->type = type; };
    //路口标号
    // nLeftIn,nLeftOut,nDownIn,nDownOut,nRightIn,nRightOut,nUpIn,nUpOut;
    int roadID[8];
    //路口是否能走通
    bool status[4][4] = {false};
    int type;
    //表示可通过的方向(目标方向)
    //AllRED = 0,LeftGreen = 1,DownGreen = 2,RightGreen = 3,UpGreen = 4,UpDownGreen = 5,LeftRightGreen = 6,cross1 = 7,cross2 = 8
    int emStatus = 0;
    long long int time = 0;
};

对接各路口

it->m_CTrafficLight_Light.roadID[4] = it->JunctionRoad[0].inID;
it->m_CTrafficLight_Light.roadID[5] = it->JunctionRoad[0].outID;

it->m_CTrafficLight_Light.roadID[0] = it->JunctionRoad[1].inID;
it->m_CTrafficLight_Light.roadID[1] = it->JunctionRoad[1].outID;
switch (it->JunctionRoad.size()) {
    case 4:
       it->m_CTrafficLight_Light.roadID[6] = it->JunctionRoad[3].inID;
       it->m_CTrafficLight_Light.roadID[7] = it->JunctionRoad[3].outID;
       //你是不是想说没有break?这里不需要break;
    case 3:
       it->m_CTrafficLight_Light.roadID[2] = it->JunctionRoad[2].inID;
       it->m_CTrafficLight_Light.roadID[3] = it->JunctionRoad[2].outID;
    }

交通灯初始化完毕.

2019-02-12 12-19-50屏幕截图.png

思路篇

思路篇主要记录程序流程思路

毕业设计思路篇(一)之道路数据的抽象

毕业设计思路篇(二)之交通灯的初始化

毕业设计思路篇(三)之预加载车辆路线

毕业设计思路篇(四)之生成车辆

毕业设计思路篇(五)之交通流量模拟

番外篇

番外篇主要记录非主要流程(即并非每次运行都会执行的模块,比如预处理等)。每个模块可单独修改或维护,而不影响主流程。

毕业设计番外篇(一)之车辆路径的构建

2019-01-13 10-50-54屏幕截图.png

1. 导入道路地图

道路地图来自网络数据,已预处理为xml格式。

<?xml version='1.0' encoding='UTF-8'?>
<Roads>
  <road m_ID="71283896--1" len="620.98">
    <from lon="113.9205606" lat="22.9317667" id="848388981"/>
    <to lon="113.9260573" lat="22.9341232" id="2522072722"/>
  </road>
  <road m_ID="553852656--2" len="322.34">
    <from lon="113.9529339" lat="22.9448978" id="5345735265"/>
    <to lon="113.9516926" lat="22.9475618" id="5345735267"/>
  </road>
</Roads>
解析:一个road节点代表一条道路,len代表道路抽象长度,from,to子节点分别表示道路两端端点。

2. 解析道路数据

a. 构建交通图

赋值道路端点.
/**
*  路口类,记录着该路口的点坐标,以及其相连的方向道路节点组
 *               |           |
 *               |     |     |
 *               |  1     2  |
 *               |     |     |
 *        --------           --------
 *           3                  5
 *        - - - -            - - - -
 *           4                  6
 *        --------           --------
 *               |     |     |
 *               |  7     8  |
 *               |     |     |
 *               |           |
 *    如上图(1,2), (3,4), (5,6), (7,8)在同一个方向,我将其称为四组方向道路节点Node.
 *    其中,Node.inRoadID=1, Node.outRoadID=2;
 *         Node.inRoadID=4, Node.outRoadID=3;
 *         ...
 *         根据车辆靠右行原则以此类推.
*/
class CrossRoad {
public:
    CrossRoad(float fLon,float fLat) : m_fLat(fLat),m_fLon(fLon){};
    /**
     * 重载运算符 (==) 判断两个路口是否为同一个
     */
    bool operator==(CrossRoad &crossRoad);
    /**
     * 添加道路节点ID
     * @param in 入度
     * @param out 出度
     * @param atan2 该点与方向道路的atan2值
     */
    void addNode(int in,int out,double atan2);
public:
    //唯一标示符
    int m_nID;
    //经纬度的定义
    float m_fLon, m_fLat;
    vector<Node> JunctionRoad;
    //该路口的交通灯
    TrafficLight m_CTrafficLight_Light;
};

CrossRoad A,B

添加道路到交通图
void addRoad(Graph &Map_Graph, CrossRoad A, CrossRoad B, double length) {
    // 初始化A,B路口的索引位置为-1
    int CrossRoadSiteB = -1, CrossRoadSiteA = -1;
    auto CrossRoadNum = Map_Graph.m_CrossRoad_v.size(), RoadNum = Map_Graph.m_Road_v.size();
    //循环判断是否有重合点
    for (int i = 0; i < CrossRoadNum; i++) {
        if (Map_Graph.m_CrossRoad_v[i] == A) {
            CrossRoadSiteA = i;
        }
        if (Map_Graph.m_CrossRoad_v[i] == B) {
            CrossRoadSiteB = i;
        }
    }
    //如果不存在与A点重合的路口,添加路口,保存路口索引
    if (CrossRoadSiteA == -1) {
        Map_Graph.m_CrossRoad_v.push_back(A);
        CrossRoadSiteA = CrossRoadNum++;
        Map_Graph.m_CrossRoad_v[CrossRoadSiteA].m_nID = CrossRoadSiteA;
    }
    if (CrossRoadSiteB == -1) {
        Map_Graph.m_CrossRoad_v.push_back(B);
        CrossRoadSiteB = CrossRoadNum++;
        Map_Graph.m_CrossRoad_v[CrossRoadSiteB].m_nID = CrossRoadSiteB;
    }
    int RoadSiteA = RoadNum, RoadSiteB = RoadNum + 1;
    // 确定A,B路的site,加入模型图
    Road roadA(RoadSiteA, CrossRoadSiteA, CrossRoadSiteB, length);
    Map_Graph.m_Road_v.push_back(roadA);
    Road roadB(RoadSiteB, CrossRoadSiteB, CrossRoadSiteA, length);
    Map_Graph.m_Road_v.push_back(roadB);
    // 对接A,B路口节点数据
    Map_Graph.m_CrossRoad_v[CrossRoadSiteA].addNode(RoadSiteA, RoadSiteB,
                                                    atan2((B.m_fLat - A.m_fLat), (B.m_fLon - A.m_fLon)));
    Map_Graph.m_CrossRoad_v[CrossRoadSiteB].addNode(RoadSiteB, RoadSiteA,atan2((A.m_fLat - B.m_fLat), (A.m_fLon - B.m_fLon)));
}
解析的结果如下
road.txt
RoadTable.txt

所有的路口标号用int road[8]表示,
bool status[8][8]表示道路可否通行。

T字路口


T路口.png
对于T字路口,将道路分为(左,右,下)三个流量出入口,存在的状态有:

0. 全红(特殊状态应对突发事故)

     for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            status[i][j] = false;
        }
    }
×012345
0××××××
1××××××
2××××××
3××××××
4××××××
5××××××
正常状态下考虑红灯可右转,同向变道不受交通灯控制,即永远可通行
status[2][1] = status[4][3] = true;
status[0][1] = status[2][3] = status[4][5] = true;
×012345
0 @
1
2 @ @
3
4 @ @
5
同时需要限制逆行,即永远不可通行
// 出口不能自转和变道
status[0][0] = status[0][2]  = status[0][4]  = false;
status[4][4] = status[4][0]  = status[4][2]  = false;
status[2][2] = status[2][0]  = status[2][4]  = false;
// 出口不能进去
status[1][0] =status[1][4]  = status[1][2] = status[1][3]   = status[1][4] = status[1][5] = false;
status[3][0] =status[3][5]  = status[3][2] = status[3][3]   = status[3][4] = status[3][5] = false;
status[5][0] =status[5][6]  = status[5][2] = status[5][3]   = status[5][4] = status[5][5] = false;
×012345
0×@× ×
1××××××
2×@×@×
3××××××
4× ×@×@
5××××××
对以上情况封装,即init()。后续应禁止对上值做任何改变。
即还有6*6-5-9-18=4个值
status[0][5],status[4][7],
status[2][5],status[0][3],

道路方向

调控状态代码如下

case 3:
            if (emStatus % 4 == 0) {
                status[0][5]=status[4][1]=1;
                status[2][5]=status[0][3]=0;
            } else if (emStatus % 4 == 1) {
                status[0][5]=status[0][3]=1;
                status[4][1]=status[2][5]=0;
            } else {
                status[0][5]=status[2][5]=1;
                status[4][1]=status[0][3]=0;
            }
            break;

解析如下

1. 对边可通行(限制0左转,限制2左转)

status[0][5]=status[4][1]=1;
status[2][5]=status[0][3]=0;

2. 疏通右侧

status[0][5]=status[0][3]=true;
status[4][9]=status[2][5]=false;

3. 导向左侧

status[0][5]=status[2][5]=1;
status[4][1]=status[0][3]=0;

+字路口


+路口.png
对于+字路口,将道路分为(左,右,上,下)四个流量出入口,存在的状态有:

0. 全红(同上)

×01234567
0××××××××
1××××××××
2××××××××
3××××××××
4××××××××
5××××××××
6××××××××
7××××××××
同时需要限制逆行,即永远不可通行
// 出口不能自转和变道
status[0][0] = status[0][2]  = status[0][4]  = status[0][6] = false;
status[2][2] = status[2][0]  = status[2][4]  = status[2][6] = false;
status[4][4] = status[4][0]  = status[4][2]  = status[4][6] = false;
status[6][6] = status[6][2]  = status[6][4]  = status[6][0] = false;
// 出口不能进去
for(int i = 0; i < 8 ; i++){
    status[1][i] = status[3][i] = status[5][i] = status[7][i] = false;
}