How to make a simple search engine route?

Question

[Not: the user asks again in the Development of the railway request system, how to simulate trains, stations and stops? ] Description of my problem:

Suppose I have BUS-123 in ROUTE-1 , it will go through A, B, C, D, E, F, G, H and BUS-321 in ROUTE-2 through D, E, F, X, Y, Z. if someone enters B as the starting point and F as the destination, then ROUTE-1 with BUS-123 should be displayed as a result. But if someone enters H as the source, and A as the result of the assignment should not be displayed, because the return may not always match the one that was sent. But if a person enters A as a source and Z as a destination, then BUS-123 with ROUTE-1 and BUS-321 with ROUTE-2 .

My problem: How to save route information in a database? if I store in an RDBMS as shown below:

BUS_NUMBER ROUTE_NUMBER VIA_ROUTES BUS-123 ROUTE-1 A, B, C, D, E, F, G, H BUS-321 ROUTE-2 D, E, F, X, Y, Z 

Whereas my search will work. I mean, how to look for it in a string. And if I store all VIA_ROUTES in different columns, then how will it be ..? Please offer me your technique. This is not urgent, but I plan to do a basic search for the bus route, so your comment using has been appreciated.

Answer 1

I would model it as a cyclic graph. Each bus stop represents a peak. Each direct connection between two stops is represented by the edge indicated by the route number; therefore, each route is a sequence of connected edges. Make also ribs. Not all routes from stop A to stop B will also necessarily travel from stop B to stop A in the other direction.

Probably, you need to fill each edge with the estimated trip time, the measure (or measures) of variance for this leg - at 2 a.m. on Sunday, the difference can be low, but at 5 p.m. on Friday night, it can be very high, as well as the list departure time.

Then it’s a matter of going around the schedule and finding the “least cost” route, however you decide to determine the “least cost”. Factors you might want to consider include:

• Total travel time
• The total waiting time for the next departure.
• Waiting time at any single stop.
• Distance?

It should be noted that too much waiting time is bad (ever spend 40 minutes waiting for a bus in January when it is -10 F?). Too little is also bad, since it increases the likelihood of a connection being absent, given that the buses have rather large variability in their schedules, since they are very sensitive to fluctuations in local traffic conditions.

This is how I do it.

I do not believe that I will try to solve the problem directly in SQL.

The model is well suited for SQL. You need the following objects, and then some, as you will need to represent graphs, etc.:

• Stop. Bus stop. Vertices of the graph.
• Route. Bus route.
• Segment . Direct connection between two stops. The edges of the graph.
• RouteSegment. An associative object representing an ordered sequence of segments that make up a route.

Answer 2

I think bus_numbers are not important because you can watch them later. Perhaps you need to create a 2d matrix with bus_stops in a large matrix that has them all, and then use a graph moving algorithm such as dijkstra to find the shortest path from A to B. When you get this, you can easily find bus_numbers and show to their customer. So, I think your database is already very good.

Answer 3

I will have a route table and a route_part table. The latter will contain a link to the route, plus a serial number for sorting and a link to the stop table. This way you can save any route.

From a search perspective, if you want to find a route between two stops, you can look at two stops in the route_part table and see if they are displayed on the same route anyway (given that the route can exist in one direction and not the other )