ÁP DỤNG THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN ĐỂ GIẢI QUYẾT BÀI TOÁN VỊ TRÍ CƠ SỞ

Abstract

cuộc sống, việc đạt lợi nhuận cao hay thấp trong kinh doanh buôn bán, cung cấp dịch vụ phụ thuộc rất nhiều yếu tố. Trong đó, có một yếu tốt quan trọng đầu tiên, đóng góp một phần rất lớn đó là xác định được địa điểm đặt dịch vụ thuật lợi – nơi cung cấp dịch vụ cho khách hàng. Có rất nhiều tiêu chí đặt ra khi chọn vị trí đặt cơ sở như: thuận tiện về giao thông, là nơi tập trung đông dân cư, … để làm sao thu được lợi nhuận cao nhất. Đặc biệt, đối với các trường hợp khẩn cấp như cứu thương, cứu hỏa thì yêu cầu về khoảng cách nhỏ nhất là vô cùng quan trọng, có thể nói là quan trọng nhất trong các yếu tố. Bài toán đặt ra là: đặt các trạm dịch vụ ở đâu để thời gian di chuyển bệnh nhân từ nơi xa bệnh viên nhất (hoặc ngược lại, từ các trạm dịch vụ đến nơi bệnh nhân xa nhất) là nhỏ nhất có thể. Còn với dịch vụ phổ biến như trạm xăng, thùng phiếu, bốt điện thoại, … thì yêu cầu lại là chi phí từ các khách hàng (hay người có nhu cầu) đến địa điểm phục vụ gần khách hàng nhất là nhỏ nhất. Bài toán này thuộc dạng NP-khó, có rất nhiều các thuật giải khác nhau được đưa ra để có thể tìm lời giải tối ưu cho bài toán này như: thuật toán di truyền, thuật toán tham lam, thuật toán tối ưu hóa bầy đàn, tìm kiếm tabu… Tuy nhiên các giải thuật trên đều tốn chi phí về thời gian và/hoặc không gian lớn. Tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận metaheuristic tương đối mới, do Dorigo giới thiệu vào năm 1991 và liên tục được phát triển cho đến nay. Thành công đầu tiên của các thuật toán ACO là giải quyết bài toán Người chào hàng nổi tiếng với số đỉnh lên tới hơn 2000 với kết quả thu được là tốt, hiệu quả của nó được chứng minh bằng thực nghiệm. Đầu tiên, luận văn đã hệ thống hóa các kiến thức cơ sở về lý thuyết độ phức tạp thuật toán, lớp các bài toán P, NP, NP-khó và NP-đầy đủ. Sau đó, luận văn trình bày các bài toán điển hình trong lớp các bài toán vị trí cơ sở cùng các nghiên cứu đã được công bố gần đây. Tiếp theo, tác giả đề xuất thuật toán dựa trên giải thuật tối ưu đàn kiến giải một số bài toán vị trí cơ sở hiện nay và so sánh kết quả thu được với một số công trình đã được công bố gần đầy nhằm rút ra được các ưu nhược điểm của thuật toán. Kết quả này đã được tác giả công bố trong 2 công trình nghiên cứu khoa học.