CN112991745B - A method for dynamic cooperative allocation of traffic flow in a distributed framework - Google Patents

Abstract

The invention discloses a traffic flow dynamic cooperative allocation method under a distributed framework, which is characterized in that a plurality of virtual local sub-planning centers are established by taking an intersection as a secondary allocation unit, and each sub-planning center manages a plurality of road sections connected with the intersection. Each sub-planning center replans the traffic route for the vehicle in the local area according to a specific rule and selects the next traffic road section. The flow distribution process of the sub-planning centers can be synchronously carried out, and the flow distribution result is finally fed back to the previous level, so that the traffic flow distribution efficiency is greatly improved; meanwhile, a dynamic cooperative distribution method for the traffic flow facing the urban road network is provided by distributing the traffic flow to the road sections by means of a bidding mechanism in the market behavior. The method comprises the steps of firstly analyzing and screening congested road intersections on the basis of road impedance analysis, taking the congested road as a bidder in each congested intersection intelligent agent, taking the unblocked road as a bidder, and allocating vehicles to the bidding road with the highest bid price by adopting a bidding mechanism.

Description

A method for dynamic cooperative allocation of traffic flow in a distributed framework

technical field

The invention belongs to the field of traffic engineering, and in particular relates to a method for dynamic collaborative allocation of traffic flow under a distributed framework.

Background technique

The dynamic distribution theory of traffic flow is the core of the study of traffic network flow. Efficient routing algorithm is a key problem that needs to be solved in the field of geographic information, traffic and even the whole network science. Dynamic traffic allocation is to allocate the time-varying traffic travel demand to the road network according to the established rules. Since the concept of dynamic traffic assignment was first proposed, scholars at home and abroad in the field of transportation have developed four types of research methods for dynamic traffic assignment: mathematical programming method, optimal control method, variational inequality method and computer simulation method. The mathematical programming method allocates traffic flow to road sections by constructing a nonlinear multi-objective mathematical programming model that conforms to the dynamic Wardrop system optimality or user optimality principle; although this method can guarantee the optimal solution, complex mathematical constraints and inefficient solutions Algorithms and FIFO rules restrict this method to be used only as a verification method for small-scale simple networks. The optimal control method uses the optimal control theory to transform the dynamic flow distribution into a continuous optimal control problem, and determines the traffic flow distribution state by controlling the optimal value condition; this type of model is usually transformed into a time-discrete integer programming problem. However, there is still a lack of mature and efficient solution algorithms. The variational inequality method divides the dynamic traffic assignment into two steps: network loading and network assignment, and decomposes the original problem into sub-linear programming problems to solve. Computer simulation methods can simulate the behavior of traffic flow signals in each iterative allocation process, but usually cannot analyze the convergence and accuracy of the results from the perspective of their own solutions. These traffic flow dynamic allocation methods enrich the theoretical basis of traffic allocation, but the complex models, inefficient solution algorithms, and ideal assumptions make them difficult to apply to large-scale urban road network environments with complex structures.

At the same time, the existing technology also has the following shortcomings: (1) The problem of low algorithm efficiency caused by the centralized global traffic flow distribution framework. In the centralized global flow distribution framework, in order to determine the optimal path of the vehicle from the current position to the target point, it is necessary to measure the impedance of all road segments according to the real-time position of the traffic flow. The time complexity of the algorithm is O(n×m×t), where n is the number of vehicles; m is the number of road sections; t is the number of re-planning. The indiscriminate calculation of all traffic flows and all road segments not only leads to a sharp drop in the efficiency of traffic flow allocation, but also the traffic flow allocation scheme may overlap with the previous time step to a large extent to generate a completely consistent scheme. At the same time, the global cooperative architecture also causes the problems of excessive computational load and low robustness.

(2) The overall traffic efficiency of the road network is low due to unreasonable traffic flow distribution rules. In the problem of traffic flow allocation, the user's path selection can be regarded as a compound assignment process of multiple vehicles and multiple feasible road segments. Any road allows multiple vehicles to pass, and a single vehicle can also use multiple road segments as candidate solutions. Therefore, dynamic traffic distribution is a typical combinatorial optimization problem. Many complex road sections, vehicles with multiple steps, and the continuous change of road load rate lead to a huge space for joint strategies. Given m road segment nodes, n vehicle tasks and t times of dynamic distribution, the number of candidate solutions to the dynamic distribution problem will be at most t×(m/2)×n-1)!. The danger of this candidate solution combinatorial explosion is the main reason for the low traffic capacity of the road network of the allocation scheme.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a method for dynamic cooperative distribution of traffic flow under a distributed framework, which can improve the efficiency of traffic distribution.

The method for dynamic cooperative allocation of traffic flow under this distributed framework provided by the present invention includes the following steps:

S1. Planning an initial routing scheme for all vehicles;

S2. Count the current road network vehicles. When the current road network vehicles are greater than the preset value, the following steps are performed; otherwise, the traffic flow of the road section is counted and the results of the cooperative allocation of all vehicles are output, and the dynamic cooperative allocation process of the current traffic flow is ended;

S3. Count the traffic density of all road sections at the current moment;

S4. Determine the congestion situation of the road section according to the congestion traffic density threshold; if the road section is not congested, go to step S5; otherwise, go to step S6;

S5. Extract the route scheme FL of the previous iteration, and go to step S8;

S6. Extract the vehicle set T of the re-planned route on the congested road section;

S7. The route scheme FN of the vehicles in the vehicle set T that re-plans the route according to the bidding mechanism;

S8. Input the new traffic demand, and update the vehicle position according to the route scheme FN of the vehicles in the vehicle set T of the re-planned route in step S7 or the route scheme FL of the previous iteration in step S5;

S9. Complete the above steps, count the traffic of the road section and output the results of all vehicle collaborative allocation;

为Among them, in the bidding mechanism, each bidding road segment node obtains k optimal shortest paths as candidate traffic loading strategies from the current road segment to the target point, and k paths have a probability of being selected according to the traffic impedance of the paths ; OD's probability of being selected for the jth path of u

for

为OD对u的第j条路径的投标路段的投标价格；J^u为OD对u之间k条候选路径的集合；Among them, OD is the starting and ending point, and θ is a discrete parameter that measures the degree of perception error of the traveling vehicle;

is the bid price of the bidding section of the jth path of OD to ^u ; Ju is the set of k candidate paths between OD and u;

Based on the above path selection probability, bidder Bidder assigns an optimal path for each vehicle task, and submits a task plan BT _e and its corresponding path impedance quotation V _e to the tenderer Tenderer.

Step S3 The traffic density refers to the traffic volume existing on the road of a unit length at a certain time, and the traffic density of the road segment r at a certain time is calculated as:

为路段r上第i个簇的车辆数目；In the formula: L _r is the length of the road segment r,

is the number of vehicles in the i-th cluster on road segment r;

When the traffic density of the road section at the current moment is not greater than 0.9 times the traffic density when the road section is congested at the current moment, the vehicles on the road section do not change the route plan, and continue to drive according to the route plan of the previous time step within this time step; otherwise, on the road section The vehicle re-plans the routing scheme according to the bidding mechanism.

The bidding mechanism includes the following steps:

(1) Calculate the impedance of the road section;

(2) Obtain the traffic loading strategy and calculate the probability that the path is selected.

Step (1), the calculation of road section impedance specifically includes the following steps:

1) Determine the impedance of each road segment in the road network;

2) Calculate the travel time of the road section in the state of traffic congestion;

3) Build a road segment impedance matrix based on the passage time of the road segment, which is used as the quotation for calculating the traffic distribution scheme.

Step 1), the road section impedance uses the vehicle running time as the travel cost, and the travel time of the road section without congestion is calculated by the BPR function:

Time _r = Time _free [1+ α(q _i /Q _i ) ^β ]

Among them, Time _r is the normal travel time of road segment ri under non-congested conditions; Time _free is the free flow travel time of road segment ri ; q _i is the traffic flow of road segment _ri ; _{Qi is} the traffic _capacity of road segment _ri ; α and β are the retardation coefficients, the reference value of α is 0.223, and the reference value of β is 2.037.

Step 2), the passage time of the road section in the traffic congestion state is as follows:

Time _jam =

为路段r _i 的临界速度；ρ _jam 为当前时刻路段拥堵时的交通密度；ρ _i为路段r _i 的交通密度。Among them, Time _jam is the traffic time of the road segment ri _when it is _congested ; Li is the length of the road segment _ri ;

is the critical speed of the road segment ri ; ρ _jam is the traffic density when the road segment is congested at the current moment ; ρ _i is the traffic density of the road segment _{ri .}

Step 3), the bidding price of the bidding section includes the travel time of the section, the delay time at the intersection and the time cost of the estimated noise:

为每个不拥堵路段的正常通行时间；

为每个拥堵路段的通行时间；Time _δ 为时间噪声；

为交叉口的延误时间，包括车辆排队延误和信号灯延误时间；Among them, Nr is the number of uncongested road sections passed by the route; Njam is the number of congested road sections passed by the route; Nis is the number of intersections passed by the route;

is the normal traffic time of each non-congested road section;

is the travel time of each congested road section; Time _δ is the time noise;

It is the delay time at the intersection, including the delay time of vehicle queuing and the delay time of signal lights;

为线性系数；ε为信号灯延误时间控制参数。Among them, N _Ve is the number of queued vehicles at the intersection;

is a linear coefficient; ε is the control parameter of signal light delay time.

Step S8, specifically calculating the traffic volume flowing into the road segment ri from the road segment r _{i -1} according to the vehicle route scheme within the time step, and updating the vehicle position information;

The traffic propagation relationship between road segments is:

y _i (x)=q _i (x)tr=min{ n _i-1 (x), Q _i (x), w[N _i (x)- n _i (x)]/v}

Among them, q _i (x) is the traffic inflow rate of road segment ri at time x; tr is the time step; n _{i -1} (x) is the traffic volume of road segment _ri at time x-1; Qi ₍ x) is the maximum inflow of the road segment ri at time x, that is, the traffic capacity of the road segment; Ni (x) is the maximum bearing capacity of the road segment _ri at time x, that is, the traffic volume at the critical point of congestion; _{ni (} x) is the road segment _{ri i} The traffic volume at time x; v is the free traffic flow speed; w is the back propagation speed when the traffic is congested; thus, the maximum number of vehicles passing through the road section is calculated as y _i (x); the traffic is realized by the FIFO principle and the above formula Propagation of streams across adjacent road segments in urban road networks and dynamically updating vehicle positions during vehicle allocation.

In the method for dynamic cooperative allocation of traffic flow under the distributed framework provided by the present invention, a plurality of virtual local sub-planning centers are set up with intersections as secondary allocation units, and each sub-planning center manages a plurality of road sections connected to the intersection. . Each sub-planning center re-plans the passing path for vehicles in this local area according to specific rules and selects the next passing road segment. The flow distribution process of multiple sub-planning centers can be carried out synchronously, and finally the flow distribution results are fed back to the upper level, which greatly improves the efficiency of traffic distribution. Traffic flow dynamic co-distribution method for network. The method first analyzes and filters the intersections of the congested sections on the basis of the impedance analysis of the road sections. In each congested intersection agent, the congested sections are regarded as the tenderers, and the unblocked sections are regarded as the bidders. The bidding mechanism is used to allocate vehicles to The bid segment with the highest bid.

Description of drawings

FIG. 1 is a schematic flow chart of the method of the present invention.

FIG. 2 is a schematic diagram of the relationship between urban traffic flow and density in the method of the present invention.

FIG. 3 is a schematic diagram of collaborative allocation based on a contract network according to an embodiment of the present invention.

FIG. 4 is a schematic diagram of a network structure and initial parameters according to an embodiment of the present invention.

FIG. 5a is a schematic diagram of the flow distribution result of the SSP method according to the embodiment of the present invention, FIG. 5b is a schematic diagram of the flow distribution result of the DSP method according to the embodiment of the present invention, FIG. 5c is a schematic diagram of the flow distribution result of the STSP method according to the embodiment of the present invention, and FIG. A schematic diagram of the flow distribution result of the method, FIG. 5e is a schematic diagram of the flow distribution result of the SL method according to an embodiment of the present invention, FIG. 5f is a schematic diagram of the flow distribution result of the DL method according to an embodiment of the present invention, and FIG. 5g is a schematic diagram of the flow distribution result of the DCA method according to an embodiment of the present invention. A schematic diagram for explaining a road segment ID according to an embodiment of the present invention.

FIG. 6 is a schematic diagram of a traffic flow transmission process of different flow distribution methods according to an embodiment of the present invention.

FIG. 7 is a schematic diagram illustrating the influence of the initial traffic flow on the traffic efficiency of the road network according to an embodiment of the present invention.

FIG. 8a is a schematic diagram of road section saturation in the DCA method according to an embodiment of the present invention, FIG. 8b is a schematic diagram of road section saturation in the DTSP method according to an embodiment of the present invention, FIG. 8c is a schematic diagram of road section saturation in the DSP method according to an embodiment of the present invention, and FIG. 8d is the present invention. Figure 8e is a schematic diagram of road section saturation in the DL method according to an embodiment of the present invention, Figure 8e is a schematic diagram of road section saturation in the STSP method according to an embodiment of the present invention, Figure 8f is a schematic diagram of road section saturation in the SL method according to an embodiment of the present invention, and Figure 8g is a schematic diagram of the SSP method in an embodiment of the present invention. Schematic diagram of road segment saturation.

FIG. 9 is a schematic diagram showing the comparison of path impedances before and after dynamic adjustment according to an embodiment of the present invention.

Detailed ways

Figure 1 is a schematic flow chart of the method of the present invention: the method for dynamic collaborative allocation of traffic flow under this distributed framework provided by the present invention comprises the following steps:

S1. The initial route scheme F _ori is planned for all vehicles by the A* algorithm; the A* (A-Star) algorithm is the most effective direct search method for solving the shortest path in the static road network.

S2. Count the current road network vehicles N _v , when N _v >0, process through the following steps; otherwise, count road traffic and output all vehicle allocation results, and end the current traffic flow dynamic collaborative allocation process;

S3. Count the traffic density ρ _a of all road sections at the current moment;

S4. According to the traffic density threshold ρ _jam of congestion, determine the congestion situation of the road section; ρ _jam is the traffic density when the road section is congested; step S5 is performed when the road segment is not congested, that is, ρ _a <0.9*ρ _jam , otherwise, step S6 is performed;

S5. Extract the route scheme FL of the previous iteration, and go to step S8;

S6. Extract the vehicle set T of the re-planned route on the congested road section;

S7. The route scheme FN of the vehicles in the vehicle set T that re-plans the route according to the bidding mechanism;

S8. Input the new traffic demand, and update the vehicle position according to the route scheme FN of the vehicle in the vehicle set T of the re-planned route in step S7 or the route scheme FL of the previous iteration in step S5;

S9. After the above steps are completed, the traffic flow of the road section is counted and the results of the coordinated allocation of all vehicles are output.

The traffic density in step S3 refers to the amount of traffic existing on a road with a unit length at a certain time, and is usually represented by the ratio of the number of vehicles on the road segment to the length of the road segment. The traffic density of road segment r at a certain moment can be calculated as:

为路段r上第i个簇的车辆数目；where L _r is the length of the road segment r,

is the number of vehicles in the i-th cluster on road segment r;

FIG. 2 is a schematic diagram of the relationship between urban traffic flow and density according to the method of the present invention, and a triangular function or trapezoidal function relationship is mostly used between urban traffic flow and traffic density. Among them, q is the traffic flow; q _max is the saturated flow of the road section; v is the free traffic flow speed; w is the back propagation speed when the traffic is congested. When the instantaneous density of the current road section is not greater than 0.9 times the traffic density of the current road section, ρ _a ≤ 0.9*ρ _jam , the vehicles on the road section do not change the route plan, and continue to drive according to the route plan of the previous time step within this time step; otherwise , when the road section is congested, the vehicles on the road section re-plan the route plan according to the bidding mechanism.

The collaborative planning method based on the bidding mechanism proposed by the present invention re-formulates a route plan for the traffic flow of a congested road section. Once traffic congestion occurs on road segment 2, the affected vehicles on road segment 1 are rerouted within this intersection. By constructing the intersection agent where road segment 2 is located, road segment 1 is used as the tenderer to issue vehicle tasks, and road segments 3, 4, and 5 with task execution conditions are used as bidders to compete for vehicle tasks.

。The collaborative planning method first determines the bidder _{ri and the bidder RS i as} shown in Figure 3, and the bidder issues the bid of task T (including task ID, task information and weight level); Calculate the k optimal paths and their vehicle traffic impedance on the basis of the traffic demand of T; combine the Logit loading model to determine the flow and vehicle tasks of each path; each bidder RS _i determines and feeds back the bid to the bidder _ri The task set GT and the corresponding offer set VT; thus, the bidder ri selects the final vehicle allocation scheme

.

The specific implementation is as follows:

且

。

为投标者反馈的投标价格集合，V_e为第e个投标者对投标任务集BTe反馈的投标价格集合。

表示中标方案

中的投标任务集合，

。Let T = {t _j | j=1,2,…,n} be the vehicle tasks to be assigned, where n is the number of tasks; P ={p _k | k=1,2,…,m} Set of sub-planning centers for intersections, where m is the number of intersections. R _k = {r _i | i= 1,2,…,mk} is the set of link nodes managed by the intersection sub-planning center p _k , and m _k is the number of link nodes. RS _i is a set of potential road segment nodes that can perform vehicle tasks on road segment _ri . GT= {BT _e | e=1,2,…,bm} is the set of bidding tasks fed back by all bidders, BT _e is the set of bidding tasks fed back by the e-th bidder, bm is the number of bidders,

and

.

is the set of bid prices fed back by bidders, and V _e is the set of bid prices fed back by the e-th bidder to the bidding task set BTe.

Indicates the winning proposal

The set of bid tasks in ,

.

。如果存在个别任务不能被此方案执行，则此部分车辆仍然采用上一时间步长的最新方案

。The cooperative flow allocation algorithm firstly determines the bidder _{ri and the bidder RS i ,} and the bidder issues the bid of the task T. Then the sub-planning center pk calculates the impedance of all road segments in the road network and constructs the road segment impedance matrix T _net , so that each bidding road segment calculates _k optimal paths according to the road segment impedance matrix T _net on the basis of capturing the traffic OD demand of the task T and its impedance. In turn, combined with the Logit loading model, the flow through each path and the vehicle mission are determined. Through the above steps, each bidder can determine and feed back the bidding task set GT and the corresponding quotation set VT to _ri . ri _selects the final vehicle allocation scheme through the winning bid determination algorithm proposed in this paper

. If there are individual tasks that cannot be executed by this scheme, this part of the vehicle still adopts the latest scheme of the last time step

.

(1) Calculate the road impedance:

In order to determine the optimal path of the vehicle task from the current position to the target point, it is first necessary to determine the impedance of each road segment in the road network. The generalized road section impedance can be the concentrated expression of various factors such as the time required to pass the road section, the driving comfort, the travel distance, the driving cost and the number of turns, which can be regarded as the comprehensive cost of vehicle operation. According to different actual needs and algorithm purposes, the road segment impedance can have different meanings.

1) In this embodiment, the road section impedance adopts the vehicle running time as the travel cost, and the free passage means that the travel time of the road section and the travel time of the congested section have a large difference, and the travel time of the road section without congestion is calculated by the BPR function:

Time _r = Time _free [1+α(q _i /Q _i ) ^β ]

Among them, Time _r is the normal travel time of road segment ri under non-congested conditions; Time _free is the free flow travel time of road segment ri ; q _i is the traffic flow of road segment _ri ; _{Qi is} the traffic _capacity of road segment _ri ; α and β are the retardation coefficients, the reference value of α is 0.223, and the reference value of β is 2.037.

2) When the road section is congested, the travel time of the road section shows a completely different rule from the free passage. This paper gives the travel time of the road section under the traffic congestion state according to the Greenberg logarithmic model:

为路段r _i 的临界速度；ρ _jam 为当前时刻路段拥堵时的交通密度；ρ _i 为路段r _i 的交通密度。Among them, Time _jam is the traffic time of the road segment ri _when it is _congested ; Li is the length of the road segment _ri ;

is the critical speed of the road segment ri ; ρ _jam is the traffic density when the road segment is congested at the current moment ; ρ _i is the traffic density of the road segment _{ri .}

3) Construct a road segment impedance matrix based on the passage time of the road section under the above traffic congestion state, as the quotation for calculating the traffic allocation plan; the bidding price of the bid road segment includes the road segment travel time in the traffic congestion state, intersection delay time and time estimation noise. Part of the time spent:

为每个不拥堵路段的正常通行时间；

为每个拥堵路段的通行时间；Timeδ为时间噪声；

为交叉口的延误时间，包括车辆排队延误和信号灯延误时间；为简化计算，在本实施例中：Among them, Nr is the number of uncongested road sections passed by the route; Njam is the number of congested road sections passed by the route; Nis is the number of intersections passed by the route;

is the normal traffic time of each non-congested road section;

is the travel time of each congested road section; Timeδ is the time noise;

is the delay time at the intersection, including vehicle queuing delay and signal light delay time; to simplify the calculation, in this embodiment:

为线性系数；ε为信号灯延误时间控制参数，本实施例中取30s。Among them, N _Ve is the number of queued vehicles at the intersection;

is a linear coefficient; ε is a control parameter of signal light delay time, which is taken as 30s in this embodiment.

(2) Obtain the traffic loading strategy and calculate the probability that the path is selected;

为：Specifically, each bidding road segment node obtains k optimal shortest paths as the candidate traffic loading strategy from the current road segment to the target point. According to the traffic impedance of the path, k paths have a probability of being selected, and the vehicle task tends to select the impedance. smaller path; in this embodiment, assuming that the random perception error of the traveling vehicle obeys the Gumbel distribution, then the probability of being selected by OD (start and end point) on the jth path of u

for:

为OD对u的第j条路径的投标路段的投标价格；J^u为OD对u之间k条候选路径的集合；Among them, OD is the origin and destination point, and θ is a discrete parameter that measures the degree of perception error of the traveling vehicle;

is the bid price of the bidding section of the jth path of OD to ^u ; Ju is the set of k candidate paths between OD and u;

Based on the above path selection probability, the bidder (road segment node) Bidder assigns the optimal path for each vehicle task, and submits the task plan BT _e and its corresponding path impedance quotation V _e to the tenderer Tenderer.

In a specific implementation manner, it is a local search algorithm based on the floating mark selection mechanism:

The winner determination problem of road segment nodes in the intersection sub-planning center is a combinatorial optimization problem. During the negotiation and allocation process of the road segment contract network, all bidders Bidder will return the bid set to the tenderer Tenderer. The bidding schemes fed back by different bidding sections may contain the same vehicle tasks, thus causing task conflicts. According to the feedback scheme, Tenderer needs to select a globally optimal vehicle routing scheme to avoid task conflict. Therefore, this paper firstly constructs an integer programming model to describe the optimal objectives and constraints, and then designs a local search algorithm based on the floating selection mechanism to efficiently solve this model.

且

。如果BT_a和BT_b两个任务集中至少存在一个相同的任务，即

, 同时BT_a和BT_b就是冲突任务集。否则，两任务集称为相容任务集。根据两两冲突关系可以构建冲突出价矩阵Mcon（对称阵）。Definition: Conflicting bids: Let BT _a and BT _b be the bidding task sets fed back by the ath and bth bidders, respectively,

and

. If there is at least one identical task in the two task sets BT _a and BT _b , namely

, and BT _a and BT _b are conflicting task sets. Otherwise, the two task sets are called compatible task sets. The conflict bid matrix Mcon (symmetric matrix) can be constructed according to the conflict relationship between pairs.

The Winner Determination Problem (WDP) is to select a subset from the candidate set as a feasible solution so that the sum of bids in the feasible solutions is the largest (smaller). In this paper, a subset of the non-conflicting bidding task set GT can be selected as a feasible solution C, and the goal of Eq. (6) is to minimize the sum of the bids of feasible solutions C. The solution can be expressed as a Boolean set X = {xe| e=1,2,…,bm}, where xe=1 means that the set of bidding tasks BT _e is selected, and bm is the number of bidding road segments. Thus, the objective function can be expressed as:

;(b)

。式中：Ve表示第e个投标路段的报价。操作符

定义为：如果 x_i=1, x_j=1, 且BT_i与BT_j冲突，则x_i

x_j =1; 否则, x_i

x_j =0。约束 (b) 表示每个任务只可以被选择一次，即被选择的任务之间不能发生冲突。The constraints are: (a)

;(b)

. In the formula: Ve represents the quotation of the e-th tendered road segment. operator

Defined as: if x _i =1, x _j =1, and BT _i conflicts with BT _j , then x _i

x _j =1; otherwise, x _i

_xj =0. Constraint (b) means that each task can only be selected once, that is, the selected tasks cannot conflict with each other.

Aiming at the problem of solving the optimal solution of the road node contract network, this paper proposes a local search algorithm (FLS) based on the floating mark selection mechanism. The algorithm uses probability parameters and floating label selection mechanism to control random walks to enhance the diversity of solutions and greatly improve the accuracy of solutions. And the priority search strategy is used to prevent the repeated retrieval of the candidate solution set space and improve the convergence speed of the optimal solution.

The FLS algorithm is a process of multiple iterations and step-by-step optimization. The number of iterations y can be determined manually or until the optimal solution is found. During the search process, if the algorithm searches all candidate bidding solution sets in each iteration, it will inevitably slow down the convergence speed. In fact, the priority search weights of the candidate solution sets are different. Therefore, in order to speed up the search, the algorithm designs a preferential search bid set Q _B . Q _B is the set of bids compatible with the current optimal solution set. In order to improve the solution efficiency, at the beginning of each iteration, the algorithm first searches the bid set QB and adds the bid vehicle task with the lowest bid in Q _B to the candidate solution C according to the conflict bid matrix Mcon. Furthermore, a temporary bidding task set TemB is obtained according to the candidate solution C: TemB=GT-C.

和报价浮动区间

。概率参数用于控制在每轮迭代中选择最低出价的概率，报价浮动区间表示当前报价和最小报价的差距以确定候选投标方案的报价范围。FLS算法以概率

执行最小报价V_min贪婪搜索，进而，以最小报价V_min的浮动区间

为报价范围从临时投标任务集TemB中选择投标任务集合F_B，即任务集合F_B的投标报价与最小报价V_min的差距在浮动区间

以内。然后，该算法从集合F_B中随机选择投标任务B_can加入到候选解C中。其中函数random(x)表示从集合x中随机选择元素。此外，FLS算法以概率

从临时任务集合TemB中随机选择一个投标任务B_can加入最优解C。In addition, in order to avoid the continuous optimization process to make the algorithm fall into local optimum, this algorithm designs a probability parameter

and quotation floating range

. The probability parameter is used to control the probability of selecting the lowest bid in each round of iterations, and the quotation floating interval represents the gap between the current bid and the minimum bid to determine the bid range of the candidate bidding scheme. The FLS algorithm uses probability

Perform a greedy search for the minimum quote V _min , and then, use the floating interval of the minimum quote V _min

Select the bidding task set FB from the temporary bidding task set _TemB for the quotation range, that is, the gap between the bidding price of the task set _FB and the minimum price V _min is in the floating range

within. Then, the algorithm randomly selects the bidding task _{B can} from the set FB to add to the candidate solution C. where the function random(x) represents the random selection of elements from the set x. In addition, the FLS algorithm uses probability

A bidding task B _can be randomly selected from the temporary task set TemB and added to the optimal solution C.

则更新全局最优解C_best。最后，FLS算法根据冲突矩阵M_con更新Q_B。The algorithm updates the candidate solution C by judging the conflict relationship of bidding tasks. Suppose VC={Vc _g | g=1,2,…,mc} is the corresponding bid price in the bidding task set C; VB={Vb _h | h=1,2,…,mb} is the optimal solution C _best The bid price corresponding to the task in the middle. if

Then update the global optimal solution C _best . Finally, the FLS algorithm updates Q _B according to the conflict matrix M _con .

Step S8 is specifically that the traffic volume flowing into the road segment ri from the road segment r _{i -1} can be calculated according to the vehicle route scheme within the time step, and the vehicle position information is updated;

When the traffic flow and traffic density obey the relationship shown in Figure 2, the instantaneous flow q of the road section is:

为交通密度，

为路段拥堵时的交通密度；qmax为路段饱和流量；v为自由交通流速度；w为交通拥挤时反向传播速度；in,

is the traffic density,

is the traffic density when the road is congested; qmax is the saturated flow of the road; v is the free traffic flow speed; w is the reverse propagation speed when the traffic is congested;

Therefore, in the time step tr, the traffic flow from the road segment _{ri -1} to the road segment ri is:

为在x时刻路段r_i-1的交通密度；

为在x时刻路段r_i的最大交通流入率；

为x时刻路段r_i的交通密度。where y _i (x) is the traffic inflow of road segment _{ri at time x; q i (} x) is the traffic inflow rate of road segment _ri at time x; tr is the time step;

is the traffic density of road segment r _i-1 at time x;

is the maximum traffic inflow rate of road segment _ri at time x;

is the traffic density of road segment _ri at time x.

As shown in Figure 2, the relationship between traffic density and traffic flow can be obtained:

为x时刻路段r_i的交通密度；tr为时间步长；v为自由交通流速度；where n _i (x) is the traffic volume of road segment _ri at time x;

is the traffic density of the road segment _ri at time x; tr is the time step; v is the free traffic flow speed;

Therefore, the traffic propagation relationship between road segments is:

y _i (x)=q _i (x)tr=min{ n _i-1 (x), Q _i (x), w[N _i (x)- n _i (x)]/v}

Among them, _Qi (x) is the maximum inflow of the road segment _ri at time x, that is, the traffic capacity of the road segment; _Ni (x) is the maximum bearing capacity of the road segment ri at time x, that is, the traffic volume at the critical point of congestion; v is the free Traffic flow speed; tr is the time step; w is the back propagation speed when the traffic is congested; therefore, the maximum number of vehicles passing through the road section is calculated as y _i (x), this embodiment realizes the traffic flow through the FIFO principle and the above formula Propagation of adjacent road sections in the urban road network, and dynamically update the vehicle position in the process of vehicle allocation; in the specific embodiment, the specific application of the present invention in traffic flow allocation is specifically described in conjunction with the Nguyen network:

Set the simulation parameters as shown in Table 1:

Table 1 Traffic distribution parameters of simulated Nguyen network

Simulation scene description: Nguyen network was originally proposed as a classic traffic research case, and since its topology is close to the real road network, it has been widely used in traffic-related research results at home and abroad. Figure 4 is a schematic diagram of the network structure and initial parameters of the embodiment of the present invention. The Nguyen network structure includes 13 nodes and 38 two-way road sections. In order to simulate the distribution of the real traffic flow as much as possible, this experiment randomly sets the initial Traffic, with four nodes at the edge of the network as the travel destination.

In order to verify the effectiveness of the dynamic cooperative flow allocation method (DCA) of the present invention, the following six classical non-equilibrium traffic flow allocation methods including three dynamic flow allocation strategies and three static flow allocation methods are compared. Among them, the static shortest path method (SSP) plans paths for all vehicles according to the A* shortest path algorithm. Once the path scheme is determined, the routing scheme is not changed during the running process of the vehicle. To prevent road congestion caused by the only shortest path, the static Top-K shortest path method (STSP) firstly determines K optimal paths between ODs based on the shortest path algorithm and selects one of them as the path scheme based on a given probability. In fact, when travelers make route selection, there will be a certain deviation between the perceived driving impedance of each route and the actual route impedance, and this deviation has different probability distribution patterns. In the discrete choice model, based on static Logit loading The stochastic utility model of (SL) assumes that the random perception error of traveling vehicles obeys the Gumbel distribution, and has been widely used in route planning and traffic distribution applications. In addition, the dynamic shortest path method (DSP), the dynamic Top-K shortest path method (DTSP) and the dynamic logit loading method (DL) are dynamic flow distribution schemes developed based on the above three classical static routing schemes. The separate path selection process is performed within the step length to achieve the effect of dynamic flow distribution.

For the comparison of the flow space distribution of the flow distribution scheme, Figure 5 is a schematic diagram of the Nguyen network flow distribution result according to the embodiment of the present invention. The traffic flow distribution results of each method show obvious differences in the road network space. Fig. 5(a) is a schematic diagram of the flow distribution result of the SSP according to the embodiment of the present invention, Fig. 5(b) is a schematic diagram of the flow distribution result of the DSP method according to the embodiment of the present invention, and Fig. 5(c) is a schematic diagram of the flow distribution result of the STSP method according to the embodiment of the present invention. FIG. 5(d) is a schematic diagram of the flow distribution result of the DTSP method according to an embodiment of the present invention, FIG. 5(e) is a schematic diagram of the flow distribution result of the SL method according to an embodiment of the present invention, and FIG. 5(f) is a schematic diagram of the flow distribution result of the DL method according to an embodiment of the present invention. 5(g) is a schematic diagram of the flow distribution result of the DCA method according to the embodiment of the present invention, and FIG. 5(h) is a schematic diagram illustrating the road segment ID according to the embodiment of the present invention. Because there is no need to reconfigure the traffic flow, and the vehicles travel along the specified route, the statistical flow of the three static flow distribution methods is significantly smaller than that of the dynamic method. However, due to the fact that the actual travel distance of congested vehicles detouring increases due to the dynamic change of the traffic path, the traffic flow of the road section in the flow distribution result of the dynamic method is too large. The flow distribution results of the SSP, STSP and SL methods are similar. The traffic on the road sections located near the 4 end points and pointing to the end points is significantly larger than that of other paths, especially the traffic on the 21 and 25 road sections leading to the end point 1 shows the highest value, while the edge road sections are basically No transmission function. In the dynamic method, the DSP method only takes the shortest path in each replanning process. Compared with the static method, although part of the traffic is transferred to other road segments (road segments 12, 20, and 22), the utility of other paths is still ignored. The DTSP method and the DL method further transfer the traffic flow to the global road network through the probabilistic selection process of the path, making full use of the transportation capacity of as many road segments as possible, but the global adjustment of each time step not only requires a lot of computational costs, but also free traffic. The path adjustment benefits of vehicles are not large and increase the transmission pressure of the relevant road sections (sections 20, 22, 27, 34), and thus crowd out the path adjustment space of congested vehicles. In contrast, the traffic distribution results of the DCA method are more balanced, which can fully coordinate the overall road transport capacity of the road network and improve the traffic efficiency of the road network.

Compared with the transmission efficiency of the road network of the flow distribution scheme, in the flow distribution process, the traffic flow transmission process of different methods is also significantly different. Figure 6 is a schematic diagram of the traffic flow transmission process of different flow distribution methods according to the embodiment of the present invention. In the traffic flow simulation transmission scenario of 1560 initial vehicles, all methods can quickly transfer the traffic to the road network in the early stage (within 80*30s). Vehicles near the end point are transported to the end point, but in the middle of the traffic flow, traffic congestion occurs due to the failure to effectively adjust the route, and the transportation efficiency of the static method begins to decline, while DTSP, DL and DCA can still maintain high transportation efficiency. . In this simulation scenario, the three dynamic methods, DTSP, DL, and DCA, completed all traffic tasks at 228*30s, 192*30s, and 123*30s, respectively, much higher than other methods. In addition, all methods repeat the calculation for the same data 5 times to obtain the error interval (shaded area) in the figure. The results show that all methods have relatively stable traffic flow results, and because the two shortest path methods SSP and DSP do not consider the probability selection problem , so the result is invariant to repetition.

In order to verify the stability and effectiveness of the method under different initial traffic conditions, this example compares the road network traffic efficiency of 10 groups of different initial traffic flows. Figure 7 is a schematic diagram of the influence of initial traffic flow on the efficiency of road network according to the embodiment of the present invention. With the increase of initial vehicles, the road network travel time of all flow distribution methods shows a stable and continuous upward trend. The network traffic efficiency is significantly better than the static method. In the static flow distribution scheme, the shortest path method SSP shows the most stable time growth trend, and the global traffic time of the road network is linearly related to the initial number of vehicles. Although the transit time of the road network in the distribution result of the SL method is locally unstable, it still shows an upward trend in general. And the results of the DCA method show the optimal road network transportation efficiency in all cases.

，如下式所示，即当前时刻路段上的车辆数目与路段容量的比值。In order to further reveal the difference between the traffic efficiency in the flow distribution process of different methods, this embodiment detects the change process of the utilization rate of the transportation capacity of the road section in the flow distribution process from the perspective of the local road network. The transport capacity of a road segment is defined as the saturation of the road segment traffic

, as shown in the following formula, that is, the ratio of the number of vehicles on the road segment at the current moment to the road segment capacity.

表示路段r _i 上在第tr次路径重规划时的车辆数目；C _i 表示路段r _i 的单次运输能力。where:

Represents the number of vehicles on the road segment ri during the t -th re-planning ; C _{i represents} the single transportation capacity of the road segment _ri .

As the center of the network, node 6 in the Nguyen network is an important global traffic convergence point and control center of the network. The process in which a large number of traffic flows gather to 6 nodes and diverge outwards can represent the flow distribution process of the corresponding method, so this embodiment selects the only 4 outwardly diffused road sections adjacent to node 6 (Road7, Road11, Road22 and Road25) as The detection object of the flow saturation change process. As a result, Fig. 8 is a schematic diagram of the comparison of the road section saturation change process according to the embodiment of the present invention, Fig. 8a is a schematic diagram of the road section saturation degree of the DCA method according to the embodiment of the present invention, and Fig. 8b is a schematic diagram of the road section saturation degree of the DTSP method according to the embodiment of the present invention. FIG. 8c is a schematic diagram of road section saturation using a DSP method according to an embodiment of the present invention, FIG. 8d is a schematic diagram of road section saturation using a DL method according to an embodiment of the present invention, FIG. 8e is a schematic diagram of road section saturation using an STSP method according to an embodiment of the present invention, and FIG. 8f is the present invention. A schematic diagram of road section saturation in the SL method according to the embodiment, and FIG. 8g is a schematic diagram of the road section saturation in the SSP method according to an embodiment of the present invention. A large amount of initial flow in section 7 causes section 7 to be in a near-flow saturation state (ρ _jam = 0.15) at the beginning of the flow distribution. The four dynamic flow distribution methods quickly guide the flow to three sections 11, 22 and 25 to balance the section utilization. Among them, the DCA method gives full play to the transportation capacity of the four road sections, and the four road sections have relatively balanced traffic saturation, so the traffic task aggregated by this node is quickly decomposed and completed. DTSP and DL methods Segments 11 and 22 spread the flow pressure of segment 7, but the relative idleness of segment 25 resulted in a longer processing time. In addition, the three static methods do not fully utilize the transportation capacity of road sections 11, 22 and 25, and the long-term congestion of road section 7 also leads to the inefficiency of the overall road network.

Compared with the road section impedance of the flow distribution scheme, the DCA method greatly improves the overall traffic efficiency of the road network through the continuous path adjustment process of the vehicles affected by the congested road sections. In this embodiment, the DCA method performs more than 3,000 path re-planning operations on the relevant vehicles during the flow distribution process. The impedance comparison before and after each path adjustment is shown in Figure 9, which shows the path impedance before and after dynamic adjustment according to the embodiment of the present invention. Comparison diagram. There is a clear correlation between the path impedances before and after adjustment. The path impedance in the early and middle stages of dynamic distribution is relatively stable. In the later stage of the distribution, when the traffic flow reaches the vicinity of the end point, the selected solution set of the route regulation becomes smaller, and the global impedance increases significantly. Overall, the impedance is reduced by an average of 32.71% after the path replanning, which greatly improves the transmission efficiency of the road network.

In addition, this embodiment compares the running times of various algorithms under different vehicle sizes. The results are shown in Table 2:

Table 2 The relationship between the size of the traffic flow and the running time of the algorithm (time: s)

All flow distribution methods are positively correlated with the initial traffic flow size, but the dynamic method occupies a large amount of computing resources due to the dynamic path re-planning at each time step, which leads to a huge gap between its computational efficiency and the static flow distribution method. The static shortest path method SSP has a computational efficiency in seconds, while the computation time of the dynamic logit loading method DL is measured in hours. Compared with other dynamic flow distribution methods, the DCA method shows a huge time cost advantage due to the determination of congested road sections, and still improves the operating efficiency by about 100% compared with the DSP method that performs better in the dynamic method. Based on the flow distribution process and results, the DCA method compresses the computational cost to the greatest extent while greatly improving the traffic efficiency of the road network.

Claims (8)

1. a traffic flow dynamic collaborative allocation method under a distributed framework is characterized in that comprising the steps: S1. Planning an initial routing scheme for all vehicles; S2. Count the current road network vehicles. When the current road network vehicles are greater than the preset value, the following steps are performed; otherwise, the traffic flow of the road section is counted and the results of the cooperative allocation of all vehicles are output, and the dynamic cooperative allocation process of the current traffic flow is ended; S3. Count the traffic density of all road sections at the current moment; S4. Determine the congestion situation of the road section according to the congestion traffic density threshold; if the road section is not congested, go to step S5; otherwise, go to step S6; S5. Extract the route scheme FL of the previous iteration, and go to step S8; S6. extracting a set of vehicles T for re-planning the route on the congested road section; S7. The route scheme FN of the vehicles in the vehicle set T of the re-planned route according to the bidding mechanism; S8. Input the new traffic demand, and update the vehicle position according to the route scheme FN of the vehicles in the vehicle set T of the re-planned route in step S7 or the route scheme FL of the previous iteration in step S5; S9. Complete the above steps, count the traffic of the road section and output the results of all vehicle collaborative allocation; Among them, in the bidding mechanism, each bidding road segment node obtains k optimal shortest paths as candidate traffic loading strategies from the current road segment to the target point, and k paths have a probability of being selected according to the traffic impedance of the paths ; OD's probability of being selected for the jth path of u

for

Among them, OD is the starting and ending point, and θ is a discrete parameter that measures the degree of perception error of the traveling vehicle;

is the bid price of the bidding section of the jth path of OD to u ; ^Ju is the set of k candidate paths between OD and u ; Based on the above path selection probability, bidder Bidder assigns an optimal path for each vehicle task, and submits a task plan BT _e and its corresponding path impedance quotation V _e to the tenderer Tenderer . 2. The method for dynamic collaborative allocation of traffic flow under a distributed framework according to claim 1, wherein in step S3, the traffic density refers to the traffic volume existing on the road of a unit length at a certain time, and the traffic density of the road section r at a certain time is calculated as: :

where L _r is the length of road segment r ,

is the number of vehicles in the i -th cluster on road segment r ; When the traffic density of the road section at the current moment is not more than 0.9 times the traffic density when the road section is congested at the current moment, the vehicles on the road section do not change the route plan, and continue to drive according to the route plan of the previous time step within this time step; otherwise, on the road section The vehicle re-plans the route plan according to the bidding mechanism. 3. the traffic flow dynamic collaborative allocation method under the distributed framework according to claim 2, is characterized in that the bidding mechanism comprises the steps: (1) Calculate the impedance of the road section; (2) Obtain the traffic loading strategy and calculate the probability that the path is selected. 4 . The method for dynamically coordinating traffic flow allocation under a distributed framework according to claim 3 , wherein in step (1), calculating the impedance of a road section specifically includes the following steps: 5 . 1) Determine the impedance of each road segment in the road network; 2) Calculate the travel time of the road section in the state of traffic congestion; 3) Build a road segment impedance matrix based on the passage time of the road segment, which is used as the quotation for calculating the traffic distribution plan. 5. The method for dynamic collaborative allocation of traffic flow under a distributed framework according to claim 4, characterized in that in step 1), the road section impedance adopts the vehicle running time as the travel cost, and the travel time of the road section without congestion is calculated by the BPR function: Time _r = Time _free [1+ α ( q _i / Q _i ) ^β ] Among them, Time _r is the normal travel time of road segment ri under non-congested conditions; Time _free is the free flow travel time of road segment ri ; q _i is the traffic flow of road segment _ri ; _{Qi is} the traffic _capacity of road segment _ri ; α and β are the retardation coefficients, the reference value of α is 0.223, and the reference value of β is 2.037. 6. The method for dynamic collaborative allocation of traffic flow under a distributed framework according to claim 5, characterized in that in step 2), the travel time of a road section under a traffic congestion state is specifically:

Among them, Time _jam is the traffic time of the road segment ri _when it is _congested ; Li is the length of the road segment _ri ;

is the critical speed of the road segment ri ; ρ _jam is the traffic density when the road segment is congested at the current moment ; ρ _i is the traffic density of the road segment _{ri .} 7. The method for dynamic collaborative allocation of traffic flow under a distributed framework according to claim 6, characterized in that in step 3), the bid price of the bidding road segment includes the time spent on the road segment travel time, intersection delay time and time estimation noise:

Among them, Nr is the number of uncongested road sections passed by the route; Njam is the number of congested road sections passed by the route; Nis is the number of intersections passed by the route;

is the normal traffic time of each non-congested road section;

is the travel time of each congested road section; Time _δ is the time noise;

It is the delay time at the intersection, including the delay time of vehicle queuing and the delay time of signal lights;

Among them, N _Ve is the number of queued vehicles at the intersection;

is a linear coefficient; ε is the control parameter of signal light delay time. 8. The traffic flow dynamic collaborative allocation method under the distributed framework according to one of claims 1 to 7, is characterized in that step S8, is specifically calculated to flow into by road segment r _{i -1} in time step according to vehicle route scheme. _Traffic volume of road segment ri and update vehicle location information; The traffic propagation relationship between road segments is: y _i ( x )= q _i ( x ) tr =min{ n _{i -1} ( x ), Q _i ( x ), w [ N _i ( x )- n _i ( x )]/ v } Among them, q _i ( x ) is the traffic inflow rate of road segment ri at time x ; tr is the time step; n _{i -1} ( x ₎ is the traffic volume of road segment ri at time x -1; Qi ₍ x ) is the maximum inflow of the road segment ri at time x , that is, the traffic capacity of the road segment; Ni ₍ x ) is the maximum bearing capacity of the road segment ri at time x, the traffic volume at the critical point of congestion; ni ( x ) is _{the road segment} ri _at the time of The traffic volume at time x ; v is the free traffic flow speed; w is the back propagation speed when the traffic is congested; thus, the maximum number of vehicles passing through the road section is calculated as y _i ( x ); the traffic flow is realized by the FIFO principle and the above formula Propagation of adjacent road segments in urban road networks and dynamically updating vehicle positions during vehicle allocation.

Images