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

Transportation Science - Tập 34 Số 3 - Trang 239-255 - 2000
Dimitris Bertsimas1, Sarah Stock Patterson2
1Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
2The Fuqua School of Business, Duke University, Durham, North Carolina 27708

Tóm tắt

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.

Từ khóa

#quản lý lưu thông #không lưu #điều hướng lại #dòng chảy mạng #lập trình số nguyên

Tài liệu tham khảo

10.2514/atcq.4.4.281

10.1287/opre.46.1.57

10.1007/978-3-642-84980-0_5

Andreatta G., Tidona G. A New Formulation for the Multi-Airport Ground-Holding Problem. (1994) . Internal Report No. 3, Department of Pure and Applied Mathematics, University of Padova, Italy

10.1007/BF02216922

10.1287/opre.46.3.406

10.1002/nav.3800270107

10.1023/A:1018909224543

10.1287/opre.11.3.399

Ford L. R., 1958, Flows in Networks

Helme M. Reducing Air Traffic Delay in a Space–Time Network. (1994) 236–242Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics

10.2514/atcq.5.3.129

10.2514/atcq.1.3.255

MacDonald L., 1998, J. Air Traffic Control, 40, 12

10.1002/9781118627372

10.1007/978-3-642-86726-2_17

Powell W. B., 1995, Handbooks in Operations Research and Management Science: Networks

10.1287/trsc.27.3.228

Richetta O., 1994, Transp. Res., 28, 167

10.1287/opre.41.1.138

10.1287/opre.42.2.249

10.1287/trsc.28.4.275

Thông tin
Thông tin xuất bản

Transportation Science

Tập 34 Số 3

239-255

Thông tin tác giả