An integer multi-objective optimization model and an enhanced non-dominated sorting genetic algorithm for contraflow scheduling problem

Abstract

To determine the onset and duration of contraflow evacuation, a multi-objective optimization (MOO) model is proposed to explicitly consider both the total system evacuation time and the operation cost. A solution algorithm that enhances the popular evolutionary algorithm NSGA-II is proposed to solve the model. The algorithm incorporates preliminary results as prior information and includes a meta-model as an alternative to evaluation by simulation. Numerical analysis of a case study suggests that the proposed formulation and solution algorithm are valid, and the enhanced NSGA-II outperforms the original algorithm in both convergence to the true Pareto-optimal set and solution diversity.

Keywords

hurricane evacuation / contraflow scheduling / multi-objective optimization / NSGA-II

References

[1] KIMS, SHEKHARS, MINM. Contraflow network reconfiguration for evacuation route planning [J]. IEEE Transaction on Knowledge and Data Engineering, 2008, 20(8): 1115-1129

[2] LVN, YANX, XUK, WUC. Bi-level programming based contraflow optimization for evacuation events [J]. Kybernetes, 2010, 39(8): 1227-1234

[3] TUYDESH, ZIZIASKOPOULOSA. Tabu-based heuristic approach for optimization of network evacuation contraflow [J]. Transportation Research Record: Journal of the Transportation Researh Board, 2006, 1964(1): 157-168

[4] THEODOULOUG, WOLSHONB. Alternative methods to increase the effectiveness of freeway contraflow evacuation [J]. Transportation Research Record: Journal of Transportation Research Board, 2004, 1865: 48-56

[5] WILLIAMSB, TAGLIAFERRIA, MEINHOLDS, HUMMERJ, ROUPHAILN. Simulation and analysis of freeway lane reversal for coastal hurricane evacuation [J]. ASCE Journal of Urban Planning and Development, 2007, 133(1): 61-72

[6] SBAYTIH, MAHMASSANIH. Optimal scheduling of evacuation operations [J]. Transportation Research Record: Journal of Transportation Research Board, 2006, 1964: 238-246

[7] CHIUY, ZHENGH, VILLALOBOSJ, PEACOCKW, HENKR. Evaluating regional contra-flow and phased evacuation strategies for Texas using a large-scale dynamic traffic simulation and assignment approach [J]. Journal of Homeland Security and Emergency Management, 2008

[8] PELA, BLIEMERMEvacuation plan evaluation: Assessment of mandatory and voluntary vehicular evacuation schemes by means of an analytical dynamic traffic model [C]//The 87th Transportation Research Board Annual Meeting, 2008WashingtonD.C: TRB08-2086

[9] YAOT, MANDALAS, CHUNGB. Evacuation transportation planning under uncertainty: A robust optimization approach [J]. Network Spatial and Economics, 2009, 9(2): 171-189

[10] NGM, WALLERT. Reliable evacuation planning via demand inflation and supply deflation [J]. Transportation Research, Part E, 2010, 46(6): 1086-1094

[11] MENGQ, KHOOH. Optimizing contraflow scheduling problem: model and algorithm [J]. Journal of Intelligent Transportation Systems, 2008, 12(3): 126-138

[12] BACKT, HAMMELU, SCHWEFELH P. Evolutionary computation: Comments on the history and current state [J]. IEEE Transactions on Evolutionary Computation, 2002, 1(1): 3-17

[13] LOUY, FONSECAD, MOYNIHANG, GURUPACKIAMS. Contraflow evacuation planning for I-65 in alabama [R]. Alabama University Transportation Center for Alabama, 2013

[14] LOUY, LIP, FONSECAD, MOYNIHANG, GURUPACKIAMS. Scheduling of contraflow evacuation: A case study of I-65 in alabama [J]. Journal of Transportation Engineering, 2014

[15] ZIZLERE, THIELEL. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach [J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271

[16] HUH, GAOY, YANGX. Multi-objective optimization method of fixed-time signal control of isolated intersections [C]//2010 International Conference on Computational and Information Sciences. Chengdu: IEEE, 20101281-1284

[17] FIKSEKAccelerating the search for optimal dynamic traffic management [D], 2011Enschede, NetherlandsUniversity of Twente

[18] LAMOTTER A, ALECSANDRUC. Fast multi-objective optimization for continuous network design problems based on gaussian process models [C]//The 93rd Transportation Research Board Annual Meeting. Washington, D.C: TRB, 201414-1210

[19] LEEL H, CHEWE P, LIH. Multi-objective compass for discrete optimization via simulation [C]// 2011 Winter Simulation Conference. Phoenix: IEEE, 20114070-4079

[20] XIANGY, ARORAJ S, RAHMATALLAS, MARLERT, BHATTR. Human lifting simulation using a multi-objective optimization approach [J]. Multibody Syst Dyn, 2010, 23(4): 431-451

[21] LIUY, CHANGG, LIUY, LAIX. Corridor-based emergency evacuation system for Washington, D.C.: System development and case study [J]. Transportation Research Record: Journal of Transportation Research Board, 2008, 2041: 58-67

[22] GULDMANNJ M, KIMWUrban transportation network design, traffic allocation, and air quality control: an integrated optimization approach [C]//European Regional Science Association 36th European Congress, 1996ZurichERSA

[23] CHANKONGV, HAIMESYMultiobjective decision making theory and methodology [M], 1983New YorkElsevier

[24] CARAMIAM, DELL’OLMOPMulti-objective management in freight logistics [M], 2008Now YorkSpringer

[25] CHARNESA, COOPERW, FERGUSONR. Optimal estimation of executive compensation by linear programming [J]. Management Science, 1955, 1(1): 138-151

[26] LAUMANNSM, THIELEL, DEBK, ZITZLERE. Combining convergence and diversity in evolutionary multiobjective optimization [J]. Evolutionary Computation, 2002, 10(3): 263-282

[27] DEBK, PRATAPA, AGARWALS, MEYARIVANT. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197

[28] JINR, CHENW, SIMPSONT W. Comparative studies of metamodelling techniques under multiple modelling criteria [J]. Structural and Multidisciplinary Optimization, 2001, 23(1): 1-13