Restatement of a problem

110 police cars patrolling the streets can not only deter criminals, reduce crime rates, but also increase citizens’ sense of security. It also speeds up the time for receiving and handling police, improves the response time, and provides a strong guarantee for social harmony.

An area in a certain city is given. Its road data and map data are known. The coordinates of three key parts in the area are: (5112, 4806), (9126, 4266), ( 7434, 1332). There are a total of 307 road intersections in this area. To simplify the problem, the road between two adjacent intersections is approximately considered to be a straight line, and all accident scenes are on the road in the picture below.

The city plans to add a batch of 110 police cars equipped with GPS satellite positioning systems and advanced communication equipment. Assume that the average patrol speed of 110 police cars is 20km/h, and the average driving speed after receiving the police is 40km/h. The police car configuration and patrol plan should try to meet the following requirements:

D1. The proportion of police cars arriving at the scene within three minutes after receiving the alarm is not less than 90%; and the time to arrive at key locations must be within two minutes. Inside.

D2. Make the patrol effect more significant;

D3. The police patrol pattern should have a certain degree of concealment.

Now we need to solve the following problems:

1. If the requirement is to meet D1, how many police cars need to be deployed in the area to patrol at least?

2. Please provide relevant indicators to evaluate the significance of patrol effects.

3. Please provide a police car patrol plan and its evaluation index value that satisfies D1 and tries to satisfy D2 conditions.

4. Based on the third question, consider the D3 condition and give your police car patrol plan and its evaluation index values.

5. If only 10 police cars are deployed in this area, how should a patrol plan be formulated to satisfy D1 and D2 as much as possible?

6. If the average driving speed of police cars increases to 50km/h after receiving the alarm, answer question three.

7. What other factors and circumstances do you think need to be considered? Provide you with corresponding solutions.

II Problem Analysis

This topic is about the deployment and patrolling of police cars in urban road networks. When configuring police cars, we must first consider the proportion of police cars that arrive at the scene within the specified time after receiving the alarm. Under this condition, model and solve with the minimum number of cars as the goal; when formulating the patrol plan, we must consider the number of patrols. Effect and concealment issues.

The problem requires meeting D1 and finding the minimum number of police car configurations. It can be considered that the police car is immobile, and the area it can reach within three or two minutes is its coverage. Based on this, the optimal solution is found under the condition that the coverage rate of all streets is not less than 90%.

Question 2: To evaluate the effectiveness of patrols, there are two aspects that need to be considered: First, the comprehensiveness of patrols, that is, the proportion of the number of streets traveled by police cars to the total number of streets after a period of time; Unevenness, that is, the number of police cars passing through each street after a period of time is not much different, is measured by variance.

Question three is to try to meet the indicators given in question two while meeting the conditions of D1, and give the indicators for the evaluation plan. First find a group of police car positions that satisfy D1, and then randomly find a point among the points connected to each police car position to determine whether the new point satisfies D1. If it does, the police car will drive to that point, otherwise search again until it is satisfied. . After a period of time, count the number of points that all cars have passed and the number of times each point has been passed, and use the two indicators given in question 2 for evaluation. Combining the two indicators, the quality of this path can be judged, and this process is repeated until the comprehensive evaluation indicator reaches a satisfactory value.

Question 4 adds concealment requirements. First, an indicator for evaluating concealment is given. Concealment can be evaluated by the randomness of the route, and it is added to the model of Question 3 to solve it.

Question 5 limits the number of police cars to 10. D1 and D2 must be considered comprehensively. First allocate these 10 vehicles to achieve the highest road coverage, and then solve the problem according to the steps of question 3. Each step has an impact on D1. The judgment only needs to make the road coverage as high as possible.

Question 6 is the same as question 3, just change the speed to 50km/h.

Assumptions of the three models

1. Police cars are patrolling on the road, and the time it takes for patrol officers to handle cases is not considered;

2. All incident scenes are at On the road, cases are equally likely to occur at any point on the road;

3. The initial stopping points of police cars are random, but try to make them dispersedly distributed, and one police car has jurisdiction over one district;

< p>4. Assume that in each divided area, at most one case will occur in a relatively short period of time;

5. Assume that every road in the area is a two-way street, regardless of the impact of turns on the results. Impact;

6. If the key parts are not on the road, it is assumed that these key parts are on the road closest to them;

7. The water area in the picture has no impact on the patrol plan.

Explanation of four symbols

Indicates the number of police cars

Indicates the shortest distance from the initial stopping point of police cars to each road

Indicates the total number of police cars in the entire area Road length

Indicates the length of roads in areas that cannot be reached within 3 minutes

Indicates the proportion of police vehicles in non-key areas that cannot reach the scene within 3 minutes

Indicates the maximum distance that can be reached from the alarm location to the incident scene within three minutes

Indicates the total number of discrete points in the entire area

Indicates the number of nodes in the area< /p>

Represents the adjustment function within the region

Represents the simulated annealing time and represents the temperature value

Represents the interval adjustment function

Represents the comprehensiveness index< /p>

Represents the non-uniformity index

Represents the comprehensive evaluation index

Represents the number of times the first vehicle passes through each road

Represents the number of times the first vehicle passes through each road in the entire area. The average number of times a road passes

Establishment of five models and design of algorithms

5.1 When D1 is satisfied, the minimum number of police cars and patrol plans that need to be deployed in the area

< p>5.1.1 When the D1 condition is met, the rule of the minimum number of police cars in the area

The question requires that when the police car configuration and patrol plan meet the D1 requirement, the minimum number of police cars needs to be deployed in the entire area. It can be seen from the assumption that all police cars are on the road, and all incident scenes are also on the road, but the total road length in the area is a fixed value; there is a time limit and probability limit for police cars to rush to the incident scene after receiving the alarm: three minutes The proportion of people arriving at crime scenes in general areas should be no less than 90%, and the time needed to arrive at key locations must be controlled within two minutes. It can be seen that the jurisdiction of each police car will not be very large, so consider dividing the entire area into several sub-areas, and each police car has jurisdiction over one sub-area.

Based on the above analysis, the problem of finding the minimum number of police cars in the entire area can be transformed into solving the problem of maximizing the street range that each police car can govern. So we looked for rules that would make the area under each police car's jurisdiction as large as possible. In order to simplify the problem, we do not consider the 90% probability limit of arriving at the scene, and only make a qualitative analysis of the situation where the police car can arrive at the scene of the incident within three minutes. The analysis diagram is shown in Figure 1. The initial parking position of the police car is randomly distributed at any node on the road. We assume that a police car is parked at point A.

Figure 1 Schematic diagram of the jurisdictional analysis of a police car

Since the average patrol speed of a police car is 20km/h, and the average driving speed after receiving the police is 40km/h, distance information is relatively easy to obtain Obtained, so we convert the time limit into a distance limit, which facilitates analysis and solution. When a police car receives an alarm, the maximum distance it can travel from the location where it receives the alarm to the scene of the incident within three minutes is , where .

As shown in Figure 1, we set the initial parking position of the police car at point A, which is the intersection of roads 1, 2, 3, and 4. We only take the police car patrolling road 1 as an example for analysis. The police car patrols between point A on road 1 at a speed of , and the distance from the initial stopping point A is . Since the case may occur at any point on the road, when the police car patrols to point A, if the crime scene occurs on roads 2, 3, and 4, the police car drives towards the incident scene at a speed of 40km/h. The police car can The maximum distance from point to scene in minutes is. If the police car continues to drive forward on Road 1, the distance within which the police car can arrive at the scene within three minutes will continue to shrink. When the police car drives from the initial point to point A but does not reach point A, the maximum jurisdiction of the police car at this time Larger than the maximum jurisdiction when the police car arrives at the point. In order to make the jurisdiction of the police car as large as possible, the patrol range of the police car should be as small as possible. At that time, that is, when the police car is stationary at the initial stopping point, the jurisdiction of the police car reaches the maximum value.

What is analyzed in Figure 1 is a special situation, where roads 1, 2, 3, and 4 are symmetrically distributed. Now let us analyze the general situation, as shown in Figure 2.

Figure 2.1 Figure 2.2

Figure 2 Schematic diagram of analysis of the maximum jurisdiction of a police car

The situation shown in Figure 2.1 is an asymmetric road distribution, which is different from Figure 1 Compared with the direction and angle of the road shown in Figure 2.1, the situation in Figure 2.3 is more complicated.

Referring to the analysis method of Figure 1, we analyze the rules of the maximum distance that a police car can reach the scene within three minutes when patrolling in these two situations. We only analyze the situation in Figure 2.2, roads 1, 2, 3, 4, 5 intersects at point C. At the same time, road 1 and road 6 also have a road intersection D. Since the police car is driving on the road when patrolling, the walking route is a segmented straight line, which does not affect the length of the path. Therefore, when the police car patrols to D is far away from the initial stopping point C. If a case occurs at this time, the police car must arrive at the scene to handle the case within three minutes. The maximum driving distance is within the maximum driving distance. If the police car continues to drive forward on road 1 , then the distance that the police car can reach the scene within three minutes continues to shrink. When the police car does not drive to point D, the maximum jurisdiction of the police car is larger than that. In order to make the jurisdiction of the police car as large as possible, the patrol range of the police car is The smaller, the better. At that time, that is, when the police car is stationary, the jurisdiction of a police car can reach its maximum value.

The above analysis is only a qualitative analysis. The same analysis can be done for the three key parts, and the conclusions are consistent. The above analysis does not take into account the 90% arrival probability limit, but in the design Algorithms need to be fully considered.

To sum up, when the police car is stationary at the initial stopping point, the maximum distance that the police car can travel from the initial stopping point to the incident scene within the three-minute time limit is .

5.1.2 Discretize the roads

Since the accident scenes are distributed on the roads with equal probability, it can be found from the regional map that the length of the roads in the entire area is uneven. In order to make the calculation results more accurate, these roads can be discretized. As long as the appropriate discrete scheme is selected, the police car can be equivalent to passing this road when passing a discrete point on the road. In this way, whether it is to solve for the initial stopping point of the police car or the road that the police car passed to arrive at the scene of the incident, the calculated results are obviously much more accurate than just considering the intersection of the entire road.

There are 307 road intersections and 458 roads in the area. We use the linear interpolation method to discretize the road, and walk a distance of one minute at a speed of Use the linear interpolation method to perform linear interpolation from one direction of the road to achieve the goal of discretizing each road. Considering that some roads are not integer multiples of , we discuss the general situation. The analysis diagram is shown in Figure 3. The length of road AB is the sum of the length of and . In order to process the CB segment of the road more accurately, it is necessary to consider whether to insert a new point between CB. Depending on the length of , the corresponding processing methods are also different.

Figure 3 Schematic diagram of road discretization analysis

Introducing the critical index, the criterion for selecting the size is to make the equivalent average patrol speed of the police car after discretization as much as possible and the speed given in the question ( ) The difference should be as small as possible. After calculation, the road discretization effect in the entire area can be better when no new coordinate points are inserted. At this time, set the CB segment length to processing, so the discretized AB road length will be shorter than the actual length; at that time, you need to insert another point between the two points, because this processing can make the overall road in the entire area The discretization effect is ideal. As shown in Figure 3, a new coordinate point is inserted between C and B, and the inserted position is at point D away from point C. The resulting road length is longer than the actual length. Using this method for linear interpolation, we use MATLAB programming to discretize the roads in the entire area. The discretization results are shown in Figure 4. After discretization, we finally get 762 nodes, which is 455 nodes more than the original data. For the final node data, see "newpoint.txt" in the attachment.

Figure 4 Discretization result map of the entire area

After discretizing the road using this interpolation method, infinite points on the straight line are converted into finite points, which facilitates analysis of problems and implementation of corresponding Algorithm, as can be seen from Figure 4, the overall discrete effect achieved is quite ideal.

5.1.3 Algorithm design for solving the number of police cars in different areas

Considering that the police car configuration and patrol plan need to meet the following requirements: the police car can arrive at the scene of an ordinary crime within three minutes after receiving the alarm. The proportion is no less than 90%, and reaching key parts must be controlled within two minutes. The goal of the design algorithm is to find the minimum total number of police cars under the condition that D1 is satisfied, that is, each area covers as many road nodes as possible. Since the initial position of the police car is unknown, we can set the initial stopping point of the police car at any point on the road, that is, it is distributed at some of the 762 discrete points shown in Figure 4. The general idea is to let every two vehicles The cars are distributed as dispersedly as possible. One police car governs one area, and these areas are used to cover the entire area.

So we design Algorithm 1, the steps are as follows:

Step1: Pre-allocate the entire area into partitions, assign a police car to each partition, and set the initial parking position of the police car. On the road node in the center of the pre-allocated area, if the center of the area is not on the road node, the police car will be placed on the road node closest to the center;

Step2: For nodes that cannot be covered by the statistical partition, adjust the police car The initial stop point is to make the partition cover as many road nodes as possible. The adjustment is divided into intra-region adjustment and interval adjustment schemes: (1) Intra-region adjustment is a function constructed according to the idea of ??simulated annealing, and the position of the initial point of the vehicle is adjusted in the interval ( (Details will be explained later). When there are more nodes in the partition, the probability of adjustment is smaller. When there are fewer nodes in the partition, the probability of adjustment is larger. (2) When there are uncovered nodes or node groups in the area. (more than or equal to three nodes are concentrated in one range), adjust the initial position of the police car to move toward these uncovered nodes according to certain rules (described in detail in the algorithm description), and at the same time ensure that 3 Key parts can be reached 100% within 2 minutes;

Step3: Use Floyd algorithm to calculate the shortest distance from the initial stopping point of the police car to the surrounding road nodes;

Step4: Use individual The ratio of the total road length not covered by the divided area to the total road length in the entire area represents the probability that the police car cannot arrive at the scene within 3 minutes;

Step5: Simulate enough times, if, the number of vehicles Subtract 1 and jump to Step1;

Step6: After the calculation, compare the corresponding values ??at that time. When the minimum value is obtained, record the area division plan at this time, which is the minimum number of police cars.

Some explanations on the algorithm:

(1) The number of vehicles taken by this algorithm is calculated from most to least. The initial value is set to 20. The selection of this value Estimated based on area map.

(2) The advantage of pre-partitioning is that the initial positions of police cars are distributed as evenly as possible. The initial stopping points of police cars are found near the center point of a partition. Compared with randomly generating stops in the entire area, point, the computational efficiency is significantly improved.

After pre-allocation, the entire area needs to be continuously adjusted. When adjusting, the adjustment direction and adjustment probability need to be considered.

The police car adjustment is based on the simulated annealing algorithm. In order to make the probability of initial parking point adjustment smaller in the partitions containing a larger number of road nodes, and in the partitions containing a smaller number of road nodes, the probability of adjustment is smaller. The probability of adjustment of the initial parking point in the zone is higher, we constructed an adjustment probability function,

(1)

(1) In the formula, are all constants, and is the entire area The number of vehicles is the number of nodes covered in the first partition, and is the time. It can also represent the temperature change of simulated annealing: the initial temperature is higher, and the regional adjustment speed is faster. As time increases, the temperature continues to decrease, and the regional adjustment speed Gradually slowing down, this change in adjustment speed is more in line with the actual situation.

The adjustment probability function can be obtained from equation (1). Assume that under the same temperature (time) conditions, since the total number of vehicles is a constant value, at that time, the number of nodes in the partition is greater than When the number of nodes in the partition is greater, the probability of partition adjustment is greater, and the probability of partition adjustment is smaller. Analyze the reason: when the partition contains a large number of nodes, the initial parking position of the police car in the partition is more appropriate. When the number of road nodes in the partition is small, it means that the initial parking position of the police car is not A good choice requires a greater probability of adjustment, and this conclusion is relatively objective.

For all uncovered road nodes and many nodes outside the partition (called node groups), it is used to adjust the direction of the police car's location migration. The analysis diagram is shown in Figure 5. The goal of the adjustment plan is to keep the number of uncovered nodes as small as possible. When designing the adjustment direction function, it is necessary to consider: (1) the number of nodes within the node group; (2) the distance between the police car and the node group. Priority is given to distance, so in formula (2), the square of distance is used to describe the adjustment direction function.

Several factors such as the number of uncovered nodes in a certain area, the total number of uncovered nodes in the entire area, and the distance between the sub-region and the uncovered nodes or node groups will affect the adjustment. plan, so these factors must be considered comprehensively. So an interval adjustment function was designed.

In the formula, represents the number of uncovered nodes in the th partition, represents the distance between the th partition and the uncovered nodes or node groups, represents the number of uncovered nodes. The number of nodes and node groups.

Now we will briefly analyze the adjustment scheme of the interval adjustment function for the first partition. When the number of nodes in a certain two node groups is equal but the distance is unequal, for example, it can be seen from the interval adjustment formula that the interval is in the direction of the node group. Adjustment. When the distance between a certain partition and two node groups is equal, but the number of internal nodes of the node groups is not equal, such as , it can be seen from (4) that the sub-region will be adjusted in the direction of the node group.

Note that during the entire adjustment process, the adjustment probability controls whether to adjust, and the adjustment direction function controls the direction of adjustment, looking for the optimal result under this adjustment plan.

Figure 5 Schematic diagram of adjusting sub-regions

(3) In step 3, use the Floyd algorithm to calculate the shortest distance from the initial stopping point of the police car to the surrounding nodes. The purpose is that when there are When the situation occurs, the police car can arrive at the scene within the required time limit.

(4) In order to find a better police car stopping point, the simulated annealing algorithm is used to calculate the local optimal solution.

5.1.4 Police car configuration and patrol plan

Using MATLAB programming to implement Algorithm 1, it is obtained that the entire area is equipped with 13 police cars. When these police cars are stationary at the initial stop point, they can meet D1 Require. The initial parking positions of the police cars are road intersection nodes 6, 25, 30, 37, 82, 84, 110, 111, 126, 214, 253, 258, and 278. The intersection points (original intersection nodes) governed by each police car are shown in Figure 6, and the partition results are shown in the appendix.

Figure 6 Differentiation diagram that satisfies the D1 condition

13 partitions*** cover 252 intersection points, and the other 55 original intersection points are not covered by these sub-regions : 137, 138, 151, 159, 167, 168, 170, 174, 175, 186, 188, 189, 211, 215, 226, 242, 255, 260, 261, 262, 263, 267, 270, 271, 272 ,275,282,283,284,287,288,289,292,296,297,299,304,305,307. Under this partitioning scheme, among these points, the ratio of the discrete value length of the road between each two connected points to the total length of the entire area is . Therefore, 13 police cars are deployed in the entire area, and each police car remains stationary at the initial stopping point. When a case occurs, the police car closest to the crime scene rushes to the scene from the initial stopping point.

5.2 Indicators for evaluating the significant effectiveness of patrols

110 The purpose of police cars patrolling the streets is to deter illegal criminals, reduce the crime rate, and increase the safety of citizens. At the same time, it also speeds up the time for receiving the police (accepting the alarm and rushing to the scene to handle the incident), improves the response timeliness, and provides a strong guarantee for social harmony. Patrol officers perform patrol tasks in bustling urban streets and public places, maintain public order, and serve the masses, which can achieve good social effects [1].

In the entire area, since the crime scenes are all on the road, and every point on the road has an equal probability of happening, the wider the police car patrols, the more streets it patrols. The better the patrol effect, the more deterrent it will be to criminals, and the more timely police cars can handle cases.

We use comprehensiveness to measure the significance of patrol effects, that is, the ratio of the number of street nodes passed by police patrols to the total number of nodes in the area. When a police car repeatedly passes the same discrete point on the same street, it is recorded only once.

(3)

In the formula, represents the number of discrete points passed by the police car, and represents the total number of discrete points in the entire area. The larger the value, the more streets the police car passes through and the more significant the effect achieved.

At the same time, consider that during the patrol process, police cars may patrol some streets many times during the same period, while some streets are rarely patrolled or even no police cars arrive. This will cause Some patrol blind spots. The distribution is very uneven. In this way, it is possible that criminals on streets with high patrol density will not dare to commit crimes on the streets, and will move to streets with sparse patrol density to commit crimes. Therefore, under the same number of police cars, the patrol effect of unbalanced patrol density will be The effect is poor, and the patrol effect achieved by a patrol method with a more balanced density will be better. We introduce a patrol unevenness to measure the significance of the patrol effect. Considering that the variance can represent the degree of imbalance, we use the size of the variance to characterize the imbalance. The larger the variance, the more uneven the patrol density is. The obtained patrol The worse the effect.

(4)

The number of police cars that meet the D1 condition given in question 1 is 13. At this time, each police car is stationary at the initial stopping point, and only the jurisdiction When a crime occurs in the area, the police car rushes to the crime scene from the initial stopping point to handle the case. When the police car is on patrol, the issues that need to be considered are more complicated, such as whether the police car can still meet the requirements of D1 when the node is moving, what is the direction of the police car's movement, etc. However, the basic algorithm idea is similar to question 1. The result The block diagram of Algorithm 2 is shown in Figure 7.

In order to simplify the problem, we assume that when police cars in each district are patrolling, try to ensure that all police cars are traveling in the same direction, and the police cars all walk on two-way streets, that is When the police cars reach a certain node, they return to the initial stopping point at the same time. There are four ways for the police cars to travel, as shown in 6.

In Figure 6, the number 1 represents the first step of patrolling, and 2 represents patrolling in the opposite direction of 1's patrolling direction. When the specific program is implemented, the four patrol directions can be selected arbitrarily, but try to ensure that all police cars patrol in the same direction.

Figure 6 Patrol direction diagram of each police car

We used MATLAB programming to calculate this patrol method. The number of vehicles obtained was 18. The comprehensive evaluation index was, and the resulting patrol plan See "1193402-Result3.txt" in the attachment.

5.4 Discuss D3 conditions, police car patrol plans and evaluation indicators on the basis of satisfying question 3.

The concealment of patrol is reflected in the fact that there is no obvious pattern in the patrol routes and times of police cars. The main purpose is to prevent criminals from committing illegal and criminal activities during non-patrol hours and endangering people's lives and property.

In order to make the patrol pattern concealed, it is necessary for the police car to have at least two different routes during patrol, preferably at different times. Therefore, when considering concealment, it is only necessary to add a random process on the basis of question 2. Regarding its evaluation index, since the police car has several optional patrol routes, when the same route appears repeatedly at the same time, the set plan will be executed again. We use this time interval to measure the degree of concealment. , when the cycle period is larger, it means that there are more patrol plans available and the pattern is more concealed, while when the cycle period is smaller, it means that there are fewer patrol plans and the concealment is poor. In the patrol state, the worst covert patrol plan is that there is only one patrol plan and the time is fixed. Such a patrol plan has no concealment at all.

5.5 Patrol plan when the entire area is 10 vehicles

From the results of the third question, it can be seen that the number of 10 vehicles cannot completely cover the entire area. The algorithm is the same as Algorithm 2 is similar. The difference is that the number of vehicles has been fixed at this time. It is required to make D1 and D2 as large as possible. The evaluation index value we obtained is. The obtained patrol plan is shown in the attachment "1193402-Result5.txt" shown.

5.6 Patrol methods and evaluation index values ??when the average driving speed is increased

The analysis method and specific implementation of question six are consistent with question three, but the average speed of the police car after receiving the alarm From the original to , the coverage of each partition has also increased. The numerical value is brought into the algorithm of question 3 to solve. The calculated index value is. The patrol plan is shown in "1193402-Result6.txt" in the attachment. Show.

Figure 7 Algorithm 2 block diagram

Analysis and evaluation of six models

In solving the problem of how many police cars need to be equipped in the entire area under the condition that D1 is met, Using the idea of ????district patrols, we first analyze the rules that can maximize the jurisdiction of each district, and then analyze it from the special to the general level. The logic is strict and the results are reasonable.

When solving for the area and the number of police cars, on the basis of initially setting the location of the police car stopping point, the simulated annealing algorithm is used to construct a function to determine the probability of adjustment. After comprehensively considering the factors that affect the interval adjustment A function is constructed to determine the adjustment direction of the partition. When the partition is adjusted according to these two adjustment functions, each partition can govern as many road nodes as possible, and the effect achieved is relatively ideal.

References

[1] Discussion on police patrol service methods in small and medium-sized cities, Yu Xiang, Journal of Jiangsu Public Security College, Issue 1, 1998

[ 2]Matlab7.0 from beginner to proficient, Qiushi Technology, People's Posts and Telecommunications Press;

[3] Model and algorithm of random vehicle routing problem with uncertain number of vehicles, Yun Huali et al., Industrial Engineering, Volume 10, Issue 3, May 2005;

[4] Determination method of effective paths in random traffic allocation, Li Zhichun et al., Transportation System Engineering and Information, Volume 3, Issue 1, February 2003.