Robust optimization for the hazardous materials transportation network design problem

In this paper, we reconsider the hazardous materials transportation network design problem with uncertain edge risk (HTNDPUR) which is proved as strong NP-hard. The natural ways to handle NP-hard problems are approximation solutions or FPT algorithms. We prove that the HTNDPUR does not admit any approximation, neither any FPT algorithm, unless P = NP. Furthermore, we utilize the minimax regret criterion to model the HTNDPUR as a bi-level integer programming formulation under edge risk uncertainty, where an interval of possible risk values is associated with each arc. We present a robust heuristic approach that always finds a robust and stable hazmat transportation network. At the end, we test our method on a network of Guangdong province in China to illustrate the efficiency of the algorithm. Our experimental results illustrate that the robust interval risk scenario network performs better than the deterministic scenario network.