Tìm đường đi tối ưu trong vận tải là một bài toán phổ biến và có rất nhiều phương án giải quyết. Tuy nhiên áp dụng vào thực tế thì không phải phương án nào cũng hoàn toàn tối ưu. ABSoft đã xây dựng một giải thuật tối ưu cho bài toán này khi áp dụng trên google map.
Đặt vấn đề
Một người đi từ điểm A đến điểm B, trên đường đi họ sẽ ghé qua các cặp điểm với điều kiện: các điểm này nằm trong một phạm vi nhất định đối với hướng di chuyển của người này. Cần tìm đường đi ngắn nhất từ A đến B đi tới tất cả các điểm, mỗi điểm trong cặp điểm có thứ tự ghé thăm nhất định (một trong hai điểm phải ghé trước điểm kia).
Giải quyết vấn đề
Thư viện tsp resolve (tài liệu ở cuối bài viết này) giúp tìm đường tối ưu đi từ A đến B ghé thăm tất cả các điểm có bao gồm đánh giá trọng số (giá trị tối ưu cho hành trình), tuy nhiên việc áp dụng thư viện này vào yêu cầu của bài toán thì chưa phù hợp.
Cần điều chỉnh lại các yếu tố sau:
- Phạm vi các điểm giới hạn theo chiều dài và chiều rộng tính theo đường chim bay từ điểm A đến điểm B
- Các cặp điểm có thứ tự ghé thăm, khi trộn mảng các điểm thỏa mãn và tính giá trị tối ưu của hành trình cần kết hợp điều kiện thứ tự ghé thăm này
- Kết hợp các hàm tính toán quãng đường, vẽ hành trình và phạm vi của thư viện google map javascript để tính giá trị tối ưu
<Quan tâm xin vui lòng liên hệ để được hỗ trợ chi tiết>
Case study
Nhân viên của một công ty ship hàng từ Nhà hát lớn Hải Phòng đi Cầu Rào, cần tìm những khách hàng có nhu cầu ship hàng với điều kiện cả người cần ship và người nhận nằm không cách trục đường từ nhà hát lớn xuống cầu rào quá 1km. Tìm đường đi ngắn nhất cho shipper này và thể hiện trên google map.
Ví dụ tìm đường đi ngắn nhất cho shipper
Ứng dụng thực tế
Dịch vụ giao nhận, ship hàng, dịch vụ vận tải hàng hóa thông thường,…
Tài liệu tham khảo
