[Back to Results | New Search]

Student Number 93342010 Author Yu-Lin Shih(¬I¦öªL) Author's Email Address 93342010@cc.ncu.edu.tw Statistics This thesis had been viewed 587 times. Download 91 times. Department Civil Engineering Year 2009 Semester 2 Degree Ph.D. Type of Document Doctoral Dissertation Language English Title Optimal Scheduling and Solution Algorithms for the Highway Emergency Repair Problem under Large-Scale Supply-Demand Perturbations Date of Defense 2010-07-02 Page Count 110 Keyword ant colony system algorithm emergency repair large-scale supply-demand perturbation threshold accepting algorithm time-space network Abstract Natural disasters, such as earthquakes, volcanic eruption, mudflows and landslides, have significant devastating effects in terms of human injuries and property damages. The 1999 Chi-chi earthquake not only indicated the low efficiency of the government for dealing with the rescue operations but also revealed the importance of the emergency repair. In the past, the emergency repair was usually planned by decision makers according to their own experiences, lacking of systematic analyses. The resultant operation could possibly be a feasible yet inferior. Recent research has developed a model that finds the optimal work team routes for emergency road repairs to improve scheduling efficiently. However, it is difficult to optimally solve the problem within the shortest possible period of time. Therefore, we first develop a solution algorithm for this problem. Furthermore, a major disaster leads to subsequent ¡§secondary¡¨ or ¡§tertiary disasters¡¨ in practice, which delays the repair time or generates new damaged points. These large-scale perturbation problems will disrupt the original work teams¡¦ repair schedule and will affect the follow-up resource assignment. In addition to the large-scale demand-side perturbation, the large-scale supply-side perturbation also affects the original schedule. For example, new work teams could be later supported by government, military or civil agencies, for more effective emergency repair. Therefore, we develop a model and solution algorithms for the highway emergency repair problem under large-scale supply-demand perturbations.

This dissertation consists of three essays. In the first essay, an ant colony system algorithm is employed, along with the threshold accepting technique, to develop an ACS-based hybrid algorithm capable of efficiently solving an emergency roadway repair time-space network flow problem. To test how well the algorithm may be applied to actual operations, a case study is carried out using data from the Chi-Chi earthquake in Taiwan. In the second essay, we develop a model and solution algorithms for the highway emergency repair problem under large-scale supply-demand perturbations. We employ the time-space network flow technique to develop a model that can help the authority decide on the best adjustment of highway emergency repair schedule. We use the C computer language, coupled with the CPLEX mathematical programming solver, to develop a heuristic algorithm for efficiently solving this problem. To evaluate the solution algorithms, we perform a case study. The results are good, showing that the model and heuristic algorithm could be useful. In the third essay, based on the problem¡¦s characteristics, and ant colony system algorithm, we further develop three global search algorithms, coupled with the techniques of the threshold accepting algorithm and efficiently solve the problem. To evaluate the solution algorithms, we perform a case study on a scale similar to that of Chi-chi earthquake. The results are good, showing that the model and the algorithms may be useful in practice.Table of Content ºKn i

Abstractii

»xÁÂiii

Contentsiv

List of Tablesvii

List of Figuresix

Chapter 1 Introduction1

Chapter 2 Essay 1: An Ant Colony System-Based Hybrid Algorithm for an Emergency Roadway Repair Time-Space Network Flow Problem5

2.1. Introduction5

2.2. The model8

2.2.1 Emergency repair time-space network8

2.2.2 The model formulation9

2.3. Development of an Ant Colony System-Based Hybrid Algorithm (ACSB)10

2.3.1 Generation of an initial solution11

2.3.2 Generation of feasible solutions12

2.3.3 State transition rule14

2.3.4 Dynamic time-space roadway network updating rule15

2.3.5 Local search16

2.3.6 Pheromone updating rules16

2.3.7 Path-and-time tracing method17

2.3.8 TA strategy18

2.3.9 Stopping criterion18

2.4. Numerical tests18

2.4.1 Data analysis and test results19

2.4.2 ACSB parameters21

2.4.2.1 Number of ants21

2.4.2.2 State transition rule parameters21

2.4.2.3 Pheromone updating rule parameters22

2.4.2.4 TA strategy parameters23

2.4.2.5 Stopping criterion parameter SU23

2.4.3 Evaluation for different roadway network patterns25

2.5. Conclusions and Suggestions30

Chapter 3 Essay 2: Optimal Scheduling for Highway Emergency Repair Problems under Large-Scale Supply-Demand Perturbations33

3.1. Introduction33

3.2. The Time-Space network design35

3.2.1 Real practices and Modeling issues35

3.2.2 Time-space network for emergency repair under large-scale supply-demand perturbations38

3.3. The model and the algorithm44

3.3.1 The model44

3.3.2. Segmenting optimization algorithm (SOPT)50

3.4. Case study51

3.4.1 Data analysis and test results51

3.4.2 The total number of back-up work teams53

3.4.3 The number of back-up work teams at each intersection54

3.4.4 The perturbation tolerance55

3.4.5 Tolerable perturbation time55

3.5. Conclusions and discussion56

Chapter 4 Essay 3: Hybrid Global Search Algorithms for Highway Emergency Repair Problems under Large-Scale Supply-Demand Perturbations58

4.1. Introduction58

4.2. The model59

4.2.1 Time-space network for emergency repair under large-scale supply-demand perturbations60

4.2.2 The model formulation61

4.3. Development of the Ant Colony System Based Hybrid Algorithms63

4.3.1 HGS-I algorithm63

4.3.1.1 Generation of feasible solutions65

4.3.2 HGS-II algorithm67

4.3.2.1 Generation of feasible solutions68

4.3.3 HGS-III algorithm70

4.3.3.1 Generation of feasible solutions71

4.4. Case Study73

4.4.1 Data analysis and test results73

4.4.2 HGS parameters75

4.4.2.1 Number of ants76

4.4.2.2 The state transition rule parameters77

4.4.2.3 The pheromone updating rule parameters77

4.4.2.4 TA strategy parameters78

4.4.2.5 Stopping criterion parameter79

4.4.2.6 Extra parameters for HGS-III79

4.4.2.7 Combinational of the individually best parameters80

4.4.3 Scenario analysis for different supply-demand situations82

4.5. Conclusions and Suggestions85

Chapter 5 Conclusions, Suggestions and Contributions87

5.1 Conclusions87

5.2 Suggestions88

5.3 Contributions89

References90

Appendix 1: The emergency repair model by Yan and Shih (2007)93

Appendix 2: Test results for HGS parameters97Reference Abachizadeh M., and Tahani M., 2009. An ant colony optimization approach to multi-objective optimal design of symmetric hybrid laminates for maximum fundamental frequency and minimum cost. Struct Multidisc Optim, 37, 367¡V376.

Ardekani SA, Hobeika A. Logistics problems in the aftermath of the 1985 Mexico city earthquake. Transportation Quarterly 1988; 42: 107-124.

Ardekani SA. Transportation operations following the 1989 Loma Prieta earthquake. Transportation Quarterly 1992; 46: 219-233.

Arimura M., Tamura T. and Saito K., 1999. Application of genetic algorithms model for road investment of restoration planning. Journal of the 2nd Eastern Asia Society for Transportation Studies, 55-69.

Barbarosoğlu G, Őzdamar L, Çevik A. An interactive approch for hierarchical analysis of helicopter logistics in disaster relief operations. European Journal of Operational Research 2002; 140(1): 118-133.

Brown G.G., Vassiliou AL. Optimizing disaster relief: real-time operational and tactical decision support. Naval Research Logistics 1993; 40: 1-23.

Bullnheimer B., Hartl R.F. and Strauss C., 1999. Applying the ant system to the vehicle routing problem. In: S. Voss, S. Martello, I.H. Osman and C. Roucairol, eds. Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer: Boston.

Chen Y.W. and Tzeng G.H., 1999. A fuzzy multi-objective model for reconstructing the post-quake road-network by genetic algorithm. International Journal of Fuzzy Systems, 1(2): 85-95.

Chen, C.H., Yan, S. and Tseng, C.H., 2010. Inter-city bus scheduling for allied carriers. Transportmetrica , 6(3) , 161-185.

Cluskey, J.M., 1979. Road form and townscape. Architectural Press.

Costa D. and Hertz A., 1997. Ants can colour graphs. Journal of the Computer Science, 34, 39-53.

Di Caro, G. and Dorigo, M., 1998. AntNet: dic control for communications networks. Journal of Artificial Intelligence Research, 9, 317-365.

Dorigo, M and Gambardella, L.M., 1997a. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

Dorigo, M. and Gambardella, L.M., 1996. A study of some properties of ant-Q. Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, September 22-27, 1996, Berlin, Germany, Berlin: Springer-Verlag, 656-665.

Dorigo, M. and Gambardella, L.M., 1997b. Ant colonies for the traveling salesman problem. BioSystems, 43, 73-81.

Dorigo, M., Maniezzo, V. and Colorni, A., 1996. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 29-41.

Dueck, G. and Scheuer, T., 1990. Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 161-175.

Feng, C.M. and Wang, T.C., 2003. Highway emergency rehabilitation scheduling in post-earthquake 72 hours. Journal of the 5th Eastern Asia Society for Transportation Studies, 3276-3285.

Feng, C.M. and Wang, T.C., 2005. Seismic emergency rehabilitation scheduling for rural highways. Transportation Planning Journal, 34(2), 177-210 (in Chinese).

Fiedrich, F., Gehbauer, F. and Rickers, U., 2000. Optimized resource allocation for emergency response after earthquake disasters. Safety Science, 35, 41-57.

Garey, M.R. and Johnson, D.S., 1979. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman & Company, San Francisco.

Haghani A, Oh S., 1996. Formulation and solution of a multi- commodity, multi-modal network flow model for disaster relief operations. Transportation Research Part A, 30(3), 231-250.

Hobeika AG, Ardekani SA, Han DL., 1988. Logistics decisions following urban disasters. Microcomputers in Civil Engineering, 3(1), 13-27.

Kemball-Cook D, Stephenson R. Lessons in logistics from Somalia. Disasters 1984; 8: 57-66.

Knott R., 1988. Vehicle scheduling for emergency relief management: a knowledge-based approach. Disasters, 12, 285-293.

Kolahan, F., Abachizadeh, M. and Soheili, S., 2006. A comparison between ant colony and tabu search algorithms for job shop scheduling with sequence-dependent setups. WSEAS transactions on systems, 12(5), 2819¡V2824.

Kuntz, P. and Snyers, D., 1997. Emergent colonization and graph partitioning. Proceedings of the 3th International Conference on Simulation of Adaptive Behavior: From Animals to Animate 3, The MIT Press, Cambridge, MA.

Montemanni, R., Gambardella, L.M., Rizzoli, A.E. and Donati, A.V., 2005. Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization, 10, 327-343.

Moore, E.F., 1957. The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching, Harvard University Press, Cambridge, Massachusetts, 285-292.

Oh SC, Haghani A. Testing and evaluating of a multi-commodity network flow model for disaster relief management. Journal of Advanced Transportation 1996; 31(2): 249-282.

Sato, T. and Ichii, K., 1996. Optimization of post-earthquake restoration of lifeline networks using genetic algorithms. Japan Society of Civil Engineers, 537 (I-35), 245-256.

Serra, M. and Venini, P., 2006. On some applications of ant colony optimization metaheuristic to plane truss optimization. Structural and Multidisciplinary Optimization, 32(6), 499¡V506.

Shyu, S.J., Yin, P.Y. and Lin B.M.T., 2004. An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research, 131, 283-304.

Stützl, T. and Dorigo, M., 1999. ACO algorithms for the quadratic assignment problem. In D. Corne and F. Glover, eds. New Ideas in Optimization. McGraw-Hill.

Talbi, E.G., Roux, O., Fonlupt, C. and Robillard, D., 2001. Parallel ant colonies for the quadratic assignment problem. Future Generation Computer Systems, 17, 441¡V449.

Tamura, T., Sugimoto, H. and Kamimae, T., 1994. Application of genetic algorithms to determining priority of urban road improvement. Japan Society of Civil Engineers, 482(IV-22), 37-46.

Yan, S. and Shih, Y.L., 2007. A time-space network model for work team scheduling after a major disaster. Journal of the Chinese Institute of Engineers, 30(1), 63-75.

Yan, S. and Shih, Y.L., 2009. Optimal scheduling of emergency roadway repair and subsequent relief distribution. Computers & Operations Research, 36(6), 2049-2065.

Yan, S., Juang, D.H., Chen, C.R. and Lai, W.S., 2005. Global and local search algorithms for concave cost transshipment problems. Journal of Global Optimization, 33(1), 123-156.

Yan, S., Lai, W. and Chen, M., 2008. Production scheduling and truck dispatching of ready mixed concrete. Transportation Research Part E, 44(1), 164-179.

Yan, S., Lo, S.C. and Gu, W.F., 1994. The comparison of complexity and real computation time on various shortest path algorithms. Transportation, 24, 11-24 (in Chinese).

Yan, S., Tang, C.H. and Lee, M.C., 2007. A flight scheduling model for Taiwan airlines under market competitions. OMEGA - The International Journal of Management Science, 35, 61-74.Advisor Shangyao Yan(ÃC¤W³ó)

Files approve in 3 years

93342010.pdf Date of Submission 2010-07-26

Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.