Bỏ qua, tới nội dung chính
Route4Green

Khái niệm

Tối ưu tuyến đường là gì, và vì sao tối ưu từng xe không đủ

Phần lớn phần mềm dừng ở việc sắp lại thứ tự điểm giao cho xe đã có sẵn đơn. Chia đơn cho xe nào mới là phần quyết định chi phí.

Nhìn từ ghế lái xe tải: hai tay tài xế trên vô lăng, điện thoại gắn trên táp lô hiển thị bản đồ, con đường hai làn chạy qua cánh đồng lúa với một xe tải khác phía trước

Định nghĩa ngắn

Tối ưu tuyến đường là bài toán tìm cách phục vụ một tập điểm giao bằng một tập phương tiện sao cho tổng chi phí thấp nhất, trong khi vẫn tôn trọng mọi ràng buộc của vận hành: khung giờ nhận và giao, tải trọng, kích thước hàng, giờ làm việc của xe, và điểm xuất phát của từng xe.

Trong tài liệu học thuật, đây là họ bài toán VRP, viết tắt của Vehicle Routing Problem. Tên gọi đó hữu ích khi bạn muốn tra cứu thêm, nhưng không cần thiết để đọc tiếp trang này.

Ba mức, và chỗ người mua hay nhầm

Ba việc khác hẳn nhau cùng được gọi là tối ưu tuyến đường.

Sắp thứ tự điểm

Chia đơn cho cả đội xe

  1. Chỉ đường

    Người mua thường gọi là
    Mở bản đồ cho tài xế
    Thứ được quyết định
    Đường đi giữa hai điểm, cho một xe
    Hôm nay ai quyết
    Tài xế, trên đường

  2. Sắp thứ tự điểm

    Người mua thường gọi là
    Xếp lại lộ trình cho từng xe
    Thứ được quyết định
    Thứ tự các điểm giao, sau khi đơn đã được chia cho xe
    Hôm nay ai quyết
    Người điều phối chia đơn, phần mềm làm nốt phần đuôi

  3. Chia đơn cho cả đội xe

    Người mua thường gọi là
    Lập kế hoạch cho cả ngày
    Thứ được quyết định
    Dùng bao nhiêu xe, xe nào lấy đơn nào, xuất phát từ đâu, rồi mới tới thứ tự điểm
    Hôm nay ai quyết
    Người điều phối, bằng kinh nghiệm

Vì sao chia đơn mới là phần khó

Phần mềm sắp lại thứ tự điểm giao chỉ làm nốt việc sau khi anh đã chia đơn cho xe. Chia đơn mới là chỗ mất tiền.

Khi sắp thứ tự điểm cho một xe, tập đơn của xe đó đã cố định. Quyết định đắt tiền xảy ra trước đó: đơn này lẽ ra đi xe khác, xe kia hôm nay không cần chạy, đơn nọ nên xuất phát từ kho gần hơn. Số cách chia đơn tăng vọt theo mỗi xe, mỗi đơn thêm vào, nên một người giỏi cũng không kiểm hết bằng tay.

Route4Green nhận toàn bộ đơn và toàn bộ xe của một ngày trong một lời gọi, tới 300 đơn cho một ngày và một chặng vận chuyển, rồi trả về kế hoạch từng xe cùng các đơn và xe không xếp được. Danh sách không xếp được cho bạn thấy việc chia đơn đã thật sự diễn ra.

Điều gì đổi khi đội xe lớn lên

Với vài xe, người điều phối thường ra phương án tốt và biết vì sao. Từ khoảng vài chục xe, chia đơn bằng tay bắt đầu vỡ: số cách ghép đơn với xe vượt quá những gì một người kịp so trước giờ phát lệnh. Đây là quan sát, không phải ngưỡng: đội mười xe chạy sáu lượt mỗi ngày cũng chạm cùng bức tường.

Những ràng buộc lời giải phải tôn trọng

Những gì API hiện nhận và chuyển vào lõi. Đối chiếu với vận hành của bạn trước khi thử.

Theo đơn hàng

  • Khung giờ nhận và giao, mỗi khung có giờ bắt đầu và kết thúc, là ràng buộc cứng
  • Thời gian xếp hàng và dỡ hàng tại điểm
  • Khối lượng, dài rộng cao, và số kiện
  • Loại hàng, khớp với loại hàng mà xe được phép chở

Theo phương tiện

  • Tải trọng và kích thước thùng
  • Khung giờ làm việc của từng xe
  • Điểm xuất phát riêng cho từng xe, nên một lời giải có thể gồm nhiều kho
  • Tối đa 200 xe trong một job

Mục tiêu của lời giải

  • Giảm tổng quãng đường
  • Dùng ít xe nhất có thể
  • Cân tải giữa các xe
  • Ưu tiên giữ đúng khung giờ
  • Giới hạn thời lượng một chuyến

Những gì chưa có

Bốn ràng buộc có thật trong ngành mà API chưa nhận. Nếu vận hành của bạn cần chúng, nên biết ngay từ bây giờ.

  1. Khung giờ mềm. Chỉ có khung giờ cứng: đơn nằm trong khung, hoặc không được xếp.
  2. Độ ưu tiên đơn hàng. Chưa khai báo được đơn nào quan trọng hơn.
  3. Lịch trực tài xế. Lời giải làm trên xe, không trên tài xế và ca trực.
  4. Giờ cấm tải và vùng hạn chế theo thành phố, như ở Hà Nội và TP.HCM. Hiện bạn vẫn phải xử lý bên ngoài Route4Green.

Một đợt Pilot có số liệu đo được

Số liệu đo được từ đợt Pilot với VNPost tại TP.HCM nằm ở trang kết quả, kèm phạm vi và cách đọc từng số.

Pilot chuẩn gồm gì, đo thế nàoXem chi tiết kết quả Pilot

Đọc tiếp

Xem đợt Pilot và tải mẫu dữ liệuĐặt câu hỏi trước
Tối ưu tuyến đường là gì | Route4Green