Vehicle Routing — Định tuyến phương tiện
Bản có ràng buộc tải trọng của bài toán định tuyến: gom điểm thành tuyến theo góc quét rồi tối ưu từng tuyến bằng 2-opt. Kết quả cho biết cần mấy xe và tuyến nào chở gì.
2-opt chỉ đảo thứ tự điểm TRONG một tuyến, không chuyển điểm giữa các tuyến — nên số xe không đổi và phần cải thiện đến hoàn toàn từ việc gỡ các đoạn đường cắt chéo nhau.
Cận dưới chỉ tính tổng nhu cầu chia tải trọng, bỏ qua vị trí. Đạt đúng cận dưới là tốt; vượt một xe thường vì các điểm ở xa nhau không gom chung được.
2-opt chỉ gỡ các đoạn cắt chéo trong từng tuyến. Nếu mức cải thiện gần 0 thì sweep đã cho tuyến khá gọn, không phải vì thuật toán không chạy.
Lấp đầy thấp làm tăng số xe và chi phí cố định. Nhưng ép lấp đầy tối đa lại kéo dài quãng đường — hai mục tiêu này ngược nhau và lời giải tốt nằm ở giữa.
Đường thật dài hơn đường thẳng khoảng 20–40% ở đô thị. Bài toán thật còn khung giờ giao và đường một chiều, mỗi ràng buộc thêm đều làm con số này xấu đi.
| Tuyến 1 | kho → 10 → 8 → 3 → 6 → kho · tải 44/45 · 30.23 |
| Tuyến 2 | kho → 12 → 5 → 4 → kho · tải 34/45 · 37.59 |
| Tuyến 3 | kho → 7 → 9 → kho · tải 34/45 · 28.91 |
| Tuyến 4 | kho → 11 → 2 → kho · tải 28/45 · 29.13 |
| Tổng nhu cầu | 140 |
| Số xe tối thiểu lý thuyết | 4 |
| Thuật toán | Sweep theo góc cực → 2-opt trong từng tuyến |
2-opt chỉ đảo thứ tự điểm TRONG một tuyến, không chuyển điểm giữa các tuyến — nên số xe không đổi và phần cải thiện đến hoàn toàn từ việc gỡ các đoạn đường cắt chéo nhau.
Tổng nhu cầu 140 trên tải trọng 45 cho cận dưới 4 xe. Một tuyến gần rỗng thường có nghĩa là góc quét cắt ngang một cụm điểm ở gần nhau.
Chỉ là vị trí, không vẽ thứ tự đi. Cụm điểm tách rời nhau trên hình là nơi ràng buộc tải trọng gây tốn kém nhất, vì một xe buộc phải chạy qua khoảng trống.
| Tuyến | Số điểm | Tải | Lấp đầy | Trước 2-opt | Sau 2-opt | Cải thiện |
|---|---|---|---|---|---|---|
| Tuyến 1 | 4 | 44 | 98% | 30.23 | 30.23 | 0.0% |
| Tuyến 2 | 3 | 34 | 76% | 37.59 | 37.59 | 0.0% |
| Tuyến 3 | 2 | 34 | 76% | 28.91 | 28.91 | 0.0% |
| Tuyến 4 | 2 | 28 | 62% | 29.13 | 29.13 | 0.0% |
| Tuyến 1 | kho → 10 → 8 → 3 → 6 → kho · tải 44/45 · 30.23 |
| Tuyến 2 | kho → 12 → 5 → 4 → kho · tải 34/45 · 37.59 |
| Tuyến 3 | kho → 7 → 9 → kho · tải 34/45 · 28.91 |
| Tuyến 4 | kho → 11 → 2 → kho · tải 28/45 · 29.13 |
| Tổng nhu cầu | 140 |
| Số xe tối thiểu lý thuyết | 4 |
| Thuật toán | Sweep theo góc cực → 2-opt trong từng tuyến |
1.234.567 lẫn 1.234,56.Bài toán định tuyến xe (Vehicle Routing Problem) tổng quát hoá bài toán người bán hàng: nhiều xe xuất phát từ kho, phục vụ tập khách hàng, quay về kho, tối thiểu tổng chi phí. Các biến thể thực tế gồm CVRP (giới hạn tải trọng), VRPTW (khung giờ) và VRPPD (vừa giao vừa nhận).
| Tổng chi phí | quãng đường + chi phí xe + phạt trễ |
| Khoảng cách tới cận dưới | đo chất lượng heuristic |
| Thời gian giải | phải nhỏ hơn thời gian ra quyết định thực tế |
Phần quan trọng nhất của trang này. Một phương pháp được mô tả mà không nói chỗ nó hỏng là phiên bản quảng cáo của phương pháp đó.
Chưa có mô hình nào gắn riêng cho chủ đề này. Đây là những mô hình của cả ngành — liên quan ở cấp ngành, không phải cấp chủ đề.
Bài toán định tuyến xe (Vehicle Routing Problem) tổng quát hoá bài toán người bán hàng: nhiều xe xuất phát từ kho, phục vụ tập khách hàng, quay về kho, tối thiểu tổng chi phí. Các biến thể thực tế gồm CVRP (giới hạn tải trọng), VRPTW (khung giờ) và VRPPD (vừa giao vừa nhận).
1. Chọn biến thể đúng với ràng buộc thực tế của bạn. 2. Mô hình hoá dưới dạng MILP nếu quy mô nhỏ (dưới ~50 điểm). 3. Với quy mô lớn, dùng heuristic hai pha: gom cụm rồi định tuyến, hoặc định tuyến rồi tách. 4. Cải thiện lời giải bằng local search (2-opt, or-opt, relocate).
Đưa quá nhiều ràng buộc mềm thành ràng buộc cứng khiến bài toán vô nghiệm — thực tế cần phạt, không cần cấm. Lời giải tối ưu cho dữ liệu hôm qua vô dụng nếu đơn hàng thay đổi trong ngày; cần khả năng tái tối ưu nhanh.
Tổng chi phí — quãng đường + chi phí xe + phạt trễ; Khoảng cách tới cận dưới — đo chất lượng heuristic; Thời gian giải — phải nhỏ hơn thời gian ra quyết định thực tế.
Chưa xây dựng. Mục này hiện là điều hướng và tài liệu tham chiếu; chúng tôi không gắn nhãn 'live' cho thứ chưa chạy.