Freeway service patrol deployment planning for incident management and congestion mitigation

This paper investigates the problem of deploying freeway service patrols to detect, respond to and clear traffic incidents in two settings, deterministic and stochastic. The deterministic setting assumes that there is only one scenario of incident occurrence and, in the stochastic counterpart, there are many scenarios, each of which occurs with a probability. The main objective of both problems is to minimize the total incident response time. Rather than minimizing the expected total response time, the stochastic model minimizes the expected total response time over the high-consequence scenarios instead. In both settings, the deployment problem can be formulated as a mixed-integer nonlinear optimization problem, a hard class of problem to solve. To obtain solutions in a reasonable amount of time, three heuristic algorithms are proposed. In particular, one makes use of the dual information, another employs a neighborhood search technique and the third uses simulated annealing, a meta-heuristic algorithm. Numerical experiments based on data from Sioux Falls demonstrate that all three algorithms provide solutions with a significant reduction in total response time without using an excessive amount of CPU time.