Thuật toán định tuyến (định tuyến, lập kế hoạch chuyến đi, ...) trên đồ thị có giới hạn thời gian

Question

Tôi có cơ sở dữ liệu về trạm dừng xe buýt/tàu hỏa/... và thời gian đến/khởi hành vào mỗi ngày, v.v. Tôi đang tìm một cách để thực hiện tìm kiếm chuyến đi nhanh nhất (ngắn nhất/rẻ nhất/ít chuyển tiếp nhất) giữa hai địa điểm. Tôi muốn có các vị trí tùy ý trong tương lai, sử dụng dữ liệu OpenStreetMap để đi bộ giữa các điểm dừng và từ điểm dừng đến điểm bắt đầu/kết thúc, tuy nhiên hiện tại tôi chỉ muốn tìm đường đi giữa hai điểm dừng trong cơ sở dữ liệu.

Vấn đề là tôi không thể tìm thấy nhiều thông tin về chủ đề này, ví dụ this Wikipedia page có rất nhiều văn bản hoàn toàn không có thông tin hữu ích trong đó.

Tôi đã tìm thấy định dạng GTFS, được sử dụng trong Google Transit. Mặc dù thành phố của tôi không cung cấp nguồn cấp dữ liệu công khai (thậm chí không phải là dữ liệu riêng tư), tôi đã có tất cả thông tin quan trọng mà GTFS chứa và thực hiện chuyển đổi sẽ là tầm thường.

Có một số phần mềm dựa trên GTFS, như là OpenTripPlanner cũng có thể thực hiện định tuyến cho người đi bộ/xe hơi/xe đạp sử dụng OpenStreetMap.

Tuy nhiên, mã định tuyến không được tài liệu kỹ lưỡng (ít nhất là từ tôi đã tìm thấy) và tôi không cần toàn bộ.

Tất cả những gì tôi đang tìm là một số tổng quan tốt về các thuật toán tôi có thể sử dụng, hiệu suất của chúng, có thể một số mã giả.

Vì vậy, câu hỏi là, được cung cấp danh sách các điểm dừng, tuyến đường và thời gian đến/đi/đi, làm cách nào tôi có thể dễ dàng tìm đường nhanh nhất từ ​​điểm dừng A đến điểm dừng B?

Answer 1

1. Mô hình sự cố của bạn là graph. Mỗi trạm sẽ là một đỉnh, và mỗi xe buýt/tàu sẽ là một cạnh.
2. tạo hàm w:Edges->R, cho biết thời gian/tiền/... cho mỗi cạnh.
3. bây giờ, bạn có một vấn đề đường dẫn tối thiểu điển hình, có thể được giải quyết bằng cách Dijkstra algorithm, tìm đường dẫn tối thiểu đến tất cả các đỉnh từ một nguồn nhất định.

(*) Đối với 'nhất chuyển', cân nặng của bạn thực sự là 1 cho mỗi cạnh, vì vậy bạn thậm chí có thể tối ưu hóa này bằng cách chạy một BFS hoặc thậm chí bi-directional BFS thay vì Dijkstra, như tôi đã giải thích trong post này [Nó được giải thích cho khoảng cách xã hội, nhưng nó thực sự là cùng một thuật toán].

---

EDIT
như một chỉnh sửa với tính chất không tĩnh của đồ thị [cho thời gian] bạn đề cập trên bình luận [cho giá cả và số lượng hiệu ứng chuyển tiếp, những gì tôi đã đề cập ở trên vẫn được áp dụng, vì những đồ thị là tĩnh], bạn có thể sử dụng distance vector routing algorithm, thực tế có nghĩa là làm việc cho đồ thị động và là biến thể phân tán của Bellman Ford algorithm.
Ý tưởng thuật toán:

• định kỳ, mỗi đỉnh gửi "khoảng cách vector" của nó để láng giềng [vector cho biết có bao nhiêu 'chi phí' để đi từ đỉnh gửi, cho mỗi đỉnh khác.
• Những người hàng xóm cố gắng cập nhật bảng định tuyến của mình [thông qua cạnh nào tốt nhất để di chuyển đến từng mục tiêu]
• cho trường hợp của bạn, mỗi nút biết cách nhanh nhất để đến hàng xóm là gì? thời gian chờ đợi] và nó [đỉnh/trạm] thêm số này vào mỗi entree trong vector khoảng cách, để biết làm thế nào và bao nhiêu thời gian nó sẽ mất, để có được đến đích. Khi xe buýt rời đi, thời gian di chuyển phải được tính lại cho tất cả các nút [từ nguồn này] và véc tơ mới sẽ được gửi đến các nước lân cận