Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 30, Issue 2, Pages 320-334Publisher
SPRINGER
DOI: 10.1007/s10878-014-9751-z
Keywords
Hazmat transportation network design; Uncertain edge risk; Computational complexity; Robust optimization; Heuristic algorithms
Funding
- National Natural Science Foundation of China [70971008]
- Ministry of Education, Humanities and Social Sciences Planning Project [09YJC630008]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available