An accelerated L-shaped method for solving two-stage stochastic programs in disaster management

( 0 đánh giá )
Miễn phí

Hai giai đoạn: (1) quyết định vị trí và lượng hàng cứu trợ trước thảm họa; (2) phân phối hàng sau khi thảm họa xảy ra, với các điều kiện mạng lưới và nhu cầu không chắc chắn.

  • Mô hình tham chiếu: Rawls & Turnquist (2010) về định vị và lưu trữ hàng cứu trợ.
  • - Phương pháp L-shaped truyền thống được tăng tốc bằng cách sử dụng thuật toán điểm nội chuyên biệt (Specialized Interior-Point Method – SIPM) để giải các bài toán con lớn ở giai đoạn hai.
  • - SIPM khai thác cấu trúc đặc biệt của ma trận ràng buộc giai đoạn hai (recourse matrix W) để giảm thời gian tính toán đáng kể.
  • - Áp dụng thực nghiệm: bài toán quy mô lớn tại vùng ven biển Đông Nam Hoa Kỳ với 90 nút, 5 loại hàng cứu trợ, 3 loại kho, 118 kịch bản bão từ dữ liệu 1900–2014.
  • - So sánh hiệu năng:
  •   - Gurobi: 65 giờ
  •   - L-shaped chuẩn: 2 giờ
  •   - L-shaped tăng tốc (SIPM): 1 giờ
  • - SIPM nhanh gấp đôi so với phương pháp nội điểm mặc định (linprog) và cạnh tranh với Gurobi barrier method.
  • - Kết quả cho thấy giải pháp lưu trữ phân tán, tránh các vùng dễ bị tổn thương, hiệu quả hơn so với giải pháp tập trung như trong Rawls & Turnquist.
  • - Phương pháp có thể áp dụng cho nhiều bài toán quy hoạch ngẫu nhiên hai giai đoạn trong quản lý thiên tai, đặc biệt khi cần phản ứng nhanh với dự báo ngắn hạn.