Operations Research: Bài Toán Pickup & Delivery 01

Một công ty vận chuyển tại TP. Hồ Chí Minh cần lập kế hoạch chi tiết cho hoạt động giao và nhận hàng (Pickup & Delivery) của đội xe trong vòng 3 ngày tới. Công ty có một kho trung tâm và phục vụ nhiều khách hàng với các yêu cầu khác nhau.

Mục Tiêu

Xây dựng lịch trình hoạt động cho đội xe sao cho tổng chi phí vận hành là thấp nhất. Tổng chi phí bao gồm:
- Chi phí cố định: Chi phí phát sinh mỗi ngày cho mỗi chiếc xe được đưa vào sử dụng
- Chi phí biến đổi: Chi phí liên quan trực tiếp đến việc xe di chuyển trên đường
Nguồn lực (Dữ liệu giả lập từ đề bài)
- Thời gian kế hoạch: 3 ngày.
- Đội xe: Có 3 xe với thông số như sau:
  - Xe 1: Sức chứa 2000 kg, Chi phí cố định/ngày: 500
  - Xe 2: Sức chứa 2500 kg, Chi phí cố định/ngày: 700
  - Xe 3: Sức chứa 2000 kg, Chi phí cố định/ngày: 900
  - Xe 4: Sức chứa 2200 kg, Chi phí cố định/ngày: 600
- Kho: Một kho trung tâm tại vị trí (4, 4) là điểm xuất phát và kết thúc của các xe. (vị trí tọa độ giả lập)

Yêu Cầu Công Việc

Trong vòng 3 ngày, công ty cần hoàn thành các yêu cầu giao nhận hàng cho các khách hàng sau: (các vị trí tọa độ giả lập)
- Khách hàng A: 4 lượt (mỗi lượt lấy 150 kg tại (2,0) và giao tại (5,2))
- Khách hàng B: 3 lượt (mỗi lượt lấy 200 kg tại (8,5) và giao tại (6,1))
- Khách hàng C: 3 lượt (mỗi lượt lấy 100 kg tại (3,7) và giao tại (3,3))
- Khách hàng D: 2 lượt (mỗi lượt lấy 250 kg tại (9,8) và giao tại (8,9))
- Khách hàng E: 2 lượt (mỗi lượt lấy 120 kg tại (0,1) và giao tại (1,0))
- Khách hàng F: 1 lượt (lấy 300 kg tại (5,8) và giao tại (1,4))
- Khách hàng G: 1 lượt (lấy 180 kg tại (7,7) và giao tại (9,1))
- Khách hàng H: 2 lượt (mỗi lượt lấy 90 kg tại (2,8) và giao tại (0,5))
Thời gian di chuyển ước tính giữa tất cả các cặp địa điểm (Kho, các điểm Pickup, các điểm Delivery) đã ước tính trước và được cung cấp dưới dạng một Ma trận Thời gian.

Các Quy Tắc & Ràng Buộc Vận Hành

Lịch trình hoạt động phải tuân thủ các quy tắc sau:
- Giới hạn Thời gian Hoạt động/Ngày: Mỗi xe không được hoạt động quá 240 phút (4 giờ) mỗi ngày (tính từ lúc rời kho đến lúc quay về kho).
- Giới hạn Sức chứa: Lượng hàng trên mỗi xe tại bất kỳ thời điểm nào không được vượt quá sức chứa tối đa của xe đó.
- Thời gian Dịch vụ: Tại mỗi điểm Pickup hoặc Delivery (không tính Kho), xe cần dừng lại 20 phút để thực hiện việc bốc/dỡ hàng. Thời gian này được tính vào tổng thời gian hoạt động trong ngày của xe.
- Thứ tự Pickup/Delivery: Đối với mỗi lượt yêu cầu, việc Pickup (lấy hàng) phải diễn ra trước việc Delivery (giao hàng) trên cùng một lộ trình của xe.
- Cùng Xe, Cùng Ngày: Việc Pickup và Delivery cho cùng một lượt yêu cầu phải được thực hiện bởi cùng một xe trong cùng một ngày.
- Không Ghé Lại Khách Trong Ngày: Nếu một khách hàng có nhiều lượt trong kế hoạch 3 ngày (Khách A, B, C, D, E, H), thì không được phép dùng cùng một chiếc xe để thực hiện nhiều hơn một lượt ghé (cả cặp P/D) cho khách hàng đó trong cùng một ngày. Các lượt ghé phải được phân bổ vào các ngày khác nhau hoặc do các xe khác nhau thực hiện trong cùng một ngày.

Kết Quả Mong Đợi

Xác định một bộ các lộ trình chi tiết cho từng xe vào mỗi ngày trong 3 ngày kế hoạch, bao gồm:
- Xe nào hoạt động vào ngày nào.
- Thứ tự các điểm dừng (Kho, Pickup, Delivery) cho mỗi xe mỗi ngày.
- Thời điểm xe đến tại mỗi điểm dừng.
- Tổng chi phí hoạt động tối ưu nhất có thể.