Thuật toán vận tải công cộng của xe buýt

Question

Tôi đang làm việc trên ứng dụng C# ngoại tuyến có thể tìm thấy tuyến xe buýt. Tôi có thể trích xuất dữ liệu lịch biểu/buýt/tuyến đường. Tôi đang tìm kiếm giải pháp đơn giản nhất sẽ làm việc với dữ liệu cơ bản.

Thuật toán nào có thể được sử dụng để tìm tuyến đường từ trạm dừng xe buýt "A" đến điểm dừng xe buýt "B"? Có một giải pháp mã nguồn mở sẵn sàng cho C#/Java không? Định dạng google GTFS cho cơ sở dữ liệu có tốt cho một giải pháp đơn giản không? http://code.google.com/transit/spec/transit_feed_specification.html

Cảm ơn bạn đã được trợ giúp. Tôi bị mắc kẹt với điều này. Tôi không biết bắt đầu từ đâu - cách lưu trữ dữ liệu và cách tìm các tuyến đường. Tôi biết về Dijkstra/A * nhưng tôi đã sử dụng chúng chỉ trên các đồ thị không phụ thuộc thời gian ...

Answer 1

Về mặt khái niệm, bạn lấy cùng một thuật toán cơ bản để đánh giá khoảng cách giữa A và B, nhưng thay vì khoảng cách, bạn nên đánh giá thời gian. Dijkstra có thể làm cả hai, nếu bạn cung cấp cho nó các đầu vào thích hợp.

Bạn thường thấy bản đồ làm thước đo khoảng cách. Tuy nhiên, cùng một bản đồ cũng có thể là một thước đo thời gian; tất cả những gì bạn cần là thêm dữ liệu về tốc độ trung bình và thời gian cần để che một khoảng cách cụ thể của một con đường cụ thể sẽ tự thoát ra. Bạn thậm chí có thể hình dung bản đồ theo thời gian; các tuyến đường mất nhiều thời gian hơn sẽ dài hơn. Dijkstra không quan tâm nó đánh giá, thực sự; nó chỉ quan tâm đến việc tìm ra con đường liên tục với số thấp nhất, và liệu số đó đại diện cho chiều dài hay thời gian là không quan trọng.

Để kết hợp tốc độ, thuật toán ngây thơ chỉ đơn giản là sử dụng giới hạn tốc độ ban ngày và giả sử bạn không bao giờ phải dừng lại khi đi từ A đến B; các thuật toán nâng cao hơn có thể kết hợp thông tin về thời gian trong ngày và các mẫu lưu lượng truy cập (điều này sẽ ảnh hưởng đến tốc độ trung bình bạn đi trên con đường đó vào thời điểm đó) và liệu đường có phải là đường cao tốc hay mặt đường hay không. tại giao lộ). Những gì bạn sử dụng phụ thuộc vào những gì bạn có sẵn, nhưng một khoảng thời gian 4 hoặc 5 lớp cơ bản của kích thước ngày phải đủ cho tất cả nhưng các ứng dụng thời gian quan trọng nhất tuyệt đối. Đối với mỗi hướng của mỗi con đường trong bản đồ của bạn, bạn cần tốc độ trung bình trong giờ cao điểm buổi sáng, ban ngày, tối cao điểm và đêm, có thể với số giờ ăn trưa. Một khi bạn có điều đó, đó là một sự thay đổi tương đối cơ bản đối với thuật toán Dijkstra để vượt qua trong một thời gian trong ngày và có nó đánh giá các tuyến dựa trên thời gian.

Answer 2

Nếu bạn quan tâm đến thông tin thời gian, thì tại sao không dán nhãn các giá trị khoảng cách trên cạnh đồ thị bằng cách sử dụng thông tin thời gian thay vì khoảng cách vật lý của chúng với nhau. Bằng cách đó, bạn sẽ tìm kiếm tuyến đường nhanh nhất, thay vì tuyến đường ngắn nhất. Sau đó, bạn có thể sử dụng Dijkstra/A * để tính toán kết quả của mình.

Tôi không rõ ràng về những gì bạn muốn nói theo thời gian. Nếu bạn có nghĩa là bạn cần trả lời các truy vấn của biểu mẫu 'chuyển từ x thành y trước 10 giờ sáng' thì bạn có thể tính toán các tuyến xe buýt nào đến trước 10 giờ sáng, có vẻ như một bộ lọc đơn giản trên dữ liệu. Sau đó áp dụng Dijkstra/A * cho dữ liệu.

Answer 3

Sự cố bạn đang làm không phải là một nhiệm vụ tầm thường. Vì vậy, nhiều như vậy, đó là có một tên: vấn đề lập trình phi tuyến hỗn hợp số nguyên (MINLP). Theo lời của một tác giả (Deb 1998):

"Khi xây dựng về mặt toán học, vấn đề lịch thời gian trở thành một nguyên hỗn hợp phi tuyến lập trình vấn đề (MINLP) có một số lượng lớn của thốn và dịch vụ- liên quan đến ràng buộc.Mặc dù nỗ lực đã được thực hiện trong quá khứ để tìm một lịch tối ưu của một mô hình đơn giản sử dụng tối ưu hóa cổ điển kỹ thuật (Thợ đóng sách & DCsilets, 1992; Kikuchi & Parameswaran, 1993), nó được quan sát thấy rằng đây là một cực kỳ nhiệm vụ khó khăn ngay cả đối với mạng chuyển tuyến nhỏ . Khó khăn phát sinh chủ yếu là do các số lượng lớn các biến và trở ngại, tính chất rời rạc của các biến, và tính chất phi tuyến liên quan đến hàm mục tiêu và ràng buộc."

Trong bài báo Deb của ông đề xuất một gen Chỉ cần để ném một cái gì đó ra khỏi đó bạn có thể thử ngay lập tức - chọn hàng ngàn tuyến đường ngẫu nhiên bắt đầu từ nguồn gốc của bạn, và cá ra những cái mà làm việc hợp lý tốt tại nhận được đến đích.

Hình ảnh thuật toán như sau: Bạn đang cố gắng tìm tuyến đường nhanh nhất từ ​​điểm dừng A để dừng B, bắt đầu tại một thời điểm nhất định. Bạn thuê 1.000 người và cánh tay họ với một phần tư để lật. Bạn yêu cầu họ lật đồng xu mỗi khi họ có cơ hội lên hoặc xuống xe buýt. Thủ trưởng, xuống xe (hoặc tiếp tục, nếu đã tắt). Đuôi, ở lại trên (hoặc tiếp tục chờ đợi, nếu tắt). Mỗi người đều có một thẻ chỉ mục để ghi lại các lựa chọn họ thực hiện khi họ đi. Bạn đi đến điểm B và chờ cho anh chàng đầu tiên xuất hiện và lấy thẻ của mình.

Answer 4

Hãy thử điều này làm mô hình dữ liệu của bạn.

Bus 1 đi vào dừng lại A, B và C. Bus 2 đi vào dừng B, D và E.

tôi sẽ lưu trữ một nút duy nhất dựa trên cả hai xe buýt và dừng lại, với khoảng cách đến các hạch được dựa trên thời gian. Chúng ta sẽ có nút A1, B1, C1, B2, D2 và E2. Trong trường hợp chuyển tiền đặc biệt, hãy đợi xe buýt tiếp theo là khoảng cách giữa các nút. Ví dụ, nếu Bus 1 đến lúc dừng B 30 phút trước Bus 2, thời gian di chuyển từ B1 đến B2 là 30 phút.

Bạn có thể áp dụng Thuật toán Dijkstra.

Answer 5

đọc nội dung này:

Lập kế hoạch đa phương thức đa phương thức. Luận văn của Thạc sĩ, Đại học Karlsruhe (TH), Fakultät für Informatik, 2009. trực tuyến có sẵn tại http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

phần định tuyến đường sắt cũng áp dụng cho định tuyến xe buýt.

Ý chính của nó: cách tiếp cận ngây thơ của việc mở rộng không gian và thời gian vào một biểu đồ duy nhất không hoạt động đối với các mạng lớn. Có những giải pháp thông minh hơn.

Answer 6

Chỉ muốn chia sẻ cách tiếp cận cuối cùng của tôi về vấn đề này. Đây là một phần của một dự án đại học, vì vậy nó có thể không hoàn toàn phù hợp để sử dụng trong thế giới thực. Nó phải chạy khá nhanh trên thiết bị Windows Mobile.

Tôi đã sử dụng 4 bảng (SQLite). Một bảng giữ danh sách các xe buýt, cái thứ hai giữ một danh sách các trạm. Một bảng khác giữ kết hợp - những gì xe buýt dừng lại tại một trạm cụ thể và nơi nào nó đi từ trạm này và mất bao lâu (phút). Tất cả các kết hợp phải được lưu trữ. Và bảng cuối cùng là một bảng thời gian đơn giản.Đối với mỗi trạm, nó liệt kê mọi xe buýt dừng ở đó và thời gian (tôi đã lưu trữ thời gian dưới dạng giá trị số nguyên - 14:34 là 1434, để làm cho nó nhanh hơn để so sánh).

Tôi đã sử dụng thuật toán tìm kiếm theo chiều rộng hai chiều. Các trạm lân cận (có thể truy cập trực tiếp) được truy xuất cho trạm bắt đầu và trạm đích. Có một con đường từ nhà ga A đến ga X nếu hai "đồ thị" trùng nhau trên một trạm. Ví dụ, từ nhà ga A, bạn có thể đến các trạm B, C, D, E (bằng cách sử dụng các xe buýt cụ thể). Và từ trạm đích X bạn có thể trực tiếp đến N, C, Z. Hai đồ thị này trùng nhau trên trạm C. Vì vậy, đường dẫn A -> C -> X tồn tại. Nếu không có đường dẫn nào được tìm thấy trong lần lặp đầu tiên này, thì thuật toán tiếp tục và lan truyền lại các đồ thị (BFS).

Thời gian không được tính đến trong bước đầu tiên - điều này làm cho nó đủ nhanh. Bạn chỉ nhận được một danh sách các đường dẫn có thể có với một danh sách các xe buýt mà bạn phải sử dụng để thực hiện các đường dẫn này. Thời gian được đánh giá ở bước cuối cùng, bạn đi qua danh sách các đường dẫn có thể và kiểm tra xem xe buýt có đi trong thời gian cụ thể không (tăng thời gian dừng).

Trên một thành phố nhỏ, với 250 trạm và hơn 100 xe buýt/đường sắt, phương pháp này hoạt động tối đa 3 thay đổi (nơi bạn phải thay đổi xe buýt trên hành trình). Chỉ mất vài giây để tính toán. Nhưng tôi phải tải toàn bộ cơ sở dữ liệu vào bộ nhớ (từ điển) để tăng tốc độ truy vấn, quá lâu.

Tôi không nghĩ rằng điều này sẽ làm việc cho một mạng lớn mặc dù. Nhưng nó hoạt động cho một phương tiện giao thông công cộng của một thành phố cỡ vừa và nhỏ.

Answer 7

Có một danh sách đầy đủ các ấn phẩm (30 +) trên các thuật toán định tuyến giao thông công cộng đã được biên soạn theo thời gian bằng cách đóng góp vào các mã nguồn mở (Java) OpenTripPlanner project đây:

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

OpenTripPlanner là công cụ định tuyến đa phương thức cũng bao gồm cả xe đạp và đi bộ - từ liên kết ở trên:

Đây là danh sách các bài viết, luận văn và sách đã truyền cảm hứng và thông báo cả công cụ định tuyến OTP hiện có nd một số thử nghiệm đang diễn ra. Hiện tại, OpenTripPlanner sử dụng biểu đồ phụ thuộc vào thời gian (trái ngược với thời gian mở rộng) chứa cả mạng lưới đường phố và mạng chuyển tuyến. Các chuyến đi chỉ dành cho xe đạp và đi bộ thường được lên kế hoạch sử dụng thuật toán A * với hệ thống phân cấp heuristic hoặc co rút Euclide. Các chuyến đi Đi bộ + Chuyển tiếp hoặc Đi xe đạp + được lên kế hoạch bằng cách sử dụng một biến thể của thuật toán MOA * với sự thống trị epsilon để cắt đường và Tung-Chew heuristic (một đồ thị cung cấp giới hạn dưới cho trọng số tổng hợp).

Thư mục định tuyến trên đã bao gồm tài liệu tham khảo cho các loại sau đây của các thuật toán và công việc liên quan:

• Đường dẫn Tìm kiếm Speedup Kỹ thuật
• Multi-mục tiêu Pareto Shortest Path
• Resource-chế Routing
• Mẫu đối chiếu và chuyển giao
• Định tuyến dựa trên thời gian biểu
• ALT và Metric Embeddings
• Hiệu chuẩn và thực hiện chi tiết
• Post-Dijkstra thông công cộng Routing

Nếu bạn tìm thấy một cái gì đó mới mà không phải trên danh sách, xin vui lòng để thêm nó vào wiki!

Theo như mã nguồn mở giao thông công cộng thư viện định tuyến khác - đó cũng là dự án RRRR bởi Bliksem Labs:

https://github.com/bliksemlabs/rrrr

Từ liên kết ở trên:

RRRR (thường phát âm R4) là một triển khai ngôn ngữ C của thuật toán định tuyến chuyển tuyến công cộng RAPTOR. Đây là thành phần định tuyến cốt lõi của kế hoạch hành trình Bliksem và hệ thống thông tin hành khách. Mục tiêu của dự án này là tạo ra các tập hợp các hành trình tối ưu Pareto trên các khu vực địa lý rộng lớn (ví dụ: BeNeLux hoặc tất cả châu Âu), cải thiện mức tiêu thụ tài nguyên và độ phức tạp của các giải pháp thay thế linh hoạt hơn hiện có. Hệ thống cuối cùng sẽ hỗ trợ cập nhật xe/chuyến đi trong thời gian thực được phản ánh trong kế hoạch chuyến đi và có khả năng chạy trực tiếp trên thiết bị di động không có kết nối Internet.

Cả OpenTripPlanner và RRRR đều sử dụng dữ liệu GTFS.