Tutorial — Điều phối xe

Các chặng đường hoàn toàn độc lập với nhau vì ban tổ chức có thể điều chỉnh số lượng xe và phân chia lại hành khách giữa các chặng mà không tốn phí. Hãy xem xét bài toán tối ưu chi phí cho từng chặng riêng biệt.

Tại mỗi chặng, điều kiện để một xe không bị quá nhiệt là chở không quá $T_i - t_i$ người. Nếu chấp nhận để xe bị quá nhiệt, việc dồn nhiều hành khách vào cùng một xe sẽ tiết kiệm tiền thuê xe hơn so với việc chia thành nhiều xe cùng quá nhiệt.

Sử dụng thuật toán tham lam để so sánh trực tiếp hai phương án: dồn toàn bộ $m$ hành khách vào đúng $1$ xe và chịu bồi hoàn với chi phí $cost_i + m \cdot x_i$, hoặc thuê $\lceil m / (T_i - t_i) \rceil$ xe để không ai bị quá nhiệt với chi phí $\lceil m / (T_i - t_i) \rceil \cdot cost_i$.