Skip to main content
Top

2021 | OriginalPaper | Chapter

5. A Branch-and-Price Framework for the Maximum Covering and Patrol Routing Problem

Authors : Paul A. Chircop, Timothy J. Surendonk, Menkes H. L. van den Briel, Toby Walsh

Published in: Data and Decision Sciences in Action 2

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The Maximum covering and patrol routing problem (MCPRP) is concerned with the allocation of police patrol cars to accident hotspots on a highway network. A hotspot is represented as a time window at a precise location on the network at which motor vehicle accidents have a high probability of occurring. The nature of these accidents may be due to speeding, driver fatigue or blind-spots at intersections. The presence of police units at hotspots serves as an accident prevention strategy. In many practical applications, the number of available cars cannot cover all of the hotspots on the network. Hence, given a fleet of available units, an optimization problem can be designed which seeks to maximize the amount hotspot coverage. The cars must be routed in such a way as to avoid multiple contributions of the patrol effort to the same hotspot. Each police car is active over a predefined shift, beginning and ending the shift at a fleet station. In this paper, we introduce a method for constructing a time-space network of the MCPRP which is suitable for the application of a branch-and-price solution approach. We propose some large-scale test problems and compare our approach to a state-of-the-art Minimum cost network flow problem (MCNFP) model. We show that our branch-and-price approach can outperform the MCNFP model on selected large-scale networks for small to medium fleet sizes. We also identify problems which are too large for the MCNFP model to solve, but which can be easily handled by our approach.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
The literature review conducted by Keskin et al. [10] notes that the MCPRP bears similarities to the Team orienteering problem with time windows (TOPTW). However, the distinguishing characteristic of the MCPRP is that the profit associated with visiting a hotspot is not fixed, but is rather a function of the amount of “dwell time” within that hotspot’s time window. The authors state that the range of time window lengths used in the problems of their study varied from \(1{-}270\) minutes (usually assuming an 8 hour shift).
 
2
The results of this study can also be found in the PhD thesis by Li [12].
 
3
Çapar et al. [3] considered a number of extensions to the standard MCPRP paradigm. These extensions included the incorporation of shift breaks and allowing the patrol vehicles to begin the shift at different locations, possibly with delayed starting times.
 
4
The MCNFP possesses the integrality property when the arc capacities are integer (see Ahuja et al. [1]). This means that the optimal solution is naturally integer if the problem is solved as a linear program.
 
5
For example, see previous work on the Patrol boat scheduling problem with complete coverage (PBSPCC) by the authors of this paper [5] or the PhD thesis by Chircop [4].
 
6
The arrival vertex at location \(i \in V_{S}\) is the vertex \(v \in V_{R}\) such that \(v = (i, t_{0i})\). The termination vertex at location \(i \in V_{S}\) is the vertex \(u \in V_{R}\) such that \(u = (i, T- t_{i0})\).
 
7
The dual variables of the RMP can be found in square parentheses along the right-hand side of (5.1)–(5.6).
 
8
This essentially describes the column generation technique for solving prohibitively large linear programs (see [6] for a comprehensive introduction). The fundamental insight of the column generation approach is to generate the columns of the constraint matrix on-the-fly by recourse to an optimization subproblem. The idea was originally suggested by Ford and Fulkerson [8], but was first implemented by Gilmore and Gomory [9].
 
9
By solving the RMP as a linear program and obtaining its dual variables, a subproblem can be solved to determine a new column (variable) to add to the RMP. The subproblem can accomplish this by casting the pricing step of the simplex algorithm (find a variable with negative reduced cost to enter the basis) as an optimization problem. The process iterates between the RMP and the subproblem, terminating when no variable can price-out favourably.
 
10
An investigation of alternative branching strategies, for example, selecting various combinations of arc variables at a time, is beyond the scope of this paper, but is recommended for future research.
 
11
Vanderbeck [13] notes that this phenomenon (i.e. fractional path flows translating to integral arc flows) can occur when the subproblem is a shortest path problem, which is precisely our case. To see why this is so, recall that \(x_{uv} = \sum _{p \in P} x_{uvp} \lambda _{p}\) for all \((u,v) \in A_{R}\). It is straightforward to see that if \(\lambda _{p} \in \{0,1\}\) for all \(p \in P\), then \(x_{uv} \in \mathbb {Z}^{+}\) for all \((u,v) \in A_{R}\), since \(x_{uvp} \in \{0,1\}\) for each \((u,v) \in A_{R}\) and \(p \in P\). However, the converse does not hold. That is, it is mathematically possible to find a set of paths taking fractional values which translates into an integral arc flow solution.
 
12
For a grid structure of size \(30 \times 30\) min, a patrol vehicle will traverse the breadth/length of the structure in 30 min.
 
13
In total, we generated 8 networks with 40 hotspots, 8 networks with 60 hotspots, 16 networks with 80 hotspots and 8 networks with 100 hotspots. Each test network was randomly generated over a grid structure of size \(30 \times 30\) min or \(60 \times 60\) min. The time window length of the hotspots was either 1 min, \(5{-}15\) min, 30 min or \(30{-}90\) min. All test problem instances were run with an 8 hour shift (that is, 480 min) and a time discretization of 1 min.
 
14
The computational results of all test problem instances can be found in Appendix G of the PhD thesis by Chircop [4].
 
15
The computational results for the branch-and-price approach to the MCPRP were produced on a 2.70 GHz dual-core processor on a 32-bit operating system with 4.00 GB of RAM. All primal and dual solutions to the linear programs were obtained with CPLEX 12.6. The column generation and shortest path algorithms, along with the required data structures for the master problem and the time-space network, were coded using the Java programming language and the Eclipse Integrated development environment (IDE). The MCNFP model was run from an executable (on the same operating system) compiled from source code supplied by the authors of [7] and the LEMON C++ libraries using the Microsoft Visual Studio (2012) IDE.
 
16
The MCNFP model crashed (due to memory capacity constraints) when we attempted to solve these large-scale instances.
 
17
The aggregate duration of all the hotspots in \(H300\_a\) was 17, 606 min. The aggregate duration for \(H500\_a\) was 15, 000 min. The shift duration in both cases was 8 hours (480 min).
 
18
The headings used in Table 5.1 are as follows: Car—the number of vehicles. R.Obj.—the objective function value at the root node. R.Ti.—the CPU time (seconds) at the root node. R.Col.—the number of columns generated at the root node. No.—the number of nodes explored (fathomed) in the branch-and-price tree. S.Ti.—the CPU time (seconds) taken to find the integer solution. Hot.—the number of hotspots visited.
 
Literature
1.
go back to reference Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms, and applications. Prentice Hall Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms, and applications. Prentice Hall
2.
go back to reference Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46:316–329 MathSciNetCrossRef Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46:316–329 MathSciNetCrossRef
3.
go back to reference Çapar İ, Keskin BB, Rubin PA (2015) An improved formulation for the maximum coverage patrol routing problem. Comput Oper Res 59:1–10 MathSciNetCrossRef Çapar İ, Keskin BB, Rubin PA (2015) An improved formulation for the maximum coverage patrol routing problem. Comput Oper Res 59:1–10 MathSciNetCrossRef
4.
go back to reference Chircop PA (2017) Column generation approaches to patrol asset scheduling with complete and maximum coverage requirements. PhD thesis, University of New South Wales, Sydney, Australia Chircop PA (2017) Column generation approaches to patrol asset scheduling with complete and maximum coverage requirements. PhD thesis, University of New South Wales, Sydney, Australia
5.
go back to reference Chircop PA, Surendonk TJ, van den Briel MHL, Walsh T (2013) A column generation approach for the scheduling of patrol boats to provide complete patrol coverage. In: Piantadosi J, Anderssen RS, Boland J (eds) Proceedings of the 20th international congress on modelling and simulation. Modelling and Simulation Society of Australia and New Zealand, pp 1110–1116 Chircop PA, Surendonk TJ, van den Briel MHL, Walsh T (2013) A column generation approach for the scheduling of patrol boats to provide complete patrol coverage. In: Piantadosi J, Anderssen RS, Boland J (eds) Proceedings of the 20th international congress on modelling and simulation. Modelling and Simulation Society of Australia and New Zealand, pp 1110–1116
6.
go back to reference Desrosiers J, Lübbecke ME (2005) A primer in column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, US, pp 1–32 MATH Desrosiers J, Lübbecke ME (2005) A primer in column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, US, pp 1–32 MATH
7.
go back to reference Dewil R, Vansteenwegen P, Cattrysse D, Oudheusden DV (2015) A minimum cost network flow model for the maximum covering and patrol routing problem. Eur J Oper Res 247:27–36 MathSciNetCrossRef Dewil R, Vansteenwegen P, Cattrysse D, Oudheusden DV (2015) A minimum cost network flow model for the maximum covering and patrol routing problem. Eur J Oper Res 247:27–36 MathSciNetCrossRef
8.
go back to reference Ford LR, Fulkerson DR (1958) A suggested computation for maximal multi-commodity network flows. Manag Sci 5:97–101 MathSciNetCrossRef Ford LR, Fulkerson DR (1958) A suggested computation for maximal multi-commodity network flows. Manag Sci 5:97–101 MathSciNetCrossRef
9.
10.
go back to reference Keskin BB, Li SR, Steil D, Spiller S (2012) Analysis of an integrated maximum covering and patrol routing problem. Transp Res Part E(mohana) Logist Transpo Rev 48:215–232 CrossRef Keskin BB, Li SR, Steil D, Spiller S (2012) Analysis of an integrated maximum covering and patrol routing problem. Transp Res Part E(mohana) Logist Transpo Rev 48:215–232 CrossRef
11.
go back to reference Király Z, Kovács P (2012) Efficient implementations of minimum-cost flow algorithms. Acta Univ Sapientiae, Inform 4:67–118 MATH Király Z, Kovács P (2012) Efficient implementations of minimum-cost flow algorithms. Acta Univ Sapientiae, Inform 4:67–118 MATH
12.
go back to reference Li SR (2012) Vehicle routing models in public safety and health care. PhD thesis, The University of Alabama TUSCALOOSA Li SR (2012) Vehicle routing models in public safety and health care. PhD thesis, The University of Alabama TUSCALOOSA
13.
go back to reference Vanderbeck F (2005) Implementing mixed integer column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, US, pp 331–358 CrossRef Vanderbeck F (2005) Implementing mixed integer column generation. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, US, pp 331–358 CrossRef
14.
go back to reference Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209:1–10 MathSciNetCrossRef Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209:1–10 MathSciNetCrossRef
Metadata
Title
A Branch-and-Price Framework for the Maximum Covering and Patrol Routing Problem
Authors
Paul A. Chircop
Timothy J. Surendonk
Menkes H. L. van den Briel
Toby Walsh
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-60135-5_5