Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân rã chuỗi cân bằng tối ưu của các tập hợp có thứ tự một phần với ứng dụng trong việc tối thiểu hóa chi phí hoạt động trong các vấn đề định tuyến máy bay
Tóm tắt
Chúng tôi xem xét nhiệm vụ xây dựng lịch bay hàng ngày với chi phí hiệu quả, yêu cầu số lượng máy bay tối thiểu và số lượng tuyến bay cân bằng tối đa, cụ thể là các tuyến có cùng vị trí xuất phát và kết thúc. Chúng tôi đề xuất một chiến lược giải quyết có khả năng xác định độ khó của vấn đề bằng cách ước lượng số lượng tất cả các kế hoạch bay với số lượng máy bay tối thiểu. Với điều kiện rằng số lượng này không quá lớn, thuật toán tương tự được sử dụng để liệt kê đầy đủ và phát hiện tập hợp các giải pháp có số lượng tuyến cân bằng tối đa. Nghiên cứu thực nghiệm của chúng tôi cho thấy phương pháp này vừa hiệu quả vừa có thể mở rộng trong thực tế. Ví dụ, khi áp dụng cho lịch bay nội địa của Úc với tổng số tám mươi tám máy bay, phương pháp của chúng tôi đã tăng số lượng tuyến bay cân bằng từ chín lên bốn mươi hai, trong khi chỉ sử dụng vài phút thời gian tính toán.
Từ khóa
Tài liệu tham khảo
Ahmed MB, Mansour FZ, Haouari M (2018) Robust integrated maintenance aircraft routing and crew pairing. J Air Transp Manag 73:15–31
Arnold F, Gendreau M, Sörensen K (2019) Efficiently solving very large-scale routing problems. Comput Oper Res 107:32–42
Asmussen S, Glynn P (2007) Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability, vol 57. Springer, New York
Bertelé U, Brioschi F (1969) Contribution to nonserial dynamic programming. J Math Anal Appl 28(2):313–325
Broder A (1986) How hard is it to marry at random? (On the approximation of the permanent). In: Proceedings of the eighteenth annual ACM symposium on theory of computing, STOC ’86, pp. 50–58. ACM
Ceder A, Stern HI (1981) Deficit function bus scheduling with deadheading trip insertions for fleet size reduction. Transp Sci 15(4):338–363
Cortes JD, Suzuki Y (2020) Vehicle routing with shipment consolidation. Int J Prod Econ 227:107–120
Curticapean R, Dell H, Fomin F, Goldberg LA, Lapinskas J (2019) A fixed-parameter perspective on #BIS. Algorithmica 81:3844–3864
Dilworth RP (1950) A decomposition theorem for partially ordered sets. Annal Math 51:161–166
Dyer M, Goldberg LA, Greenhill C, Jerrum M (2004) The relative complexity of approximate counting problems. Algorithmica 38:471–500
Fulkerson DR (1956) Note on Dilworth’s decomposition theorem for partially ordered sets. Proc Am Math Soc 7:701–702
Goldreich O (2008) Computational complexity: a conceptual perspective. ACM SIGACT News 39(3):35–39
Hopcroft JE, Karp RM (1973) An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J Comput. 2(4):225–231
Knuth DE (1975) Estimating the efficiency of backtrack programs. Math Comput 29(129):122–136
Lan S, Clarke JP, Barnhart C (2006) Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transp Sci 40(1):15–28
Lei Z, Zhe L, Chun-An C, Wanpracha Art C (2020) Airline planning and scheduling: Models and solution methodologies. Front Eng Manag 7:1–26
Liu T, Ceder A (2017) Deficit function related to public transport: 50 year retrospective, new developments, and prospects. Transp Res Part B Methodol 100:1–19
Marla L, Vaze V, Barnhart C (2018) Robust optimization: Lessons learned from aircraft routing. Comput Oper Res 98:165–184
Nasibov E, Eliiyi U, Ertac MO, Kuvvetli U (2013) Deadhead trip minimization in city bus transportation: A real life application. Promet Traffic Transp 25(2):137–145
Provan JS, Ball MO (1983) The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J Comput 12:777–788
Rubinstein RY, Ridder A, Vaisman R (2013) Fast Sequential Monte Carlo Methods for Counting and Optimization. John Wiley & Sons, New York
Simovici DA, Djeraba C (2014) Mathematical Tools for Data Mining: Set Theory. Partial Orders. Combinatorics. Advanced Information and Knowledge Processing, Springer, London
Sinclair AJ (1988) Randomised algorithms for counting and generating combinatorial structures, PhD thesis, University of Edinburgh
Stern HI, Gertsbakh IB (2019) Using deficit functions for aircraft fleet routing. Oper Res Perspect 6:100–104
Stojković G, Soumis F, Desrosiers J, Solomon MM (2002) An optimization model for a real-time flight scheduling problem. Transp Res Part A Policy Pract 36(9):779–788
Vaisman R, Kroese DP (2017) Stochastic enumeration method for counting trees. Methodol Comput Appl Probab 19(1):31–73
Vaisman R, Kroese DP, Gertsbakh IB (2016) Improved sampling plans for combinatorial invariants of coherent systems. IEEE Trans Reliabil 65(1):410–424
Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8(3):410–421
Vazirani VV (2003) Approximation algorithms. Springer, Berlin