Location-allocation models for traffic police patrol vehicles on an interurban network

Abstract

This research investigates the traffic police routine patrol vehicle (RPV) assignment problem on an interurban road network through a series of integer linear programs. The traffic police RPV’s main task, like other emergency services, is to handle calls-for-service. Emergency services allocation models are generally based on the shortest path algorithm however, the traffic police RPV also handles other roles, namely patrolling to create a presence that acts as a deterrence, and issuing tickets to offenders. The RPVs need to be located dynamically on both hazardous sections and on roads with heavy traffic in order to increase their presence and conspicuousness, in an attempt to prevent or reduce traffic offences, road accidents and traffic congestion. Due to the importance of the traffic patrol vehicle’s location with regard to their additional roles, allocation of the RPVs adheres to an exogenous, legal, time-to-arrival constraint. We develop location-allocation models and apply them to a case study of the road network in northern Israel. The results of the four models are compared to each other and in relation to the current chosen locations. The multiple formulations provide alternatives that jointly account for road safety and policing objectives which aid decision-makers in the selection of their preferred RPV assignments. The results of the models present a location-allocation configuration per RPV per shift with full call-for-service coverage whilst maximizing police presence and conspicuousness as a proxy for road safety.

1 Introduction

Emergency services must provide reasonable service levels in order to ensure public safety and security as stipulated in the laws and practices of the relevant country. These emergency services are typically provided by vehicles based at fixed or dynamic locations, and the number and placement of vehicles generally influences the quality of services offered. Increasing the number of vehicles is often limited by capital and manpower constraints, and the efficient deployment of emergency service vehicles therefore becomes a crucial issue (Araz et al. 2007). The general aim of the emergency service vehicle location formulation is to determine the most appropriate base locations for vehicles in order to meet specific service level objectives. The routine patrol vehicle (RPV) assignment problem is different from that of other emergency services because of the multi-criteria nature of the issues involved. Traffic police fulfill two major functions: enforcing traffic laws and assisting road users. These are accomplished by maintaining presence and conspicuousness, issuing traffic violation tickets, handling vehicle accidents and other calls-for-services, directing traffic and accompanying special convoys. In general, interurban patrol vehicles are allocated to routine work and separately to special operations. The special operation vehicles are involved in both accompanying convoys and enforcing the traffic laws through a concentration of forces in a specific area or time or concentrating on specific offences, whilst the routine patrols perform all other tasks. In this research, we focus on the RPVs assignment problem because this topic has not been covered in the academic literature to date (Elvik and Vaa 2004; Hakkert et al. 2001). According to a pre-planned timetable, each vehicle is located to an enforcement-stretch where it is stationed for the length of a shift and enforces the law by issuing traffic tickets as well as showing a presence. Each patrol vehicle is also allocated an extended area of responsibility defined as an operating area. When a call-for-service is received, the control room dispatches an appropriate vehicle. The total time span for a call-for-service includes the time taken to drive to the call from the enforcement-stretch, the time spent dealing with the problem and the time required to return to the original location. In general, a protocol (legal requirement) specifies the maximum time permitted to reach an event location.

The location-allocation planning models for the interurban traffic police RPVs developed in this research are based on the existing working policy of the Israeli Police Force. The models are based on the decision makers’ preference for dividing the budget among automatic enforcement, concentrated force, and RPVs. We focus on the interurban traffic police because it is organized as a single unit and 40 % of severe accidents in Israel occur on the interurban road network. Note that for interurban roads, traffic data is available which supports the rational allocation of enforcement effort. The objectives considered in the models include the optimization of the benefits (presence and conspicuousness) based on the traffic police vehicles’ locations, and the allocation of vehicles based on legal and other stipulations. The models determine the optimal, temporary, base locations for a limited number of vehicles in such a way that service-level objectives are achieved under the constraint of complete network coverage. We develop integer linear programs and apply them to a case study of the northern part of Israel’s interurban roads. We demonstrate the applicability of the results of the models in comparison to the currently chosen locations.

Four models were developed in this study, progressing from the basic model addressing maximized presence and conspicuousness based on traffic flow, to gradually handling additional objectives and constraints. The second formulation addresses the location and distribution of the likelihood of calls-for-service. The third formulation changes the coverage requirements such that pre-determined sections of roads may be served more quickly than others in order to better deal with the problems of congestion and their effect on subsequent accidents. The fourth formulation maximizes presence and conspicuousness dynamically over varying locations, accounting for multiple shifts and considering the halo effects identified in the literature (Elvik and Vaa 2004; Newsread et al. 2001).

This is the first study that plans the locations of traffic police RPVs so as to maximize their availability for handling road events and concurrently enforce road regulations. Police force planning has been analyzed as a maximum covering location problem (MCLP) (Church and Revelle 1974; Curtin et al. 2005, 2010), balancing deployment over beats in an urban area (Chaiken and Dormont 1978a, 1978b; Church et al. 2001; Green and Kolesar 1989, 2004; Larson 1974; Sacks 2000; Simpson and Hancock 2009) or serving a rural region, where travel time is a major component of the total service time (Birge and Pollock 1989). While the literature has focused on rescue services, there has been no discussion on the joint role of traffic police as a rescue service that also combines their effectiveness in reducing road accidents. For example, rescue service location has a specific, clearly defined objective function, namely to cover a given network within the budget limitations. In the case of RPVs, network coverage is a legal constraint and the objective function is better defined in terms of the need for a dynamic presence and conspicuousness. The interurban traffic RPVs location-allocation problem is different in some aspects from the other emergency services described in the literature. First, there are more than the minimum number of vehicles required to cover demand therefore coverage of the network becomes a constraint and the objectives are derived from the public benefit of safety and security in the form of multi-objective functions. Second, the interurban traffic police differs from the urban patrol police because the RPVs’ locations ought to change dynamically to obtain a “halo effect” for improved deterrence, whereas the patrol beat in urban areas is mostly fixed. Workload balancing across patrol vehicles is less important for the RPVs because the workload (handling calls-for-service and issuing traffic tickets) is generally a small proportion of the RPVs’ tasks. The RPVs should be located on road accident and traffic offence “blackspots” to reduce the number and severity of accidents through deterrence and enforcement.

We have thus developed a set of models that combines an incident-response dispatch system from depots, similar to that of ambulances, together with location choices over a road network in order to detect and prevent offenses and respond to incidents in a timely fashion when necessary. The new formulations combine two domains: traffic enforcement and operational research. The mathematical formulations are based on theories of hazardous road identification (Elvik 1997; Hauer 2005) and the halo effect of enforcement (Elvik and Vaa 2004; Newstead et al. 2001). The allocation solution covering calls-for-service thus not only considers the closest RPV, as in other rescue services, but also a behavioral cost-benefit evaluation.

The paper is organized as follows. Section 2 is devoted to a literature review and a discussion of existing models published in the literature. Section 3 describes the methodology and the formulation of the proposed models we implemented. Section 4 describes the case study with the current locations chosen by the existing police traffic model and the solutions from the four proposed models. The computational results of the proposed models with respect to the case study demonstrate the effectiveness of the solution. The final section presents conclusions and suggestions for future research.

2 Literature review

In this section we discuss the modeling approaches developed in the literature with regard to location and allocation problems, as well as the literature on traffic law enforcement.

2.1 Location literature

Optimal location-allocation is important in both the private sector (location of plants, warehouses, stores, allocation of customers, etc.), and the public sector (location of schools, waste sites, allocation of students, housing etc.). Typically, the private sector deals with cost-benefit objectives, whereas in the public sector the objective is the social benefit that must be defined by each public sector according to its goals (Daskin 1995; ReVelle and Eiselt 2005).

Within the location-allocation literature, there is a special focus on the location of stations and emergency services vehicles (Church et al. 2001; Curtin et al. 2005, 2010; Daskin 1982; Green and Kolesar 2004; Larson 1974; Larson and McKnew 1982; Peleg 2000; Toregas et al. 1971; Simpson and Hancock 2009; Wright et al. 2006). The first major research project involving fire department deployment was the New York City Rand Project in the 1970s (Walker et al. 1979). Most of the research carried out on police force resource allocation applies to urban public safety, where the solution generates an optimal beat balanced workload. Allocations are seldom changed unless new stations are added, moved or closed (Curtin et al. 2005; Larson 1974; Ma 2003). Recent work by Yin (2006) discusses freeway service patrol (FSP) location on pre-designed beats for faster response and the reduction of the impact of traffic incidents. The number and location of the FSP is defined in terms of the economic value of delay, fuel savings and improved road safety. It should be noted that FSP systems operate differently to incident-response dispatch systems, since the former spontaneously detect, respond to and clear incidents, whereas the latter locate trucks at specific depots whilst waiting for dispatch commands. In the RPV location-allocation problem, the objectives and constraints are different, as described in the methodology section (Sect. 3).

In many emergency facility location problems, the objective is to “cover” demand within a pre-defined timeframe (Berman et al. 2010; ReVelle and Eiselt 2005). A number of strategic location models have been developed in the literature (see Owen and Daskin 1998 for a survey). The coverage formulations deal mainly with two types of problems: the set-covering model and the maximum covering location model. The set-covering problem (SCP), originally proposed in this context by Toregas et al. (1971), evaluates the minimum number of facility sites needed to cover all demand within a pre-specified time limit. The mathematical formulation of this problem is:

Notations

I :

set of demand sites

J :

set of potential facility sites

i :

index of demand sites i∈I

j :

index of potential facility site j∈J

c _j :

fixed cost of locating a facility at node j

d _ij :

the distance between node i and j

S :

maximum acceptable service distance

N _i :

set of facility sites j within acceptable distance of node i, i.e. N _i ={j∈J|dij≤S}

Decision variables

The set-covering problem is represented by the following integer program:

$$\everymath{\displaystyle} \begin{array}{l@{\quad }l} \mbox{Minimize}& \sum_{j \in J} c_{j}x_{j}\\ \mbox{subject to} & \sum_{j \in N_{i}} x_{j} \ge 1\quad \forall i \in I \\ & x_{j} \in \{ 0,1\} \quad \forall j \in J \end{array} $$

The objective function minimizes the cost of facility location. In many cases, the costs c _j are assumed to be equal for all potential facility sites j, implying an objective equivalent to minimizing the number of facilities located. The constraints require that all demand nodes i have at least one facility located within an acceptable service distance. Distances in network location problems are measured on the network itself, typically as the shortest route on the network of arcs connecting two points. Although the SCP is an NP-hard problem, some instances of large network-based location set-covering problems have been solved relatively easily, achieving integer solutions when combining linear formulations with solution-derived cutting plane constraints (ReVelle and Eiselt 2005). Toregas and ReVelle (1973) describe logical constraints that significantly reduce the problem size. For the majority of problems, several repetitions of the reduction rules applying the principles of row and column dominance rapidly reduce the size of the facility location problem. When the sequence of rules fails to reduce the size of the problem such that an integer solution is found in reasonable time, the remaining matrix is termed cyclic and an integer solution may be found either with additional constraints or by applying the branch and bound algorithm.

The maximum covering location problem (MCLP), originally formulated by Church and Revelle (1974), locates a fixed number of facilities (P) such that the number of demand nodes that can be covered in a pre-specified time limit are maximized. For example, the legal standard may be defined as the requirement to respond to 90 % of emergency medical service calls within 8 minutes (Church et al. 2001). The formulation of this problem is:

Additional notation

P :

fixed number of facilities

h _i :

positive weight on the demand node (e.g. importance, profit, traffic flow etc.)

Additional decision variables

$$\everymath{\displaystyle} \begin{array}{l@{\quad }l} \mbox{Maximize}& \sum_{i \in I} h_{i}z_{i} \\ \mbox{subject to}& \sum_{j \in N_{i}} x_{j} \ge z_{i}\quad \forall i \in I \\ & \sum_{j \in J} x_{j} \le P \\ & x_{j} \in \{ 0,1\} \quad \forall j \in J \\ & z_{i} \in \{ 0,1\} \quad \forall i \in I \end{array} $$

In the basic MCLP formulation the objective function maximizes demand covered according to weight h _i . The first constraints determine which demand nodes are covered within the acceptable service distance by node j. Each node i can only be considered covered (with z _i =1) if there is at least one facility located at some site j which is within S of node i (i.e. x _j =1 for some j∈N _i ). In order to account for limited resources, the second constraint limits the solution to at most P facilities. The last two sets of constraints limit the decision variables to integral values. Although the MCLP is an NP-hard problem, some large-dimension instances have been solved using commercial IP-solvers (Berman et al. 2010).

In the case of multiple optimal solutions, alternative solutions can be found using an additional constraint:

$$\sum_{j \in M} x_{j} - \sum_{j \in N} x_{j} \le| M | - 1,\quad M = \{ j| x_{j} = 1 \},\ N = \{ j| x_{j} = 0 \}. $$

This constraint, used interactively, enables the development of a dynamic formulation for the integer linear program, consisting solely of binary variables (Tsai et al. 2008; Balas and Jeroslow 1972). According to this constraint, only M−1 locations from the first iteration may be included in the solution to the subsequent iteration, consequently permitting a continued search (M and N represent subsets of facility sites for set j).

Location problems are likely to have other operational objectives such as location-routing (ReVelle and Eiselt 2005), location-scheduling (Church 2001), location-inventory (Daskin 2002) or location and backup (Curtin et al. 2010). These problems are solved in stages or by combining objective functions within the linear programming formulation using mathematical approaches such as goal programming which require the decision makers to set goals for each objective. The objective function minimizes the deviations from each goal, subject to the goal constraints and the system constraints (Araz et al. 2007).

To overcome the relatively large amount of input data, aggregation methods have been applied. Aggregation often decreases data collection, modeling and computing costs, confidentiality concerns and statistical uncertainty but increases the issue of errors (Francis et al. 2005; Plastria and Vanhaverbeke 2007). In our research, both aggregated and more detailed data were applied, enabling a comparison of their impact on the results.

2.2 Traffic law enforcement literature

In the accident prevention literature it is argued that police enforcement is an important road safety factor in reducing accidents and deterring driving offences (Bester 2001; Chang and Chen 2005; Christensen and Elvik 2007; Elvik and Vaa 2004). The main objective of traffic law enforcement is to increase road safety, achieved mainly by deterring road users from committing offences proven to be related to road accidents and injuries (ETSC 1999). However, it is very difficult to measure road safety levels (Bester 2001). Beenstock and Gafni (2000), for example, found that the accident rate varies inversely with road quality and police enforcement and directly with the proportion of old vehicles on the road. Hakkert et al. (2001) hypothesized that increased police activity leads to increased enforcement on the roads, which implies a growth in the real risk of being detected when violating traffic rules that, together with the accompanying publicity, raises a driver’s perceived subjective probability of being apprehended. The subjective probability of apprehension, together with the expected punishment for violators meted out by the judicial process, constitute the deterrent effect. Ultimately, deterrence and detection, in combination with proper education and training, may cause positive changes in driving norms and tangible traffic behavior, which will manifest themselves in a reduction in the number and severity of accidents. The major factors influencing the optimal level of enforcement are the costs of apprehending and convicting traffic offenders, the nature of the punishment, e.g. fines, license revocation or prison terms, and traffic offenders’ responses to changes in enforcement (Becker 1968).

The OECD (1974) defined traffic law enforcement as “the area of activity aimed at controlling road user behavior by preventative, persuasive and punitive measures in order to encourage the safe and efficient movement of traffic”. Police work encompasses two aspects: prevention and enforcement. Prevention aims at increasing drivers’ perceptions of the probability of detection through a lack of predictability in terms of time and space (ETSC 1999; Fell et al. 2003). The enforcement aspect, namely the repression approach, involves targeting times and places where the largest number of offenders is anticipated. Rather than attempting to affect the subjective chance of being caught, this approach seeks to increase the objective likelihood of being caught (Vanlaar 2008). Elvik and Vaa (2004) summarized over 100 papers and found relationships between different types of enforcement and the time and distance halo effects of offences. A time halo effect of anything between 2 days up to 10 weeks was found between the enforcement and some effect on behavior. The distance halo effect varies between 1 km and 22 km (Newsread et al. 2001). Typical values of the distance halo effect lie in the region of 1.6 to 3.5 km downstream from the enforcement site and 0.5 km upstream (ETSC 1999). The results vary depending on the type of speeding enforcement (patrol or camera), police car (marked or unmarked), working method (stationary or mobile) and location (covert or open). It is highly unlikely that the police would ever be able to detect every delinquent driver on the road. It is therefore important for enforcement strategies to increase the perceived risk of being caught in order to deter dangerous driving (Fell et al. 2003). Enforcement programs in Australia and New Zealand, for example, have demonstrated a substantial reduction in road accident rates as a result of random police deployment (Newstead et al. 2001). It is generally agreed that good enforcement practices should be based on accident analysis and on scientifically supported insight into enforcement effectiveness (Hakkert et al. 2001). It is also important to analyze the effectiveness and efficiency of the police officers’ work (Hurley et al. 2009; Tillyer et al. 2010).

In this study we develop four formulations that produce differing locations and allocations for RPVs in order to maximize effectiveness with regard to the measured time and distance halo effects. The models developed in this research are different to those published in the emergency services operations research literature because the benefits derived from the location choice were previously ignored. The law enforcement literature, on the other hand, has focused their attention only on the RPV locations thus ignoring the covering problem. Consequently, this research combines the two areas in order to produce a complete schedule that accounts for all RPV functional tasks.

3 Methodology

The RPV location-allocation problem is derived from the emergency, road safety and public security disciplines. The RPVs are located on an interurban road network, which is represented as an undirected graph, G=(V,E). The network comprises a set V of vertices representing road intersections together with a set E of edges representing roads that connect the intersections. Each RPV is located on an enforcement-stretch, which is a section of road. The RPV graph is defined as G′=(V′,E′) where the set V′ of vertices represents potential enforcement-stretches, and the set E′ of edges represents the shortest distances between the enforcement-stretches.

The RPVs are located dynamically in order to maximize presence and conspicuousness while the allocation is defined as a covering problem, considering legally set upper bound service times. The RPVs location problem uses a fixed number of RPVs derived from a budget constraint. Solving the SCP problem for the case study of Northern Israel identified the minimum number of vehicles required for full network coverage. Since the resources were greater than the lower bound required, we could add further constraints to model the traffic police operational procedures. First we develop a location-allocation formulation to distinguish the operating area for each RPV. The objective function (1) maximizes police conspicuousness measured in terms of traffic volume (number of vehicles per time period) per location. Hence the size of the operating areas was chosen in order to maximize the conspicuousness of the RPV locations rather than minimize the shortest route to the likely calls-for-service.

Model 1: Conspicuous-coverage trade-off model

Notation

I :

set of “enforcement-stretches” on network

i,j :

indices representing enforcement-stretches where i,j∈I

P :

number of Routine Police Vehicles

Data

d _ij :

shortest distance between enforcement-stretch i and j

D :

maximum acceptable service distance

N _i :

set of enforcement-stretches j within acceptable distance of enforcement-stretch i, i.e. N _i ={j∈I|d _ij ≤D}

U _j :

number of vehicles per hour passing an RPV on enforcement-stretch j

Decision variables

$$ \mbox{Maximize}\quad \sum_{j \in I} U_{j}x_{j} (1) $$

(1)

(1a)

(1b)

(1c)

(1d)

(1e)

Constraint (1a) requires the solution to locate exactly P RPVs. Constraints (1b) require that each enforcement-stretch i is covered by exactly one RPV located from enforcement-stretch j, thus allocating the operating areas with respect to calls-for-service. Although the solution delineates the operating areas for each RPV, a back-up scenario for each potential enforcement-stretch can be calculated for a second RPV according to the shortest covering distance. This constraint implicitly assumes that there are sufficient RPVs to cover all potential enforcement-stretches otherwise alternative constraints should be formulated to obtain the maximum coverage available. Constraints (1c) require that potential enforcement-stretch i may only be covered by an RPV at location j if an RPV has been located at enforcement-stretch j.

Model 1 is an extension of the SCP problem with an additional constraint on the number of RPVs. Therefore it could be formulated with a single set of one dimensional decision variables. However, we decided to add a set of allocation variables z _ij in order to facilitate more complex constraints on the allocation in the extensions presented below.

Model 2: Maximum conspicuousness accounting for calls-for-service model

Additional notation

H :

shift in hours

Additional data

t _ij :

travel times between i and j and back (in hours)

E _i :

time handling events on node i in a shift (in hours)

$$ \max\sum_{j \in I} \biggl( HU_{j}x_{j} - \sum_{i \in I} (t_{ij} + E_{i})U_{j}z_{ij}\biggr) $$

(2)

subject to constraints (1a) to (1e).

The objective function maximizes the number of passing vehicles encountered by the RPVs in the allotted enforcement-stretches. Note that the first term in the summation represents the total number of drivers that encounter the RPVs were the vehicles to remain on their enforcement stretches throughout the shift. The second term detracts the number of passing vehicles that are missed because the RPVs need to leave the enforcement-stretch in order to handle incidents within their allocated areas.

In the third model (Model 3: Maximize conspicuousness with varying time coverage) we set a priority for each section on the network. Events cause congestion, delays and accidents on the roads. The impact of events on a particular section of road is a function of specific parameters, for example, a road with a relatively low capacity but high traffic flow will be more affected by a traffic event for a longer period of time than a relatively minor road. The assumption is that shortening the response time of the police vehicle on problematic roads dissipates potential congestion more quickly. The implementation of this priority was translated into varying the required response time according to road type. For the third model we define D _i as the maximal acceptable distance of an RPV from stretch i and redefine N _i as N _i ={j∈I|d _ij ≤D _i }.

The fourth model diversifies the location of the RPVs over a period of time in order to maximize utility. As specified in the literature, there is a halo effect of a few days during which drivers recall the location of the RPV and accordingly slow down (Newsread et al. 2001; Elvik and Vaa 2004). Developing solutions with multiple, changing locations will add to the likelihood that drivers pass an RPV on their route, thus increasing their awareness and potentially their behavior. For safety reasons, certain locations may be important RPV locations, due to specific problems such as failed traffic lights, obstacles, or roadwork. Furthermore, for economic and road safety reasons, a specific location may prove consistently more important, e.g. to clear an event from the road immediately after it occurs because congestion may prove problematic leading to a chain reaction of accidents. The utility of a specific location may be based on different functions e.g. traffic volume, number and likelihood of offences and type of road or drivers.

Formulation (4) draws on the objective function of Model 2 (maximum utility accounting for calls-for-service) and the constraints from Model 3 (conspicuous-coverage trade-off). In addition, we define a strong constraint that each location, once chosen, may not be chosen in any other shift (constraint (4d)). All other constraints and the objective function remain as before, except for the addition of an index, f, representing the different shifts.

Model 4: Multiple shift model

Additional notation

F :

number of scheduled shifts

f :

index representing shift where f∈F

Decision variables

(4)

(4a)

(4b)

(4c)

(4d)

(4e)

(4f)

We note that the various versions of RPV location-allocation problems are strongly NP-Hard and demonstrate this by proving the hardness of Model 1 by reduction from the vertex cover problem (Garey and Johnson 1979).

Proposition

The RPV location-allocation problem defined by Model 1 is strongly NP-Hard.

Proof

We carry out the proof by a reduction from the vertex-cover decision problem that is known to be NP-Complete. The vertex-cover problem is defined as follows: given an undirected graph G=(V,E) decide whether a subset C⊂V with cardinality k that includes at least one end vertex of each edge e⊂E exists. Given an instance of vertex cover, we construct the RPV location/allocation problem with the same node (vertex) set, V, and define N _i ={j:{i,j}∈E}, U _i =1 for all i∈V and P=k. Model 1 admits a feasible solution if and only if a vertex cover with k vertices exists. To see this consider a feasible solution of model 1, then a vertex cover of cardinality k is obtained by C={j:x _j =1}. The cardinality of this set is P=k by constraint (1a) and every vertex j is covered because by constraint (1b) there is one pair (i,j) such that z _ij =1 and hence by constraint (1c) there must be a vertex i adjacent to j that is included in C. Conversely, the existence of a cover C of cardinality k for G implies the existence of a feasible solution of Model 1, with x _i =1 if i∈C and z _ij =1 if i∈C and j∈N _i . In case the former holds for more than one vertex j, the variable i with minimal index in C is selected. The rest of the decision variables are set to zero. This shows that the problem is strongly NP-Hard since the numerical values of all the parameters in the reduced problem are small relative to the input size of the vertex cover problem (U _i =1 and P=k≤|V|). □

We note that other variants of the RPV location/allocation can be shown to be NP-Hard by similar arguments. Although our problems proved to be strongly NP-Hard, fairly large instances can be solved to optimality with a commercial mixed integer solver due to the special structure of the model. Indeed, once the values of x variables are selected, the remaining variables and constraints in all four models form a Totally Unimodular Matrix (TUM). Therefore, the dimension of these integer programs in terms of integer co-ordinates is much smaller than initially appears. We demonstrate this claim for Model 1 and Model 2 (that share the same constraints) and note that the proofs for Model 3 and 4 are very similar.

Proposition

The coefficient matrix of Model 1 and Model 2 with the values of the x variables fixed is totally unimodular.

Proof

First note that constraint (1a) contains only x variables hence vanishes once the values of these variables are fixed. Each column of the remaining matrix is indexed by an (i,j) pair, for each variable z _ij =1. The number of “1” coefficients in each column is exactly two while the rest are zeros. To see this note that each variable z _ij appears once in the constraint set (1b) and one in the set (1c). Therefore, the coefficient matrix is TUM. □

Recall that a TUM is a matrix for which every square sub matrix admits a determinant of −1, 1 or 0. Any feasible basic solution of a linear program whose constraints are defined by a TUM, is an integer. This follows directly from a classical result in linear algebra, namely Cramer’s rule. As a result, an integer linear program defined by a TUM can be solved in polynomial time by any polynomial time algorithm for linear programming (Schrijver 1998). In our case, a subset of the column of the coefficient matrices forms a TUM. Integer programming solvers, such as ILOG’s CPLEX, identify and exploit this structure by branching first on decision variables that correspond to the columns that do not belong to the TUM. Once the integer values of these variables are set, the remaining linear programming relaxations at the nodes are tight which reduces the depth of the branch and bound tree and the time required to solve the model.

These four models were applied to a case study of the Northern Israel interurban road network which is discussed in Sect. 4.

4 Case study: Northern Israel interurban road network

The interurban road network in Northern Israel can be defined as a sparse graph with 49 intersections (V=49) and 73 road sections (E=73) covering approximately 600 km of roads. The roads that connect the intersections were divided into 222 sections. Each section (generally about 2.5 km long) is an enforcement-stretch (Fig. 1). In addition, V′=222 and E′=243. For undirected simple graphs, the graph density is defined as: $A = \frac{2|E |}{| V |(| V | - 1)}$. The maximum number of edges is $\frac{1}{2}|V| (|V|-1)$, so the maximal density is 1 (for complete graphs) and the minimal density is 0 (Coleman and Moré 1983). In our case study, in the original network A=0.062 and in the digitized network A=0.001, therefore it is a sparse network.

Fig. 1

The interurban road network of Northern Israel with 222 digitized nodes

Alternative types of digitization could be applied and this form was chosen so that each node would be sufficiently long to allow the RPV to find an appropriate parking place but not too long such that the allocation area is inaccurate. Figure 2 highlights the major and minor roads. Location on major roads is likely to provide greater benefits from the RPVs because the traffic volume is generally higher, so presence and conspicuousness will be greater.

Fig. 2

The interurban road network of Northern Israel showing road type designation

In Sect. 4.1 we describe the current operation and its failure to fully cover the network. In Sect. 4.2 we present and discuss the solutions to the four routine patrol vehicle location-allocation models developed in Sect. 3 using the case study data.

4.1 Case study: current operations

In Israel, patrol vehicles are assigned to enforcement-stretches according to a “traffic model”. The assumptions of the model are that presence and conspicuousness ought to be greater where traffic volume and car accidents occur more frequently, acting as a deterrent and reducing the likelihood of traffic offences, in turn leading to a reduction in the number of car accidents and their severity. Furthermore, the presence of police on the roads with statistically the most accidents reduces the time of arrival of the police car to these kinds of calls-for-service. Therefore, the model weights the enforcement-stretches based on historical data including the number and severity of accidents and the traffic volume. The output of the traffic model is a ranked list of enforcement-stretches (Hakkert et al. 1990).

The current police protocol calls for a maximum arrival time of 20 minutes after a call-for-service has been received. This is translated into 27 km (driving at a speed of 80 km/h on average) for the cover constraint. The six cars in Fig. 3 present the enforcement-stretches (nodes on the network) where the traffic police are currently located. The pale sections represent roads covered according to the police protocol, whereas the bold sections are currently not covered. As highlighted in Fig. 3, the six RPVs are located on major arteries covering the majority of the traffic volume, car accidents and other events (roads 90, 85, 65). The coverage percentage today is 80 % because the eastern part of the network is not accessible within the pre-specified legal time limit. Currently, the value of the traffic volume is 5,648 representing the number of vehicles that drive past the six RPVs in an 8-hour shift, given the chosen locations and ignoring the lost time during which the RPVs leave their location to handle traffic events within their allocated area. This represents 85 % of the maximum traffic volume value that can be achieved with six RPVs on this road network, considering traffic volume data alone. If we deduct the lost time based on historical data, during which the RPVs are busy responding to calls-for-service, the objective function value drops to 5,356 which corresponds to 81 % of the maximum attainable.

Fig. 3

Current police patrol vehicle location-allocation solution

4.2 The routine patrol vehicle location-allocation models

In this case study we applied the maximum covering location problem (MCLP) and set-covering problem (SCP) defined in the literature survey. Then we solved the four models described in Sect. 3, namely (1) the conspicuous-coverage trade-off model, (2) the maximum conspicuousness accounting for calls-for-service, (3) the maximizing conspicuousness with varying time coverage and (4) the multiple shift model.

4.2.1 The maximum covering location problem and set-covering problem

The maximum covering location problem (MCLP) was applied to our case study with six RPV’s using CPLEX 7.0. A pre-processing stage was undertaken to compute the parameters of the model. The shortest-path Dijkstra algorithm (Dijkstra 1959) computed N _i , the set of nodes within acceptable distance of node i, for all 222 nodes. The result of the MCLP achieved 100 % coverage, suggesting that fewer RPVs could be used to ensure complete coverage within the legal limits. Application of the set-covering problem (SCP) showed that four RPV’s were sufficient to cover the network in this case study. The SCP and MCLP solutions for P=4 RPVs provided several optimal solutions. The SCP solution located four RPVs on nodes 41, 70, 187 and 195, denoted as triangles in Fig. 4, of which three of the locations correspond to main roads. The MCLP solution covered four different nodes (36, 60, 141 and 200) denoted as octagons in Fig. 4 in which two of the nodes cover main roads. Comparing the police force’s current choices with those of the models (Figs. 3 and 4), it is clear that two RPVs are located to the west of the region and two are located to the east in order to ensure coverage that is not currently achieved. Since the two modeling approaches, SCP and MCLP, arrived at different solutions, we applied the additional constraints described in Sect. 2.1 interactively with P=4 and identified 19 potential solutions. Utilizing these solutions by adjusting locations on a regular basis may be useful in light of the halo effect identified in the literature.

Fig. 4

The set-covering problem and the maximum covering location problem solutions (with four routine patrol vehicles)

The SCP and MCLP models do not differentiate between types of road, traffic volume, calls-for-service etc. (c _j =h _i =1 respectively). Given that four RPVs could cover the network and that the police currently possess six RPVs in the region of the case study, it may be possible to increase police presence in an attempt to affect driving behavior and ultimately reduce the number of road accidents and offences. All the models were formulated as integer linear programs and were solved using CPLEX Version 7. The conspicuous-coverage trade-off model (Model 1) was applied using traffic volume data as a proxy to maximize police conspicuousness. The maximum conspicuousness accounting for calls-for-service (Model 2) expanded the first model by taking into consideration the total time required to handle calls-for-service based on historical data. The maximizing conspicuousness with varying time coverage (Model 3) differentiates between enforcement-stretches (nodes on the network) such that higher priority roads receive shorter response times. The multiple shift model (Model 4) scheduled RPVs over the planning horizon such that the halo effect is taken into account.

4.2.2 Model 1: The conspicuous-coverage trade-off model

In Model 1 the objective function maximizes police conspicuousness as a function of traffic volume on each node (the data of average annual daily traffic was collected by the Israeli Central Bureau of Statistics 2006). We use average flow data although flow is often peaked, which should be considered once data is available. The assumption is that traffic volume is a reasonable proxy for presence and conspicuousness of the RPV.

In this case study there are 14,310 z _ij allocation variables and 222 x _j location variables, leading to a total of 14,532 binary decision variables. The solution to this model locates five RPVs on main roads covering the major traffic volumes (nodes: 91, 120, 172, 194, 202, roads: 89, 90 and 98) and the last RPV is located on a minor road (node 24, road 989), mostly for purposes of coverage (represented by octagons on Fig. 5). Again, there are multiple optimal solutions over locations depending on the quality and precision of the traffic volume data. If traffic volumes are ignored i.e. U _j =1, the locations of RPVs are much more spread out and only one high traffic volume node is directly covered (nodes: 22, 86, 121, 123, 165 and 215 represented as triangles on Fig. 5).

Fig. 5

The solution maximizing presence given six routine patrol vehicles

Comparing the current police solution (Fig. 3) and the results of the conspicuous-coverage model (Fig. 5), one can see that two RPVs have been located to the east in the latter solution because of the coverage constraint. When applying the conspicuous-coverage model whereby traffic volume is ignored (i.e. U _j =1), the results are spatially much more spread out than the alternative solution (with traffic volume data) such that the more heavily congested road 90 has significantly greater coverage, in a similar manner to that of the current police solution.

4.2.3 Model 2: Maximum conspicuousness accounting for calls-for-service

Model 2 considers the total time required to handle calls-for-service. In order to adapt the objective function, we defined the length of a shift (H) as eight hours. The time spent handling events on section i during an eight-hour shift includes the average event time (half an hour), multiplied by the average number of calls at node i that was collected from calls-for-service data over the case study network during a 2-month period from April to May 2007 (E _i ), and the travel time between nodes, t _ij , which can be drawn from the Dijkstra solution based on the network structure and the 27 km legal restriction. The integer linear program thus consists of objective function (2) and constraints (1a to 1e).

Figure 6 presents the solution to Model 2 in which benefit is maximized and the time spent handling events is also taken into account within the objective function. Four locations are on main roads (roads 90 and 89) and the other two are for purposes of coverage on side roads to the east of the area (roads 989 and 808). The solution is similar to that presented in Fig. 5 because there are relatively few events in this rural area. The difference is that the locations are more spread out on the western side once we account for the time required to reach events. The objective function value equals 4,320 representing the average number of vehicles that will drive past six RPVs in an 8-hour shift, given the locations chosen and the average “lost” time during which the RPVs leave their location to handle traffic events within their pre-allocated area. This value represents 65 % of the maximum value attainable. It is less than the current police solution (5,356 with 81 % of the maximum value attainable) but ensures complete coverage of the network.

Fig. 6

Maximizing presence given calls-for-service

4.2.4 Model 3: Maximize conspicuousness with varying time coverage model

For purposes of demonstration, we assume that the first enforcement-stretch receives a higher priority than all others. Consequently, we set D ₁≤3 km resulting in N ₁ containing two enforcement-stretches, namely 1 and 2, instead of the 36 stretches previously. Since one of the locations must be either stretch 1 or 2, all remaining locations change, as presented in Fig. 7. The results allocate two additional nodes (127, 162) for coverage purposes on the eastern section and the three remaining locations cover high traffic volume roads (nodes: 65,124, 194).

Fig. 7

Maximizing presence given calls-for-service and varying time coverage requirements

4.2.5 Model 4: The multiple shift model

Out of the possible 222 nodes available in the case study network, only six nodes can be allocated per shift due to resource restrictions, therefore, for deterrence purposes, dynamically determined location sets on the nodes are required. In this study, a strong constraint is defined: once a location (node) is chosen, it may not be chosen in any other shift (constraint (4d)). Current computer capabilities (Pentium(R) quad core 3.40 GHz, 3.24 GB of RAM) are able to solve a maximum of two shifts (F=2). The two shift formulation contains approximately 30,000 binary variables (444 X _jf and 28,620 Z _ijf ). The traffic volume that flowed via the RPVs was 4,315 on average per shift, 65 % of the maximum utility achievable. Since it is known that the halo effect lasts over some period of time, it is preferable to continually change the location of RPVs, certainly across two adjacent shifts. Total capture may be lower as a result, leading to a lower objective function value, however in this case dynamic locations are strictly preferable. The solutions of formulation (4) over two shifts can be compared to that of formulation (2) for a single shift. All locations chosen for a single shift appear in the two shift solution, but the additional six locations are all very close to the original single shift solution, with most of them on the same main roads (roads 99, 90 and 89) suggesting that this outcome is strongly preferable to alternative, spatially different outcomes in this case study. Figure 8 demonstrates the six RPVs location regions (encircled) for the two shifts, within which the double locations of each RPV are located. If strictly different solutions are required, it would be possible to restrict the proximity of solution locations according to the distance-halo effect.

Fig. 8

Two-shift solution

In order to locate seven shifts, representing a working week, we subsequently aggregated the nodes. In this case study we chose 111 nodes (out of the 222 nodes) by simply summing every two nodes so that each node now represents approximately 5 km of road. The number of events per node (C _i ) has been defined as the summation of the two nodes, based on historical data. With 111 X _j and 3,481 Z _ij per day, the maximum number of shifts solvable was 7 (F=7), which consists of approximately 25,000 variables. The same six regions are chosen over the seven shifts, with the radius around each region widening due to the additional locations.

Table 1 demonstrates the total objective function values for the aggregate problem per number of shifts. The average objective function values per single shift decrease with the addition of shifts because of the additional constraints and the lack of multiple optimal solutions. For example, for 7 shifts, the average objective function value is 95.6 % of the objective function value of a single shift (3,815 out of 4,377). However, the advantage of dynamic location each day increases the halo effect.

Table 1 Objective function value and computation time in seconds per formulation

Given the computer’s limitations (a maximum of seven shifts i.e. 30,000 variables could be solved without running out of memory) and the time-consuming calculations of multiple shifts, we tested the difference between the aggregated model (formulation (4)) and running the original model over a single shift (formulation (2)) with recursive constraints over the location choices (we solved for one shift, then constrained the subsequent shifts by not permitting the previous solutions). Table 1 compares the two approaches according to the objective function values, average objective function levels (Fig. 9) and the computer time required to solve the formulations.

Fig. 9

The effect of the iterative and aggregative models on the value of the objective function

As demonstrated in Table 1 and Fig. 9, the objective function value is always higher in the aggregate solution, however the difference in the values between the two modeling approaches is at most 2.17 % (in the four shift solution).

The computation time (Table 1) suggested for the iterative approach requires 3.3 seconds at most for 7 shifts, as opposed to the aggregate approach in which the computation time rises exponentially as the number of shifts increases linearly (from 0.37 seconds for a single shift to 3,000 seconds for seven shifts). For planning purposes this may not be an issue, but if the problem is to be solved online after an event has occurred in order to reconfigure the locations, the computation time is likely to become more of an issue.

5 Conclusions and future directions

This study focuses on the traffic police routine patrol vehicle (RPV) location-allocation problem on an interurban road network. The aim is to locate the RPVs and generate beats such that all areas are covered within a pre-specified time limit whilst maximizing the utility drawn from the locations themselves. The benefit can be measured for example in terms of traffic flow captured in order to deter poor driving behavior and reduce the number and severity of road accidents.

The main results (coverage percentage and locations on main roads) for each model are summarized in Table 2. The current police location choices produce different results compared with the other formulations, because the current practice does not fully cover the eastern region (mostly lightly travelled roads) but on the other hand all six RPVs are located on main roads. We then demonstrated through the application of two basic covering models (SCP and MCLP) that it was possible to legally cover the network with less than the existing resources. Covering the network with the minimum requirement of four RPVs, and locating the remaining RPVs on main roads, results in a total of five RPVs located on main roads. This is the same result as that found in the first formulation that maximized utility defined in terms of presence and conspicuousness, utilizing traffic flow data given legal requirements. The second formulation, in addition to accounting for traffic flow, also considered the likelihood of handling calls-for-service, and the time spent doing so. In analyzing the results of the different formulations, it became apparent that accounting for calls-for-service leads to more widely spread solutions across the network. On the other hand, the models capturing traffic flow locate the RPVs on major roads with higher traffic volume because of the benefits accruing from visibility. The third formulation permitted the police planners to change the coverage requirements, such that certain roads may be served more quickly than others in order to better account for the problems of congestion and their effect on subsequent accidents. The results of the third formulation with respect to locations on main roads depend on the prioritization rule. The fourth formulation maximized presence and conspicuousness dynamically, accounting for multiple shifts and considering the halo effects identified in the literature.

Table 2 Comparison of results

When searching for multiple-shift solutions, in a further attempt to capture the different flows, the traffic flow objective function value drops, but herein lies the trade-off between encouraging good behavior mainly on arterial roads or maximizing the halo effect across the network.

This research has analyzed various approaches to the basic question of how to optimize the traffic police’s resources with the ultimate aim of combatting fatalities and casualties on the roads. The different solutions analyze alternative operational methods, such as flow capture via location on roads with high traffic volume, maximizing presence with regard to calls-for-service distribution, ensuring presence according to varying levels of service coverage and maximizing the halo effect based on dynamic locations. We provide a basis for building the traffic police force according to preferred operational methods. Furthermore, given these modeling approaches, the police will be better able to analyze their influence on drivers’ behavior, car accidents, calls-for-service and traffic problems.

The solutions to the traffic police, interurban network, multi-purpose, emergency service, RPV location-allocation models produce increased public security and safety over current choices. The proposed models maximize presence and consciousness in order to increase deterrence and prevention, which in conjunction with complete coverage, differ from existing models in the literature. However, the constraints of the models could also be adapted according to new policy initiatives. For example, automatic enforcement could be further developed leading to a reduction in the number of RPVs available and their usage.

Further research could be directed in several directions. First, the results of implementation of our models could be analyzed, helping the decision-makers to increase road safety with the limited budget at their disposal. Second, we intend to analyze a multi-objective location-allocation problem. Analyzing the traffic volume, road accident, calls for service and traffic offence data together with the decision-makers’ priorities, we find multiple, conflicting objectives which cannot be summarized by a single parameter. Finally, we intend to develop an enforcement model for traffic ticket issuance. The objective function would maximize road safety subject to the RPV location-allocation constraints and the limitation on the number and distribution of the traffic tickets to be issued.