Ứng dụng lập trình ràng buộc vào bài toán xếp lịch tài xế cho công ty vận chuyển hàng hóa
Tóm tắt
Bài toán xếp lịch tài xế là một bài toán quan trọng, ảnh hưởng trực tiếp đến hiệu suất hoạt động của công ty vận chuyển hàng hóa và sự hài lòng của khách hàng. Công việc của tài xế bao gồm việc giao nhận hàng đúng thời gian, tuân thủ các quy định về giao thông và luật lệ của nhà kho. Do đó, bài toán xếp lịch tài xế không chỉ là một vấn đề phân công công việc mà còn liên quan đến việc tối ưu hóa hoạt động của toàn bộ hệ thống vận chuyển hàng hóa. Để áp dụng các kỹ thuật lập trình ràng buộc (constraint programming) vào tình huống cụ thể, là việc xếp lịch tài xế tại công ty vận chuyển Phan Long, Quận 11, Tp. Hồ Chí Minh, chúng tôi ứng dụng cách tiếp cận lập trình ràng buộc với giải thuật tối ưu hóa nhánh-và-cận (branch-and-bound) để giải quyết hai bài toán con quan trọng trong công tác xếp lịch này: (i) xếp lịch chuyến hàng sao cho tối ưu hóa về thời gian dựa vào bài toán xếp lịch với các ràng buộc thứ tự trước sau và (ii) bài toán gán (assignment problem) để phân công tài xế phụ trách các chuyến hàng sao cho thích hợp nhất. Kết quả thực nghiệm trên dữ liệu thực tế tại công ty Phan Long cho thấy tính ổn định, tính chính xác và tính hữu hiệu về thời gian tính toán của giải pháp đề xuất.
