Vấn Đề Điều Hướng Lưu Thông Trong Quản Lý Không Trời: Cách Tiếp Cận Dòng Chảy Mạng Động

Chúng tôi giải quyết vấn đề xác định cách định tuyến lại các máy bay trong hệ thống kiểm soát không lưu khi phải đối mặt với các điều kiện thời tiết thay đổi động. Mục tiêu tổng thể của vấn đề này là tối thiểu hóa chi phí trễ. Vấn đề này là mối quan tâm chủ yếu trong hệ thống kiểm soát không lưu ở châu Âu và đặc biệt là ở một số vùng trong hệ thống kiểm soát không lưu của Hoa Kỳ. Chúng tôi trình bày một cách tiếp cận lập trình toán học tích hợp bao gồm nhiều phương pháp khác nhau. Để giải quyết độ phức tạp cao, chúng tôi bắt đầu bằng cách trình bày một mô hình tổng hợp, trong đó vấn đề được hình thành như một bài toán dòng chảy mạng động, đa hàng hóa, số nguyên với một số ràng buộc bên ngoài nhất định. Sử dụng phương pháp thư giãn Lagrange, chúng tôi tạo ra các dòng chảy tổng hợp. Chúng tôi phân tách các dòng chảy tổng hợp thành một tập hợp các lộ trình bay cho từng máy bay bằng cách sử dụng một phương pháp làm tròn theo ngẫu nhiên. Tập hợp các lộ trình này sau đó được sử dụng trong một cách tiếp cận lập trình số nguyên đóng gói, giải pháp của nó tạo ra các lộ trình khả thi và gần tối ưu cho từng chuyến bay. Thuật toán Tạo Ra Lagrange tổng thể được sử dụng để giải quyết các vấn đề thực tế ở phần tây nam Hoa Kỳ. Trong các thí nghiệm tính toán, các giải pháp mà thuật toán của chúng tôi trả về nằm trong khoảng 1% so với các giới hạn dưới tương ứng.