Route Optimization — Tối ưu tuyến đường
Đây là bộ giải thật: dựng tuyến bằng nearest neighbour rồi cải thiện bằng 2-opt cho tới khi không còn hoán đổi nào tốt hơn. Kết quả kèm mức tiết kiệm so với đúng thứ tự bạn nhập — con số quyết định việc tối ưu có đáng làm không.
Nearest neighbour dựng tuyến ban đầu, 2-opt cắt thêm 1.6% bằng 1 lần đảo đoạn. Chênh lệch giữa cột đầu và cột cuối mới là số quyết định việc tối ưu có đáng làm hay không.
Quy ra tiền là 739,857.77 mỗi chuyến. Dưới 5% thì thứ tự bạn đang chạy vốn đã gần tối ưu và công sức nên dồn sang chỗ khác.
Nearest neighbour luôn để lại vài đoạn cắt chéo nhau vì nó chọn tham lam từng bước. 2-opt gỡ đúng các nút chéo đó, và dừng khi không còn cặp nào đảo được cho ngắn hơn.
Chặng 4→1. Một chặng chiếm trên một phần tư tuyến nghĩa là có điểm nằm lệch hẳn — vấn đề phân vùng, không phải vấn đề thuật toán.
Toàn bộ tính toán trên dùng khoảng cách đường chim bay. Hệ số 1,2–1,4 là ước lượng phổ biến ở đô thị Việt Nam; nó không đổi THỨ TỰ tối ưu nhưng đổi hẳn con số chi phí.
| Thứ tự ghé tối ưu | 1 → 6 → 3 → 10 → 8 → 5 → 7 → 9 → 2 → 4 → 1 |
| Số điểm | 10 |
| Thứ tự nhập vào | 94.81 |
| Sau nearest-neighbour | 46.23 |
| Sau 2-opt | 45.49 (1 lần hoán đổi) |
| Thuật toán | nearest neighbour → 2-opt tới khi không cải thiện được nữa |
Nearest neighbour dựng tuyến ban đầu, 2-opt cắt thêm 1.6% bằng 1 lần đảo đoạn. Chênh lệch giữa cột đầu và cột cuối mới là số quyết định việc tối ưu có đáng làm hay không.
Điểm nằm tách hẳn khỏi cụm luôn đắt, dù thuật toán sắp thế nào. Với hình như thế, chia vùng hoặc gộp chuyến khác ngày tiết kiệm nhiều hơn là tối ưu tuyến.
Chặng dài nhất là 4→1 với 7.81, chiếm 17.2% tổng quãng đường. Chặng cuối luôn là đường về kho.
| Chặng | Từ | Tới | Quãng đường | Luỹ kế | Chi phí luỹ kế |
|---|---|---|---|---|---|
| 1 | điểm 1 | điểm 6 | 3.16 | 3.16 | 47,434.16 |
| 2 | điểm 6 | điểm 3 | 6.32 | 9.49 | 142,302.49 |
| 3 | điểm 3 | điểm 10 | 3.61 | 13.09 | 196,385.76 |
| 4 | điểm 10 | điểm 8 | 3.61 | 16.70 | 250,469.03 |
| 5 | điểm 8 | điểm 5 | 5.83 | 22.53 | 337,933.31 |
| 6 | điểm 5 | điểm 7 | 4.24 | 26.77 | 401,572.92 |
| 7 | điểm 7 | điểm 9 | 2.83 | 29.60 | 443,999.33 |
| 8 | điểm 9 | điểm 2 | 4.47 | 34.07 | 511,081.37 |
| 9 | điểm 2 | điểm 4 | 3.61 | 37.68 | 565,164.64 |
| 10 | điểm 4 | điểm 1 | 7.81 | 45.49 | 682,318.38 |
| Thứ tự ghé tối ưu | 1 → 6 → 3 → 10 → 8 → 5 → 7 → 9 → 2 → 4 → 1 |
| Số điểm | 10 |
| Thứ tự nhập vào | 94.81 |
| Sau nearest-neighbour | 46.23 |
| Sau 2-opt | 45.49 (1 lần hoán đổi) |
| Thuật toán | nearest neighbour → 2-opt tới khi không cải thiện được nữa |
2-opt: đảo đoạn [i..j] nếu d(a,c)+d(b,d) < d(a,b)+d(c,d)
Đây là công thức thật mà mã nguồn chạy, không phải mô tả gần đúng.
API tại /api/v1/tools/route-optimise gọi đúng hàm
này, nên kết quả trên trang và qua API không thể lệch nhau.
1.234.567 lẫn 1.234,56.Tối ưu tuyến đường tìm thứ tự ghé các điểm sao cho tổng chi phí nhỏ nhất. Đây là bài toán NP-khó, nên thực tế dùng heuristic cho lời giải đủ tốt trong vài giây thay vì lời giải tối ưu trong vài giờ.
| Tổng quãng đường | chỉ số cơ bản |
| Số xe cần dùng | thường tiết kiệm nhiều hơn quãng đường |
| Tỷ lệ giao đúng khung giờ | chỉ số khách hàng cảm nhận |
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ủ đề.
Tối ưu tuyến đường tìm thứ tự ghé các điểm sao cho tổng chi phí nhỏ nhất. Đây là bài toán NP-khó, nên thực tế dùng heuristic cho lời giải đủ tốt trong vài giây thay vì lời giải tối ưu trong vài giờ.
1. Xây ma trận khoảng cách và thời gian di chuyển từ dữ liệu bản đồ thật, không từ khoảng cách đường chim bay. 2. Đưa ràng buộc thực tế vào: khung giờ nhận hàng, tải trọng, giờ làm việc tài xế, đường cấm giờ. 3. Giải bằng heuristic (savings, tabu search) hoặc solver chuyên dụng. 4. So tuyến đề xuất với tuyến tài xế thực chạy để hiệu chỉnh mô hình.
Thời gian di chuyển phụ thuộc giờ trong ngày; ma trận tĩnh cho lời giải vô dụng ở đô thị tắc đường. Tài xế không đi theo tuyến được giao nếu tuyến trái với kinh nghiệm của họ — cần giải thích được, không chỉ tối ưu.
Tổng quãng đường — chỉ số cơ bản; Số xe cần dùng — thường tiết kiệm nhiều hơn quãng đường; Tỷ lệ giao đúng khung giờ — chỉ số khách hàng cảm nhận.
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.