Strategic design of patrol routing for incident response programs

Debashis Saha

In this work, we have tried to address the problem of determining optimal routes for incident response team on freeways. Quick response to the incidents is the key priority for freeway patrolling. However, response time has hardly been used as a performance measurement in the existing routing strategies. While planning for first respondents' activities, it is critical to take into account their station location and patrol routing plans in the network. Previously travel time has been used in different routing problem as a performance measurement. However, this thesis uses expected maximum response time to determine an optimal routing strategy so that response time to all the hotspots in the selected network can be optimized. A mixed-integer linear program is developed that minimizes the routing cost with a particular focus on the expected maximum response time from each arbitrary location to all incident hotspots under various occurrence probabilities. However, as the number of hotspots increases, finding the optimal routes from the huge set of possible routes gets nearly impossible using traditional optimization algorithms. That is why an integrated relaxation-based solution technique with embedded column generation (CG) algorithm is developed to tackle the complexity of the proposed problem. Later on, in order to find the suitable combinations of stations more efficiently a genetic algorithm (GA) based framework has been proposed where each chromosome will provide the location of the station and based on these decisions the routing problem will be solved by column generation (CG) technique. Continuum Approximation (CA) has been used inside the solution framework to estimate the routing cost. Several numerical tests have been conducted to check the efficiency of the proposed algorithm which includes Sioux Falls network with 24 hotspots and another hypothetical network with 101 nodes. A series of sensitivity analyses have been performed to see the impact of different parameters on the optimal emergency response plan. Although our primary focus is on freeway patrolling, our proposed model can also be applied to other patrolling purposes.

Strategic design of patrol routing for incident response programs

Files and links (1)

Abstract

Metrics

Details