Người giao hàng lười nhất là người đi ít nhất.Tối ưu lộ trình giao hàng
Một tài xế, hàng chục điểm giao. Thuật toán tìm đường vòng ngắn ngay trên máy bạn, và bạn xem nó nghĩ từng bước.
- Số điểm giao
- …
- Quãng đường ban đầu
- …km
- Quãng đường hiện tại
- …km
- Rút ngắn
- …%
- Thời gian máy tính thật
- …ms
- Phép so sánh đã thử
- …
Chạm vào bản đồ để thêm điểm giao (tối đa 160). Ô vuông là kho. Hoạt hình chậm lại để mắt người theo kịp; con số “thời gian máy tính thật” mới là tốc độ thuật toán.
Nó chạy thế nào
Bài toán không có lời giải nhanh tuyệt đối
Tìm vòng đi ngắn nhất qua mọi điểm là bài toán người bán hàng. Với 70 điểm, số cách đi nhiều hơn số nguyên tử trong vũ trụ; không ai thử hết được.
Bước một: tham lam
Đứng ở kho, luôn đi tới điểm gần nhất chưa ghé. Nhanh, nhưng hay bỏ sót và để lại những đường cắt chéo nhau.
Bước hai: gỡ nút
Thuật toán 2-opt tìm hai đoạn đường cắt nhau rồi đảo ngược đoạn giữa để gỡ nút. Lặp lại cho tới khi không còn nút nào gỡ được.
Vì sao quan trọng
Cùng một ý tưởng dùng cho giao hàng, xe thu gom rác, lịch tuần tra, lộ trình kiểm tra hiện trường. Rút 20% quãng đường là rút 20% xăng và giờ công mỗi ngày.
Dùng được cho
Thí nghiệm tiếp theoKét sắt trong trình duyệtKể vấn đề của bạn. Càng khó càng vui.Trao đổi với chúng tôi về nhu cầu của tổ chức bạn.
Rút lá nói chuyệnGửi yêu cầu tư vấn