TY - JOUR
T1 - Optimal scheduling for highway emergency repairs under large-scale supply-demand perturbations
AU - Yan, Shangyao
AU - Chu, James C.
AU - Shih, Yu Lin
N1 - Publisher Copyright:
© 2000-2011 IEEE.
PY - 2014/12/1
Y1 - 2014/12/1
N2 - In this paper, we develop a model for emergency repair problems under large-scale supply-demand perturbations. The model formulation proposed in this paper has the following key features. First, a novel time-space network flow technique is adopted to generate detailed schedules for repair teams and allow dynamic updates of the network due to perturbations. Second, the original schedules prior to the perturbations are considered by controlling the total difference between the original schedule and the adjusted schedule. Third, to reduce computational complexity, the model is formulated with different levels of detail (individual teams versus a team group). The model is also formulated as a special mixed-integer network flow problem with side constraints, which is characterized as NP-hard. An ant-colony-system-based hybrid global search algorithm is developed to efficiently solve large-scale problems. To test how well the model formulation and the heuristic algorithm may perform in actual operations, we conduct a case study using actual data from the 1999 Chi-Chi earthquake in Taiwan. The results show that the proposed model and solution algorithm perform very well and thus have great potential for assisting with the making of emergency repair decisions in the event of disasters given large-scale perturbations in supply and demand.
AB - In this paper, we develop a model for emergency repair problems under large-scale supply-demand perturbations. The model formulation proposed in this paper has the following key features. First, a novel time-space network flow technique is adopted to generate detailed schedules for repair teams and allow dynamic updates of the network due to perturbations. Second, the original schedules prior to the perturbations are considered by controlling the total difference between the original schedule and the adjusted schedule. Third, to reduce computational complexity, the model is formulated with different levels of detail (individual teams versus a team group). The model is also formulated as a special mixed-integer network flow problem with side constraints, which is characterized as NP-hard. An ant-colony-system-based hybrid global search algorithm is developed to efficiently solve large-scale problems. To test how well the model formulation and the heuristic algorithm may perform in actual operations, we conduct a case study using actual data from the 1999 Chi-Chi earthquake in Taiwan. The results show that the proposed model and solution algorithm perform very well and thus have great potential for assisting with the making of emergency repair decisions in the event of disasters given large-scale perturbations in supply and demand.
KW - Ant colony system (ACS)
KW - emergency repair
KW - large-scale supply-demand perturbations
KW - threshold accepting (TA) algorithm
KW - time-space network
UR - http://www.scopus.com/inward/record.url?scp=84915803010&partnerID=8YFLogxK
U2 - 10.1109/TITS.2014.2313628
DO - 10.1109/TITS.2014.2313628
M3 - 期刊論文
AN - SCOPUS:84915803010
SN - 1524-9050
VL - 15
SP - 2378
EP - 2393
JO - IEEE Transactions on Intelligent Transportation Systems
JF - IEEE Transactions on Intelligent Transportation Systems
IS - 6
M1 - 0001
ER -