Tổng quan nghiên cứu

Thực trạng ùn tắc và tai nạn giao thông tại các đô thị đang là bài toán nhức nhối đối với nền kinh tế và xã hội Việt Nam. Thống kê từ Ủy ban An toàn Giao thông Quốc gia cho thấy hàng năm cả nước ghi nhận từ 9.000 đến 13.000 ca tử vong do tai nạn giao thông, trong đó tai nạn giao thông đường bộ chiếm tỷ trọng áp đảo từ 97% đến 99%, với hơn 70% số vụ liên quan trực tiếp đến ô tô và xe máy. Tại các trung tâm kinh tế lớn, tốc độ gia tăng phương tiện cơ giới cá nhân đã vượt xa năng lực phát triển của mạng lưới hạ tầng. Riêng tại Hà Nội, số lượng phương tiện đăng ký mới trong 3 quý đầu năm 2015 đã đạt mốc 5,5 triệu phương tiện, đẩy tổng lưu lượng xe hoạt động trên thực tế gấp 6 lần sức chịu tải thiết kế của toàn bộ hệ thống đường đô thị.

Các công cụ dẫn đường phổ biến hiện nay như Google Maps, Bing Maps hay bản tin radio VOV Giao thông vẫn bộc lộ hạn chế lớn khi chỉ dựa trên dữ liệu vệ tinh GPS tĩnh hoặc thông tin phản hồi chậm, chưa thể tích hợp dữ liệu mật độ xe theo thời gian thực để chủ động điều hướng phân luồng. Nhằm giải quyết triệt để vấn đề này, luận văn tập trung nghiên cứu ứng dụng kỹ thuật khai phá dữ liệu kết hợp giải thuật tối ưu hóa đàn kiến (Ant Colony System - ACS) trên nền tảng mạng Ad-hoc phương tiện (VANET).

Mục tiêu chính của đề tài là xây dựng mô hình định tuyến thông minh có khả năng tự động thích ứng với biến động giao thông, phát hiện điểm tắc nghẽn và tái định tuyến lộ trình tối ưu cho người lái xe. Nghiên cứu được triển khai thực nghiệm mô phỏng trên mạng lưới giao thông của thủ đô Hà Nội và thành phố Berlin trong giai đoạn năm 2015. Kết quả thực nghiệm khẳng định giải pháp đề xuất giúp rút ngắn tới 48,96% chiều dài lộ trình và giảm từ 5,05% đến 8,13% thời gian di chuyển, mang lại giá trị thực tiễn cao cho việc tối ưu chi phí vận hành và giảm phát thải môi trường trong thời đại kết nối vạn vật.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng tích hợp giữa lý thuyết hệ đa tác tử, kiến trúc mạng truyền thông không dây di động và lý thuyết tối ưu hóa bầy đàn sinh học.

Hệ đa tác tử (Multi-Agent System - MAS) và tác tử thông minh (Intelligent Agent) đóng vai trò khung kiến trúc trung tâm. Mỗi phương tiện tham gia giao thông được mô hình hóa thành một tác tử tự chủ có khả năng cảm nhận môi trường liên tục, phản ứng kịp thời trước các xung đột giao thông và chủ động cộng tác với các tác tử lân cận để giải quyết bài toán phân luồng phi tập trung.

Mạng Ad-hoc phương tiện giao thông (Vehicular Ad Hoc Network - VANET) cung cấp cơ chế kết nối không dây phân tán giữa các phương tiện (V2V) và giữa phương tiện với thiết bị hạ tầng ven đường (V2I). Mạng VANET cho phép mỗi phương tiện hoạt động như một bộ định tuyến di động với bán kính phủ sóng từ 100 đến 300 mét. Khi hai xe di chuyển ngược chiều với vận tốc 25 m/s (tương đương 90 km/h), cửa sổ kết nối vô tuyến trực tiếp chỉ duy trì trong khoảng 5 giây, đòi hỏi các giao thức định tuyến phải có tính thích nghi cao và khả năng chịu lỗi ngắt kết nối liên tục.

Lý thuyết tối ưu hóa bầy đàn, tiêu biểu là giải thuật tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) và biến thể cải tiến Ant Colony System (ACS), mô phỏng cơ chế tìm đường bằng dấu vết mùi pheromone của đàn kiến tự nhiên. Thuật toán sử dụng 4 khái niệm then chốt:

  • Nồng độ vết mùi pheromone biểu thị tri thức tích lũy của toàn đàn trên từng đoạn đường.
  • Thông tin heuristic phản ánh nghịch đảo độ dài vật lý của tuyến đường đang xét.
  • Quy tắc cập nhật vết mùi cục bộ với tham số suy giảm nhằm kích thích việc khám phá các nhánh đường mới chưa từng đi qua.
  • Quy tắc cập nhật vết mùi toàn cục chỉ dành riêng cho lộ trình tối ưu nhất của toàn hệ thống, kết hợp hệ số bay hơi mùi được thiết lập ở mức 0,1 để loại bỏ các quyết định sai lầm.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp mô phỏng thực nghiệm đối sánh (Benchmarking Simulation) dựa trên công cụ phần mềm VANETsim phiên bản 1.2 viết trên nền tảng Java. Hệ thống thử nghiệm được thiết lập trên máy trạm trang bị bộ xử lý Intel Core i5 tốc độ 2,4 GHz, bộ nhớ trong RAM 8GB chuẩn DDR3 và môi trường thực thi OpenJDK 8.

Nguồn dữ liệu không gian được trích xuất trực tiếp từ cơ sở dữ liệu bản đồ mở OpenStreetMap cho hai khu vực đô thị đại diện: khu vực trung tâm thành phố Berlin (Đức) và quận Cầu Giấy, thành phố Hà Nội (Việt Nam). Dữ liệu giao thông vi mô (micro-traffic) mô phỏng chính xác hành vi tăng tốc, giảm tốc và chuyển làn của nhiều chủng loại phương tiện gồm ô tô con dưới 7 chỗ, xe bán tải, xe buýt và xe máy, với quy mô quần thể mô phỏng lên tới 16.000 phương tiện.

Phương pháp chọn mẫu thực nghiệm có chủ đích (purposive sampling) được áp dụng để khảo sát các cặp tọa độ xuất phát và đích đến có mật độ giao thông đông đúc, ví dụ như tuyến đường Holzmarktstraße đến Littenstraße tại Berlin hay trục đường Trần Thái Tông đến ký hiệu tuyến S1204 tại Hà Nội.

Lý do lựa chọn phương pháp phân tích mô phỏng trên phần mềm VANETsim kết hợp kiểm định thuật toán A* đối sánh với thuật toán Ant Colony System là vì công cụ này có kiến trúc phân tách độc lập giữa các module Bản đồ, Tác tử, Giao diện và Định tuyến. Cấu trúc này cho phép can thiệp trực tiếp vào module định tuyến để đo đếm chính xác 3 chỉ số hiệu năng: quãng đường di chuyển thực tế (mét), tổng thời gian hành trình (giây) và thời gian thực thi thuật toán (mili giây), đồng thời chủ động tạo dựng các kịch bản ùn tắc nhân tạo tại các nút giao cắt trọng điểm mà không gây rủi ro hay tốn kém chi phí như thử nghiệm thực địa.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh giữa thuật toán Ant Colony System (ACS) và thuật toán tìm đường kinh điển A* trên hai bản đồ đô thị mang lại các phát hiện cốt lõi:

Thứ nhất, giải thuật ACS thể hiện khả năng tối ưu hóa cự ly vượt trội so với thuật toán A*. Trên bản đồ thành phố Berlin tại tuyến Holzmarktstraße đi Littenstraße, thuật toán A* chỉ dẫn quãng đường dài 1060 mét, trong khi thuật toán ACS tìm ra lộ trình thay thế chỉ dài 541 mét, giúp giảm 48,96% chiều dài di chuyển. Trên hai tuyến thử nghiệm bổ sung tại Berlin là Leipziger Straße - Charlottenstraße và Immanuelkirch - Marienburger, ACS tiếp tục duy trì ưu thế khi giảm cự ly từ 889 mét xuống 624 mét (giảm 29,81%) và từ 730 mét xuống 520 mét (giảm 28,77%). Trên bản đồ Hà Nội từ đường Trần Thái Tông đến tuyến S1204, quãng đường di chuyển theo thuật toán A* là 1150 mét, trong khi ACS rút ngắn về 802 mét, tương đương mức cắt giảm 30,26%.

Thứ hai, thời gian hành trình của phương tiện được cải thiện rõ rệt. Tại Berlin, phương tiện điều hướng bởi ACS hoàn thành lộ trình trong 53,80 giây, nhanh hơn 4,76 giây (giảm 8,13%) so với mức 58,56 giây của A*. Tại Hà Nội, thời gian di chuyển giảm từ 64,12 giây xuống 60,88 giây, tiết kiệm được 3,24 giây (giảm 5,05%) trên một cung đường ngắn.

Thứ ba, mô hình đề xuất sở hữu khả năng tự động nhận diện và né tránh điểm ùn tắc theo thời gian thực. Khi thực nghiệm cố tình gia tăng mật độ xe tại ngã tư Littenstraße - Stralauer Straße (Berlin) và ngã tư Trần Thái Tông - S1583 (Hà Nội), thuật toán ACS đã kích hoạt hàm phạt tắc nghẽn với trọng số thực nghiệm w = 15 cho mỗi xe phía trước. Ngay lập tức, hệ thống tự động chuyển hướng phương tiện qua các tuyến đường thay thế thông thoáng (như tuyến vòng Dircksenstraße - Voltairestraße tại Berlin hoặc tuyến Thành Thái tại Hà Nội), giúp phương tiện không bị kẹt lại tại điểm đen ùn ứ.

Thứ tư, nghiên cứu ghi nhận sự đánh đổi về mặt tài nguyên tính toán. Thời gian thực thi thuật toán của ACS dao động từ 31 đến 41 mili giây (cụ thể là 41 mili giây tại Berlin và 31 mili giây tại Hà Nội), cao hơn mức 18 đến 25 mili giây của thuật toán A*.

Thảo luận kết quả

Nguyên nhân căn bản giúp thuật toán Ant Colony System vượt trội hơn thuật toán A* nằm ở cơ chế tìm kiếm thông minh kết hợp giữa tri thức kinh nghiệm heuristic và thông tin cập nhật mùi pheromone động. Trong khi A* là thuật toán tìm kiếm cục bộ dựa trên hàm chi phí khoảng cách hình học thuần túy, ACS cho phép các kiến nhân tạo thăm dò nhiều nhánh đường song song. Cơ chế cập nhật mùi cục bộ với tham số suy giảm 0,1 làm giảm dần sức hấp dẫn của các đoạn đường vừa có xe đi qua, ngăn ngừa hiện tượng dồn toa và kích thích hệ thống khai phá các tuyến đường ngõ ngách có tổng chi phí thấp hơn.

Dữ liệu so sánh giữa hai thuật toán được tổng hợp minh họa rõ nét qua bảng thống kê hiệu năng đa tiêu chí và biểu đồ cột so sánh tương quan giữa độ dài cung đường và thời gian phản hồi:

Bản đồ đô thị Tuyến đường thử nghiệm Thuật toán áp dụng Khoảng cách (mét) Thời gian di chuyển (giây) Thời gian xử lý (mili giây)
Berlin Holzmarktstraße - Littenstraße A* 1060 58,56 25
Berlin Holzmarktstraße - Littenstraße Ant Colony System 541 53,80 41
Berlin Leipziger - Charlottenstraße A* 889 65,84 19
Berlin Leipziger - Charlottenstraße Ant Colony System 624 61,88 39
Berlin Immanuelkirch - Marienburger A* 730 68,56 23
Berlin Immanuelkirch - Marienburger Ant Colony System 520 63,43 37
Hà Nội Trần Thái Tông - S1204 A* 1150 64,12 18
Hà Nội Trần Thái Tông - S1204 Ant Colony System 802 60,88 31

So với các công bố khoa học trước đây vốn chỉ áp dụng lý thuyết tối ưu đàn kiến trên đồ thị tĩnh, việc tích hợp hàm mục tiêu mở rộng có tính đến trọng số tắc nghẽn n nhân với 15 (trong đó n là số lượng phương tiện đang dồn ứ) là bước tiến có ý nghĩa thực tiễn lớn. Độ trễ tính toán 31 đến 41 mili giây hoàn toàn nằm trong ngưỡng trễ cho phép của các hệ thống viễn thông di động hiện nay, bảo đảm khả năng phản hồi tức thời cho các thiết bị điều hướng trên xe.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu và thực nghiệm, bốn giải pháp trọng tâm được đề xuất nhằm chuyển hóa mô hình định tuyến thông minh vào thực tiễn quản trị đô thị:

Thứ nhất, tích hợp thuật toán Ant Colony System vào hệ thống điều hành giao thông thông minh (Intelligent Transport Systems - ITS) cấp thành phố. Cơ quan thực hiện: Sở Giao thông Vận tải phối hợp cùng các Trung tâm Quản lý và Điều hành Giao thông Đô thị. Mục tiêu hành động: Triển khai thí điểm module định tuyến thông minh trên ứng dụng giao thông công cộng nhằm giảm 20% đến 25% thời gian trễ do ùn ứ tại các nút giao thông trọng điểm. Lộ trình thực hiện: Hoàn thành trong giai đoạn 2026 - 2028.

Thứ hai, tối ưu hóa thuật toán bằng công nghệ điện toán phân tán (Distributed Computing) và tính toán biên (Edge Computing). Chủ thể thực hiện: Các kỹ sư phần mềm hệ thống, viện nghiên cứu công nghệ thông tin và trường đại học. Mục tiêu hành động: Phân bổ quá trình tính toán tìm đường của đàn kiến về các cụm máy chủ biên đặt tại các trạm ven đường (RSU), nhằm kéo giảm thời gian xử lý thuật toán từ mức 31 - 41 mili giây xuống dưới 10 mili giây. Lộ trình thực hiện: Giai đoạn 2026 - 2027.

Thứ ba, chuẩn hóa và mở rộng hạ tầng thiết bị thu phát sóng Ad-hoc trên các phương tiện giao thông công cộng. Chủ thể thực hiện: Các doanh nghiệp vận tải hành khách bằng xe buýt, các hãng taxi cùng sự hỗ trợ của các tập đoàn viễn thông. Mục tiêu hành động: Lắp đặt thiết bị On-Board Unit (OBU) đạt chuẩn kết nối VANET trong bán kính 100 đến 300 mét trên 100% phương tiện vận tải công cộng, tạo mạng lưới nút cảm biến di động liên tục truyền tải dữ liệu mật độ xe về trung tâm điều khiển. Lộ trình thực hiện: Giai đoạn 2027 - 2029.

Thứ tư, ban hành quy chế chia sẻ dữ liệu giao thông mở và chuẩn hóa bản đồ số thời gian thực. Chủ thể thực hiện: Bộ Giao thông Vận tải chủ trì, phối hợp cùng Bộ Thông tin và Truyền thông. Mục tiêu hành động: Thiết lập nền tảng API chia sẻ dữ liệu lưu lượng giao thông mở cho cộng đồng doanh nghiệp công nghệ, số hóa 100% mạng lưới biển báo và làn đường theo định dạng bản đồ GIS động. Lộ trình thực hiện: Hoàn thiện khung kỹ thuật trong giai đoạn 2026 - 2028.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả của luận văn mang lại giá trị tham chiếu sâu sắc cho bốn nhóm đối tượng chuyên môn:

Nhóm 1: Cơ quan quản lý nhà nước và các nhà quy hoạch giao thông đô thị. Công trình cung cấp phương pháp luận khoa học và công cụ mô phỏng vi mô VANETsim để đánh giá tác động giao thông, mô phỏng thử nghiệm các phương án phân luồng và quy hoạch vị trí lắp đặt đèn tín hiệu hoặc cầu vượt trước khi triển khai thi công trên thực địa.

Nhóm 2: Doanh nghiệp phát triển phần mềm bản đồ và ứng dụng điều hướng thông minh. Các kỹ sư thuật toán có thể khai thác trực tiếp mã nguồn cải tiến của thuật toán Ant Colony System và bộ thông số thực nghiệm (hệ số mùi 0,1, tham số ngẫu nhiên 0,4) để nâng cấp tính năng dynamic routing tránh tắc đường cho các ứng dụng định vị thương mại.

Nhóm 3: Học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Công nghệ thông tin, Hệ thống thông tin và Khoa học dữ liệu. Luận văn là tài liệu tham khảo mẫu mực về quy trình kết hợp giữa lý thuyết hệ đa tác tử, giải thuật meta-heuristic bầy đàn và kỹ thuật mô phỏng mạng viễn thông Ad-hoc, mở ra nhiều hướng đề tài phát triển tiếp theo.

Nhóm 4: Các doanh nghiệp vận tải hàng hóa và logistics đô thị. Áp dụng thuật toán dẫn đường tối ưu giúp doanh nghiệp cắt giảm từ 28% đến 48% cự ly di chuyển không cần thiết của đội xe giao hàng, từ đó tiết kiệm từ 15% đến 20% chi phí tiêu hao nhiên liệu và bảo dưỡng phương tiện.

Câu hỏi thường gặp

Thuật toán Ant Colony System (ACS) khác biệt thế nào so với thuật toán A* truyền thống? Thuật toán A* sử dụng hàm đánh giá tĩnh dựa trên khoảng cách hình học nên dễ rơi vào điểm tối ưu cục bộ khi giao thông biến động. Ngược lại, thuật toán ACS mô phỏng hành vi đàn kiến bằng cách cập nhật vết mùi pheromone và nồng độ mùi động, giúp tìm ra đường đi ngắn hơn tới 48,96% và tự động chuyển hướng khi phát hiện tuyến đường có mật độ phương tiện cao.

Mạng VANET hỗ trợ việc tìm đường cho xe cộ trong thực tế bằng cách nào? Mạng VANET biến mỗi phương tiện thành một nút mạng truyền thông không dây có bán kính phủ sóng từ 100 đến 300 mét. Khi xảy ra va chạm hoặc ùn ứ, các xe ở gần sẽ lập tức phát gói tin cảnh báo cho các xe phía sau thông qua các nút trung gian, giúp hệ thống định tuyến cập nhật dữ liệu tắc nghẽn chỉ trong vài giây mà không cần trạm phát sóng cố định.

Tại sao thời gian thực thi của thuật toán ACS lại cao hơn thuật toán A*? Thời gian xử lý của ACS đạt từ 31 đến 41 mili giây, trong khi A* chỉ mất từ 18 đến 25 mili giây. Sự chênh lệch này xuất phát từ việc ACS phải mô phỏng hàng chục cá thể kiến nhân tạo đồng thời xây dựng lời giải và tính toán công thức cập nhật mùi cục bộ lẫn toàn cục sau mỗi vòng lặp để bảo đảm độ chính xác tối ưu.

Trọng số ùn tắc w = 15 trong mô hình nghiên cứu có vai trò gì? Trọng số w = 15 là hệ số phạt thời gian (tính bằng giây) được xác định qua nhiều lần thực nghiệm. Khi một tuyến đường có n xe đang bị dồn ứ, hàm mục tiêu sẽ tự động cộng thêm giá trị n nhân 15 vào chi phí của tuyến đường đó, khiến nồng độ mùi trên nhánh này suy giảm và hướng đàn kiến lựa chọn các nhánh đường vòng thông thoáng hơn.

Công cụ mô phỏng VANETsim có thể đáp ứng quy mô kịch bản lớn đến mức nào? Phần mềm VANETsim phiên bản 1.2 có khả năng mô phỏng mô hình giao thông vi mô với quy mô mạng lưới lên tới 16.000 phương tiện hoạt động đồng thời. Công cụ này tích hợp bản đồ từ OpenStreetMap, hỗ trợ chạy trên máy tính cá nhân lẫn các hệ thống máy chủ đa vi xử lý để phục vụ đánh giá thuật toán chính xác.

Kết luận

Luận văn đã hoàn thành trọn vẹn mục tiêu nghiên cứu và mang lại những đóng góp học thuật lẫn thực tiễn quan trọng:

  • Xây dựng thành công mô hình tích hợp thuật toán Ant Colony System (ACS) vào module định tuyến của công cụ mô phỏng giao thông mạng VANETsim phiên bản 1.2.
  • Chứng minh thực nghiệm tính ưu việt của giải thuật đề xuất khi giúp giảm từ 28,77% đến 48,96% quãng đường di chuyển và rút ngắn từ 5,05% đến 8,13% thời gian hành trình so với thuật toán A*.
  • Thiết lập cơ chế tự động né tránh điểm ùn tắc thời gian thực nhờ tích hợp hàm trọng số phạt tắc nghẽn w = 15 dựa trên mật độ và vận tốc xe.
  • Phân tích chi tiết sự đánh đổi giữa chất lượng tối ưu lộ trình và thời gian tính toán thuật toán trong ngưỡng 31 đến 41 mili giây, bảo đảm tính khả thi cho việc ứng dụng thời gian thực.
  • Đặt nền móng vững chắc cho việc ứng dụng công nghệ khai phá dữ liệu và mạng phương tiện di động vào chiến lược phát triển giao thông thông minh tại Việt Nam.

Kế hoạch phát triển tiếp theo của nghiên cứu trong giai đoạn 2026 - 2027 là nâng cấp thuật toán trên nền tảng tính toán song song phân tán và tích hợp thêm dữ liệu cảm biến thời gian thực từ môi trường IoT. Các nhà nghiên cứu, kỹ sư hệ thống và nhà quản lý đô thị quan tâm được khuyến khích tiếp cận, kế thừa mô hình và đẩy mạnh triển khai thử nghiệm trên các mạng lưới giao thông thực tế.