Thuật toán cho các vấn đề Lập lịch và Lộ trình Xe cộ với các ràng buộc Thời gian

Bài báo này xem xét thiết kế và phân tích các thuật toán cho các vấn đề lập lịch và lộ trình xe cộ với các ràng buộc thời gian. Với tính khó khăn vốn có của loại vấn đề này, các phương pháp xấp xỉ dường như mang lại nhiều hứa hẹn nhất cho các vấn đề có kích thước thực tiễn. Sau khi mô tả một loạt các phương pháp heuristics, chúng tôi tiến hành một nghiên cứu tính toán toàn diện về hiệu suất của chúng. Tập hợp các vấn đề bao gồm các môi trường lập lịch và lộ trình khác nhau về loại dữ liệu được sử dụng để tạo ra các vấn đề, tỷ lệ phần trăm khách hàng có thời gian cửa, độ chặt chẽ và vị trí của chúng, cũng như tầm nhìn lập lịch. Chúng tôi phát hiện rằng một số phương pháp heuristics hoạt động tốt trong các môi trường vấn đề khác nhau; đặc biệt, một thuật toán loại chèn liên tục đưa ra kết quả rất tốt.