Tối Ưu Hóa Đa Mục Tiêu Trong Điều Khiển Đèn Giao Thông

• Tác giả: Prof. Yingjie Yang
• Trường học: De Montfort University
• Chuyên ngành: Intelligent Transport Systems
• Đề tài: Tối Ưu Hóa Đa Mục Tiêu Trong Điều Khiển Đèn Giao Thông
• Loại tài liệu: thesis
• Năm xuất bản: 2019
• Địa điểm: Leicester

• Abstract
• Acknowledgements
• Contents
• 1. CHƯƠNG 1: INTRODUCTION
• 1.1. Motivation
• 1.2. Traffic Signal Control Systems
• 1.2.1. Introduction to Traffic Signal Control Systems
• 1.2.2. Fundamental Definitions of Traffic Signal Control Systems
• 1.2.3. Overview of Traffic Signal Control Systems
• 1.2.4. Performance Measures of Traffic Signal Control Systems
• 1.3. Aims and objectives
• 1.4. Major Contributions of the Thesis
• 1.5. Simulation of Urban Mobility (SUMO)
• 1.6. Multi-objective evolutionary algorithms
• 1.6.1. Definition of Multi-objective Optimization Problems and Basic Concepts
• 1.6.2. General Framework of Multi-objective Evolutionary Algorithms
• 1.7. Surrogate-assisted evolutionary algorithms
• 2. CHƯƠNG 2: EVOLUTIONARY ALGORITHMS AND SURROGATE MODELS
• 2.1. Evolutionary algorithms vs. surrogates-assisted evolutionary algorithms
• 2.2. Strategies for managing surrogates
• 2.2.1. Model management: its roles and classification
• 2.2.2. Criteria for choosing individuals for re-evaluation
• 2.2.3. Techniques for constructing surrogates
• 2.2.4. Artificial Neural Networks
• 2.3. Multi-objective Traffic Signal Optimization
• 2.3.1. Traffic Signal Optimization using MOEAs
• 2.3.2. Multi-objective Traffic Signal Optimization using Local Search based MOEAs
• 2.4. Objectives in Traffic Signal Optimization
• 2.4.1. Optimization Objectives in Traffic Signal Control
• 2.4.2. Objective Calculation using Mathematical Programming Methods
• 2.4.3. Objective Calculation using Simulation-based Methods
• 2.5. Reducing Computational Cost using Surrogate Models
• 2.5.1. Computational Cost of Traffic Signal Optimization using MOEAs and Traffic Simulators
• 2.5.2. Techniques for constructing surrogates
• 2.5.3. Surrogate Assisted Optimization in Transportation
• 2.6. The local search strategy
• 2.6.1. Creating neighbours of a solution
• 2.6.2. Motivation of the local search method
• 2.6.3. The flow of the proposed local search
• 2.7. NS-LS algorithm
• 2.7.1. Overview of NS-LS
• 2.7.2. The flow of NS-LS
• 2.7.3. Design of the evolutionary search
• 2.7.3.1. Selection and Reproduction Operators
• 2.8. The surrogate model
• 2.8.1. Constructing a surrogate model
• 2.8.1.1. Choosing the model
• 2.8.1.2. The training algorithm
• 2.8.1.3. The error function
• 2.8.2. Updating a surrogate model
• 2.9. Fitness evaluation scheme
• 2.9.1. The motivation of the fitness evaluation scheme
• 2.9.2. The closeness of two solutions
• 2.9.3. The framework of the fitness evaluation scheme
• 2.10. SA-LS algorithm
• 2.10.1. Overview of SA-LS
• 2.10.2. The flow of SA-LS
• 3. CHƯƠNG 3: TRAFFIC SCENARIOS AND PERFORMANCE ASSESSMENT
• 3.1. Introduction to the traffic scenario of Andrea Costa
• 3.2. Introduction to the traffic scenario of Pasubio
• 3.3. Extracting optimization objective values from SUMO output
• 3.4. Indicators for Performance Assessment
• 3.5. Experimental design for evaluating the performance of the algorithms
• 3.5.1. Experiment 1 - Benchmark functions
• 3.5.2. Experiments using real-time traffic scenarios simulated by SUMO
• 3.5.2.1. Experiment 2 - Andrea Costa scenario
• 3.5.2.2. Experiment 3 - Pasubio scenario
• 7. CHƯƠNG 7: CONCLUSIONS, RECOMMENDATIONS, AND FUTURE WORK
• 7.1. Key findings of the research
• 7.2. Key contributions of the research
• 7.3. Limitations of the Research
• 7.4. Recommendations and Future Work
• A Published Papers
• B Mean hypervolume with standard deviation of the algorithms in Experiment 2
• C Mean hypervolume with standard deviation of the algorithms in Experiment 3
• Bibliography
• List of Figures
• List of Tables
• Abbreviations
• Symbols

I. Tổng Quan Về Điều Khiển Đèn Giao Thông Thông Minh Hiện Nay

Giao thông đóng vai trò quan trọng trong xã hội, góp phần vào tăng trưởng kinh tế, phát triển xã hội và cải thiện đời sống. Tuy nhiên, lĩnh vực giao thông đang đối mặt với nhiều thách thức, đặc biệt là ở khu vực đô thị. Tình trạng ùn tắc giao thông nghiêm trọng dẫn đến tăng tiêu thụ nhiên liệu, ô nhiễm không khí, gây ảnh hưởng tiêu cực đến kinh tế. Giảm số lượng tai nạn và thương tích do tai nạn giao thông là một thách thức lớn, đặc biệt ở các nước có thu nhập thấp và trung bình. Theo báo cáo toàn cầu về an toàn đường bộ năm 2018 của Tổ chức Y tế Thế giới, khoảng 1,35 triệu người chết mỗi năm do tai nạn giao thông. Giảm lượng khí thải giao thông là một nhiệm vụ cấp bách vì ngành vận tải là tác nhân chính gây ra hiện tượng nóng lên toàn cầu. Để giải quyết những vấn đề này, có thể áp dụng nhiều phương pháp như xây dựng đường mới, mở rộng hệ thống giao thông hiện có, tối ưu hóa hiệu suất của hệ thống giao thông hiện tại và xây dựng chính sách giao thông. Tùy thuộc vào tình hình và đặc điểm của từng khu vực, các phương pháp phù hợp và hiệu quả sẽ được lựa chọn.

1.1. Tầm Quan Trọng Của Hệ Thống Giao Thông Thông Minh ITS

Đối với các thành phố không còn không gian để xây dựng đường mới, việc nâng cấp và tối ưu hóa hệ thống giao thông hiện có để trở nên thông minh hơn là một xu hướng hấp dẫn trong nghiên cứu giao thông. Hệ thống giao thông thông minh (ITS) đã được đề xuất và triển khai ở nhiều thành phố trên thế giới để cải thiện hiệu suất của lĩnh vực giao thông. ITS kết hợp công nghệ thông tin và truyền thông vào cơ sở hạ tầng của hệ thống giao thông để cải thiện hiệu suất, hiệu quả và an toàn.

1.2. Vai Trò Của Điều Khiển Đèn Giao Thông Trong ITS

Mục đích của ITS là tận dụng các công nghệ tiên tiến để giải quyết các vấn đề giao thông, ví dụ như an toàn, ùn tắc giao thông, hiệu quả vận tải và bảo vệ môi trường bằng cách tạo ra những con đường thông minh hơn. Hệ thống điều khiển đèn giao thông là một công cụ hiệu quả về chi phí cho quản lý giao thông đô thị và đã trở thành một lĩnh vực nghiên cứu quan trọng trong ITS. Nó điều khiển giao thông tại các giao lộ đường bộ, xác định luồng nào được phép đi qua và luồng nào phải dừng lại.

II. Thách Thức Trong Tối Ưu Hóa Đa Mục Tiêu Đèn Giao Thông

Hoạt động chính xác và hiệu quả của điều khiển đèn giao thông có ý nghĩa quan trọng đối với hiệu suất của mạng lưới giao thông đô thị và được coi là một yếu tố thiết yếu của ITS. Vai trò của tối ưu hóa đèn giao thông là cải thiện đáng kể hiệu suất mạng lưới giao thông bằng cách tối ưu hóa các mục tiêu như giảm thời gian chờ đợi. Tuy nhiên, việc tối ưu hóa này gặp nhiều khó khăn, đặc biệt khi phải cân bằng nhiều mục tiêu khác nhau. Việc chỉ tập trung vào một mục tiêu (ví dụ: giảm thời gian chờ đợi) có thể làm ảnh hưởng đến các mục tiêu khác (ví dụ: giảm lượng khí thải). Do đó, cần có các phương pháp tối ưu hóa đa mục tiêu hiệu quả.

2.1. Sự Phức Tạp Của Bài Toán Tối Ưu Đa Mục Tiêu

Các mục tiêu thường xung đột lẫn nhau, ví dụ như giảm thời gian chờ đợi có thể dẫn đến tăng tốc độ lưu thông nhưng đồng thời làm tăng lượng khí thải. Bài toán tối ưu hóa đa mục tiêu yêu cầu các phương pháp tiếp cận phức tạp để tìm ra các giải pháp cân bằng, đáp ứng tốt nhất cho tất cả các mục tiêu. Theo nghiên cứu của Phuong Thi Mai Nguyen (2019), việc cân bằng giữa các mục tiêu khác nhau là một thách thức lớn trong điều khiển đèn giao thông.

2.2. Giới Hạn Về Mặt Tính Toán Trong Điều Khiển Đèn Giao Thông Thích Ứng

Các phương pháp tối ưu hóa dựa trên mô phỏng (simulation-based optimization) thường tốn kém về mặt tính toán, đặc biệt khi sử dụng các mô hình mô phỏng giao thông vi mô (microscopic traffic simulators). Việc đánh giá một giải pháp có thể mất nhiều thời gian, làm hạn chế khả năng khám phá không gian giải pháp một cách hiệu quả. Yêu cầu về thời gian phản hồi nhanh chóng trong các hệ thống đèn giao thông đáp ứng nhu cầu thực tế đặt ra áp lực lớn lên hiệu quả của các thuật toán tối ưu hóa.

III. Phương Pháp Tối Ưu Hóa Đa Mục Tiêu Bằng Thuật Toán Tiến Hóa

Thuật toán tiến hóa (Evolutionary Algorithms - EAs) là một lựa chọn phổ biến để giải quyết các bài toán tối ưu hóa đa mục tiêu trong điều khiển đèn giao thông. Các thuật toán này có khả năng tìm kiếm không gian giải pháp một cách hiệu quả và tìm ra các giải pháp Pareto tối ưu (Pareto optimal solutions) - các giải pháp mà không thể cải thiện một mục tiêu nào mà không làm giảm các mục tiêu khác. Một số thuật toán tiến hóa phổ biến được sử dụng trong lĩnh vực này bao gồm NSGA-II và MOEA/D. Tuy nhiên, việc sử dụng các thuật toán này với các mô hình mô phỏng giao thông vi mô có thể rất tốn thời gian.

3.1. Giới Thiệu Về Thuật Toán NSGA II Trong Tối Ưu Hóa Luồng Giao Thông

NSGA-II (Non-dominated Sorting Genetic Algorithm II) là một thuật toán tiến hóa đa mục tiêu phổ biến. NSGA-II sử dụng khái niệm thống trị Pareto để xếp hạng các giải pháp và duy trì một tập hợp các giải pháp không bị thống trị. Thuật toán này cũng sử dụng một toán tử lựa chọn (selection operator) dựa trên độ đa dạng (diversity) để duy trì sự đa dạng của quần thể.

3.2. Ưu Điểm Của Thuật Toán MOEA D Trong Điều Khiển Giao Thông Thông Minh

MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition) là một thuật toán tiến hóa đa mục tiêu khác, dựa trên phân rã (decomposition) bài toán thành nhiều bài toán con (sub-problems). MOEA/D sử dụng một tập hợp các hàm mục tiêu vô hướng (scalarized objective functions) để đánh giá các giải pháp và một toán tử lân cận (neighborhood operator) để chia sẻ thông tin giữa các bài toán con.

IV. Tối Ưu Hóa Kết Hợp Tìm Kiếm Cục Bộ Và Mô Hình Surrogates

Để cải thiện hiệu quả của tối ưu hóa đa mục tiêu trong điều khiển đèn giao thông, có thể sử dụng các phương pháp kết hợp tìm kiếm cục bộ (local search) và mô hình surrogates. Tìm kiếm cục bộ giúp cải thiện các giải pháp hiện có bằng cách khám phá các vùng lân cận của chúng. Mô hình surrogates là các mô hình xấp xỉ (approximation models) được xây dựng dựa trên các giải pháp đã được đánh giá. Mô hình surrogates có thể được sử dụng để ước tính hiệu suất của các giải pháp mới, giảm số lượng đánh giá tốn kém bằng mô phỏng giao thông.

4.1. Chiến Lược Tìm Kiếm Cục Bộ Để Cải Thiện Độ Trễ Đèn Giao Thông

Chiến lược tìm kiếm cục bộ tập trung vào việc cải thiện các giải pháp hiện có bằng cách khám phá các vùng lân cận của chúng. Điều này có thể giúp tìm ra các giải pháp tốt hơn trong một khoảng thời gian ngắn hơn so với việc chỉ sử dụng các thuật toán tiến hóa. Nguyen (2019) đã đề xuất thuật toán NS-LS, một thuật toán kết hợp NSGA-II với tìm kiếm cục bộ.

4.2. Xây Dựng Mô Hình Surrogates Để Giảm Chi Phí Tính Toán

Mô hình surrogates có thể giúp giảm chi phí tính toán bằng cách ước tính hiệu suất của các giải pháp mới mà không cần phải chạy mô phỏng giao thông tốn kém. Các mô hình surrogates có thể được xây dựng bằng nhiều kỹ thuật khác nhau, chẳng hạn như mạng nơ-ron nhân tạo (artificial neural networks) và Gaussian process regression. Nguyen (2019) đã đề xuất thuật toán SA-LS, một thuật toán sử dụng mô hình surrogates để hỗ trợ tìm kiếm cục bộ.

V. Ứng Dụng Thực Tế Và Kết Quả Nghiên Cứu Về Tối Ưu Hóa Giao Thông

Các phương pháp tối ưu hóa đa mục tiêu trong điều khiển đèn giao thông đã được ứng dụng thành công trong nhiều tình huống thực tế. Các nghiên cứu đã chứng minh rằng các phương pháp này có thể giúp giảm ùn tắc giao thông, giảm lượng khí thải và cải thiện an toàn giao thông. Ví dụ, Nguyen (2019) đã đánh giá các thuật toán NS-LS và SA-LS trên hai tình huống giao thông thực tế: Andrea Costa và Pasubio.

5.1. Đánh Giá Hiệu Quả Trên Mô Hình Giao Thông Andrea Costa

Tình huống Andrea Costa là một mạng lưới giao thông thực tế ở Bologna, Ý. Nguyen (2019) đã sử dụng mô hình này để so sánh hiệu suất của các thuật toán NS-LS, SA-LS, NSGA-II và MOEA/D. Kết quả cho thấy rằng các thuật toán NS-LS và SA-LS có thể tối ưu hóa hiệu quả thời gian đèn giao thông trong tình huống này.

5.2. Thử Nghiệm Tối Ưu Hóa Trên Mạng Lưới Giao Thông Pasubio

Tình huống Pasubio là một mạng lưới giao thông thực tế khác ở Bologna, Ý. Nguyen (2019) đã sử dụng mô hình này để đánh giá hiệu suất của các thuật toán NS-LS, SA-LS, NSGA-II và MOEA/D. Kết quả cũng cho thấy rằng các thuật toán NS-LS và SA-LS có thể tối ưu hóa hiệu quả thời gian đèn giao thông trong tình huống này.

VI. Triển Vọng Tương Lai Cho Điều Khiển Đèn Giao Thông Thông Minh

Lĩnh vực tối ưu hóa đa mục tiêu trong điều khiển đèn giao thông vẫn còn nhiều tiềm năng phát triển. Các hướng nghiên cứu trong tương lai có thể bao gồm: Phát triển các thuật toán tối ưu hóa hiệu quả hơn, có thể xử lý các bài toán lớn hơn và phức tạp hơn. Sử dụng dữ liệu giao thông theo thời gian thực (real-time traffic data) để điều khiển đèn giao thông thích ứng. Tích hợp ứng dụng trí tuệ nhân tạo (AI) và học máy (Machine Learning) để dự đoán lưu lượng giao thông và điều chỉnh thời gian đèn giao thông một cách linh hoạt. Nghiên cứu các phương pháp để giảm thiểu tác động của điều khiển đèn giao thông đến môi trường.

6.1. Ứng Dụng Học Máy Để Dự Đoán Lưu Lượng Giao Thông

Học máy có thể được sử dụng để dự đoán lưu lượng giao thông dựa trên dữ liệu lịch sử và dữ liệu thời gian thực. Thông tin này có thể được sử dụng để điều chỉnh thời gian đèn giao thông một cách chủ động, giúp giảm ùn tắc giao thông.

6.2. Phát Triển Các Thuật Toán Điều Khiển Tối Ưu Tiên Tiến

Nghiên cứu và phát triển các thuật toán điều khiển tối ưu tiên tiến, có khả năng thích ứng với các điều kiện giao thông thay đổi và cân bằng nhiều mục tiêu khác nhau, là một hướng đi quan trọng để cải thiện hiệu quả của điều khiển đèn giao thông.