Lamotte, Raphaël A. F. (2014) A Fast Multi-Objective Optimization Approach to Solve the Continuous Network Design Problem with Microscopic Simulation. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
2MBLamotte_MASc_S2014.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
The capacity of microscopic traffic simulation to estimate the environmental and road safety impacts opens the possibility to address the Network Design Problem from a new multi-objective point of view. Computation time, however, has hindered the use of this tool. The aim of this thesis was to find a continuous optimization method that would require only a very limited number of evaluations, and thus reduce the computation time. For this purpose, the most recent optimization literature was studied and two algorithms were selected: PAL and SMS-EGO. Both these algorithms rely on Gaussian process meta-models, but they are distinct with respect to the assumptions, criteria and methods used. They were then compared on a real-world case-study with NSGA-II, a genetic algorithm considered as state-of-the-art. Within the very limited computational budget allowed, SMS-EGO was found to outperform PAL and NSGA-II in the three configurations studied. However, the computational time required was still too important to allow for large scale optimization. To further accelerate the optimization process, three main adjustments were proposed, based on variable noise modeling, gradient-based optimization and conditional updates of the meta-models. Considering 20 runs for each optimization process, only variable noise modeling exhibited a statistically significant positive impact. The two other modifications also accelerated the optimization process on average, but high variability in the results led to p-values in the order of 0.15. Overall, the proposed optimization methodology represents a useful tool for transportation researchers to solve multi-objective optimization problems of limited scale.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Building, Civil and Environmental Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Lamotte, Raphaël A. F. |
| Institution: | Concordia University |
| Degree Name: | M.A. Sc. |
| Program: | Civil Engineering |
| Date: | April 2014 |
| Thesis Supervisor(s): | Alecsandru, Ciprian |
| Keywords: | Optimization; Network Design; Microscopic Simulation; Multi-objective; Gaussian processes; Meta-model |
| ID Code: | 978402 |
| Deposited By: | RAPHAEL ALI FRA LAMOTTE |
| Deposited On: | 16 Jun 2014 18:49 |
| Last Modified: | 18 Jan 2018 17:46 |
References:
1. Magnanti, T. L., and R. T. Wong. Network Design and Transportation Planning : Models and Algorithms. Transportation Science, Vol. 18, No. 1, 1984, pp. 1–55.2. Yang, H., and M. G. H. Bell. Models and algorithms for road network design: a review and some new developments. Transport Reviews: A Transnational Transdisciplinary Journal, Vol. 18, No. 3, 1998, pp. 257–278.
3. Guihaire, V., and J.-K. Hao. Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice, Vol. 42, No. 10, 2008, pp. 1251–1273.
4. Kepaptsoglou, K., and M. Karlaftis. Transit Route Network Design Problem : Review. Journal of Transportation Engineering, Vol. 135, No. 8, 2009, pp. 491–505.
5. Chow, J. Y. J. Flexible Management of Transportation Networks under Uncertainty. Ph. D. diss., University of California - Irvine, 2010.
6. Cascetta, E., M. Gallo, and B. Montella. Models and algorithms for the optimization of signal settings on urban networks with stochastic assignment models. Annals of Operations Research, Vol. 144, No. 1, 2006, pp. 301–328.
7. Farahani, R. Z., E. Miandoabchi, W. Y. Szeto, and H. Rashidi. A review of urban transportation network design problems. European Journal of Operational Research, Vol. 229, No. 2, 2013, pp. 281–302.
8. Correa, J. R., and N. E. Stier-Moses. Wardrop Equilibria. In Wiley Encyclopedia of Operations Research and Management Science, ed J. J. Cochran, John Wiley & Sons, Inc., 2010.
9. PTV Planung Transport Verkehr AG. VISSIM 5.40 - User Manual. Karlsruhe, Germany, 2012.
10. Fellendorf, M., and P. Vortisch. Microscopic Traffic Flow Simulator VISSIM. In Fundamentals of Traffic Simulation, ed J. Barceló, Springer New York, New York 2010.
11. Osorio Pizano, C. Mitigating Network Congestion : Analytical Models, Optimization Methods and their Applications. Ph. D. diss., Ecole Polytechnique Fédérale de Lausanne, 2010.
12. Stevanovic, A., J. Stevanovic, and C. Kergaye. Optimization of traffic signal timings based on surrogate measures of safety. Transportation Research Part C: Emerging Technologies, Vol. 32, 2013, pp. 159–178.
13. Robles, D. Optimal signal control with multiple objectives in traffic mobility and environmental impacts. M. Sc. Diss., Royal Institute of Technology (KTH) Stockholm, 2012.
14. Fikse, K. Accelerating the Search for Optimal Dynamic Traffic Management. M. Sc. Diss., University of Twente, 2011.
15. Guldmann, J.-M., and W. Kim. Urban transportation network design, traffic allocation, and air quality control: an integrated optimization approach. European Regional Science Association 36th European Congress, ETH Zurich, Switzerland, No. August, 1996, pp. 1–42.
16. Sharma, S., and T. V Mathew. Multiobjective network design for emission and travel-time trade-off for a sustainable large urban transportation network. Environment and Planning B: Planning and Design, Vol. 38, No. 3, 2011, pp. 520–538.
17. Stevanovic, A., J. Stevanovic, K. Zhang, and S. Batterman. Optimizing Traffic Control to Reduce Fuel Consumption and Vehicular Emissions. Transportation Research Record: Journal of the Transportation Research Board, Vol. 2128, No. -1, 2009, pp. 105–113.
18. Wismans, L., E. van Berkum, and M. Bliemer. Accelerating solving the dynamic Multi-Objective Network Design Problem using Response Surface Methods. Journal of Intelligent Transportation Systems: Technology, Planning, and Operations, Vol. 18, No. 1, 2013, pp. 17–29.
19. Perkins, S. R., and J. I. Harris. Criteria for traffic conflict characteristics. Research Laboratories, General Motors Corporation, 1967.
20. Tarko, A., G. Davis, N. Saunier, T. Sayed, and S. Washington. Surrogate Measures of Safety. 2009.
21. Gettman, D., and L. Head. Surrogate Safety Measures From Traffic Simulation Models. Federal Highway Administration, 2003.
22. Gettman, D., L. Pu, T. Sayed, and S. Shelby. Surrogate Safety Assessment Model and Validation. Federal Highway Administration, 2008.
23. Chen, A., J. Kim, S. Lee, and Y. Kim. Stochastic multi-objective models for network design problem. Expert Systems with Applications, Vol. 37, No. 2, 2010, pp. 1608–1619.
24. Bureau of Public Roads. Traffic Assignment Manual. U.S. Department of Commerce, Urban Planning Division, Washington, D.C., 1964.
25. Shimamoto, H., J.-D. Schmöcker, and F. Kurauchi. Optimisation of a Bus Network Configuration and Frequency Considering the Common Lines Problem. Journal of Transportation Technologies, Vol. 02, No. 03, 2012, pp. 220–229.
26. Cantarella, G. E., and A. Vitetta. The multi-criteria road network design problem in an urban area. Transportation, Vol. 33, No. 6, 2006, pp. 567–588.
27. Hu, H., Y. Gao, and X. Yang. Multi-objective Optimization Method of Fixed-Time Signal Control of Isolated Intersections. 2010 International Conference on Computational and Information Sciences, 2010, pp. 1281–1284.
28. Sun, D., F. Benekohal, and S. T. Waller. Multi-objective Traffic Signal Timing Optimization Using Non-dominated Sorting Genetic Algorithm. 2003 IEEE Intelligent Vehicles Symposium, Columbus, Oh., 2003, pp. 198–203.
29. MathWorks. What is Multiobjective Optimization? Available at: http://www.mathworks.com/help/gads/what-is-multiobjective-optimization.html [Accessed November 20, 2013].
30. Deb, K., A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, 2002, pp. 182–197.
31. Zuluaga, M., A. Krause, E. T. H. Zurich, G. Sergent, and P. Markus. Active Learning for Multi-Objective Optimization. JMLR: W&CP, Vol. 28, 2013.
32. Ponweiser, W., T. Wagner, D. Biermann, and M. Vincze. Multiobjective Optimization on a Limited Budget of Evaluations Using Model-Assisted S-Metric Selection. PPSN X, LCNS 5199, Dortmund, Germany, Vol. LCNS 5199, 2008, pp. 784–794.
33. Knowles, J., and E. J. Hughes. Multiobjective Optimization on a Budget of 250 Evaluations. In Evolutionary Multi-Criterion Optimization, Third International Conference, eds Coello CA, Aguirre AH, Zitzler E, 2005.
34. Box, G. E. P., and K. B. Wilson. On the Experimental Attainment of Optimum Conditions. Journal of the Royal Statistical Society, Series B (Methodological), Vol. 13, No. 1, 1951, pp. 1–45.
35. Clarke, S. M., J. H. Griebsch, and T. W. Simpson. Analysis of Support Vector Regression for Approximation of Complex Engineering Analyses. Journal of Mechanical Design, Vol. 127, No. 6, 2005, pp. 1077.
36. Jin, R., W. Chen, and T. W. Simpson. Comparative Studies of Metamodeling Techniques Under Multiple Modeling Criteria. Structural and Multidisciplinary Optimization, Vol. 23, No. 1, 2001, pp. 1–13.
37. Friedman, J. H. Multivariate Adaptive Regression Splines. The Annals of Statistics, Vol. 19, No. 1, 1991, pp. 1–67.
38. Gutmann, H.-M. A Radial Basis Function Method for Global Optimization. Journal of Global Optimization, Vol. 19, 2001, pp. 201–227.
39. Regis, R. G., and C. a. Shoemaker. Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions. Journal of Global Optimization, Vol. 31, 2005, pp. 153–171.
40. Mullur, A. A., and A. Messac. Extended Radial Basis Functions : More Flexible and Effective Metamodeling. AIAA Journal, Vol. 43, No. 6, 2005, pp. 1306–1315.
41. Matheron, G. Principles of geostatistics. Economic Geology, Vol. 58, 1963, pp. 1246–1266.
42. Sacks, J., W. J. Welch, T. J. Mitchell, and H. P. Wynn. Design and Analysis of Computer Experiments. Statistical Science, Vol. 4, No. 4, 1989, pp. 409–423.
43. Jones, D. R., M. Schonlau, and J. William. Efficient Global Optimization of Expensive Black-Box Functions. Journal, Vol. 13, 1998, pp. 455–492.
44. Cortes, C., and V. Vapnik. Support-Vector Networks. Machine Learning, Vol. 20, No. 3, 1995, pp. 273–297.
45. Vapnik, V., S. E. Golowich, and A. Smola. Support Vector Method for Function Approximation, Regression Estimation, and Signal Processing. Proceedings of the 1996 Neural Information Processing Systems Conference, 1996, pp. 281–287.
46. Kim, B.-S., Y.-B. Lee, and D.-H. Choi. Comparison study on the accuracy of metamodeling technique for non-convex functions. Journal of Mechanical Science and Technology, Vol. 23, No. 4, 2009, pp. 1175–1181.
47. Yuan, R., and B. Guangchen. 2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing, 2009.
48. Chowdhury, M., A. Alouani, and F. Hossain. Comparison of ordinary kriging and artificial neural network for spatial mapping of arsenic contamination of groundwater. Stochastic Environmental Research and Risk Assessment, Vol. 24, No. 1, 2008, pp. 1–7.
49. Paiva, R. M., A. R. D. Carvalho, C. Crawford, and A. Suleman. Comparison of Surrogate Models in a Multidisciplinary Optimization Framework for Wing Design. AIAA Journal, Vol. 48, No. 5, 2010, pp. 995–1006.
50. Matias, J. M., A. Vaamonde, J. Taboada, and W. Gonzales-Manteiga. Comparison of Kriging and Neural Networks With Application to the Exploitation of a Slate Mine 1. Mathematical Geology, Vol. 36, No. 4, 2004, pp. 463–486.
51. Müller, J., and R. Piché. Mixture surrogate models based on Dempster-Shafer theory for global optimization problems. Journal of Global Optimization, Vol. 51, No. 1, 2010, pp. 79–104.
52. Viana, F. a. C., R. T. Haftka, and L. T. Watson. Efficient global optimization algorithm assisted by multiple surrogate techniques. Journal of Global Optimization, Vol. 56, No. 2, 2013, pp. 669–689.
53. Chen, A., K. Subprasom, and Z. Ji. A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem. Optimization and Engineering, Vol. 7, No. 3, 2006, pp. 225–247.
54. Stevanovic, A., J. Stevanovic, and C. Kergaye. Optimization of traffic signal timings based on surrogate measures of safety. Transportation Research Part C: Emerging Technologies, Vol. 32, 2013, pp. 159–178.
55. Xiong, Y., and J. B. Schneider. Transportation Network Design Using a Cumulative Genetic Algorithm and Neural Network. Transportation Research Record: Journal of the Transportation Research Board, No. 1364, 1992, .
56. Bielli, M., P. Carotenuto, and G. Confessore. A New Approach for Transport Network Design and Optimization. 38th Congress of the European Regional Science Association, 1998.
57. Regis, R. G., and C. a. Shoemaker. A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions. INFORMS Journal on Computing, Vol. 19, No. 4, 2007, pp. 497–509.
58. Osorio Pizano, C., and M. Bierlaire. A simulation-based optimization framework for urban traffic control. Transport and Mobility Laboratory (Ecole Polytechnique Fédérale de Lausanne), 2010.
59. Osorio, C., and L. Chong. An efficient simulation-based optimization algorithm for large-scale transportation problems. Proceedings of the 2012 Winter Simulation Conference (WSC), 2012, pp. 1 – 11.
60. Mockus, J. On Bayesian methods for seeking the extremum. Optimization techniques IFIP International Conference Novosibirsk, 1974, pp. 400–404.
61. Knowles, J. ParEGO : A Hybrid Algorithm With On-Line Landscape Approximation for Expensive Multiobjective Optimization Problems. IEEE Transactions on Evolutionary Computation, Vol. 10, No. 1, 2005, pp. 50–66.
62. Jeong, S., and S. Obayashi. Efficient Global Optimization (EGO) for Multi-Objective Problem and Data Mining. 2005 IEEE Congress on Evolutionary Computation, Vol. 3, 2005, pp. 2138–2145.
63. Zitzler, E., and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, 1999, pp. 257–271.
64. Zitzler, E., L. Thiele, M. Laumanns, C. M. Fonseca, and V. Grunert. Performance Assessment of Multiobjective Optimizers : An Analysis and Review. IEEE Transactions on Evolutionary Computation, Vol. 7, No. 2, 2003, pp. 117–132.
65. Rasmussen, C. E., and C. K. I. Williams. Gaussian processes in machine learning. The MIT Press, 2006.
66. Rasmussen, C. E., and H. Nickisch. Gaussian Process Regression and Classification Toolbox Version 3.1 for Matlab 7.x., 2010.
67. Knowles, J., D. Corne, and A. Reynolds. Noisy Multiobjective Optimization on a Budget of 250 Evaluations. Evolutionary Multi-Criterion Optimization, 5th International Conference, Nantes, France, 2009, pp. 36–50.
68. Wagner, T., M. Emmerich, A. Deutz, and W. Ponweiser. On Expected-Improvement Criteria for Model-based Multi-objective Optimization. PPSN XI, Part I, LNCS 6238, Krakow, Poland, 2010, pp. 718–727.
69. Do, C. B. Gaussian processes. 2007, pp. 1–13. Available at: http://see.stanford.edu/materials/aimlcs229/cs229-gp.pdf.
70. Rasmussen, C. E. minimize.m. 2010, Available at: http://learning.eng.cam.ac.uk/carl/code/minimize/minimize.m.
71. Hansen, N., and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, Vol. 9, No. 2, 2001, pp. 159–195.
72. Lamotte, R. A. F., and C. Alecsandru. Fast Multi-Objective Optimization for Continuous Network Design Problems Based on Gaussian Process Models. Proceedings of the 93rd Annual Meeting of the Transportation Research Board, Washington, D.C., 2014.
73. Pictometry International. Aerial photograph. 2012.
74. Huang, D., T. T. Allen, W. I. Notz, and N. Zheng. Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models. Journal of Global Optimization, Vol. 34, No. 3, 2006, pp. 441–466.
75. J. Forrester, A. I., A. J. Keane, and N. W. Bressloff. Design and Analysis of “Noisy” Computer Experiments. American Institute of Aeronautics and Astronotics Journal, Vol. 44, No. 10, 2006, pp. 2331–2339.
76. Ankenman, B., B. L. Nelson, and J. Staum. Stochastic Kriging for Simulation Metamodeling. Operations Research, Vol. 58, No. 2, 2010, pp. 371–382.
77. Sasena, M. J. Flexibility and Efficiency Enhancements for Constrained Global Design Optimization with Kriging Approximations. Ph. D. diss., University of Michigan, 2002.
78. Lophaven, S. N., H. B. Nielsen, and J. Søndergaard. Aspects of the matlab toolbox dace. 2002.
79. The MathWorks. Documentation Center - R2013b Documentation - Choosing a Solver. 2014, Available at: http://www.mathworks.com/help/optim/ug/choosing-a-solver.html#bsbqd7i [Accessed February 1, 2014].
80. Vanhatalo, J., and A. Vehtari. Modelling local and global phenomena with sparse Gaussian processes. Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, 2008.
81. Rasmussen, C. E., and Z. Ghahramani. Infinite Mixtures of Gaussian Process Experts. Advances in Neural Informaiton Processing Systems 14, 2002, pp. 881–888.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics