Mô phỏng bài toán người bán hàng bằng quy hoạch tuyến tính hỗn hợp nguyên (mip) của Python

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Mỹ Hạnh Phạm

Ngôn ngữ: Vie

Ký hiệu phân loại: 004 Data processing || Computer science

Thông tin xuất bản: Khoa học (Đại học Đồng Tháp) 2022

Mô tả vật lý: 29-34

Bộ sưu tập: Metadata

ID: 408115

Thêm vào giỏ Liên kết toàn văn

Tóm tắt
Chủ đề

Bài toán người bán hàng là một bài toán nổi tiếng vì nó được trình bày đơn giản nhưng lời giải thì thật phức tạp. Bài toán này đã thu hút sự nghiên cứu của đông đảo nhà khoa học và nhiều thuật toán đã được đề xuất. Trong bài viết này, tác giả sử dụng phần mềm MIP (quy hoạch tuyến tính trên tập số nguyên) được viết bởi ngôn ngữ lập trình python để giải quyết bài toán với các kích cỡ khác nhau của dữ liệu đầu vào. Kết quả cho thấy đối với dữ liệu nhỏ thì thuật toán hội tụ khá nhanh về giá trị tối ưu, tuy nhiên với dữ liệu đầu vào lớn, khối lượng bước tính nhiều, cần sự cải tiến về mặt thuật toán và áp dụng tùy chọn tính toán song song. , Tóm tắt tiếng anh, A famous travelling salesman problem, appearing simple to state but complex to solve, has been widely investigated and various algorithms have been proposed. In this article, mixed integer linear programming of python (MIP) is used to model this problem with varying input data. The result shows that with small input data the modelling code of MIP executing quickly and converging to optimal value, while large scale input data require plenty of computation time
thereby algorithm improvement as well as parallel implementation are suggested.

Tạo bộ sưu tập với mã QR