Định tuyến giao hàng đa kho

MDVRP · Giải thuật di truyền (GA)

Mô hình bài toán

3 kho 5 xe 13 cửa hàng
Dda
Quãng đường (km)
τda
Thời gian di chuyển (phút)
qc
Nhu cầu cửa hàng (kg)
Xdav
Xe v đi cung d → a (0/1)

Tham số

Hàm mục tiêu

Z1 = C · ∑ Dda Xdav
Z2 = ∑v Lv · f · D(kho, điểm đầu)
lexmin (Z₁, Z₂) · Chi phí trước, phát thải sau

Ràng buộc

Giải thuật di truyền (GA)

Một cá thể là một thứ tự ghé 13 cửa hàng. Giải mã thứ tự đó thành các tuyến rồi mới tính chi phí và phát thải.

Một vòng tiến hóa

Chưa đủ thế hệ → Quay lại bước 2Đủ thế hệ → Lấy phương án tốt nhất đã tìm được

Nhiễm sắc thể → các tuyến

Lai PMX · ví dụ 5 gen

Lê Đức Đạo, bài giảng Giải thuật di truyền, slide 2 và 7.

Mô phỏng các tuyến xe

Chi phí
–
Quãng đường
–
Phát thải
–
Số xe
–

Tối đa 500 kg mỗi xe

Thứ tự giao hàng Mốc tối ưu
Các tuyến giao hàngMỗi hàng là một tuyến. Xe rời kho, giao tại các cửa hàng theo thứ tự rồi quay về bằng đường nét đứt.
Giao hàngVề kho
1 phút dữ liệu = 0,32 giây mô phỏng · dừng minh họa 0,6 giây/điểm

Hội tụ của GA

Chưa có lượt chạy GA

Chạy GA để xem chi phí và độ đa dạng qua các thế hệ.

Chi tiết các tuyến

Tùy chỉnh và thử nghiệm

Mốc quy hoạch động – Chưa chạy · Thế hệ –

Độ ổn định qua nhiều seed

Mỗi chấm là một lượt có nghiệm khả thi. Xanh lá: khớp cả Z₁ và Z₂; cam: khớp Z₁; đỏ: cao hơn mốc.