Opportunity cost-based models for traffic incident response problems

Real-time traffic incident response strategies deal with the determination of optimal resource allocation policies in response to traffic incidents occurring on a network. Such strategies also should address the effect of loss in coverage caused by the nonavailability of response vehicles that currently are serving certain primary incidents. In this paper, we first formulate a mixed-integer programming (MIP) model MIMR-1 for the multiple-incident multiple-response (MIMR) problem using standard modeling techniques. The effect of loss in coverage is reflected in the model by including in the objective function a new term related to an opportunity cost for serving future (secondary) incidents that might occur probabilistically on the network. We next present an alternative, equivalent MIP model (MIMR-2) that injects a particular structure into the problem. This is shown to yield a dramatic improvement in the performance of the commercial software package CPLEX-MIP when applied to this revised model in comparison with its application to MIMR-1. Furthermore, for certain special cases of the MIMR problem, efficient polynomial-time solution approaches are prescribed that yield a far superior performance over CPLEX-MIP. An algorithmic module composed of the developed specialized solution procedures, model MIMR-2, and a prescribed heuristic scheme, has been incorporated into a real-time area-wide incident management decision support system.