CN108876045A - Emergency tender optimal route recommended method based on LSTM model prediction - Google Patents

Abstract

The present invention provides an optimal route recommendation method for emergency vehicles based on LSTM model prediction. The present invention utilizes the LSTM model in RNN to construct a three-layer calculation hierarchy, and at the same time determines the number of memory elements layer by layer. The data such as the average running time of the road, the average speed of the vehicle, and the total number of running vehicles are used to predict the data of the next minute in units of 5 minutes. The five time periods of the day were used as the background, and the experiment was carried out with the same starting point and end point as the conditions. When it is a relatively busy time of the day, and the road is in a state of congestion and slow traffic, different routes will be selected for the control scheme and the experimental scheme. Compared with the control scheme, the experimental scheme saves 0.5min, 1.5min, 0.7min, and 0.4min respectively, accounting for 4.5%, 15.0%, 7.5%, and 4.7% of the experimental scheme.

Description

Optimal route recommendation method for ambulance based on LSTM model prediction

technical field

The invention relates to a method for recommending an optimal route of an ambulance based on LSTM model prediction.

Background technique

How to send the emergency patient to the hospital as soon as possible is an important factor for successfully rescuing the patient. Although the vehicle has been equipped with a navigation system to assist the staff in route planning and selection, the current navigation system is based on the processing and analysis of past data, and generally does not respond to the condition of "time is life" for medical emergencies. optimization.

Contents of the invention

The object of the present invention is to provide a method for recommending the optimal route of an ambulance based on LSTM model prediction.

In order to solve the above problems, the present invention provides a method for recommending an optimal route for emergency vehicles based on LSTM model prediction, including:

Use the LSTM model in RNN to build a three-layer computing hierarchy, and at the same time determine the number of memory elements layer by layer, and predict the traffic data of the next minute in units of 5 minutes according to the traffic data of the preset roads in the urban road network;

According to the predicted traffic data in the next minute, the optimal route recommendation for the ambulance is made.

Further, in the above method, according to the traffic data of preset roads in the urban road network, including:

According to the traffic data of the average running time, average speed, and total number of running vehicles of preset roads in the urban road network.

Further, in the above method, the traffic data of the next minute is predicted in units of 5 minutes, including:

The traffic data of the average running time, average speed, and total number of running vehicles in the next minute is predicted in units of 5 minutes.

Further, in the above method, the total number of running vehicles is the total number of vehicles passing a certain preset road per unit time, wherein the same two-way road is regarded as two roads with opposite directions.

Further, in the above method, the average running time refers to the average time taken by all vehicles passing by on a certain preset road per unit time to complete the journey.

Further, in the above method, the average vehicle speed refers to the average speed used by all vehicles passing by on a certain preset road per unit time to travel a complete distance.

Further, in the above method, the LSTM model in RNN is used to construct a three-layer computing hierarchy, including:

Build a predictive model based on LSTM, determine the parameters in the predictive model of the LSTM;

According to the parameters in the prediction model of the LSTM, a three-layer calculation hierarchy is constructed.

Compared with the prior art, the present invention utilizes the LSTM model in the RNN to predict the traffic data of some roads in the urban road network in the next minute with 5 minutes as the unit time, and update it in real time. Through the above data processed and analyzed, the emergency vehicle can be notified in a timely and convenient manner, which can help it find the route to the hospital more quickly and lay a good foundation for saving the lives of patients.

Description of drawings

Fig. 1 is the basic unit schematic diagram of the LSTM model of an embodiment of the present invention;

Fig. 2 is a schematic diagram of information interaction of memory elements in LSTM according to an embodiment of the present invention;

Fig. 3 is the statistical diagram of the average running time, the average vehicle speed, and the total number of running vehicles predicted by the LSTM model of an embodiment of the present invention;

Fig. 4 is a comparison schematic diagram of the control scheme and the experimental scheme circuit of an embodiment of the present invention;

Fig. 5 is a schematic diagram of running a sigmoid layer to determine which part of the cell state will be output according to an embodiment of the present invention;

Figures 6a, 6b, and 6c are schematic diagrams of the average running time, the average vehicle speed, and the total number of vehicles in operation, respectively, according to an embodiment of the present invention;

FIG. 7 is a schematic diagram of a time-divided road selection scheme according to an embodiment of the present invention.

Detailed ways

In order to make the above objects, features and advantages of the present invention more comprehensible, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

As shown in Figure 1, the present invention provides a method for recommending an optimal route for emergency vehicles based on LSTM model prediction, including:

Use the LSTM model in RNN to build a three-layer computing hierarchy, and at the same time determine the number of memory elements layer by layer, and predict the traffic data of the next minute in units of 5 minutes according to the traffic data of the preset roads in the urban road network;

According to the predicted traffic data in the next minute, the optimal route recommendation for the ambulance is made.

Here, the road information is changing rapidly. Although it is known that the traffic data presents periodic and time-sequential changes, it is very necessary to achieve accurate prediction and real-time updates for medical rescue.

AutoNavi Maps is a leading provider of digital map content, navigation and location service solutions in China, and can provide more reliable navigation services. However, the existing navigation application data is based on the processing and understanding of past data, and can provide solutions or suggestions for "current" traffic conditions, such as route planning, but cannot predict future traffic data.

Using the LSTM model in RNN, this paper predicts the average travel time (avgtraveltime), average speed (speed), total number of vehicles (totalcount) and other data of some roads in the urban road network, and predicts the next minute in units of 5 minutes. data and update it in real time. Through the above data processed and analyzed, the emergency vehicle can be notified in a timely and convenient manner, which can help it find the route to the hospital more quickly and lay a good foundation for saving the lives of patients.

The five time periods of the day can be used as the background, and the experiment can be carried out with the same starting point and end point as the conditions. When it is a relatively busy time of the day, and the road is in a state of congestion and slow traffic, different routes will be selected for the control scheme and the experimental scheme. Compared with the control scheme, the experimental scheme saves 0.5min, 1.5min, 0.7min, and 0.4min respectively, accounting for 4.5%, 15.0%, 7.5%, and 4.7% of the experimental scheme.

Road information changes rapidly. Although it is known that traffic data presents periodic and time-sequential changes, it is very necessary to achieve accurate prediction and real-time updates for medical rescue. Using the LSTM model in RNN, this paper predicts the traffic data of some roads in the urban road network in units of 5 minutes to predict the data of the next minute and update it in real time. Through the above data processed and analyzed, the emergency vehicle can be notified in a timely and convenient manner, which can help it find the route to the hospital more quickly and lay a good foundation for saving the lives of patients.

In an embodiment of the method for recommending the optimal route for emergency vehicles based on LSTM model prediction of the present invention, the main traffic data in the traffic road network are extracted, including average running time, average vehicle speed, and total number of vehicles in operation, among which the running time and average vehicle speed are the most It can reflect the actual traffic capacity of a road and provide the most reliable reference for emergency vehicles to choose a road.

In an embodiment of the method for recommending the optimal route of an ambulance based on LSTM model prediction of the present invention, the traffic data of the next minute is predicted in units of 5 minutes, including:

The traffic data of the average running time, average speed, and total number of running vehicles in the next minute is predicted in units of 5 minutes.

Here, based on the prediction model of LSTM, it is determined that the traffic data of roads in a certain area include average travel time (avgtraveltime), average vehicle speed (speed), and total number of vehicles in operation (totalcount). By using the LSTM model, the algorithm in this paper can predict the average travel time (avgtraveltime), average speed (speed), and total number of vehicles (totalcount) of the road in the next minute based on the data basis of the previous five minutes.

In an embodiment of the method for recommending the optimal route for emergency vehicles based on LSTM model prediction of the present invention, the total number of running vehicles is the total number of vehicles passing by a certain preset road per unit time, wherein the same two-way road is regarded as Two roads with opposite directions.

In an embodiment of the method for recommending the optimal route for emergency vehicles based on LSTM model prediction of the present invention, the average running time refers to the average time taken by all vehicles passing through a unit time on a certain preset road to complete the journey number.

In an embodiment of the method for recommending the optimal route for emergency vehicles based on LSTM model prediction of the present invention, the average vehicle speed refers to the average speed used by all vehicles passing through a unit time on a certain preset road to travel the entire distance .

Figure 2 is a statistical chart of the average running time, average speed, and total number of running vehicles predicted by using the LSTM model in this paper (the dark color is the actual data, and the light color is the predicted data). Because the average running time and average vehicle speed are more important for optimizing route selection and counting the running time, this application focuses on analyzing the two graphs of average running time and average vehicle speed.

In an embodiment of the method for recommending the optimal route of an ambulance based on LSTM model prediction of the present invention, the LSTM model in the RNN is used to construct a three-layer calculation hierarchy, including:

Build a predictive model based on LSTM, determine the parameters in the predictive model of the LSTM;

According to the parameters in the prediction model of the LSTM, a three-layer calculation hierarchy is constructed.

Here, the Long Short Term network (generally called LSTM) is a special type of RNN that can learn long-term dependent information. LSTM was proposed by Hochreiter & Schmidhuber (1997), and was recently improved and promoted by Alex Graves. LSTM avoids long-term dependency problems through deliberate design. Remembering long-term information is in practice the default behavior of LSTMs, not an ability to acquire at great cost. All RNNs have a form of chains of repeating neural network modules. In a standard RNN, this repeating module has only a very simple structure, such as a "layer". LSTM has the same structure, but the repeated modules have a different structure. Instead of a single neural network layer, there are four here, interacting in a very specific way as shown in Figure 2. The repeating module in LSTM consists of four interacting layers. In order to make the influence of the output of the hidden layer on the next moment controllable, LSTM introduces the concept of input gate and output gate.

In the present invention, five representative time periods in one day are used as the background, and experiments are carried out under the same starting point and end point. The experimental results show that when the road traffic is smooth, the control scheme and the experimental scheme choose the same route. And when it is a relatively busy time of the day, when the road is congested and slow-moving, different routes will be selected for the control scheme and the experimental scheme. Compared with the control scheme, the experimental scheme saves 0.5min, 1.5min, 0.7min, and 0.4min respectively, accounting for 4.5%, 15.0%, 7.5%, and 4.7% of the experimental scheme. Through the above data processed and analyzed, the emergency vehicle can be notified in a timely and convenient manner, which can help it find the route to the hospital more quickly and lay a good foundation for saving the lives of patients.

In practical applications, the RNN model has the problems of gradient disappearance and gradient explosion. According to the chain rule, the partial derivative of the output error for the input layer is equal to the product of the partial derivatives of each layer. Assuming that the average squared error is used, at time t, the error signal of the output layer ht _-1 is expressed as:

v _k (t)=f′ _k (net _k (t))(d _k (t)-y ^k (t))

Among them, y ⁱ (t) = f _i (net _i (t)) represents a non-input unit, f _i is a differentiable function,

Represents the input of the current network unit, w _ij is the weight between unit j and i. The reverse error signal of non-output unit j is:

For an RNN network with a time step of q, the error at time t-q can be solved by the following recursive function:

Let l _q = v, l ₀ = u, the above formula can be further written:

Since the gradient is finally obtained in the form of a product, if each item (or most) of the multiplication formula is greater than 1,

will result in a gradient explosion; if each item is less than 1,

Then as the number of multiplications increases, the gradient will disappear. Both vanishing and exploding gradients seriously affect the learning process. In order to avoid gradient disappearance and gradient explosion, a simple method is to force the error flowing through each neuron to be 1, that is, simple derivation shows that f is a linear function. This ensures that the error will flow in the network in the form of parameters, and there will be no problem of gradient explosion or gradient disappearance. This structure is called CEC (constant error carousel). But this approach has the problem of weight conflict.

In a standard RNN, this repeated module has only a very simple structure, such as a "tanh layer". LSTM has the same structure, but the repeated modules have a different structure. Instead of a single neural network layer, here are four, interacting in a very specific way. The repeating module in LSTM consists of four interacting layers. In order to make the influence of the output of the hidden layer on the next moment controllable, LSTM introduces the concept of input gate and output gate. The basic unit of LSTM is called memory cell, which is expanded on the basis of CEC, as shown in Figure 1 and Figure 2.

LSTM has the ability to remove or add information to the cell state through carefully designed structures called "gates", as shown in Figure 3. A gate is a way to allow selective passage of information. They consist of a sigmoid neural network layer and a pointwise multiplication operation. The sigmoid layer outputs a value between 0 and 1, describing how much of each part can pass. 0 means "no amount is allowed to pass", and 1 means "any amount is allowed to pass". LSTM has three gates to protect and control the cell state.

The first step in LSTM is to decide what information we will throw away from the cell state. This decision is made through a layer called the "forget gate". This gate will read h _t-1 and x _t and output a value between 0 and 1 for each digit in cell state C _t-1 . 1 means "completely keep", 0 means "completely discard".

f _t = σ(W _f ·[h _t-1 , x _t ]+b _f ) i _t =σ(W _i ·[h _t-1 , x _t ]+b _i )

The next step is to determine what new information is stored in the cell state. There are two parts here. First, the sigmoid layer called the "input gate layer" decides what values we are going to update, as shown in Figure 4. Then, a tanh layer creates a new vector of candidate values will be added to the state. Next, C _t-1 is updated to C _t . The previous steps have determined what will be done, and we are now going to actually do it. We multiply the old state by ft, _discarding information we are sure needs to be discarded. then add These are the new candidate values, which change according to how much we decide to update each state.

O _t =σ(W _o [h _t-1 , x _t ]+b _o ) h _t =o _t *tanh(C _t )

Ultimately, we need to determine what value to output. This output will be based on our cell state, but also a filtered version. First, we run a sigmoid layer to determine which part of the cell state to output, as shown in Figure 5. Next, we pass the cell state through tanh (to get a value between -1 and 1) and multiply it with the output of the sigmoid gate, and finally we only output the part that we determine the output.

Next, we determine the backpropagation of the error. First, the subscript representation is specified as follows:

k: output unit

i: hidden unit

C _j : the jth memory element block

The vth cell in the jth memory element block C _j

l, m, u: any network unit

t: all time steps of the given input sequence

At time t, the squared error of the LSTM is calculated as follows:

Among them, t ^k (t) is the output target of output unit k at time t. Under the condition of learning rate α, the gradient-based update of w _lm is as follows:

The error (error) of unit l at time t is defined as:

The standard directional error propagation algorithm (backdrop) can be used to calculate the output unit (output unit, l=k), hidden unit (hidden unit, l=i), output gate unit (output gate unit, l=out _j ) Weight update:

l=k(output):e _k (t)=f′ _k (net _k (t))(t ^k (t)-y ^k (t))

For all possible units l, the update contributed by time t to the weight w _lm is:

△w _lm (t)=αe _l (t)y ^m (t-1)

In the calculation formula, it can be found that the calculation formula of the output gate is: in Yes function of h and irrelevant, according to the derivation rule, h is preserved, So get the above formula.

The rest of the updating of the input gate unit (l=in _j ) and the memory element unit j ^v will be somewhat different from conventional units. define internal state The error is:

Although the form of the above formula is somewhat complicated at first glance, it can be found through careful analysis that it is similar to the case of finding the gradient of the output gate, because With irrelevant term, so it is preserved during the derivation process.

It can be obtained from the above derivation that when l=in _j or Error when:

intermediate state unit for input unit weight The partial derivative of can be calculated as follows:

Therefore, at time t for The updated contributions are:

intermediate state unit for input unit weight The partial derivative of can be calculated as follows:

Therefore, at time t for The updated contributions are:

The above is the equation that the backpropagation algorithm needs to use. In the process of updating weights, the total update value of each weight is the sum of the contributions of all time t to w weight update.

The computational complexity of each update of LSTM is: o(KH+KCS+HI+CSI)=o(W)

Among them, K represents the number of output units, C represents the number of memory element blocks, S>0 represents the size of memory element blocks, H is the number of hidden units, and I is the number of units directly connected to memory elements, gate units, and hidden units. quantity, and W=KH+KCS+CSI+2CI+HI=O(KH+KCS+CSI+HI) is the quantity of weight.

The main traffic data in the traffic road network include average running time, average speed, and total number of running vehicles. Among them, running time and average speed can best reflect the actual traffic capacity of a certain road, and provide the most reliable reference for emergency vehicles to choose roads. The total number of running vehicles is the total number of vehicles passing a certain road per unit time. This paper considers the same two-way road as two roads with opposite directions. The average running time refers to the average time taken by all vehicles passing through a certain road per unit time to complete the journey, and the average vehicle speed refers to the average speed of all vehicles passing through a certain road per unit time to complete the journey. number.

As shown in Figures 6a, 6b, and 6c, the present invention can obtain the first peak-morning peak at 500min (about 8:30am) in average running time, and last for about 60min (from 8:00am to 9:00am). And reached the second peak at 1080min (about 6:00pm) - the evening peak, which lasted about 65min (from 5:30pm to 6:35pm). The change of the average running time curve and the change of the total number of running vehicles (ie traffic flow) curve show a positive correlation trend. The average vehicle speed curve continued to fluctuate after reaching the morning peak, basically maintained at a high level, and finally dropped at a relatively rapid rate after the evening peak.

Immediately after receiving the emergency call, the ambulance rushed to the office building of Building F, Block N6, Yuanrong Times Square, Industrial Park, Wuzhong District, Suzhou City, as described by the call. The data currently provided is based on the processing and understanding of past data and cannot predict future traffic data. A road selection plan (experimental plan) based on the LSTM model to predict the average travel time of the road is proposed for the control sample by time period.

Table 1 Information on recommended solutions for AutoNavi Maps

plan 1 Scenario 2 Option 3 Total route length/km 2.60 2.70 2.60 Total travel time/mins 8.0 8.0 8.5 Number of passing traffic lights 7 6 7

By using the LSTM model, the algorithm in this paper can predict the average running time, average speed, and total number of running vehicles of the road in the next minute based on the data basis of the previous five minutes. This paper gives a road selection plan for different periods. As shown in the following table, the existing urban roads are divided into red (congestion), yellow (slow traffic), and green (smooth) according to the predicted average vehicle speed. The solid line in the map is The control plan, the dotted line is the experimental plan (the total travel time is the sum of the average running time of all roads in the plan) as shown in Figure 7.

Table 2 Control scheme and experimental scheme data table

For the patients on the ambulance, time is life. If the ambulance arrives at the hospital one minute earlier, there will be more hope of recovery, and even save lives. LSTM avoids long-term dependence problems through deliberate design, and predicts the average running time, average speed, and total number of running vehicles of the road in the next minute based on the previous five-minute data basis. Among them, the running time and average speed can best reflect the actual traffic capacity of a certain road, and provide the most reliable reference for emergency vehicles to choose a road. In the above case, this article takes five representative time periods of the day as the background, and carries out the experiment under the same starting point and end point. The experimental results show that when the road traffic is smooth, the control scheme and the experimental scheme choose the same route. And when it is a relatively busy time of the day, when the road is congested and slow-moving, different routes will be selected for the control scheme and the experimental scheme. Compared with the control scheme, the experimental scheme saves 0.5min, 1.5min, 0.7min, and 0.4min respectively, accounting for 4.5%, 15.0%, 7.5%, and 4.7% of the experimental scheme. If patients with acute cerebral hemorrhage receive treatment one minute earlier, it is very possible to save their lives.

Each embodiment in this specification is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other.

Professionals can further realize that the units and algorithm steps of the examples described in conjunction with the embodiments disclosed herein can be implemented by electronic hardware, computer software or a combination of the two. In order to clearly illustrate the possible For interchangeability, in the above description, the composition and steps of each example have been generally described according to their functions. Whether these functions are executed by hardware or software depends on the specific application and design constraints of the technical solution. Those skilled in the art may use different methods to implement the described functions for each specific application, but such implementation should not be regarded as exceeding the scope of the present invention.

Obviously, those skilled in the art can make various changes and modifications to the invention without departing from the spirit and scope of the invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and equivalent technologies thereof, the present invention also intends to include these modifications and variations.

Claims (7)

1. A method for recommending an optimal route of an ambulance based on LSTM model prediction, characterized in that, comprising: Use the LSTM model in RNN to build a three-layer computing hierarchy, and at the same time determine the number of memory elements layer by layer, and predict the traffic data of the next minute in units of 5 minutes according to the traffic data of the preset roads in the urban road network; According to the predicted traffic data in the next minute, the optimal route recommendation for the ambulance is made. 2. The emergency vehicle optimal route recommendation method based on LSTM model prediction as claimed in claim 1, is characterized in that, according to the traffic data of preset road in the city road network, comprising: According to the traffic data of the average running time, average speed, and total number of running vehicles of preset roads in the urban road network. 3. the ambulance optimal route recommendation method based on LSTM model prediction as claimed in claim 2, is characterized in that, take 5min as unit time and predict the traffic data of next minute, comprise: The traffic data of the average running time, average speed, and total number of running vehicles in the next minute is predicted in units of 5 minutes. 4. as claimed in claim 2 or 3 described based on the emergency vehicle optimal route recommendation method of LSTM model prediction, it is characterized in that, described total running vehicle number is the total number of vehicles that a certain preset road passes in unit time, Among them, the same two-way road is regarded as two roads with opposite directions. 5. The optimal route recommendation method for emergency vehicles based on LSTM model prediction as claimed in claim 2 or 3, wherein said average running time refers to all vehicles passing by on a certain preset road and per unit time The average amount of time it takes to travel the entire distance. 6. The optimal route recommendation method for emergency vehicles based on LSTM model prediction as claimed in claim 2 or 3, wherein said average vehicle speed refers to the travel of all vehicles passing by on a certain preset road in unit time The average speed used for the entire distance. 7. the ambulance optimal route recommendation method based on LSTM model prediction as claimed in claim 1, is characterized in that, utilizes the LSTM model in the RNN, builds three layers of computing levels, comprising: Build a predictive model based on LSTM, determine the parameters in the predictive model of the LSTM; According to the parameters in the prediction model of the LSTM, a three-layer calculation hierarchy is constructed.