Luận văn: Bài toán định tuyến xe và ứng dụng trong tối ưu mạng viễn thông - Bùi Thu Hiền, ĐH Thái Nguyên

Luận văn nghiên cứu bài toán định tuyến xe CVRP và các thuật toán tối ưu, từ đó đề xuất mô hình giải quyết bài toán quy hoạch và tối ưu hóa mạng viễn thông.

• Tác giả: Bùi Thu Hiền
• Người hướng dẫn: TS. Lê Quang Minh
• Trường học: Trường Đại học Công nghệ Thông tin & Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bài toán định tuyến xe và ứng dụng trong tối ưu mạng viễn thông
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về bài toán định tuyến xe và tối ưu mạng viễn thông

Bài toán định tuyến xe (Vehicle Routing Problem - VRP) là bài toán tối ưu hóa tổ hợp kinh điển trong khoa học máy tính. Mục tiêu chính là xác định tập hợp các lộ trình tối ưu cho đội phương tiện xuất phát từ một hoặc nhiều điểm cung ứng đến các điểm nhu cầu. Trong công trình nghiên cứu tại Đại học Thái Nguyên, mô hình định tuyến xe có dung lượng giới hạn (CVRP) được mở rộng sang lĩnh vực hạ tầng viễn thông. Hệ thống mạng viễn thông hiện đại đối mặt với sự gia tăng lưu lượng dữ liệu truyền dẫn. Việc quy hoạch đường cáp quang và phân phối tải giữa các trạm thu phát sóng (BTS) đòi hỏi phương pháp tính toán chặt chẽ. Cấu trúc mạng cáp kết nối từ máy chủ trung tâm đến các trạm phụ trợ có tính tương đồng trực tiếp với mô hình CVRP. Thay vì phương tiện vận tải, các luồng truyền dẫn dữ liệu đóng vai trò là các tuyến phân phối lưu lượng. Việc chuyển đổi bài toán giao thông vận tải sang bài toán viễn thông mở ra hướng tiếp cận mới. Mô hình toán học này giúp giảm đáng kể chi phí lắp đặt hạ tầng mạng, đồng thời nâng cao hiệu quả khai thác tài nguyên phần cứng.

1.1. Lịch sử phát triển và bản chất toán học của mô hình VRP

Bài toán định tuyến xe được Dantzig và Ramser đề xuất lần đầu tiên vào năm 1959. VRP là bài toán mở rộng trực tiếp từ bài toán người du lịch (TSP). Đây là bài toán thuộc lớp NP-khó trong lý thuyết độ phức tạp tính toán. Khi số lượng đỉnh và ràng buộc tăng lên, không gian tìm kiếm nghiệm mở rộng theo hàm số mũ. Các thuật toán duyệt toàn bộ không thể tìm ra nghiệm tối ưu trong thời gian đa thức đối với dữ liệu quy mô lớn. Do đó, các nhà khoa học máy tính liên tục phát triển các mô hình xấp xỉ và tối ưu hóa tổ hợp. Mô hình VRP cung cấp cơ sở lý thuyết vững chắc cho các bài toán phân phối tài nguyên thực tế.

1.2. Mối liên hệ giữa định tuyến xe và cấu trúc mạng viễn thông

Mạng viễn thông cấu thành từ hệ thống máy chủ trung tâm và các trạm thu phát sóng mặt đất. Mỗi đường truyền nối trạm tương đương một tuyến đường xe chạy. Điểm xuất phát của xe tương ứng với máy chủ quản lý. Khách hàng nhận hàng tương ứng với các trạm BTS tiếp nhận dung lượng dữ liệu. Giới hạn tải trọng của phương tiện vận tải tương đương với băng thông tối đa của đường cáp quang. Chi phí khoảng cách di chuyển giữa các địa điểm chuyển hóa thành độ dài vật lý của đường cáp viễn thông. Sự tương đồng hình học và logic này cho phép áp dụng hoàn hảo mô hình CVRP vào thiết kế mạng.

II. Phân tích bài toán định tuyến mạng viễn thông tại ĐH Thái Nguyên

Nghiên cứu của Đại học Thái Nguyên tập trung mô hình hóa hệ thống mạng trục viễn thông phức tạp. Mạng viễn thông được biểu diễn dưới dạng đồ thị vô hướng trọng số G=(V, E). Tập đỉnh V bao gồm đỉnh 0 đại diện cho máy chủ trung tâm và các đỉnh còn lại đại diện cho các trạm BTS. Tập cạnh E thể hiện các tuyến cáp vật lý kết nối giữa các trạm BTS với nhau hoặc với máy chủ. Trọng số trên mỗi cạnh phản ánh độ dài thực tế của tuyến cáp nối giữa hai điểm nút. Hệ thống đặt ra nhiều ràng buộc kỹ thuật khắt khe. Máy chủ chỉ sở hữu số lượng cổng kết nối giới hạn ký hiệu là K. Mỗi tuyến cáp có băng thông tối đa xác định ký hiệu là Q. Mỗi trạm BTS có nhu cầu lưu lượng dữ liệu riêng biệt không vượt quá băng thông kênh truyền. Mục tiêu then chốt là tìm kiếm phương án đấu nối tất cả các trạm BTS vào mạng sao cho tổng chiều dài cáp ngắn nhất. Mọi trạm BTS phải được phục vụ duy nhất bởi một đường truyền kết nối về máy chủ.

2.1. Các ràng buộc kỹ thuật cốt lõi trong mô hình mạng

Mô hình mạng viễn thông đặt ra ba nhóm ràng buộc cơ bản. Thứ nhất, số lượng tuyến truyền dẫn khởi tạo từ máy chủ trung tâm không được vượt quá số cổng vật lý K có sẵn. Thứ hai, tổng nhu cầu truyền dẫn dữ liệu của các trạm BTS trên cùng một tuyến không được vượt quá băng thông giới hạn Q của đường cáp. Thứ ba, mỗi trạm BTS chỉ được nằm trên một đường truyền duy nhất để bảo đảm tính toàn vẹn của luồng tín hiệu. Các ràng buộc này ngăn ngừa hiện tượng nghẽn mạng và xung đột địa chỉ gói tin. Đồng thời, các điều kiện trên bảo đảm tính khả thi khi triển khai thi công phần cứng thực tế.

2.2. Thách thức tối ưu hóa chi phí hạ tầng viễn thông

Chi phí đầu tư hạ tầng mạng viễn thông phụ thuộc trực tiếp vào tổng chiều dài cáp nối. Các trạm BTS phân bố rải rác trên các vùng địa hình phức tạp. Khoảng cách giữa các trạm tuân theo bất đẳng thức tam giác và tính chất đối xứng. Việc đấu nối tùy tiện sẽ làm gia tăng chiều dài đường cáp, kéo theo chi phí vật tư và suy hao tín hiệu đường dài. Việc tìm cấu hình mạng tối ưu tương đương với việc giải bài toán NP-khó. Kích thước mạng càng lớn thì số lượng cấu hình mạng khả thi càng tăng theo cấp số nhân. Điều này đòi hỏi các giải thuật tính toán hiệu năng cao để tìm nghiệm tối ưu.

III. Phương pháp giải bài toán định tuyến xe tối ưu mạng viễn thông

Để giải quyết bài toán CVRP áp dụng trong viễn thông, luận văn phân tích hai nhóm phương pháp tiếp cận chính: thuật toán chính xác và thuật toán gần đúng. Thuật toán chính xác bảo đảm tìm ra giải pháp tối ưu toàn cục cho mạng lưới. Trong đó, thuật toán Nhánh cận (Branch and Bound) là phương pháp nổi bật nhất. Thuật toán này chia không gian tìm kiếm thành các bài toán con và sử dụng hàm cận dưới f_bound để cắt tỉa các nhánh không có triển vọng. Kỹ thuật đánh giá cận dưới dựa trên độ giãn Lagrange và cây trung tâm bậc K (K-DCT) hoặc M-tree giúp giới hạn hiệu quả cây tìm kiếm. Ngoài ra, quy hoạch tuyến tính nguyên và phương pháp quy hoạch động cũng được nghiên cứu để giải các cấu hình mạng quy mô nhỏ. Khi mạng lưới mở rộng với hàng trăm trạm BTS, các phương pháp Heuristic và Metaheuristic được ứng dụng để tìm nghiệm xấp xỉ chất lượng cao trong thời gian thực thi hợp lý.

3.1. Thuật toán nhánh cận và kỹ thuật xác định hàm cận dưới

Thuật toán Nhánh cận tiến hành phân hoạch tập nghiệm thành các tập con có triển vọng nhất. Giá trị hàm f_bound xác định cận dưới chi phí cho mỗi tập con. Nếu cận dưới của một tập con lớn hơn hoặc bằng giá trị mục tiêu tốt nhất đã ghi nhận, tập con đó bị loại bỏ ngay lập tức. Cận dưới do Christofides và Fisher đề xuất áp dụng cấu trúc cây bao trùm giúp thu hẹp đáng kể không gian tìm kiếm. Kỹ thuật này cho phép giải quyết triệt để các bài toán quy mô dưới 25-50 nút mạng viễn thông. Thuật toán đảm bảo nghiệm tìm được luôn đạt tính tối ưu tuyệt đối về độ dài dây cáp.

3.2. Thuật toán Heuristic và tiếp cận quy hoạch tuyến tính

Bên cạnh thuật toán nhánh cận, các kỹ thuật quy hoạch tuyến tính nguyên và phân chia tập hợp cũng mang lại hiệu quả cao. Mô hình rẽ nhánh và cắt (Branch and Cut) bổ sung các mặt phẳng cắt vào bài toán nới lỏng tuyến tính để thắt chặt biên nghiệm. Đối với các bài toán quy mô thực tế lớn, thuật toán Heuristic tham lam và tìm kiếm cục bộ được triển khai để giảm thời gian xử lý. Các giải thuật tiến hóa và mô phỏng luyện kim giúp tránh rơi vào các cực trị địa phương. Sự kết hợp giữa Heuristic và tối ưu hóa toán học tạo ra các khung giải thuật lai hiệu năng cao.

IV. Kết luận và ứng dụng định tuyến xe tối ưu mạng viễn thông

Đề tài nghiên cứu tại Đại học Thái Nguyên chứng minh tính khả thi vượt trội của việc ứng dụng mô hình định tuyến xe vào tối ưu hóa mạng viễn thông. Việc trừu tượng hóa các kết nối cáp quang thành bài toán CVRP giúp đơn giản hóa bài toán thiết kế hạ tầng phức tạp. Kết quả thực nghiệm trên mô hình mạng mẫu với máy chủ trung tâm và các trạm BTS chứng minh sự sụt giảm rõ rệt về tổng độ dài cáp truyền dẫn. Các tuyến truyền dẫn được phân bổ khoa học, tuân thủ nghiêm ngặt giới hạn cổng K của Server và trần băng thông Q của đường truyền. Giải pháp này giúp các doanh nghiệp viễn thông tiết kiệm chi phí xây dựng ban đầu và chi phí bảo trì hệ thống định kỳ. Đồng thời, độ trễ tín hiệu và nguy cơ suy hao đường truyền được giảm thiểu đáng kể nhờ các tuyến cáp ngắn nhất. Công trình mở ra tiềm năng ứng dụng rộng rãi cho quy hoạch mạng 5G và mạng cảm biến không dây trong tương lai.

4.1. Hiệu quả kinh tế và kỹ thuật của mô hình tối ưu

Ứng dụng mô hình tối ưu đem lại lợi ích kinh tế trực tiếp thông qua việc cắt giảm tổng chiều dài cáp mạng cần lắp đặt. Hạ tầng viễn thông được tinh gọn giúp giảm lượng thiết bị trung gian và công suất tiêu thụ điện tại các trạm chuyển tiếp. Về mặt kỹ thuật, việc rút ngắn khoảng cách truyền dẫn giúp tăng cường độ ổn định của đường truyền và giảm tỷ lệ mất gói tin. Lưu lượng dữ liệu tại các trạm BTS được phân bổ đồng đều theo dung lượng kênh truyền. Nhờ đó, hệ thống viễn thông hạn chế tối đa nguy cơ quá tải cục bộ vào các khung giờ cao điểm.

4.2. Hướng mở rộng nghiên cứu trong hạ tầng viễn thông tương lai

Các nghiên cứu tiếp theo có thể mở rộng mô hình CVRP sang bài toán định tuyến với khung thời gian (VRPTW) để giải quyết các dịch vụ mạng thời gian thực. Việc tích hợp các yếu tố mạng động như biến động lưu lượng theo thời gian và sự cố nút mạng sẽ nâng cao tính thực tiễn. Hơn nữa, việc ứng dụng mạng nơ-ron nhân tạo kết hợp với học tăng cường hứa hẹn tạo ra các cơ chế tự động định tuyến thích nghi. Các mô hình tối ưu này đóng vai trò then chốt trong việc thiết kế kiến trúc mạng 6G và trung tâm dữ liệu biên.

Nội dung chính

Tổng quan nghiên cứu

Bài toán tối ưu hóa chi phí vận hành và xây dựng mạng lưới là thách thức trọng tâm trong kỷ nguyên chuyển đổi số và phát triển hạ tầng mạng viễn thông. Theo các thống kê trong ngành vận tải và truyền thông, việc ứng dụng các giải thuật vi tính hóa vào bài toán định tuyến có thể giúp giảm thiểu từ 5% đến 20% tổng chi phí đầu tư và vận hành hệ thống. Đứng trước sự phát triển mạnh mẽ của mạng di động thế hệ mới, số lượng các trạm thu phát sóng di động (BTS) gia tăng nhanh chóng, đòi hỏi một phương án quy hoạch cáp truyền dẫn trục tối ưu nhằm kết nối các trạm về trung tâm dữ liệu với chi phí thấp nhất mà vẫn đảm bảo tải trọng băng thông.

Nghiên cứu của học viên Bùi Thu Hiền dưới sự hướng dẫn của TS. Lê Quang Minh tại Đại học Thái Nguyên đã giải quyết trực diện bài toán này bằng cách mô hình hóa mạng viễn thông thành Bài toán định tuyến xe có dung lượng giới hạn (Capacitated Vehicle Routing Problem - CVRP). Mục tiêu cụ thể của luận văn là xây dựng mô hình toán học giải tích, áp dụng và so sánh các thuật toán tối ưu bao gồm thuật toán Tham lam, Quy hoạch động và Quy hoạch tuyến tính nguyên (ILP) để thiết kế cấu trúc mạng cáp quang nối các trạm BTS về máy chủ Server.

Phạm vi nghiên cứu tập trung vào cấu trúc mạng truyền dẫn phân tán tại một địa phương với hệ thống trạm BTS có tọa độ không gian hai chiều xác định, tổng lưu lượng dữ liệu truyền tải của từng cụm không vượt quá ngưỡng băng thông cực đại 4.000 đơn vị dữ liệu và số lượng cổng kết nối tại Server giới hạn ở mức K = 4. Kết quả nghiên cứu mang lại ý nghĩa kinh tế và kỹ thuật to lớn, giúp giảm chiều dài lắp đặt cáp quang từ 10% đến 18%, tối ưu hóa 100% hiệu suất cổng mạng và tiết kiệm hàng trăm triệu đồng chi phí triển khai hạ tầng viễn thông thực 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 được xây dựng trên nền tảng vững chắc của lý thuyết Tối ưu hóa tổ hợp (Combinatorial Optimization) và lý thuyết đồ thị mạng. Trong đó, hai mô hình lý thuyết cốt lõi được vận dụng gồm:

• Lý thuyết bài toán định tuyến xe CVRP: Khởi nguồn từ công trình nghiên cứu kinh điển năm 1959 của Dantzig và Ramser, CVRP là bài toán thuộc lớp NP-khó (NP-hard). Mô hình biểu diễn một mạng lưới gồm điểm trung tâm (Server đóng vai trò như kho hàng Depot) và tập hợp n nút mạng (các trạm BTS đóng vai trò như khách hàng có nhu cầu lưu lượng dữ liệu xác định). Mỗi tuyến cáp xuất phát từ Server, đi qua một nhóm trạm BTS và quay về điểm gốc sao cho tổng nhu cầu không vượt quá sức chứa băng thông Q = 4.000.
• Mô hình Quy hoạch tuyến tính nguyên (Integer Linear Programming - ILP): Vận dụng hệ thống bất đẳng thức tuyến tính kết hợp ràng buộc loại bỏ chu trình con Miller-Tucker-Zemlin (MTZ) được công bố năm 1960. Ràng buộc MTZ đóng vai trò sống còn trong việc đảm bảo tính liên tục của tuyến truyền dẫn, triệt tiêu hoàn toàn các hành trình phụ bị cô lập khỏi Server trung tâm.
• Lý thuyết Quy hoạch động và Cận dưới Lagrange: Kế thừa công trình của Richard Bellman năm 1950 và các nghiên cứu nới lỏng không gian trạng thái của Christofides giai đoạn 1981 - 1985, cho phép xác định tỷ lệ cận dưới trên giá trị tối ưu đạt từ 93,1% đến 99,6%.

Các khái niệm chuyên ngành nền tảng bao gồm: Trạm BTS (Base Transceiver Station), dung lượng truyền dẫn cực đại Q, số cổng kết nối K, ma trận chi phí khoảng cách đối xứng c_ij thỏa mãn bất đẳng thức tam giác, và cấu trúc lân cận trong tìm kiếm cục bộ (Local Search Operators như Swap, 2-opt, Relocate).

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

Nghiên cứu sử dụng phương pháp định lượng thực nghiệm kết hợp mô hình hóa toán học. Quy trình nghiên cứu được triển khai chặt chẽ qua các bước:

• Cỡ mẫu và kỹ thuật chọn mẫu: Mẫu thực nghiệm chính bao gồm cụm 5 trạm BTS tiêu chuẩn với nhu cầu lưu lượng dữ liệu lần lượt là 110, 700, 800, 1.400 và 2.100 đơn vị băng thông, kết nối về 1 Server trung tâm có 4 cổng kết nối. Mẫu kiểm thử mở rộng được thiết lập trên không gian tọa độ 2 chiều với các tập dữ liệu từ 25 đến 135 nút nhằm đánh giá toàn diện năng lực mở rộng của giải thuật.
• Phương pháp phân tích: Phân tích đối sánh đa thuật toán giữa nhóm giải thuật Heuristic xây dựng (Thuật toán Tham lam), Quy hoạch động (Dynamic Programming), và Thuật toán tối ưu chính xác (Quy hoạch tuyến tính nguyên ILP).
• Lý do lựa chọn phương pháp: Vì CVRP là bài toán NP-khó, việc đối chiếu giữa phương pháp chính xác (ILP) và phương pháp gần đúng (Heuristic) là bắt buộc. Phương pháp ILP giúp tìm ra lời giải tối ưu toàn cục làm mốc chuẩn (benchmark), trong khi Heuristic và Quy hoạch động chứng minh tính khả thi về mặt thời gian xử lý khi quy mô trạm BTS tăng cao trong thực tế.
• Khung thời gian thực hiện: Đề tài được hoàn thiện và bảo vệ thành công trong năm 2023 tại Trường Đại học Công nghệ Thông tin và Truyền thông Thái Nguyên.

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

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

• Phát hiện 1 - Hiệu năng tối ưu tuyệt đối của mô hình ILP: Thuật toán Quy hoạch tuyến tính nguyên với hệ ràng buộc MTZ đã tìm ra lời giải tối ưu toàn cục cho mạng lưới 5 trạm BTS mẫu. Tổng chiều dài cáp truyền dẫn được rút ngắn xuống mức tối thiểu, giúp tiết kiệm 15,4% chiều dài cáp so với phương án đấu nối hình sao trực tiếp từ từng trạm về Server.
• Phát hiện 2 - Tốc độ thực thi vượt trội của Thuật toán Tham lam: Giải thuật Heuristic Tham lam hoàn thành việc tìm tuyến đường với thời gian thực thi siêu nhanh (dưới 0,05 giây), đáp ứng tức thì các bài toán quy mô lớn. Tuy nhiên, chất lượng lời giải của Tham lam có tổng độ dài đường truyền lớn hơn khoảng 8,2% đến 12,5% so với lời giải tối ưu của ILP do bị mắc kẹt tại các điểm tối ưu cục bộ.
• Phát hiện 3 - Khả năng cân bằng của Quy hoạch động: Phương pháp Quy hoạch động đạt độ chính xác tương đương 96,8% so với mô hình ILP trên tập dữ liệu kích thước nhỏ và trung bình, đồng thời giảm khoảng 40% thời gian tính toán so với phương pháp duyệt nhánh cận vét cạn truyền thống.
• Phát hiện 4 - Tác động của tham số băng thông và cổng kết nối: Khi ngưỡng dung lượng kênh truyền Q tăng lên 25%, cấu trúc gom cụm mạng lưới thay đổi rõ rệt, giúp giảm bớt 1 tuyến cáp trục vật lý xuất phát từ Server, qua đó tiết kiệm thêm 18% chi phí cổng kết nối phần cứng trung tâm.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự khác biệt giữa các phương pháp xuất phát từ bản chất không gian trạng thái tổ hợp tăng theo hàm giai thừa khi số lượng nút mạng gia tăng. Thuật toán ILP loại bỏ triệt để các hành trình phụ nhờ hệ phương trình tuyến tính chặt chẽ, tạo ra cấu trúc cây mạng tối ưu nhất.

Dữ liệu thực nghiệm của nghiên cứu được trực quan hóa sinh động thông qua sơ đồ ma trận khoảng cách hai chiều giữa Server và các trạm BTS, kết hợp bảng thống kê chi tiết các tham số: số tuyến cáp hình thành, tổng lưu lượng tải trên mỗi tuyến, chiều dài cáp vật lý và thời gian CPU thực thi. Biểu đồ đối sánh đa trục thể hiện rõ rệt sự tương quan đánh đổi giữa độ chính xác của giải pháp và chi phí thời gian tính toán giữa ILP, Quy hoạch động và Thuật toán Tham lam.

Kết quả này hoàn toàn nhất quán với các nghiên cứu kinh điển của Fisher (1994) và Augerat (1995) về năng lực giải quyết bài toán định tuyến bằng thuật toán nhánh - cắt và quy hoạch nguyên, đồng thời chứng minh tính đúng đắn khi chuyển dịch từ bài toán logistics vận tải thuần túy sang lĩnh vực tối ưu hóa hạ tầng viễn thông.

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

• Ứng dụng mô hình hóa Quy hoạch tuyến tính nguyên (ILP) vào quy hoạch mạng cáp quang đô thị: Các doanh nghiệp viễn thông cần áp dụng mô hình toán học CVRP kết hợp ràng buộc MTZ để thiết kế mạng cáp quang FTTx và các trạm phát sóng 5G. Mục tiêu: Cắt giảm từ 12% đến 15% tổng chiều dài dây cáp quang kéo mới trong vòng 6 tháng đầu triển khai. Chủ thể thực hiện: Ban Kỹ thuật và Trung tâm Quy hoạch Thiết kế Mạng của các nhà mạng viễn thông.
• Tích hợp module Metaheuristic vào hệ thống điều hành mạng thông minh: Phát triển và nhúng các thuật toán metaheuristic như Giải thuật Di truyền (GA), Tối ưu đàn kiến (ACO) và Tìm kiếm Tabu vào hệ thống quản lý mạng tự động (Software-Defined Networking - SDN). Mục tiêu: Tự động tái định tuyến luồng dữ liệu khi có sự cố đứt cáp với thời gian phản hồi dưới 2 giây. Lộ trình thực hiện: Quý 3 đến Quý 4 năm 2024. Chủ thể: Đội ngũ Kỹ sư Phần mềm và Vận hành Mạng NOC.
• Chuẩn hóa cơ sở dữ liệu GIS và lưu lượng động: Xây dựng hệ thống bản đồ số tích hợp dữ liệu tọa độ không gian chính xác cùng lưu lượng truyền dẫn theo thời gian thực cho 100% trạm BTS trên toàn mạng lưới. Mục tiêu: Nâng cao độ chính xác trong dự báo tải dung lượng lên 95% trước năm 2025. Chủ thể thực hiện: Bộ phận Phân tích Dữ liệu và Quản lý Cơ sở Hạ tầng Viễn thông.
• Ban hành tiêu chuẩn thiết kế mạng hình cây và vòng khép kín: Doanh nghiệp cần xây dựng bộ quy chuẩn nội bộ về việc kết hợp các toán tử tìm kiếm cục bộ (như 2-opt, Or-opt, Relocate) trong bảo trì và nâng cấp mạng truyền dẫn. Mục tiêu: Tối ưu hóa 100% công suất các cổng kết nối Server và tiết kiệm 20% chi phí đầu tư thiết bị chuyển mạch trong chu kỳ ngân sách giai đoạn 2024 - 2026. Chủ thể: Giám đốc Công nghệ (CTO) và Hội đồng Khoa học Doanh nghiệp.

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

• Kỹ sư Quy hoạch Mạng và Chuyên gia Hạ tầng Viễn thông: Nắm vững phương pháp luận ánh xạ bài toán vật lý viễn thông sang mô hình toán học CVRP. Ứng dụng thực tế: Thiết kế tuyến cáp trục nối trạm BTS với Server trung tâm đạt chi phí tối thiểu và bảo đảm dung lượng băng thông.
• Kỹ sư Phần mềm và Nhà phát triển Giải thuật Tối ưu hóa: Tiếp cận chi tiết các mã giả thuật toán, kỹ thuật cài đặt thuật toán nhánh cận, quy hoạch tuyến tính nguyên và các toán tử tìm kiếm cục bộ (Swap, 2-opt, 3-opt). Ứng dụng thực tế: Xây dựng các phần mềm điều vận logistics, giao hàng chặng cuối và định tuyến thiết bị mạng giúp giảm 15% chi phí vận hành.
• Giảng viên, Học viên Cao học và Nghiên cứu sinh ngành Khoa học Máy tính: Sử dụng luận văn làm tài liệu học thuật tham khảo có giá trị cao về phương pháp giải lớp bài toán NP-khó. Ứng dụng thực tế: Phát triển các đề tài nghiên cứu mở rộng như bài toán định tuyến xe có cửa sổ thời gian (VRPTW) hoặc định tuyến mạng cảm biến không dây IoT.
• Giám đốc Công nghệ (CTO) và Nhà quản lý Doanh nghiệp Công nghệ: Có cơ sở khoa học và số liệu định lượng vững chắc để thẩm định, phê duyệt các dự án đầu tư mạng lưới. Ứng dụng thực tế: Tối ưu hóa chỉ số chi phí vốn (CAPEX) và chi phí vận hành (OPEX) trong các chiến lược chuyển đổi số hạ tầng viễn thông giai đoạn 2024 - 2030.

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

• Điểm khác biệt cốt lõi giữa bài toán định tuyến xe CVRP và bài toán người bán hàng TSP là gì? Bài toán người bán hàng TSP là bài toán tìm một chu trình duy nhất đi qua tất cả các điểm với khoảng cách ngắn nhất, tương đương với trường hợp CVRP chỉ có 1 xe và sức chứa vô hạn (K = 1, Q vô cùng). Trong khi đó, CVRP phức tạp hơn rất nhiều vì phải giải đồng thời 2 bài toán con: bài toán phân cụm khách hàng thành K nhóm thỏa mãn tải trọng Q (ví dụ Q = 4.000) và bài toán tìm lộ trình tối ưu cho từng cụm.

• Tại sao việc quy hoạch mạng viễn thông có thể chuyển đổi thành bài toán CVRP? Mô hình CVRP có sự tương đồng hoàn hảo với mạng viễn thông: Server trung tâm đóng vai trò như kho hàng Depot, các trạm BTS tương ứng với các khách hàng có nhu cầu dung lượng dữ liệu xác định (từ 110 đến 2.100 đơn vị lưu lượng), dung lượng băng thông đường cáp tương ứng với sức chứa Q, và số cổng kết nối tại Server tương ứng với số lượng xe K.

• Hạn chế lớn nhất của thuật toán Quy hoạch tuyến tính nguyên (ILP) khi ứng dụng vào thực tế là gì? Hạn chế lớn nhất của ILP là độ phức tạp tính toán bùng nổ theo cấp số nhân khi số lượng nút mạng vượt quá 100 điểm. Đối với các hệ thống mạng quy mô lớn hàng nghìn trạm BTS, thuật toán ILP mất rất nhiều thời gian để tìm ra nghiệm tối ưu tuyệt đối, do đó cần kết hợp với các thuật toán Heuristic hoặc Metaheuristic để có lời giải nhanh trong thời gian thực.

• Các toán tử tìm kiếm cục bộ (Local Search) nào mang lại hiệu quả cải tiến cao nhất cho bài toán định tuyến? Toán tử 2-opt và Relocate mang lại hiệu quả cải thiện rõ rệt nhất. Toán tử 2-opt giúp đảo ngược một đoạn đường đi để loại bỏ các đoạn cáp chéo nhau không cần thiết, trong khi toán tử Relocate di chuyển một trạm BTS sang vị trí tuyến cáp khác phù hợp hơn, giúp giảm từ 5% đến 12% tổng độ dài mạng lưới chỉ sau 50 đến 100 vòng lặp.

• Kết quả của mô hình nghiên cứu này có thể ứng dụng cho các lĩnh vực công nghệ nào khác? Bên cạnh quy hoạch cáp cho trạm BTS, mô hình có thể ứng dụng trực tiếp để định tuyến luồng dữ liệu trong mạng chuyển mạch gói, tối ưu hóa vị trí máy chủ trong Trung tâm Dữ liệu (Data Center), điều phối thiết bị bay không người lái (UAV) thu thập dữ liệu IoT, và quy hoạch hệ thống phân phối logistics cho các đô thị thông minh quy mô từ 50 đến 200 điểm nút.

Kết luận

• Luận văn đã mô hình hóa thành công bài toán thiết kế mạng viễn thông trục kết nối các trạm BTS về Server thành bài toán định tuyến xe có dung lượng giới hạn CVRP.
• Xây dựng hoàn chỉnh mô hình toán học Quy hoạch tuyến tính nguyên (ILP) kết hợp ràng buộc Miller-Tucker-Zemlin (MTZ), đảm bảo tính liên tục và tìm ra cấu trúc mạng tối ưu tuyệt đối cho hệ thống trạm BTS mẫu.
• Thực hiện so sánh toàn diện giữa 3 phương pháp tiêu biểu: Thuật toán Tham lam (tốc độ dưới 0,05 giây), Quy hoạch động (độ chính xác 96,8%) và Quy hoạch tuyến tính nguyên ILP (nghiệm tối ưu toàn cục).
• Chứng minh khả năng tiết kiệm từ 10% đến 20% tổng chi phí đầu tư cáp quang và tối ưu hóa 100% công suất cổng kết nối phần cứng của hệ thống máy chủ mạng viễn thông.
• Đề xuất khung kiến trúc mở rộng ứng dụng các giải thuật Metaheuristic (GA, ACO) và dữ liệu không gian GIS phục vụ quá trình tự động hóa quy hoạch hạ tầng số hiện đại.

Đóng góp chính của công trình là cung cấp một phương pháp luận khoa học, có tính ứng dụng thực tiễn cao, giúp giải quyết triệt để bài toán kinh tế - kỹ thuật trong quy hoạch hạ tầng viễn thông. Để tiếp tục phát triển nghiên cứu, trong giai đoạn 2024 - 2025, các kỹ sư và nhà nghiên cứu nên mở rộng mô hình cho các bài toán định tuyến động với lưu lượng biến thiên theo thời gian thực (Dynamic CVRP) và mạng viễn thông đa trung tâm dữ liệu (Multi-Depot VRP). Hãy áp dụng ngay mô hình toán học này vào dự án quy hoạch hạ tầng mạng của doanh nghiệp bạn để tối đa hóa hiệu quả đầu tư và nâng cao năng lực cạnh tranh trong kỷ nguyên số.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: TỔNG QUAN VỀ LỚP BÀI TOÁN ĐỊNH TUYẾN XE 1.1 Giới thiệu về bài toán định tuyến xe Bài toán định tuyến xe – VRP (Vehicle Routing Problem) thuộc lớp bài toán tối ưu tổ hợp, quan tâm tới việc tìm cách định tuyến các xe chở hàng để vận chuyển hàng hóa từ một hoặc nhiều kho hàng tới một tập các khách hàng với vị trí và nhu cầu (demand) cho trước [6]. VRP hỏi phải điều phối xe chở hàng như thế nào để có thể tối thiểu hóa/tối đa hóa một mục tiêu cho trước nào đó. Bài toán VRP là một bài toán quan trọng trong lĩnh vực quản lý chuỗi cung ứng và giao nhận hàng hóa, liên quan trực tiếp tới việc vận chuyển, phân phối hàng hóa cho nên nghiên cứu nó có ứng dụng lớn trong việc giảm chi phí logistic. Bài toán Định tuyến xe với dung lượng vận chuyển giới hạn - CVRP (Capacitated Vehicle Routing Problem) là một bài toán cơ bản nhất thuộc lớp các bài toán VRP.

CVRP được đề xuất lần đầu tiên bởi Dantzig và Ramser vào năm 1959 [3], trong đó tác giả giới thiệu một bài toán thực tiễn về việc di chuyển xăng tới các trạm xăng. Với số lượng xe chở xăng cùng với dung lượng chứa của chúng được biết trước, tác giả muốn tìm cách di chuyển các xe chở xăng tới các trạm xăng sao cho mỗi trạm xăng được đến đúng một lần, tổng lượng xăng chuyển cho trạm xăng được thăm bởi một xe không vượt quá dung lượng chứa của xe đó, và đồng thời quãng đường di chuyển của các xe là nhỏ nhất có thể. Bài toán này là dạng đơn giản nhất của lớp các bài toán VRP. Trong một bài toán định tuyến xe cơ bản, các xe sẽ xuất phát từ các kho hàng, đi giao hàng hoặc nhận hàng từ khách hàng và quay trở về điểm xuất phát.1 Các khái niệm được sử dụng trong bài toán bao gồm  Khách hàng (Customer): Khách hàng được biểu diễn bởi vị trí địa lý, có thể đón hàng do xe giao tới hoặc chuyển hàng lên xe để vận chuyển về kho hoặc cả hai.

Mỗi khách hàng yêu cầu một lượng hàng 4 hóa nhất định, có thể đưa ra một số yêu cầu khác về thời gian cho phép xe đến giao hàng, thời gian cho phép bốc dỡ hàng…  Xe vận chuyển (Vehicle): Xe là phương tiện được dùng để vận chuyển hàng hóa. Trong thực tế hầu như các xe là không đồng nhất, mỗi xe có một số thuộc tính gắn với nó, ví dụ như là lượng hàng hóa tối đa mà nó có thể chở, loại hàng hóa mà xe có thể vận chuyển, hoặc lượng khách hàng tối đa mà nó được thăm,.  Kho hàng (Depot): Kho hàng được biểu diễn bởi vị trí địa lý, là nơi cất trữ hàng hóa hay cũng có thể là địa điểm xuất phát/quay về của các xe. Trong một số bài toán, hàng hóa cần giao có thể được cất trữ trong một vài kho hàng.

 Kho xe (fleet): Kho xe tương ứng với tập hợp các xe có sẵn có thể dùng để giao hàng. Kho xe có thể là đồng nhất (tất cả các xe là giống nhau, có cùng thuộc tính) hoặc không. Trong thực tế hầu như các xe là không đồng nhất, chúng được phân loại dựa vào các đặc điểm như sức chứa của xe (tức tải trọng hàng hóa tối đa xe có thể đáp ứng), loại hàng hóa mà xe có thể vận chuyển (hàng hóa đông lạnh, hàng hóa khô…), chi phí vận chuyển (có hai loại chi phí thông dụng: chi phí cố định – chi phí cần thiết ban đầu để xe có thể khởi hành, chi phí này không phụ thuộc vào quãng đường mà xe phải đi; chi phí động – chi phí tiêu tốn trên từng đơn vị quãng đường mà xe phải đi)  Mạng lưới giao thông: Vận chuyển đi lại giữa các khách hàng thông qua mạng lưới giao thông này. Mạng lưới giao thông thường sẽ được biểu diễn bằng đồ thị, trong đó đỉnh của đồ thị là khách hàng và kho chứa, các cạnh nối giữa 2 đỉnh sẽ có một trọng số tương ứng là chi phí (có thể là độ dài hoặc thời gian) nếu xe đi qua cạnh đấy.

 Tuyến xe (Route): 5 Tuyến xe là một chuỗi có thứ tự các vị trí được thăm bởi xe đó. Thông thường, một tuyến xe sẽ xuất phát và kết thúc tại kho hàng, và các khách hàng được thăm ở khoảng giữa.  Mục tiêu định tuyến: Hàm mục tiêu của bài toán VRP thường là tối thiểu hóa/tối đa hoa một định lượng nào đó. Mục tiêu cơ bản và thông dụng nhất là tối thiểu hóa tổng độ dài quãng đường mà xe di chuyển.

Một hàm mục tiêu có thể khác là tối đa hóa lợi nhuận thu được bằng cách phục vụ một tập khách hàng.  Lời giải của VRP. Bài toán định tuyến xe được xem là một trong những bài toán phức tạp và kinh điển nhất của Vận tải học (Transportation Engineering). VRP là dạng bài toán ra quyết định, nhằm tìm các lộ trình tối ưu cho đội xe vận chuyển hàng hóa đến các khách hàng ở các địa điểm khác nhau.

Mục tiêu của bài toán thường là tối thiểu tổng khoảng cách hoặc thời gian di chuyển với nhiều ràng buộc cụ thể như khả năng chuyên chở của xe, khoảng thời gian mong muốn được đáp ứng của khách hàng,. Bài toán VRP thường bao gồm ít nhất hai bài toán con liên quan nhau: - Bài toán phân hoạch: nhằm phân chia tập khách hàng thành các tập con sao cho mỗi tập con chỉ được phục vụ bởi một xe nào đó. - Bài toán định tuyến: nhằm tìm ra lộ trình tối ưu cho mỗi xe vận chuyển. VRP là một vấn đề rộng và có thể bao gồm nhiều vấn đề con ứng với các tình huống và các ràng buộc khác nhau.

Do đó, để đơn giản khi giải quyết bài toán VRP, tùy theo mục tiêu mà người ta thường cụ thể hóa một số ràng buộc phụ. Ví dụ mục tiêu phục vụ khách hàng cao là phải phân phát chính xác, nghĩa là phân phát đúng số lượng, đúng chất lượng, đúng thời gian tại một địa điểm chính xác.2 Các tiêu chuẩn phân loại bài toán VRP Như đã trình bày trên, VRP có nhiều mục tiêu và các ràng buộc khác nhau. Vì thế, trong thực tế có rất nhiều lớp bài toán VRP tùy theo mục tiêu và sự nới lỏng hoặc 6 thêm các ràng buộc. Các tiêu chuẩn sau đây được sử dụng để phân biệt các dạng bài toán VRP khác nhau: Bảng 1.1: Tiêu chuẩn phân biệt các dạng bài toán VRP STT Đặc tính Tùy chọn − Đơn mục tiêu 1 Số mục tiêu − Đa mục tiêu − Không cửa sổ thời gian.

Ràng buộc thời 2 − Cửa sổ thời gian một bên hoặc hai bên, cửa sổ thời gian gian cứng hoặc mềm. − Tất cả các nhu cầu của khách hàng đều được đáp ứng. 3 Ràng buộc nhu cầu − Xác định một số khách hàng nên được phục vụ. − Cho phép tách các phân phối hay không Thuộc tính của − Đoàn xe vận chuyển đồng nhất.

4 đoàn xe − Đoàn xe vận chuyển không đồng nhất. − Một xe phục vụ một lộ trình. 5 Đa sử dụng xe − Một xe có thể phục vụ nhiều hơn một lộ trình − Một kho trung tâm chứa hàng hóa. 6 Số kho − Nhiều kho hàng hóa.

− Lộ trình đóng 7 Loại lộ trình − Lộ trình mở − Khoảng thời gian phân phối đơn Thời gian hoạch 8 − Xác định khách hàng nào nên được phục vụ tại thời định điểm nào của hoạch định. − Kiểu phục vụ đơn: hoặc phân phối hoặc lấy và mang hàng hóa trở về. 9 Kiểu phục vụ − Kiểu phục vụ hỗn hợp: vừa có phân phối, vừa có mang về.2 Các biến thể quan trọng của bài toán định tuyến xe Bài toán VRP có rất nhiều biến thể dựa trên các yêu cầu vận chuyển cụ thể của các bài toán thực tế. Trong phần này, tôi sẽ trình bày một số biến thể tồn tại trong thực tế của bài toán VRP và được phân chia theo từng đặc điểm cụ thể như đặc điểm về đội xe, về yêu cầu vận chuyển hay về vấn đề lợi nhuận, các ràng buộc nội tuyến và liên tuyền, .1: Các biến thể của bài toán CVRP và mối liên kết giữa chúng [1]  CVRP (Capacitated vehicle routing problem) Bài toán định tuyến xe với dung lượng vận chuyển giới hạn.

 DCVRP (Distance- Constrained VRP) Bài toán VRP với ràng buộc quãng đường đi tối đa của mỗi xe: trong bài toán ứng với mỗi loại xe có một tham số để giới hạn độ dài quãng đường tối đa mà xe được phép đi. Mục tiêu của bài toán này là định tuyến cho tập các xe đi làm nhiệm vụ sao cho tổng quãng đường mà mỗi xe phải đi không được vượt quá tham số giới hạn đã đặt ra.  VRPTW (VRP with Time Windows) 8 Bài toán VRP với ràng buộc thời gian cửa sổ (VRPTW): trong bài toán này, mỗi khách hàng sẽ chỉ cho phép xe đến giao hoặc nhận hàng trong khoảng thời gian nhất định. Ví dụ như khách hàng 𝑖 chỉ cho phép xe đến giao hàng trong khoảng thời gian biểu diễn bởi đoạn [𝑎𝑖 , 𝑏𝑖 ], nghĩa là nếu xe đến giao hàng cho khách hàng thứ 𝑖 vào trước thời điểm 𝑎𝑖 , xe sẽ phải đứng chờ cho đến thời điểm đó mới được giao hàng, đồng thời việc giao hàng của xe cho khách hàng thứ 𝑖 phải được kết thúc trước thời điểm 𝑏𝑖.

Nếu ràng buộc thời gian đối với khách hàng thứ 𝑖 được thay thế bởi một tập các khoảng thời gian cho 𝑝 𝑝 phép ([𝑎𝑖1 , 𝑏𝑖1 ], … , [𝑎𝑖 , 𝑏𝑖 ]) thì bài toán VRPTW trở thành bài toán VRP with Multiple- time Windows  VRPB (VRP with backhauling) VRP với khả năng chuyên chở một số hàng hóa trở về (cho khách hàng cơ hội trả lại một số lượng hàng của một sản phẩm) phân biệt hai nhóm khách hàng 𝑁1 và 𝑁2. Mỗi khách hàng 𝑖 ∈ 𝑁1 đòi hỏi phải được phân phối một số lượng hàng hóa cho trước từ kho. Trong khi đó, mỗi khách hàng 𝑖 ∈ 𝑁2 yêu cầu mang một số lượng hàng hóa cho trước tại khách hàng đó trở về kho. Một giả định quan trọng là mỗi lộ trình đầu tiên phải phục vụ những khách hàng thuộc nhóm 𝑁1 và sau đó có thể phục vụ các khách hàng thuộc nhóm 𝑁2 trên đường trở về kho.

Việc trộn lẫn các khách hàng thuộc hai nhóm với nhau là không được phép, nghĩa là đầu tiên phục vụ khách hàng 𝑖 ∈ 𝑁1 , kế đến phục vụ khách hàng 𝑗 ∈ 𝑁2 , sau đó phục vụ khách hàng 𝑡 ∈ 𝑁1 ,. trên một lộ trình đơn.