Distance Matrix là gì? Thời gian di chuyển, API và Routing

Distance matrix là một lưới thời gian và khoảng cách di chuyển giữa nhiều điểm gốc và nhiều điểm đích. Đó là cấu trúc dữ liệu đứng sau mọi xếp hạng "cửa hàng gần nhất", mọi quyết định dispatch giao hàng và mọi solver tối ưu hóa lộ trình. Bất cứ khi nào một ứng dụng phải chọn ứng viên tốt nhất trong số nhiều ứng viên theo thời gian lái xe, distance matrix đang làm việc bên dưới.

Bài viết này giải thích distance matrix thực sự là gì, thời gian di chuyển khác đường thẳng ra sao, nơi matrix xuất hiện trong các hệ thống production và những cạm bẫy gặp phải khi tập đầu vào vượt qua một nhúm điểm.

Distance matrix thực sự là gì

Ở dạng đơn giản nhất, distance matrix là một bảng hai chiều. Hàng là các điểm gốc, cột là các điểm đích, và mỗi ô chứa hai số: distance và duration. Với N điểm gốc và M điểm đích, matrix có N nhân M ô. Một request với 25 tài xế và 25 công việc tạo ra 625 ô trong một lệnh gọi.

Các giá trị trong những ô đó đến từ một routing engine đi qua đồ thị mạng lưới đường thực. Nó chọn đường nhanh nhất từ mỗi điểm gốc đến mỗi điểm đích, cộng chi phí các đoạn và trả về tổng. Điều đó về cơ bản khác với phép tính haversine, vốn vẽ một đường thẳng giữa hai tọa độ và bỏ qua việc nhà cửa, sông, đường một chiều có tồn tại.

Một cặp tọa độ cho bạn biết hai điểm ở đâu. Distance matrix cho bạn biết thực sự tốn bao nhiêu để đi giữa chúng.

Distance vs Duration

Ba con số khác nhau thường được gọi là "distance", và nhầm lẫn chúng là bug phổ biến nhất trong code routing.

Khoảng cách haversine là khoảng cách great-circle giữa hai cặp vĩ độ và kinh độ. Nó tính nhanh, không cần network call, và sai cho mọi tác vụ liên quan đến lái xe. Khoảng cách haversine 2 km có thể là 7 km lái xe khi bạn tính đến con sông không thể vượt.

Khoảng cách trên mạng lưới đường là độ dài của đường có thể lái thực sự. Nó tính cả đường một chiều, hạn chế rẽ và topology của đồ thị đường. Đây là thứ distance matrix API trả về trong trường distance.

Duration with traffic là thời gian chuyến đi sẽ mất với điều kiện giao thông hiện tại hoặc dự đoán. Một đoạn cao tốc 12 km mất sáu phút lúc 02:00 và hai mươi lăm phút lúc 17:30. Hệ thống production quan tâm đến ETA sẽ yêu cầu duration nhận biết giao thông và truyền thời điểm khởi hành để routing engine mô hình hóa tắc nghẽn đúng.

Cho ranking và dispatch, duration gần như luôn thắng distance. Tài xế không quan tâm rằng công việc gần hơn xa thêm 800 mét nếu nó tiết kiệm bốn phút lái xe.

Distance matrix xuất hiện ở đâu

Distance matrix âm thầm chạy bên dưới phần lớn các tính năng logistics và nhận biết vị trí.

• Gán tài xế giao hàng: mỗi đơn đang chờ được khớp với mỗi tài xế rảnh. Dispatcher chọn ô có duration thấp nhất tôn trọng sức chứa xe và ràng buộc ca làm
• Dispatching và rebalancing đội xe: nền tảng ride-hailing và last-mile tính matrix giữa xe và vùng cầu mỗi vài giây để giữ xe gần khách
• Xếp hạng store và venue locator: thay vì trả về năm cửa hàng gần nhất theo haversine, locator tính một matrix nhỏ từ vị trí người dùng đến các ứng viên và xếp hạng theo thời gian lái xe
• Tính ETA quy mô lớn: marketplace với nhiều đơn đồng thời gộp ETA vào lệnh gọi matrix thay vì bắn hàng nghìn request route đơn lẻ
• VRP solver: solver vehicle routing problem (OR-Tools, jsprit, optimiser thương mại) cần một matrix chi phí đầy đủ làm input. Chất lượng giải pháp routing bị giới hạn bởi chất lượng matrix bạn cấp
• Chọn vị trí và lập kế hoạch lãnh thổ: nhà phân tích tính matrix giữa các vị trí ứng viên và cụm khách hàng để chọn kho giảm thiểu tổng thời gian lái xe

Trong tất cả những việc này, matrix là primitive tính toán hàng loạt. Đó là thứ cho phép một hệ thống lập luận về "tốt nhất trong nhiều" mà không phải trả chi phí của N nhân M lệnh gọi routing đơn lẻ.

Cạm bẫy trong production

Distance matrix dễ trong ngày đầu và nhanh chóng khó hơn.

Bất đối xứng là mặc định. Mạng lưới đường thực có đường một chiều, đường có dải phân cách và chi phí rẽ bất đối xứng. Ô tại (A, B) hiếm khi bằng ô tại (B, A). Coi matrix là đối xứng để tiết kiệm bộ nhớ là một trong những nguyên nhân kinh điển gây routing sai chiều trong hệ thống dispatch.

Chi phí N nhân M. Matrix 100 nhân 100 là 10.000 ô. Matrix 500 nhân 500 là 250.000 ô. Chi phí và độ trễ tăng theo bậc hai. Phần lớn hệ thống production gộp matrix thành chunk (50 nhân 50 hoặc 100 nhân 100), parallel hóa các request và cache kết quả không thay đổi thường xuyên, ví dụ matrix giữa một tập kho cố định và một tập cửa hàng cố định.

Biến động theo giờ trong ngày. Matrix tính lúc 03:00 không còn hợp lệ lúc 17:00. Nếu logic dispatch của bạn phụ thuộc vào lưu lượng giao thông, hãy yêu cầu matrix nhận biết giao thông tại thời điểm ra quyết định hoặc tính trước một tập nhỏ matrix theo khung giờ (cao điểm sáng, off-peak, cao điểm tối) và chọn cái phù hợp.

Batching và rate limit. Distance matrix API tính phí theo phần tử, không theo request, và phần lớn nhà cung cấp giới hạn kích thước một lệnh gọi. Hãy lên kế hoạch chunking và back-pressure ngay từ đầu thay vì phát hiện khi đã ở quy mô lớn.

Tọa độ kém vào, rác ra. Matrix chỉ tốt như tọa độ cấp cho nó. Một geocode rơi nhầm bên đường có dải phân cách sẽ tạo ra duration sai bét. Hãy validate tọa độ đầu vào trước khi đưa vào request matrix.

Distance matrix trong MapAtlas

MapAtlas Distance Matrix API tính matrix N nhân M đầy đủ về thời gian và khoảng cách di chuyển trên mạng lưới đường thực toàn châu Âu và toàn cầu. Nó hỗ trợ profile xe hơi, xe tải, xe đạp và người đi bộ, chấp nhận request nhận biết giao thông với thời điểm khởi hành, và được xây dựng cho kích thước batch mà workload dispatch và tối ưu hóa thực tế cần.

Cho workload vượt quá ranking, Distance Matrix API kết hợp tự nhiên với Optimize Route API, nhận một matrix và một tập điểm dừng và trả về một tuyến có thứ tự giảm thiểu tổng thời gian lái xe, và với Isochrone API cho bộ lọc "mọi thứ có thể đến trong X phút" thu hẹp tập ứng viên trước lệnh gọi matrix.

Distance matrix không hào nhoáng. Nó chỉ là một lưới số. Nhưng đó là lưới số biến "tìm cái tốt nhất trong nhiều" từ một cơn ác mộng routing N nhân M thành một request hàng loạt duy nhất, và làm đúng mảnh dữ liệu đó là điều phân biệt một sản phẩm logistics thật với một demo có năm pin trên bản đồ.