# The Optimal Dispatch of Traffic and Patrol Police Service Platforms

Authors: Ke Quan Zhao; Li Luo; Yuan Mei Xia
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

The main goal of this paper is to present a minmax programming model for the optimal dispatch of Traffic and Patrol Police Service Platforms with single traffic congestion. The objective is to minimize the longest time of the dispatch for Traffic and Patrol Police Service Platforms. Some numerical experiments are carried out, and the optimal project is given.


---

## Body

## 1. Introduction

Traffic and Patrol Police Service Platforms (in short, TPPSP) in the city have been playing an important role in dealing with emergency and traffic administration. The national college mathematical modeling contest of China in 2011 proposed the problem related to the optimal dispatch of TPPSP. However, only the case without any traffic congestion is considered for the problem. It is well known that the optimal dispatch and design of TPPSP is very complicated and it is affected by many real factors, such as(i)
the influence of traffic congestion on the optimal dispatch;(ii)
the influence of police resources allocation for each platform;(iii)
the influence of the uncertainty of road weights.The shortest path between any two nodes in urban traffic network is usually solved by Floyd shortest path algorithm in traffic computing and path search. Also the shortest path algorithms are widely applied to computer science, operational research, geographic information systems and traffic guidance, navigation systems, and so forth [1–5]. Especially, given a detailed GIS mapping and image display program, Liao and Zhong [4] proved that the Floyd shortest path algorithm can quickly and easily retrieve the shortest path between two locations, saving computing time and overhead.The minmax programming model has received more attentions in operations research and optimization fields in the literatures [6–9]. Averbakh and Berman [8] considered the location minmax p-TSP problem, where only optimal locations of the servers must be found, without the corresponding tours and without the optimal value of the objective function. Exact linear time algorithms for the cases p=2 and p=3 are presented.In recent years, the research on optimal dispatch of TPPSP has also received some attentions in the literatures [10–12]. However, we noted that these works only focused on the case without any traffic congestion for the optimal dispatch of TPPSP.In this paper, we first consider the optimal dispatch with single traffic congestion when the emergent event and establish a minmax programming model (model II) which objective is to minimize the longest time of the dispatch for TPPSP. Furthermore, some numerical experiments are carried out, and the optimal project is presented.


## 2. Notations

m: The number of the TPPSP
n: The number of intersections that should be blockaded
d
i
j
′: (i=1,2,…,m,j=1,2,…,n) The shortest distance from the ith TPPSP to the jth intersection without traffic congestion
t
i
j: (i=1,2,…,m,j=1,2,…,n) The shortest time from the ith TPPSP to the jth intersection
v: The speed of police vehicles
x
i
j: (i=1,2,…,m,j=1,2,…,n) The ith TPPSP is dispatched to the jth intersection or not.Assume that every TPPSP has almost the same police force, TPPSP have been settled at some traffic centers and key parts of an urban area of a city. The average of the police car is 60 km/h.


## 3. Mathematical Models

In this section, we first introduce a minimax programming model for the optimal dispatch of TPPSP without any traffic congestion in the literatures. Then, we present our main model for the optimal dispatch of TPPSP with single traffic congestion.


### 3.1. The Case without Any Traffic Congestion

When the road section has no traffic congestion, some authors presented the following minimax programming model, which is also a 0-1 integer programming model, see literatures [10, 12], and so forth.(model I)(3.1)minmax{tijxij}(3.2)s.t.∑i=1m‍xij=1,j=1,2,…,n;(3.3)∑j=1n‍xij≤1,i=1,2,…,m;(3.4)xij(1-xij)=0,i=1,2,…,m,j=1,2,…,n;(3.5)tij=100dij′60υ,i=1,2,…,m,j=1,2,…,n.The objective function (3.1) requires that the maximum time from the ith TPPSP to the jth node which is minimum. Besides, constraint (3.2) requires that every intersection should be blockaded by only one TPPSP. Constraint (3.3) ensures that one TPPSP can only blockade one intersection. Constraint (3.4) requires that xij is 0-1 variable. Constraint (3.5) shows that the relation between the time and the distance from the ith TPPSP to the jth intersection. Furthermore, in Constraint (3.5), the unite of tij is minutes, v is meters per second and the symbol dij′ (the unite is millimeters) is the distance of map, 100dij′ (the unite is meters) is the real distance.


### 3.2. The Case with Single Traffic Congestion

In the real life, traffic congestion may occur in urban traffic network. Therefore, the research on the optimal dispatch of TPPSP with Traffic congestions is important and meaningful. Considering that the emergency may occur at any time and place, and the road section may have some traffic congestions, in this subsection, we present one minmax programming model for the optimal dispatch of TPPSP with single traffic congestion. The optimal dispatch of TPPSP with Traffic congestions model is more effective than model I. Moreover, the optimal dispatch of TPPSP with Traffic congestions model's results has immediate practical applications.We assume that the traffic congestion occurs on the road section from the nodep to the node q, where the node p is adjacent to the node q. And Tpq denotes the average time of blocking. Besides, dij′′ denotes the shortest distance from the TPPSP i to the jth intersection without the road section from the node p to the node q, Pij denotes the shortest path from the ith TPPSP to the jth node. R denotes the set of Pij which go through p and q nodes. tij′(i=1,2,…,m,j=1,2,…,n) denotes the shortest time from the ith TPPSP to the jth intersection without traffic congestion, and tij′′ denotes the shortest time from the ith TPPSP to the jth intersection without the road section from the node p to the node q.We establish the following minmax programming model II for the dispatch of TPPSP with single traffic congestion:(model II)(3.6)minmax{tijxij},(3.7)s.t.∑i=1m‍xij=1,j=1,2,…,n;(3.8)∑j=1n‍xij≤1,i=1,2,…,m;(3.9)xij(1-xij)=0,i=1,2,…,m,j=1,2,…,n,
where
(3.10)tij={tij′,Pij∈A1;tij′′,Pij∈A2;tij′+Tpq-min{tip′,tiq′},Pij∈A3;tij′=100dij′60υi=1,2,…,m,j=1,2,…,n;tij′′=100dij′′60υi=1,2,…,m,j=1,2,…,n;A1={Pij∣Pij∉RorPij∈R,min{tip′,tiq′}≥Tpq};A2={Pij∣Pij∈R,min{tip′,tiq′}<Tpq,tij′+Tpq-min{tip′,tiq′}>tij′′};A3={Pij∣Pij∈R,min{tip′,tiq′}<Tpq,tij′+Tpq-min{tip′,tiq′}≤tij′′}.The objective function (3.6) requires that the maximum times from the ith TPPSP to the jth node which is minimum. The analysis of constraints (3.6)–(3.9) is the same as constraints (3.2)–(3.4). However, the value of tij is different from the time of the model I. In the model II, the function of tij is divided into three segments.


## 3.1. The Case without Any Traffic Congestion

When the road section has no traffic congestion, some authors presented the following minimax programming model, which is also a 0-1 integer programming model, see literatures [10, 12], and so forth.(model I)(3.1)minmax{tijxij}(3.2)s.t.∑i=1m‍xij=1,j=1,2,…,n;(3.3)∑j=1n‍xij≤1,i=1,2,…,m;(3.4)xij(1-xij)=0,i=1,2,…,m,j=1,2,…,n;(3.5)tij=100dij′60υ,i=1,2,…,m,j=1,2,…,n.The objective function (3.1) requires that the maximum time from the ith TPPSP to the jth node which is minimum. Besides, constraint (3.2) requires that every intersection should be blockaded by only one TPPSP. Constraint (3.3) ensures that one TPPSP can only blockade one intersection. Constraint (3.4) requires that xij is 0-1 variable. Constraint (3.5) shows that the relation between the time and the distance from the ith TPPSP to the jth intersection. Furthermore, in Constraint (3.5), the unite of tij is minutes, v is meters per second and the symbol dij′ (the unite is millimeters) is the distance of map, 100dij′ (the unite is meters) is the real distance.


## 3.2. The Case with Single Traffic Congestion

In the real life, traffic congestion may occur in urban traffic network. Therefore, the research on the optimal dispatch of TPPSP with Traffic congestions is important and meaningful. Considering that the emergency may occur at any time and place, and the road section may have some traffic congestions, in this subsection, we present one minmax programming model for the optimal dispatch of TPPSP with single traffic congestion. The optimal dispatch of TPPSP with Traffic congestions model is more effective than model I. Moreover, the optimal dispatch of TPPSP with Traffic congestions model's results has immediate practical applications.We assume that the traffic congestion occurs on the road section from the nodep to the node q, where the node p is adjacent to the node q. And Tpq denotes the average time of blocking. Besides, dij′′ denotes the shortest distance from the TPPSP i to the jth intersection without the road section from the node p to the node q, Pij denotes the shortest path from the ith TPPSP to the jth node. R denotes the set of Pij which go through p and q nodes. tij′(i=1,2,…,m,j=1,2,…,n) denotes the shortest time from the ith TPPSP to the jth intersection without traffic congestion, and tij′′ denotes the shortest time from the ith TPPSP to the jth intersection without the road section from the node p to the node q.We establish the following minmax programming model II for the dispatch of TPPSP with single traffic congestion:(model II)(3.6)minmax{tijxij},(3.7)s.t.∑i=1m‍xij=1,j=1,2,…,n;(3.8)∑j=1n‍xij≤1,i=1,2,…,m;(3.9)xij(1-xij)=0,i=1,2,…,m,j=1,2,…,n,
where
(3.10)tij={tij′,Pij∈A1;tij′′,Pij∈A2;tij′+Tpq-min{tip′,tiq′},Pij∈A3;tij′=100dij′60υi=1,2,…,m,j=1,2,…,n;tij′′=100dij′′60υi=1,2,…,m,j=1,2,…,n;A1={Pij∣Pij∉RorPij∈R,min{tip′,tiq′}≥Tpq};A2={Pij∣Pij∈R,min{tip′,tiq′}<Tpq,tij′+Tpq-min{tip′,tiq′}>tij′′};A3={Pij∣Pij∈R,min{tip′,tiq′}<Tpq,tij′+Tpq-min{tip′,tiq′}≤tij′′}.The objective function (3.6) requires that the maximum times from the ith TPPSP to the jth node which is minimum. The analysis of constraints (3.6)–(3.9) is the same as constraints (3.2)–(3.4). However, the value of tij is different from the time of the model I. In the model II, the function of tij is divided into three segments.


## 4. Numerical Experiments

In this paper, we takem=20, n=|I|=13, where
(4.1)I={12,14,16,21,22,23,24,28,29,30,38,48,62},
to do specific analysis for our model. The data is based on (http://www.mcm.edu.cn/). We use Floyd Shortest Path Algorithm to figure out dij′ and dij′′ by Matlab software. We can obtain the dispatch project of TPPSP without any traffic congestion when the emergent event happens in the city as Table 1.Table 1
The optimal dispatch project of TPPSP without any traffic congestion.
Dispatching project
Path of choosing project
Time from theith TPPSP to the jth intersection
1–38
1-69-70-2-40-39-38
5.880900
2–16
2-40-39-38-16
7.388100
4–48
4-57-58-59-51-50-5-47-48
7.395900
7–29
7-30-29
8.015500
9–30
9-34-33-32-7-30
3.492300
10–12
10-26-27-12
7.586600
11–22
11-22
3.269600
12–23
12-25-24-13-23
6.477000
13–24
13-24
2.385400
14–21
14-21
3.265000
15–28
15-28
4.751800
16–14
16-14
6.741700
20–62
20-85-62
6.448900Considering the case with single traffic congestion for the optimal dispatch of TPPSP in urban traffic network, we do the numerical experiments for the minmax programming model II by using Matlab software. Here, we takep=36, q=16, Tpq=5min. The dispatching project of TPPSP with one road section having single traffic congestion when the emergent event happens is shown in Table 2.Table 2
The optimal dispatch project of TPPSP withTpq = 5 min.
Dispatching project
Path of choosing project
Time from theith TPPSP to the jth intersection
1–38
1-69-70-2-40-39-38
5.880900
2–16
2-40-39-38-16
7.388100
4–48
4-57-58-59-51-50-5-47-48
7.395900
5–30
5-47-48-30
3.182900
7–29
7-30-29
8.015500
10–12
10-26-27-12
7.586600
11–24
11-25-24
3.805300
12–22
12-25-24-13-22
6.882500
13–23
13-23
0.500000
14–21
14-21
3.265000
15–28
15-28
4.751800
16–14
16-14
6.741700
18–62
18-80-79-19-77-76-64-63-4-62
6.734400From Tables1 and 2, we can clearly see that the maximum time of the optimal dispatch for TPPSP is the same for the case without any traffic congestion and the case with single traffic congestion in the given urban traffic network. However, the optimal dispatch project of TPPSP is different each other. Consequently, this shows that traffic congestion between the nodes in urban traffic network system will influence the optimal dispatch project of TPPSP in a certain degree when the emergent event happens.From Tables2, 3, 4, and 5, we can gain the different dispatch project when the time of a traffic congestions is different. We can know the traffic congestion can influence the dispatching project. The influence degree is different when the time of a traffic congestion is different. However, for the node p and node q, the maximum time from the TPPSP to the intersection is 8.015500 min when the time of a traffic congestion is different.Table 3
The optimal dispatch project of TPPSP withTpq = 10 min.
Dispatching project
Path of choosing project
Time from theith TPPSP to the jth intersection
1–38
1-69-70-2-40-39-38
5.880900
2–16
2-40-39-38-16
7.388100
5–62
5-50-51-59-58-57-60-62
5.255100
6–48
6-47-48
2.506400
7–29
7-30-29
8.015500
8–30
8-33-32-7-30
3.060800
10–12
10-26-27-12
7.586600
11–23
11-22-13-23
4.675100
12–22
12-25-24-13-22
6.882500
13–24
13-24
2.385400
14–21
14-21
3.265000
15–28
15-28
4.751800
16–14
16-14
6.741700Table 4
The optimal dispatch project of TPPSP withTpq = 30 min.
Dispatching project
Path of choosing project
Time from theith TPPSP to the jth intersection
1–62
1-75-76-64-63-4-62
4.885200
2–16
2-40-39-38-16
7.388100
6–30
6-47-48-30
3.213500
7–29
7-30-29
8.015500
8–48
8-47-48
3.099500
9–38
9-35-36-39-38
4.725700
10–22
10-26-11-22
7.707900
11–23
11-22-13-23
4.675100
12–12
12-12
0.000000
13–24
13-24
2.385400
14–21
14-21
3.265000
15–28
15-28
4.751800
16–14
16-14
6.741700Table 5
The optimal dispatch project of TPPSP withTpq = 60 min.
Dispatching project
Path of choosing project
Time from theith TPPSP to the jth intersection
2–16
2-40-39-38-16
7.388100
4–48
4-57-58-59-51-50-5-47-48
7.395900
7–29
7-30-29
8.015500
9–30
9-34-33-32-7-30
3.492300
10–22
10-26-11-22
7.707900
11–24
11-25-24
3.805300
12–23
12-25-24-13-23
6.477000
13–12
13-24-25-12
5.977000
14–21
14-21
3.265000
15–28
15-28
4.751800
16–14
16-14
6.741700
19–38
19-79-78-1-69-70-2-40-39-38
7.639300
20–62
20-85-62
6.448900In order to avoid the data that we use may be too special, we further takep=7, q=30. Still take m=20, n=13, and Tpq=5 or 10 or 30 or 60 min, respectively, the dispatching project about the TPPSP with one road section having a traffic congestion when the emergent event happens as Table 6, where M1 means blocking time, M2 means dispatching project, M3 means path of choosing project, and M4 means time from the ith TPPSP to the jth intersection.Table 6
The optimal dispatch project of TPPSP withTpq = 5,10,30,60 min.
M
1
5 min
10 min
30 min
60 min
M
2
1→38
1→38
1→38
3→48
4→48
5→48
2→16
7→28
5→16
7→28
4→48
8→30
6→62
9→14
7→28
10→24
7→28
10→12
9→14
11→21
9→14
11→21
10→22
12→21
10→22
12→22
11→12
13→22
11→23
13→24
12→24
14→23
12→24
14→23
13→23
15→29
13→12
15→29
14→21
16→14
14→21
16→30
15→29
17→16
15→29
17→16
16→30
19→38
16→30
20→62
20→62
20→62
M
3
1-69-70-2-40-39-38
1-69-70-2-40-39-38
1-69-70-2-40-39-38
3-55-54-53-49-5-47-48
4-57-58-59-51-50-5-47-48
5-47-48
2-40-39-38-16
7-15-28
5-47-8-9-35-36-16
7-15-28
4-57-58-59-51-50-5-47-48
8-47-48-30
6-59-58-57-60-62
9-35-36-16-14
7-15-28
10-26-11-25-24
7-15-28
10-26-27-12
9-35-36-16-14
11-22-21
9-35-36-16-14
11-22-21
10-26-11-22
12-12
10-26-11-22
12-25-24-13-22
11-25-12
13-22
11-22-13-23
13-24
12-25-24
14-21-22-13-23
12-25-24
14-21-22-13-23
13-23
15-28-29
13-24-25-12
15-28-29
14-21
16-14
14-21
16-36-35-9-8-47-48-30
15-28-29
17-40-39-38-16
15-28-29
17-40-39-38-16
16-36-35-9-8-47-48-30
19-79-78-1-69-70-2-40-39-38
16-36-37-7-30
20-85-62
20-85-62
20-85-62
M
4
5.880900
5.880900
5.880900
8.197900
7.395900
2.475800
7.388100
8.570200
6.228000
8.570200
7.395900
3.806600
5.337300
8.274200
8.570200
8.243600
8.570200
7.586600
8.274200
5.072300
8.274200
5.072300
7.707900
0.000000
7.707900
6.882500
3.791400
0.905540
4.675100
2.385400
3.591600
6.473300
3.591600
6.473300
0.500000
5.700500
5.977000
5.700500
3.265000
6.741700
3.265000
6.498900
5.700500
8.161600
5.700500
8.161600
6.498900
7.639300
5.583100
6.448900
6.448900
6.448900In Table6, where p=7, q=30, we can also gain the different dispatching project when the time of a traffic congestion is different. However, the maximum time from the TPPSP to the intersection is 8.570200 min when the time of a traffic congestion is different.Road section with having a traffic congestion is different, the maximum time from the TPPSP to the intersection is different. The influence degree of the time of a traffic congestion is not too large to the maximum time from the TPPSP to the intersection, but is large to the dispatching project.


## 5. Concluding Remarks

In this paper, we present a minmax programming models for the optimal dispatch of TPPSP with single traffic congestion. Some numerical experiments are carried out by using Matlab software and the optimal dispatch projects are given. However, in this paper, we only consider the case with single traffic congestion in model II. Hence, it is possible and meaningful to study the optimal dispatch project of TPPSP with several traffic congestions. This will be the future topics that we study.



---

*Source: 292415-2012-12-06.xml*