Travelling salesman problem modelling by mixed integer linear programming of python (MIP)

Tóm tắt

Bài toán người bán hàng là một bài toán nổi tiếng vì nó được trình bày đơn giản nhưng lời giải thì thật phức tạp. Bài toán này đã thu hút sự nghiên cứu của đông đảo nhà khoa học và nhiều thuật toán đã được đề xuất. Trong bài viết này, tác giả sử dụng phần mềm MIP (quy hoạch tuyến tính trên tập số nguyên) được viết bởi ngôn ngữ lập trình python để giải quyết bài toán với các kích cỡ khác nhau của dữ liệu đầu vào. Kết quả cho thấy đối với dữ liệu nhỏ thì thuật toán hội tụ khá nhanh về giá trị tối ưu, tuy nhiên với dữ liệu đầu vào lớn, khối lượng bước tính nhiều, cần sự cải tiến về mặt thuật toán và áp dụng tùy chọn tính toán song song.