Hill-Climbing Algorithm for Robust Emergency System Design with Return Preventing Constraints

Research background: This paper deals with smart design of robust emergency service system. The robustness means here resistance of the system to various detrimental events, which can randomly occur in the associated transportation network. Consequences of the detrimental events are formalized by establishing a set of detrimental scenarios. A robust emergency service system is usually designed so that the deployment of given number of service centers minimizes the maximal value of objective functions corresponding with the specified scenarios. The original approach to the system design using means of mathematical programming faces computational difficulties caused by the link-up constraints. Purpose of the article: The main purpose of our research is to overcome the computational burden of the branch-and-bound method caused by the min-max constraints in the model. We suggest an iterative hill climbing algorithm, which outperforms the original approach in both computational time and computer memory demand. Methodology/methods: The methodology consists in approximation of the maximum of original objective functions by a suitable convex combination of the objective functions. The previously developed hill climbing algorithm is extended by return preventing constraints and their influence on computational effectiveness is studied within this paper. Especially, we focus on finding the most suitable form of the return preventing constraints and strategy of their implementation. Findings & Value added: We present here a comparison of the suggested algorithm to the original approach and the Lagrangean relaxation of the original approach. We found that the suggested algorithm outperforms the original exact approach as concerns the computational time with maximal two percent deviation from the optimal solution. In addition, the algorithm outperforms the Lagrangean approach in both computational time and the deviation.