Deepak K. Merchant1, George L. Nemhauser2
1Stanford Research Institute Menlo Park, California
2Cornell University, Ithaca, New York
Tóm tắt
Một mô hình thời gian rời rạc được trình bày cho bài toán phân bổ giao thông động với một điểm đến duy nhất. Sự ùn tắc được xử lý rõ ràng trong các phương trình lưu lượng. Mô hình là một bài toán lập trình toán học phi tuyến tính và phi lồi. Một phiên bản tuyến tính từng đoạn của mô hình, với một số giả định bổ sung về hàm mục tiêu, có thể được giải cho nghiệm toàn cục bằng cách sử dụng thuật toán simplex một lần—không cần phương pháp branch-and-bound. Chương trình tuyến tính từng đoạn có cấu trúc bậc thang và có thể được giải bằng các kỹ thuật phân rã hoặc phương pháp nén cho các ma trận thưa.
Từ khóa
#Phân bổ giao thông #Mô hình thời gian rời rạc #Tối ưu hóa #Thuật toán simplex #Cấu trúc bậc thang