A strategy to find the best route only via public transport?

Question

Finding routes for the car is quite simple: you keep a weighted schedule of all roads, and you can use the Jikstra algorithm [1]. The route of the bus is less obvious. With a bus, you should present things like “wait 10 minutes for the next bus” or “go one block to another stop” and submit them to your path search algorithm.

It is not always easy for cars. In some cities, some roads go one way only to the city in the morning, and in the evening one way only from the city. Some advanced GPS devices know how to avoid busy routes during rush hour.

How would you effectively present such a time-dependent graph and find a route? There is no need for a provably optimal solution; if the traveler wanted to be on time, they would buy a car .; -)

[1] The wonderful algorithm mentioned in the example is because everyone has heard about it, although A * is the more likely choice for this application.

Answer 1

I participated in the development of one magazine planning system for Stockholm public transport in Sweden. It was based on the Jikstra algorithm, but with completion before each node was visited on the system. Today, when there are reliable coordinates available for each stop, I assume that the A * algorithm will be the choice.

Upcoming traffic data was regularly extracted from several databases and compiled into large tables loaded into the memory of our search server cluster.

One key to the sucessfull algorithm used a path cost function based on travel time and wait times multiplied by different values. Known in Swedish as “kresu” -time, these weighted times reflect the fact that, for example, a one minute wait time is usually equivalent to an “inconvenience” for two minutes of travel time.

KRESU scale table

• x1 - Travel time
• x2 - Walking between stops
• x2 - Waiting to stop while traveling. A stop under the roof, with shops, etc., you can get a little lower weight and the crowded stations above to configure the algorithm.
• The weight for the waiting time at the first stop is a function of traffic intensity and can range from 0.5 to 3.

Data structure

Region The named region in which you travel can begin or end. A bus stop can be a two-stop area. A larger station with multiple platforms can be one area with one stop for each platform. Data: Name, Stop in scope

Stops Array with all bus, train and metro stops. Please note that you usually need two stops, one for each direction, because it takes some time to cross the street or go to another platform. Data: name, links, nodes

Links List with other stops you can reach by going from that stop. Data: Rest stop, Time to go to another stop

Lines / Tours You have a bus number and destination. The bus starts at one stop and passes several stops along the way to the destination. Data: number, name, purpose

Nodes Usually you have a schedule with a minimum time when it should be at the first and last stop on the tour. Each time a bus / train passes a stop, you add a new node array to the array. This table can have millions of values ​​per day. Data: line / tour, stop, arrival time, departure time, error field, next node in the tour

Search An array with the same size as the array of nodes used to store how you got there and the cost of the path. Data: Back-link with previous node (not set if node is not set), Path Cost (endless for invisible)

Answer 2

What you are talking about is more complicated than something like mathematical models that can be described using simple data structures such as graphs and simple algorithms like Djikstra's. What you are asking for is a more complex problem, similar to those found in the world of automated logistics management.

One way to think that you are asking a multidimensional problem, you should be able to calculate:

• Distance optimization
• Time optimization
• Route optimization
• Optimization of the “time horizon” (if it’s 5:25, and the bus only appears at 7:00, choose a different route.)

Given all these circumstances, you can try to make deterministic modeling using complex multi-layer data structures. For example, you could use a weighted graph to represent existing potential routes, where each node also contained finite state machines that added a weight offset to the route depending on the time values ​​(therefore, crossing a node at 5:25 you get a different value, than if your simulation crossed it at 7:00.)

However, I think that at this stage you will come across a simulation that is becoming increasingly complex, which most likely does not provide an “excellent” approximation of optimal routes when the advice is passed to the real world. It turns out that software and mathematical modeling and simulation are, at best, a weak tool when confronted with chaotic behavior and dynamism in the real world.

My suggestion is to use an alternative strategy. I would try to use a genetic algorithm in which DNA for an individual calculated a potential route, then I would create a fitness function that encodes costs and weights in a more user-friendly form of the search table. Then I would like the Genetic Algorithm to try to get closer on an almost optimal solution for the public transport search route. On modern GA computers, this is likely to work quite well, and it should be at least relatively resistant to real-world dynamics.

I think most systems that do this kind of thing take a “simple way out” and just do something like the A * search algorithm or something like a greedy, calculated, weighted ordinary walk. It should be remembered that users of public transport themselves do not know what the optimal route will be, so an optimal solution of 90% will still be an excellent solution for the average case.

Answer 3

Some data points you need to know in the public transport arena:

• Each transfer carries a 10-minute penalty (unless it is a time transfer) in the minds of riders. That is, mentally riding with one tire, which takes 40 minutes, is approximately equivalent to a 30-minute ride requiring transmission.
• The maximum distance that most people want to go to the bus stop is 1/4 mile. Train Station / Light Rail about 1/2 mile.
• The distance is not related to the public transport driver. (Only time is important)
• Frequency matters (if the connection is missing, how long until the next bus). Riders prefer more frequent service options if the alternative is within an hour for the next express.
• The railroad has a higher preference than the bus (more confidence that the train will come and will go in the right direction).
• The acquisition of a new tariff is a great success. (add about 15-20 minutes fine)
• The total travel time matters (with excess fines).
• How seamless is the mix? Should a racer exist at a train station crossing a busy street? Or is it just getting off the train and taking 4 steps to the bus?
• Crossing busy streets - another big penalty for transfers - may miss the connection because it cannot go through the street fast enough.

Answer 4

Finding routes for the car is pretty easy: you keep a weighted schedule of all roads, and you could use the Jikstra Algorithm. The bus route is less obvious.

This may be less obvious, but the reality is that it's just another dimension of the car’s problem with the addition of endless costing.

For example, you mark tires whose time has passed as having infinite value - then they are not included in the calculation.

You can then decide how to evaluate each aspect.

Transit time can be weighted by 1. Waiting time can be weighted by 1. Transfers can become weighted by 0.5 (since I would rather go back there and get an additional transfer)

Then you calculate all the routes on the graph using any conventional cost algorithm with the addition of infinite cost:

Each time you move around the edge, you must track the "current" time (add transition time), and if you reach the vector, you must assign an infinite value to any tires that are up to your current time. The current time increases by time waiting on this vector until the next bus remains, then you can move around the other edge and find new costs.

In other words, there is a new “current time” restriction, which is the start time of the first bus, summed up with all transit and waiting times for buses and stops.

This complicates the algorithm only a little, but the algorithm is still the same. You can see that most of the algorithms can be applied to this, for some it may take several passes, and some of them will not work, because you cannot add time -> infinite cost calculation inline. But most should work fine.

You can simplify this by simply assuming that the buses are on schedule and there is ALWAYS a different bus, but it increases the waiting time. Make the algorithm only by summing the transit costs, then go through the tree again and add the expected expenses depending on when the next bus arrives. Sometimes this leads to less effective versions, but the overall schedule of even a large city is actually quite small, so this is not a problem. In most cases, one or two routes will be the obvious winners.

Google has this, but also includes additional edges for moving from one bus stop to another so that you can find a slightly better route if you are willing to walk in cities with large bus systems.

-Adam

Answer 5

if the cost of each stage of the trip is measured in time, then the only complication is factoring in the schedule, which simply changes the cost of each node to a function of the current time t, where t is simply the total shutdown time (provided that the graphs are normalized to start with t = 0) .

therefore, instead of node A having a cost of 10 minutes, it has a cost f (t), defined as:

• t1 = nextScheduledStop (t); // to get the next stop time at or after time t
• baseTime for leg = 10 // e.g. a 10 minute ride
• return (t1-t) + baseTime

waiting time is included dynamically in the cost of each leg, and walks between stops are just arcs with a constant cost of time

with this view you should be able to directly apply the A * or Dijkstra algorithm

Answer 6

The way I think about this problem is that you are ultimately trying to optimize your average speed from the start point to the end point. In particular, you don’t care about the total distance, if you drive [well] out of your way, it saves time. Thus, the bulk of the decision space will need to determine the effective available routes that span the non-trivial parts of the total distance at relatively high speeds between the beginning and the end.

According to your initial moment, the typical car route algorithms used by GPS navigation devices to make a trip by car are a good reference to the optimal optimal time and optimal route estimates. In other words, your bus ride will be very useful for a car-based solution. Obviously, a bus-based routing system will have much more limitations than car-based solutions, but having a car-based solution as a reference (time and distance) gives the bus algorithm an optimization for *. Thus, if you want to be free, you want to turn the car solution into the set of possible bus solutions in an iterative way or, perhaps more likely, take the possible bus solutions and compare them with your car solution to know if you are doing “well” or not.

To make this somewhat more specific, a limited number of buses will be available for a specific departure time at any reasonable time, which can cover a significant percentage of your total distance. Based on direct automobile analysis, a reasonable period of time and a significant percentage of the distance become quantifiable using some slightly subjective indicators. Of course, it becomes easier to evaluate each possibility against another in a more absolute sense.

As soon as you have a set of possible main segments available as possible answers within the solution, you need to connect them together with other possible tracks for walking and waiting .... or if the recursive choice of additional short bus routes is far enough from each other. Intuitively, it seems that there really is no prohibitive set of options due to paradoxical restrictions (see footnote below). Even if you cannot undo all possible combinations from there, what remains must be optimized using simulated annealing (SA) type algorithm. A Monte Carlo method would be another option.

The way we overcame the problem up to this point leaves us with something that is quite similar to how SA algorithms are applied to the automated layout and routing of ASIC, FPGA chips, as well as the placement and routing of printed circuit boards, that there is quite a lot of published work on optimizing this type of problematic form.

* Note: Usually I call it the “Paradox of Constraints” - my term. While people can naturally think of more limited issues that are harder to solve, restrictions reduce choices, and less choices mean more brute force. When you can use brute force, then even the best solution is available.

Answer 7

Basically, the node on your graph should contain not only the location, but also the earliest time you can get there. You can think of it as exploring a graph in space (place, time). Also, if you have (place, t1) and (place, t2), where t1 <t2, drop (place, t2).

Theoretically, this will be the earliest arrival time for all possible directions from your starting node. In practice, you need heuristics to trim roads that take you too far from your destination.

You also need heuristics to consider promising routes to less promising ones - if the route leads far from your destination, it is less likely (but not entirely unlikely) to be good.

Answer 8

I think your problem is more complicated than you expect. A recent COST action is focused on solving this problem: http://www.cost.esf.org/domains_actions/tud/Actions/TU1004 : "Modeling passenger traffic flows in the era of intelligent transport systems."

From my point of view, conventional SPS algorithms are not suitable for this. You have a dynamic state of the network, where some options for moving forward are unexcited (the route is always "open" for a car, bicycle, pedestrian, and a transit connection is available only for a certain stay).

I think that here we need a new multi-criteria (time, reliability, cost, comfort and more criteria). It should be calculated in real time: 1) publish information to the end user in a short time; 2) be able to configure the path in real time (based on the conditions of traffic in real time - from ITS).

I am going to think about this problem over the next few months (perhaps even throughout my doctoral dissertation).

Relationship Rafal

Answer 9

I don’t think that there is any other special data structure that will satisfy these specific needs, but you can still use regular data structures, such as a linked list, and then perform route calculations for each given factor - you will need some then enter in your application variables that affect the result, and then perform the calculations accordingly, i.e. depending on the input.

As for expectations and so on, are these factors that are associated with a particular node right? You can translate this factor into the node route for each branch attached to the node. For example, you can say for each branch from node X, if there is an expectation of m minutes on node X, then increase the weight of the branch by [m / Some base value * 100]% (just an example). This way you took other factors into account evenly, but at the same time supported a simple view of the problem you want to solve.

Answer 10

If I were to solve this problem, I would probably start with an annotated graph. Each node on the graph will represent each intersection in the city, regardless of whether the public transport system stops there - this helps explain the need for walking, etc. At intersections with transit services, you comment on them using stop labels - labels that allow you to find a service schedule for a stop.

Then you have a choice. Do you need the best route or just a route? Do you show routes in real time or can you calculate and cache solutions?

If you need "real-time computation", you probably want to go with a greedy algorithm, I think the A * algorithm is probably quite suitable for this problem area.

If you need optimal solutions, you should look at dynamic programming on the chart ... optimal solutions will probably require much more time to calculate, but you only need to find them once, and then they can be cached. Perhaps your A * algorithm may use pre-calculated optimal paths to inform your decisions about "similar" routes.

Answer 11

A terribly inefficient way that could work would be to keep a copy of each intersection in the city for every minute of the day. The bus route from Elm and 2 to the Main and 25th will be presented as, say,

elm_st_and_2nd[12][30].edges : elm_st_and_1st[12][35] # 5 minute walk to the next intersection time = 5 minutes transport = foot main_st_and_25th[1][15] # 40 minute bus ride time = 40 minutes transport = bus elm_st_and_1st[12][36] # stay in one place for one minute time = 1 minute transport = stand still 

Run your favorite path finding algorithm on this chart and pray for a good virtual memory implementation.

Answer 12

You answer the question yourself. Using the A * or Dijkstra algorithm, all you have to do is choose the best price for each part of each route.

For a bus route, you mean that you do not need the shortest, but the fastest route. Therefore, the cost of each part of the route should include the average speed of the bus in this part, and any expectations at the bus stops.

The search algorithm for the most suitable route then remains the same as before. With A *, all magic happens as a function of value ...

Answer 13

You need to weigh your legs in different ways. For example, on a rainy day, I think that someone might prefer traveling more in a car than walking in the rain. In addition, someone who hates walking or cannot walk can take a different / longer trip than someone who is not averse to walking.

These edges are costs, but I think you can expand the concept / concept of costs, and they can have different relative values.

Answer 14

The algorithm remains unchanged, you simply increase the weight of each graph graph in accordance with various scenarios (bus schedules, etc.).

I put together a search for a route in the metro as an exercise in a graphical path found some time ago:

http://gfilter.net/code/pathfinderDemo.aspx