DMU’s Interdisciplinary research Group in Intelligent Transport Systems, (DIGITS) Faculty of Computing, Engineering and Media Multi-objective Optimization in Traffic Signal Control Supervisor: Author: Prof. Yingjie Yang Phuong Thi Mai Nguyen Dr. Benjamin Passow Dr. Lipika Deka A thesis submitted in fulfilment of the requirements for the degree of Doctor of Philosophy August 2019 Abstract Traffic Signal Control systems are one of the most popular Intelligent Transport Sys- tems and they are widely used around the world to regulate traffic flow.
Recently, complex optimization techniques have been applied to traffic signal control systems to improve their performance. Traffic simulators are one of the most popular tools to eval- uate the performance of a potential solution in traffic signal optimization. For that reason, researchers commonly optimize traffic signal timing by using simulation-based approaches. Although evaluating solutions using microscopic traffic simulators has sev- eral advantages, the simulation is very time-consuming.
Multi-objective Evolutionary Algorithms (MOEAs) are in many ways superior to tra- ditional search methods. They have been widely utilized in traffic signal optimization problems. However, running MOEAs on traffic optimization problems using microscopic traffic simulators to estimate the effectiveness of solutions is time-consuming. Thus, MOEAs which can produce good solutions at a reasonable processing time, especially at an early stage, is required.
Anytime behaviour of an algorithm indicates its ability to provide as good a solution as possible at any time during its execution. Therefore, optimization approaches which have good anytime behaviour are desirable in evaluation traffic signal optimization. Moreover, small population sizes are inevitable for scenarios where processing capabilities are limited but require quick response times. In this work, two novel optimization algorithms are introduced that improve anytime behaviour and can work effectively with various population sizes.
NS-LS is a hybrid of Non-dominated Sorting Genetic Algorithm II (NSGA-II) and a local search which has the ability to predict a potential search direction. NS-LS is able to produce good solutions at any running time, therefore having good anytime behaviour. Utilizing a local search can help to accelerate the convergence rate, however, computational cost is not considered in NS-LS. A surrogate-assisted approach based on local search (SA-LS) which is an enhancement of NS-LS is also introduced.
SA-LS uses a surrogate model constructed using solutions which already have been evaluated by a traffic simulator in previous generations. NS-LS and SA-LS are evaluated on the well-known Benchmark test functions: ZDT1 and ZDT2, and two real-world traffic scenarios: Andrea Costa and Pasubio. The proposed algorithms are also compared to NSGA-II and Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D). The results show that NS-LS and SA-LS can ef- fectively optimize traffic signal timings of the studied scenarios.
The results also confirm that NS-LS and SA-LS have good anytime behaviour and can work well with different population sizes. Furthermore, SA-LS also showed to produce mostly superior results as compared to NS-LS, NSGA-II, and MOEA/D. Acknowledgements I would like to express my sincere gratitude to my supervisory team Prof. Yingjie Yang, Dr.
Passow and Dr. Lipika Deka who provided unstinting support with their insights, expertise, and valuable comments. Without their encouragement and support, this thesis would not have been completed on a limited time frame. Especially, I would like to expand deepest thank to my dedicated supervisor Dr.Passow who share his pearls of wisdom during this research, devoted his time and made valuable comments for better insight.
Also, inspiration and encouragement play important role in keeping me moving forward. I gratefully thank the Ministry of Education and Training of Vietnam for funding me a four-year scholarship for my study in the UK. Without this financial sponsorship, I would not be able to come to study in the UK. My sincere thanks also go to the De Montfort University Interdisciplinary research Group in Intelligent Transport Systems (DIGITS) for the financial support to participate the WCCI 2016 conference in Vancouver and the International student workshop 2016 in Wroclaw, Poland.
I also would like to thank all member of DIGITs for offering assistance to my study. Last but not least, I would like to thank my parents and my sister for always encouraging me throughout this journey. Especially, I owe thanks to a very special person, my husband, for his love, support, and understanding during my pursuit of Ph. I greatly appreciate his belief in me that gave me extra strength to get things done.
ii Contents Abstract i Acknowledgements ii Contents iii List of Figures vii List of Tables ix Abbreviations x Symbols xi 1 Introduction 1 1.3 Aims and objectives .4 Major Contributions of the Thesis .2 Traffic Signal Control Systems .1 Introduction to Traffic Signal Control Systems .2 Fundamental Definitions of Traffic Signal Control Systems .3 Overview of Traffic Signal Control Systems .4 Performance Measures of Traffic Signal Control Systems .2 Simulation of Urban Mobility (SUMO) .4 Multi-objective evolutionary algorithms .1 Definition of Multi-objective Optimization Problems and Basic Concepts .2 General Framework of Multi-objective Evolutionary Algorithms .5 Surrogate-assisted evolutionary algorithms. 27 iii Contents iv 2.1 Evolutionary algorithms vs. surrogates-assisted evolutionary al- gorithms .2 Strategies for managing surrogates .1 Model management: its roles and classification .2 Criteria for choosing individuals for re-evaluation .3 Techniques for constructing surrogates .4 Artificial Neural Networks .1 Multi-objective Traffic Signal Optimization .2 Traffic Signal Optimization using MOEAs .3 Multi-objective Traffic Signal Optimization using Local Search based MOEAs .2 Objectives in Traffic Signal Optimization .1 Optimization Objectives in Traffic Signal Control .2 Objective Calculation using Mathematical Programming Methods 44 3.3 Objective Calculation using Simulation-based Methods .3 Reducing Computational Cost using Surrogate Models .1 Computational Cost of Traffic Signal Optimization using MOEAs and Traffic Simulators .2 Techniques for constructing surrogates .3 Surrogate Assisted Optimization in Transportation .2 The local search strategy .1 Creating neighbours of a solution .2 Motivation of the local search method .3 The flow of the proposed local search .3 NS-LS algorithm .1 Overview of NS-LS .2 The flow of NS-LS .3 Design of the evolutionary search .2 Selection and Reproduction Operators .4 The surrogate model .1 Constructing a surrogate model .1 Choosing the model .2 The training algorithm .3 The error function .2 Updating a surrogate model .5 Fitness evaluation scheme .1 The motivation of the fitness evaluation scheme .2 The closeness of two solutions .3 The framework of the fitness evaluation scheme .6 SA-LS algorithm .1 Overview of SA-LS .2 The flow of SA-LS .1 Introduction to the traffic scenario of Andrea Costa .2 Introduction to the traffic scenario of Pasubio .3 Extracting optimization objective values from SUMO output .4 Indicators for Performance Assessment .5 Experimental design for evaluating the performance of the algorithms .1 Experiment 1 - Benchmark functions .2 Experiments using real-time traffic scenarios simulated by SUMO .1 Experiment 2 - Andrea Costa scenario .2 Experiment 3 - Pasubio scenario .2 Experiment 1: ZDT1 and ZDT2 test functions .3 Results of experiments using traffic scenarios .1 Results of Experiment 2 - Andrea Costa .2 Results of Experiment 3. 133 7 Conclusions, Recommendations, and Future Work 135 7.2 Key findings of the research .3 Key contributions of the research .4 Limitations of the Research .5 Recommendations and Future Work.
144 A Published Papers 145 Contents vi B Mean hypervolume with standard deviation of the algorithms in Ex- periment 2 146 C Mean hypervolume with standard deviation of the algorithms in Ex- periment 3 150 Bibliography 154 List of Figures 2.1 Movements in a two-phase system.2 A diagram of two-phase signal system .3 The structure of the node file of a traffic scenario simulated by SUMO .4 The structure of the edge file of a traffic scenario simulated by SUMO .5 The structure of the traffic light file of a traffic scenario simulated by SUMO 19 2.6 The Netconvert command to generate a traffic network file of a scenario simulated by SUMO .7 The structure of the route file of a traffic scenario simulated by SUMO .8 The structure of the configuration file of a traffic scenario simulated by SUMO .1 The neighbour creation: a neighbour nbR(t) is created from solution Ri i (t) (t) based on two other reference solutions Ru and Ru using equation 4.2 The overall optimisation framework of NS-LS.3 The framework of the optimization process in NS-LS .4 Chromosome representation where gi is a variable representing the green duration of i(th) phase.5 Overall structure of the surrogate model.6 Sigmoid function with a = 4.7 Grid search for hyperparameter fine-tuner.8 The n-fold cross validation technique.9 Relationship between distance and approximation error of new solutions and available solutions in the database .10 The framework of the fitness evaluation scheme.11 The framework of the proposed algorithm SA-LS .1 The traffic network of Andra Costa extracted from Open Street Map .2 The Andrea Costa traffic map simulated by SUMO .3 The traffic flow of three days in Bologna city provided by the municipality 95 5.4 Case study area in Andrea Costa .5 Phases of the signal control program of the case study in Andrea Costa.6 A traffic network of Pasubio taken from Open Street Map .7 The Pasubio road network simulated by SUMO.8 Case study area in Pasubio .9 Phases of the signal control program of the case study in Pasubio. 101 vii List of Figures viii 5.10 A part of a trip information output file from the Andrea Costa scenario. This file is produced after the simulation finished containing departure and arrival times, time loss, and route length and other information.11 A part of the acosta detectors.12 A part of the e1 output.xml file from Andrea Costa scenario.1 The mean of HV on 20 runs obtained by NS-LS, SA-LS, NSGA-II, and MOEA/D over the number of evaluations using the original objective function. The objective function is ZDT1.2 Mean of HV on 20 runs obtained by NS-LS, SA-LS, NSGA-II, and MOEA/D over the number of evaluations using the original objective function.
The objective function is ZDT2.3 Average HV with standard deviation on 20 independent runs obtained by MOEA/D, NSGA-II, NS-LS, and SA-LS at the end of the optimization process in Experiment 2.4 Mean of HV on 20 runs obtained by NS-LS, SA-LS, NSGA-II, and MOEA/D over the number of evaluations using SUMO in Experiment 2.5 Mean HV with standard deviation of MOEA/D, NSGA-II, NS-LS, and SA-LS on 20 different runs in population size 20 in Experiment 2.6 Distribution of solutions in the non-dominated set achieved by NS-LS, SA-LS, NSGA-II, and MOEA/D at the end of the optimization process in Experiment 2. These solutions are selected from the final solutions of 20 runs.7 Average HV with standard deviation on 20 independent runs obtained by MOEA/D, NSGA-II, NS-LS, and SA-LS at the end of the optimization process in Experiment 3.8 Mean of HV on 20 runs obtained by NS-LS, SA-LS, NSGA-II, and MOEA/D over the number of evaluations using SUMO in Experiment 3.9 Mean HV with standard deviation of MOEA/D, NSGA-II, NS-LS, and SA-LS on 20 different runs in population size 20 in Experiment 3.10 Distribution of solutions in the non-dominated set achieved by NS-LS, SA-LS, NSGA-II, and MOEA/D at the end of the optimization process in Experiment 3. These solutions are selected from the final solutions of 20 runs.1 Mean HV with standard deviation of NS-LS, SA-LS, MOEA/D, and NSGA-II on 20 different runs with population size 40 in Experiment 2.2 Mean HV with standard deviation of NS-LS, SA-LS, MOEA/D, and NSGA-II on 20 different runs with population size 60 in Experiment 2.3 Mean HV with standard deviation of NS-LS, SA-LS, MOEA/D, and NSGA-II on 20 different runs with population size 80 in Experiment 2.1 Mean HV with standard deviation of NS-LS, SA-LS, MOEA/D, and NSGA-II on 20 different runs with population size 40 in Experiment 3.2 Mean HV with standard deviation of NS-LS, SA-LS, MOEA/D, and NSGA-II on 20 different runs with population size 60 in Experiment 3.3 Mean HV with standard deviation of NS-LS, SA-LS, MOEA/D, and NSGA-II on 20 different runs with population size 80 in Experiment 3. 153 List of Tables 3.1 Evolutionary algorithms in traffic signal control systems.2 Optimization objectives in traffic signal optimization using MOEAs.