fikisipi/elkai

🚚 elkai: Giải bài toán TSP nhanh chóng với LKH trong Python

elkai - thư viện Python cho TSP dựa trên LKH 3, kết quả chính xác hơn Google OR-Tools.

elkai là thư viện Python dùng để giải gần đúng bài toán người bán hàng (TSP) dựa trên thuật toán LKH 3 của Keld Helsgaun. Hỗ trợ cả TSP đối xứng và bất đối xứng, cung cấp API đơn giản với một dòng lệnh.

✨ Điểm nổi bật

• Dựa trên LKH 3: Kết quả tối ưu chứng minh được đến N=315, chính xác hơn Google OR-Tools
• Hỗ trợ TSP đối xứng và bất đối xứng: Linh hoạt cho nhiều dạng bài toán
• API đơn giản: Chỉ cần một dòng lệnh để nhận kết quả
• Cài đặt dễ dàng: pip install elkai
• Hỗ trợ tọa độ 2D và ma trận khoảng cách: Linh hoạt với đầu vào khác nhau

💡 Vì sao đáng chú ý

elkai khác biệt nhờ sử dụng thuật toán LKH 3 mạnh mẽ, cho kết quả chính xác hơn Google OR-Tools. Đặc biệt, dự án đã refactor LKH để không có trạng thái toàn cục, cho phép chạy nhiều bài toán khác nhau mà không cần khởi động lại chương trình. Tuy nhiên, elkai giữ GIL trong quá trình giải, nên cần dùng đa tiến trình nếu muốn chạy đồng thời với các tác vụ khác.

---

#TSP #Optimization #Python #LKH #TiniX