MỘT THUẬT TOÁN HIỆU QUẢ DỰA TRÊN GIẢI THUẬT TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN r|p TRUNG TÂM

Vũ Đức Quang, Hoàng Xuân Huấn, Đỗ Thanh Mai



DOI: 10.15625/vap.2016.00059

Abstract


Bài toán (r|p) trung tâm nhằm định vị điểm mở cơ sở cho hai đối thủ Trước và Sau (đối thủ của Trước) để mỗi người thu hút được thị phần lớn nhất cho mình đang là bài toán thời sự. Trong bài toán này, Trước được mở p cơ sở và Sau được mở r cơ sở. Thông thường, các khách hàng sẽ chọn cơ sở gần họ nhất làm nhà cung cấp cho họ. Chúng ta cần tìm cách chọn ra p vị trí đặt cơ sở cho Trước nhằm tối đa hóa thị phần (và đó là lợi nhuận) của mình với lưu ý là Sau cũng luôn tìm cách tối ưu hóa thị phần dựa trên phân bố cơ sở đã biết của Trước. Đây là một bài toán quy hoạch 2 mức thuộc loại NP-khó và đã có nhiều thuật toán được đề xuất. Trong bài báo, chúng tôi đề xuất một thuật toán tối ưu đàn kiến có sử dụng tìm kiếm địa phương. Kết quả thử nghiệm cho thấy thuật toán mới đề xuất của chúng tôi so với 3 phương pháp công bố gần đây có sử dụng phần mềm công cụ CPLEX thì: thuật toán thứ nhất có kết quả ngang bằng với kết quả của chúng tôi, nhưng chạy chậm hơn; thuật toán thứ hai có kết quả kém hơn kết quả của chúng tôi, nhưng chạy nhanh hơn; còn thuật toán thứ 3 cho kết quả ngang bằng và chạy nhanh hơn thuật toán của chúng tôi.

Keywords


thuật toán ACO, tìm kiếm địa phương, (r|p)-trung tâm



Copyright (c) 2017 PROCEEDING of Publishing House for Science and Technology



PROCEEDING

PUBLISHING HOUSE FOR SCIENCE AND TECHNOLOGY

Website: http://vap.ac.vn

Contact: nxb@vap.ac.vn