Multicommodity Maximal Covering Network Design Problem for Planning Critical Routes for Earthquake Response

A multicommodity maximal covering network design problem (MCNDP) is formulated for identifying critical routes for earthquake response and seismically retrofitting bridges. MCNDP seeks routes that minimize the total travel time over the selected routes and maximize the total population covered, subject to a budget constraint on bridge retrofitting costs on the selected routes. The problem is formulated as a two-objective integer programming model and solved with the branch-and-cut module in the CPLEX optimizer. The model performance is analyzed with the transportation network of a seismically prone region in southwestern Indiana. A problem reduction strategy is introduced to reduce computational times by recognizing that the critical routes usually are not circuitous. Thereby, the search for the critical routes for an origin–destination (O-D) pair is confined to a limited geographical region around it. To further reduce computational costs, the formulation is extended to incorporate valid inequalities that exploit the problem structure. Computational experiments are conducted to investigate the effects of varying the budget and the relative weights of the two objectives. Noninferior frontiers that illustrate the trade-offs between the conflicting objectives for different budgets are constructed to provide practical insights to decision makers. In addition, a vulnerability analysis is performed for the various solution instances to infer their ability to ensure connectivity between all O-D pairs after an earthquake.