Giải pháp Lập trình động cho Vấn đề Gọi xe theo yêu cầu Nhiều đến Nhiều với Một phương tiện

Một cuộc điều tra về vấn đề gọi xe theo yêu cầu nhiều đến nhiều với một phương tiện được phát triển thành hai phần (I và II). Phần I tập trung vào trường hợp "tĩnh" của vấn đề. Trong trường hợp này, các yêu cầu trung gian có thể xuất hiện trong quá trình thực hiện tuyến đường không được xem xét. Một hàm mục tiêu tổng quát được khảo sát, đó là việc tối thiểu hóa tổ hợp trọng số giữa thời gian phục vụ tất cả khách hàng và tổng độ "không hài lòng" mà họ trải qua trong thời gian chờ đợi được phục vụ. Độ không hài lòng này được giả định là một hàm tuyến tính của thời gian chờ đợi và thời gian đi của mỗi khách hàng. Các ràng buộc về khả năng chứa của phương tiện và các quy tắc ưu tiên đặc biệt là một phần của vấn đề. Một phương pháp Lập trình Động được phát triển. Thuật toán thể hiện một nỗ lực tính toán mà, mặc dù là một hàm mũ của kích thước vấn đề, thì về tiệm cận là nhỏ hơn so với nỗ lực tương ứng của thuật toán Lập trình Động cổ điển áp dụng cho một Vấn đề Người bán du lịch có cùng kích thước. Phần II mở rộng phương pháp này để giải quyết trường hợp "động" tương đương. Trong trường hợp này, các yêu cầu của khách hàng mới sẽ tự động đủ điều kiện xem xét khi chúng xảy ra. Quy trình là một chuỗi cập nhật mở, mỗi lần theo sau mỗi yêu cầu của khách hàng mới. Thuật toán chỉ tối ưu hóa trên các đầu vào đã biết và không dự đoán yêu cầu của khách hàng trong tương lai. Sự hoãn yêu cầu của khách hàng không xác định được ngăn chặn bởi các quy tắc ưu tiên được giới thiệu trong Phần I. Các ví dụ trong cả hai trường hợp "tĩnh" và "động" được trình bày.