JP3176009B2 - Route search device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route search device,
In particular, the present invention relates to an apparatus for searching for a route from a certain point to another certain point, including a transfer of a railway.

[0002]

2. Description of the Related Art Hitherto, the search for a route including a transit from a certain point to another certain point has often been made manually, but the Dijkstra method is known as a method of calculating with a computer. . In this method, the route to be calculated is divided into a number of parts, and the divided points become nodes,
A path including nodes and nodes is set as a link, a node or link closest to the starting point is set as a start point, a node or link closest to the destination is set as an end point, and a tree of links from the start point to the end point is assumed, and a tree is formed. This is a method of sequentially adding the link costs of all the routes to be performed and selecting only the route with the lowest link cost that reaches the destination. If the route is calculated in this way, as long as there is a route from the starting point to the destination, the vehicle will surely reach the destination.

[0003]

However, in the above-described Dijkstra method, the calculation time is determined according to the number of nodes and the number of links in an area to be calculated. Therefore, when the number of nodes and the number of links increase, the calculation time explosively increases, and there is a possibility that a desired route cannot be obtained within a practical time.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problem, and has as its object to provide a route search device capable of finding a desired route within a practical time by a simple calculation.

[0005]

Means for Solving the Problems] route search device according to the invention of claim 1 is a route search device for searching for a route between the departure point and the destination point, any point, one or more
Location to associate with the pair of the nearest station above and the line of the nearest station
Storage means for storing information; and
And the starting point is defined as one or more nearest stations
Express the element as a pair with the line of the nearest station.
A departure point is displayed based on the departure point display means represented by a first vector as an element number and the stored location information.
A pair of one or more nearest stations at a point and the line of the nearest station
Destination display means for representing an element by a second vector having the number of routes as the number of dimensions;
Inner product means for obtaining an inner product with the vector of

[0006] route searching apparatus according to the invention of claim 3, a route search device for route searching the between the departure point and the destination point, the arbitrary point, the one or more nearest station THEREOF
A record that stores the location information associated with the pair with the line of the nearest station
Based on the storage means and the stored location information
With one or more nearest stations of departure and the routes of the nearest stations
Represents the element as a pair of
The starting point display means for representing a vector of the stored field
Based on the location information, the destination point can be
Express the element as a pair of the nearest station and the line of the nearest station,
Destination point display means represented by a second vector having the number of routes as the number of dimensions , and transfer information between a certain route and another route,
Line types can be assigned to rows and columns, and transfers can be made
Connection status display means represented by a matrix having station pairs as elements ,
Multiplying means for multiplying the first vector or the second vector by the matrix an arbitrary number of times; and calculating an inner product of the third vector obtained by the multiplying means and the second vector or the first vector And inner product means.

[0007]

According to the first aspect of the present invention, an inner product of a first vector representing a starting point and a second vector representing a destination point is obtained.

[0008] In the invention of claim 3 , a certain route and another route
The first or second vector is multiplied an arbitrary number of times by a matrix representing the transfer information with the route of, and the inner product of the multiplication result and the second or first vector is obtained.

[0009]

FIG. 1 is a block diagram showing the configuration of a route search apparatus according to a first embodiment of the present invention.

The route search device of this embodiment is shown as a device for searching for a transit of a railway. Here, “link” corresponds to “route”, and “node” corresponds to “station”.
Referring to the figure, information of a pair (departure point, destination point) is input to input unit 101. The information of this pair is passed to the location node association unit 103. The location information storage unit 102 stores information on a pair of (route, station) that is commonly used from an arbitrary location. In addition, even if it is not stored in the location information storage unit 102, the station name itself,
If a point can be specified by a pair of a line name and a station name itself, the point can be set as a departure point or a destination point.

The location node associating unit 103 refers to the information in the location information storage unit 102 and associates a departure point and a destination with information of a pair of (route, station). Specifically, the number of routes is the number of dimensions, each column corresponds to a route, and the element is represented by a vector in which the elements are the station names of the route corresponding to the column.
For convenience, the starting point represented by a vector is referred to as VS, and the destination point represented by a vector is referred to as VD.

For example, in the location information storage unit 102, locations such as "Company A B Building" near Kaihin Makuhari Station (Keiyo Line, Kaihin Makuhari), (Keiyo Rapid Service, Kaihin Makuhari) or (Makuhari Hongo D Route Bus, It is said that it can be associated with the D route bus in front of Company A), and the location called "C bookstore" near Tokyo Station is associated with (Keiyo Line, Tokyo), (Keiyo Rapid Service, Tokyo) and (Yamanote Line, Tokyo) It is assumed that The line is Keiyo Line,
It is assumed that there are four Keiyo Rapid Service, Makuhari Hongo D Route Bus, and Yamanote Line, which correspond to the vector columns in this order. When (A company B building, C bookstore) is input as (departure point, destination point) from the input unit 101, the vector corresponding to the departure point is VS = (Keiyo Line Kaihin Makuhari, Keiyo Rapid Kaihin Makuhari) , Makuhari Hongo D route bus stop in front of Company A, NULL), and the vector corresponding to the destination is VD = (Tokyo on Keiyo Line, Tokyo on Keiyo Rapid Service, NULL, Tokyo on Yamanote Line).

By taking the inner product of these two vectors, a path without transfer is obtained. The inner product here is as follows, and the NULL here means that there is no corresponding station or route.

That is, there are three routes, each of which is a route, a route, and a route. The inner product of (a, b, c) and (d, e, f) = ad or be or cf. Here, the meaning of the right side is as follows: xy = route from x to y using the route corresponding to the element (however, if either or both of x and y are NULL, xy = NULL) Become. After all, the specific meaning of the result of the inner product is (a, b, c) · (d, e, f) = a
Or d from the route, from b to e using the route, or from c to f using the route.

In the above example, VS · VD = (Kaiyo Line Kaihin Makuhari, Keiyo Rapid Rapid Kaihin Makuhari, Makuhari Hongo D route bus stop in front of Company A, NULL)
(Tokyo on Keiyo Line, Tokyo on Keiyo Rapid Line, NULL, Tokyo on Yamanote Line) = You can get the route from Keihin Line from Kaihin Makuhari to Tokyo or Keiyo Rapid Line from Kaihin Makuhari to Tokyo.

When the transfer information is not used, only a route that can be reached without transfer is obtained. However, by using the information in the transfer information storage unit 104, the route search unit 105 is used.
Thus, a route using transfer can be obtained. In this processing, a matrix is used in which the number of routes is the number of dimensions, each row and each column corresponds to a route, and the elements are information on transfer from the route in the row to the route in the column. For convenience, this matrix is represented by T.

For example, in the transfer information storage unit 104, "You can transfer between Shin-Urayasu on Keiyo Line and Shin-Urayasu on Keiyo Rapid", "You can transfer between Tokyo on Keiyo Line and Tokyo on Keiyo Rapid", "Keiyo Line If the information "Tokyo on the Yamanote Line and Tokyo on the Yamanote Line can be changed" is stored, the transfer matrix is expressed as shown in FIG. Will be.

In this case, each row and each column correspond to the Keiyo Line, Keiyo Rapid Service, Makuhari Hongo D Route Bus, and Yamanote Line in order from the upper left. (X, Y) indicates that it is possible to transfer from the X station on the line corresponding to the row to the Y station on the line corresponding to the column. NULL indicates that it is not possible to transfer directly from a line corresponding to a row to a line corresponding to a column. The reason why two station names are described in parentheses is that, depending on the route, it is possible to transfer at a station having a different station name, so two station names are required.

The route search unit 105 searches for a route using VS, VD, and T. The method will be described with reference to FIG. FIG. 3 is a flowchart showing specific contents of the route search by the route search unit 105 according to the first embodiment of the present invention.

First, in step S601, the starting point is represented by a vector VS, and the destination point is represented by a vector Vs.
D and T representing transfer information in a matrix are set. Next, in step S602, a loop counter i is initialized to 0. In step S603, an inner product of VS and VD is obtained, and the obtained inner product is substituted into a variable A storing a route. Next, in steps S604, 605, and 606, while A is NULL, the value of the transfer information T is multiplied by VS.
It is checked whether or not the route that can be reached by changing from S for i times can reach the route represented by VD.

This part will be described in more detail. First, V
In S, a station on a route that can be reached from the starting point without transfer is initially assigned. A value obtained by multiplying this by T is newly added to V
When replaced with S, this VS stores the route from the departure point to the route as an element of a column corresponding to the route that can be reached by one transfer from the departure point. This replacement is apparent when considering the configuration of VS and T.

For example, in the above-mentioned example, VS.T = ((Transfer from Keihin Expressway Kaihin Makuhari to Keiyo Line at Shin-Urayasu, change from Keiyo Rapid Kaikai Makuhari to Tokyo to Keiyo Line), (Keiyo Line Transfer to Keiyo Rapid at Shin-Urayasu from Kaihin Makuhari, and transfer to Keiyo Rapid at Tokyo from Kaihin Makuhari on Keiyo Line)
NULL, (Transfer from Kaihin Makuhari on Keiyo Line to Yamanote Line in Tokyo, and transfer from Kaihin Makuhari on Keiyo Rapid to Tokyo on Yamanote Line)
Becomes

If this is newly set as VS and VS · VD is calculated, the route can be obtained if the transfer can be made once and the destination can be reached, and if not, NULL can be obtained. If a route cannot be obtained, NULL has been obtained. In this case, VS · T is further calculated to increase the number of transfers and check whether a route can be obtained. However, if the route is not obtained even if the transfer is performed the number of times equal to the total number of routes, it is clear that the route cannot be obtained even if the transfer is repeated more than that. Therefore, the calculation is terminated (steps S604, 607, S604). 608). On the other hand, when a route is obtained, the first route obtained is the one with the least number of transfers. Therefore, after that, once more V
By calculating S · T (S609), it is possible to obtain a route with the least number of transfers. Empirically, all routes can be practically obtained by calculating VS · T three times the number of routes. Therefore, if the calculation time is sufficient, it is sufficient to multiply T by a total of three times the total number of routes. If only the route with the minimum number of transfers needs to be obtained, the step The loop of S609 and 610 may be reduced to zero.

In this manner, the vector VS is obtained by multiplying T from the right by the number of transfers from the start point to the number of transfers from the start point to each element of the VS from the start point to the route of the element from the start point. The route is stored. Therefore, by multiplying this by VD, a route from the starting point to the destination point can be obtained.

In the route calculation process so far, all the obtained routes are added to A, so that all the obtained routes are stored in A in step S611. In addition, when VS is multiplied by T, a route in which transfer at the same station occurs continuously may be obtained. However, this is meaningless transfer, and such a route is used for subsequent route search. In the process, ignoring them in the process improves the efficiency of subsequent calculations.

FIG. 4 is a block diagram showing the configuration of a route search device according to a second embodiment of the present invention.

The route search device of this embodiment also searches for a transit of a railway and obtains the fare, time, departure time, and arrival time of the obtained route. In this case, "link" becomes "route"
“Node” corresponds to “station”.

If only the fare and the required time are to be obtained, a pair of (departure point, destination point) is input to the input unit 501, and if the departure time is to be obtained, the (departure point, destination point, arrival time) ) Is input, and (departure point, destination point, departure time) is input if it is desired to obtain the arrival time. These data are stored in the location node associating unit 5
03 is passed. The location information storage unit 502 stores commonly used locations (routes, stations, and time required from the location to the station on the route) from an arbitrary location. Even if the location is not stored in the location information storage unit 502, if the location can be specified by the station name itself or the pair of the route name and the station name itself, the location can be set as a departure point or a destination point. In this case, The required time to the station is set to zero.

The place node associating unit 503 refers to the information in the place information storage unit 502 and associates a departure point and a destination point with (route, station, required time). This is represented by a vector in which the number of lines is the number of dimensions, each column corresponds to a line, and the elements are the station name and the required time of the line corresponding to the line. For convenience, the starting point is represented by a vector V
S, a destination point represented by a vector is referred to as VD.

For example, the location information storage unit 502 stores “Company A B
"Building" is associated with (Keiyo Line, Kaihin Makuhari, 10 minutes), (Keiyo Rapid, Kaihin Makuhari, 10 minutes) and (Makuhari Hongo D route bus, D route bus stop in front of Company A, 3 minutes). It is assumed that a place called “E Tower” near Hamamatsucho Station is associated with (Yamanote Line, Hamamatsucho, 15 minutes). The routes are Keiyo Line, Keiyo Rapid Service, Makuhari Hongo D Route Bus, Yamanote Line, and correspond to the vector columns in this order. Then, when (A company B building, E tower) is input as the (departure point, destination point) from the input unit 501,
The vector corresponding to the departure point is VS = (10 minutes to Kaihin Makuhari on the Keiyo Line, 10 minutes to Kaihin Makuhari on the Keiyo Rapid Line, 3 minutes to the stop in front of Company A of Makuhari Hongo D route bus, NULL) The corresponding vector is VD = (NULL, NULL, NULL, 15 minutes to Hamamatsucho on the Yamanote Line).

By taking the inner product of these two vectors, a path without transfer is obtained. The definitions of NULL and inner product are the same as those described in the previous embodiment.

In the present example, VS.VD = (10 minutes to Kaihin Makuhari on Keiyo Line, 10 minutes to Kaihin Makuhari on Keiyo Rapid, 3 minutes to stop in front of Company A of Makuhari Hongo D route bus, NULL). (NULL, NULL, N
UL, 15 minutes to Hamamatsucho on the Yamanote Line) = NULL, indicating that it is not possible to reach "E Tower" from "Company B Building" without transfer.

The route obtained by the transfer is obtained in the same manner as described in the previous embodiment (the only difference is that the time required for the transfer is stored in the transfer information storage unit). . Therefore, for example, in the transfer information storage unit 504, "It is possible to transfer between Shin-Urayasu on the Keiyo Line and Shin-Urayasu on the Keiyo Rapid in one minute" and "Transfer between Tokyo on the Keiyo Line and Tokyo on the Keiyo Rapid in one minute.""You can transfer between Tokyo on the Keiyo Line and Tokyo on the Yamanote Line in 5 minutes" and "You can transfer between Tokyo on the Keiyo Rapid Line and Tokyo on the Yamanote Line in 5 minutes." Then
The transfer matrix T is represented as shown in FIG.

Each row and column corresponds to the Keiyo Line, Keiyo Rapid Service, Makuhari Hongo D Route Bus, and Yamanote Line in order from the upper left.
(X, Y, n) indicates that it is possible to transfer from the X station on the line corresponding to the row to the Y station on the line corresponding to the column in n minutes. NULL indicates that it is not possible to transfer directly from a line corresponding to a row to a line corresponding to a column.

The route search unit 505 searches for a route in the same manner as the route search unit 105 of the previous embodiment. Therefore, an example of the route search according to this embodiment will be described with reference to the flowchart of FIG.

First, in steps S601 and 602, VS,
The values of VD, T, and i are set, respectively. Next, in step S603, A = VS.VD = NULL, and
A is set to NULL. Since A is NULL,
The flow goes to step S605 to calculate VS = VS · T. In this example, VS = VS · T = (Go to Kaihin Makuhari of Keiyo Rapid in 10 minutes, then go to Shin-Urayasu and transfer to Keiyo Line in 1 minute,
Take the Keiyo Rapid Kaihin Makuhari in 10 minutes, then go to Tokyo and go to Tokyo in 5 minutes, transfer to the Keiyo Line in 10 minutes. Go to the Keiyo Line Kaihin Makuhari in 10 minutes and go there in 1 minute to Shin-Urayasu, transfer to Keiyo Rapid. 10 minutes to Kaihin Makuhari, then go to Tokyo and change to Keiyo Rapid in 5 minutes., NULL, (10 minutes to Keihin Line Kaihin Makuhari, then go to Tokyo and change to Yamanote Line in 5 minutes, Keiyo Rapid It takes 10 minutes to Kaihin Makuhari and from there it goes to Tokyo and transfers to Yamanote Line in 5 minutes)).

By multiplying the vector VS from the right by the number of transfers from the departure point to the number of transfers from the starting point,
In each element of the VS, the route from the starting point to the route of the element is stored together with the time required for transfer. Therefore, by multiplying this by VD, a route from the starting point to the destination point can be obtained together with the time required for transfer.

For example, if the inner product of this new VS and VD is calculated, VS · VD = Keiyo Line Kaihin Makuhari in 10 minutes, then to Tokyo, and in 5 minutes, transfer to Yamanote Line and go to Hamamatsucho From there, you can take a 15-minute route, or go to Keiyo Rapid Kaihin Makuhari in 10 minutes, then go to Tokyo, change to the Yamanote Line in 5 minutes, go to Hamamatsucho, and get a route that takes 15 minutes.

Note that when VS is multiplied by T, a route in which transfer at the same station occurs successively may be obtained. However, this is meaningless transfer, and such a route is deleted. The efficiency of the subsequent calculation is improved by setting to.

In this way, the route which can be reached by one transfer = VS, T, VD = Keihin Makuhari on the Keiyo Line in 10 minutes, then go to Tokyo and transfer to Yamanote Line in 5 minutes to Hamamatsucho From there, take the route that takes 15 minutes, or take the Keiyo Rapid Rapid Kaihin Makuhari in 10 minutes, then go to Tokyo, change to the Yamanote line in 5 minutes, go to Hamamatsucho, and take the route that takes 15 minutes from there. Route = VS, TT, T, VD = Keiyo Rapid Express Kaihin Makuhari in 10 minutes, then go to Shin-Urayasu, transfer to Keiyo line in 1 minute, go to Tokyo, 5
Transfer to Yamanote Line in 1 minute and go to Hamamatsucho, then take 15 minutes from there, or go to Keihin Line Kaihin Makuhari in 10 minutes, then go to Shin-Urayasu, transfer to Keiyo Rapid in 1 minute and go to Tokyo, 5 minutes Change to the Yamanote line in 1 minute and go to Hamamatsucho, from which you can find a route that takes 15 minutes. In this example, when searching for a route that can be reached by making two transfers, a route that changes from the Keiyo Rapid Service to the Keiyo Line at the Tokyo Station and then transfers to the Yamanote Line at the time of calculating VS / TT is obtained. Since the route includes a meaningful transfer, it has been deleted.

When the route is obtained in this manner, the information on the route is passed to the time calculation unit 507, the time calculation unit 509, and the fare calculation unit 511.

The time calculation unit 509 obtains one time of each route with reference to the time information storage unit 508, thereby obtaining the required time of the route obtained by the route search unit 505. In this example, the time information storage unit 508 stores “39 minutes from Kaihin Makuhari on the Keiyo Line to Tokyo”, “31 minutes from Kaihin Makuhari on the Keiyo Rapid Service to Tokyo”, and “6 minutes from Tokyo on the Yamanote Line to Hamamatsucho”.
Minute "is included. Then, in the time calculation unit 509, the route "10 minutes to Keihin Line Kaihin Makuhari, then go to Tokyo, change to the Yamanote Line in 5 minutes, go to Hamamatsucho, and then take 15 minutes", 10 + 39 + 5 + 6 + 15 = 75, this route takes 75 minutes, and it takes "10 minutes to Keiyo Rapid Kaihin Makuhari, then to Tokyo, and in 5 minutes, transfer to the Yamanote Line to Hamamatsucho and take 15 minutes from there." Then, 10 + 31 + 5 + 6 + 15 = 67, and it is calculated that this route takes 67 minutes.

The fare calculation unit 511 obtains the fare between the stations on each route by referring to the fare information storage unit 510, thereby obtaining the fare of the route obtained by the route search unit 505. In this example, assuming that the information that the fare from JR Kaihin Makuhari to Hamamatsucho is 610 yen is stored in the fare information storage unit 510, the fare calculation unit 511 calculates the two fares obtained by the previous VS / VD. It is calculated that the fare is 610 yen for either route. Since fares have different systems depending on the route company, it is advisable to add a railway company name to each route and calculate the fare using this information. In this example, the fare is calculated on the assumption that the Keiyo Line, Keiyo Rapid Service, and Yamanote Line are all registered as JR.

The time calculation unit 507 stores information indicating when a train on each line departs and arrives at each station in the time information storage unit 50.
6, the arrival time and the departure time can be obtained. In this example, it is assumed that time information as shown in FIG. 6 is included. In the figure, HH: MM / h
h: mm indicates that the time of arrival at the station is HH: MM and the time of departure from the station is hh: mm. If there is only HH: MM, it means that the time of arrival at the station is HH: MM.

Here, for example, the departure point “Company A B Building”
It is assumed that a destination point “E tower” and a departure time “13:55” are input to determine an arrival time. In this case, the route obtained by the route search unit 505 is traced while checking the time information.

This processing will be described first for the first path of VS / VD. Departing from Company A's B Building at 13:55, so you arrive at Kaihin Makuhari Station on Keiyo Line at 14:55.
05. Referring to the time information, there is the Keiyo Line departing from Kaihin Makuhari at time 14:06. If you get on this, you will arrive at Tokyo on the Keiyo Line at time 14:50, so transfer to the Yamanote Line there. It takes 5 minutes to transfer, so it is 14:55 to arrive at the Yamanote Line platform at Tokyo Station. Referring to the time information, there is a Yamanote Line departing Tokyo at time 14:55, so when you get on it, you will arrive at Hamamatsucho at time 15:01. Since it takes 15 minutes from here to arrive at the E tower, the time to arrive at the E tower is 15:16. Departure time is 13:55 and arrival time is 1
Since it is 5:16, the required time is required to be 1 hour and 21 minutes.

Next, the second route will be described. Since the departure from Building A at 13:55 at time 13:55, it is 14:05 to arrive at Kaihin Makuhari Station on the Keiyo Rapid Service. If you refer to the time information, there is Keiyo Rapid Service departing Kaihin Makuhari at time 14:12. If you get on it, you will arrive at Tokyo at Keiyo Rapid Service at time 14:43, so transfer to the Yamanote Line there.
The transfer time is 5 minutes, so you arrive at the platform on the Yamanote Line at Tokyo Station at 14:48. Referring to the time information, there is a Yamanote Line departing from Tokyo Station at 14:50, so when you get on it, you will arrive at Hamamatsucho at 14:56. It will take 15 minutes from here to arrive at E Tower,
The time of arrival at E Tower is 15:11. Since the departure time is 13:55 and the arrival time is 15:11, the required time is required to be 1 hour and 16 minutes.

Next, it is assumed that the departure time is obtained by inputting, for example, the departure point “Company A B Building”, the destination point “E Tower”, and the arrival time “15:20”. In this case, the route obtained by the route search unit 505 is traced in the opposite direction while checking the time information.

This process will be described first for the first route. Since the arrival time at E-Tower is 15:20, it must arrive at Hamamatsucho Station on the Yamanote Line at 15:05. Referring to the time information, the latest Yamanote line arriving at Hamamatsucho Station before 15:05 arrives at Hamamatsucho Station at 15:01, and this train leaves Tokyo Station at 14:55. ing. To depart from Tokyo Station on the Yamanote Line at 14:55, take the Tokyo Station on the Keiyo Line at 1
You must have arrived at 4:50. Referring to the time information, there is the Keiyo Line arriving at time 14:50, and this train has left Kaihin Makuhari Station at time 14:06.
To depart from Kaihin Makuhari Station on the Keiyo Line at time 14:06, you must have departed from Company A Building B at time 13:56. Therefore, the required departure time is 13:56. Departure time is 13:56 and arrival time is 1
Since it is 5:20, the required time is required to be 1 hour and 24 minutes.

Next, the second route will be described. Since the arrival time at E-Tower is 15:20, it must arrive at Hamamatsucho Station on the Yamanote Line at 15:05. Referring to the time information, the latest Yamanote Line arriving at Hamamatsucho Station before time 15:05 arrives at time 15:01, and this train leaves Tokyo Station at time 14:55. To depart from Tokyo Station on the Yamanote Line at 14:55, you must arrive at Tokyo Station on the Keiyo Rapid Service at 14:50. When you refer to the time information, time 1
There is Keiyo Rapid Service arriving at 4:43, which is at 14:43
12 departs from Kaihin Makuhari Station. To depart from Kaihin Makuhari Station on the Keiyo Line at time 14:12, you must have departed from Company A Building B at time 14:02. Therefore, the required departure time is 14:02. Since the departure time is 14:02 and the arrival time is 15:20, the required time is required to be 1 hour and 18 minutes.

In the example of the two routes, the required time was calculated with the arrival time kept at 15:20 for simplicity.
The real arrival time can be obtained by following the route in the forward direction from the obtained departure time. In this case, since the arrival time is 15:16 on the first route, the required time is 1 hour and 20 minutes, and the arrival time is 1 hour on the second route.
Since it is 5:11, the required time is required to be 1 hour and 9 minutes.

As described above, the required time, the fare, the arrival time, and the departure time are obtained, and these are passed to the condition determination unit 512. In addition, the route itself is also passed from the route search unit 505 to the condition determination unit 512, so that information on the route and the trouble of transferring can be obtained. The condition determination unit 512 selects a route that satisfies the condition input from the input unit 501 from all the obtained routes, and passes it to the output unit 513. Usually, the route with the shortest required time, the route with the lowest fare, the route with the latest departure time, the route with the earliest arrival time, and the route with the least number of transfers are selected. Information necessary for the selected route and its required time, fare, departure time, and arrival time is output by the output unit 513.

As an application of the second embodiment, an optimum departure time can be obtained. This is because, when (departure point, destination point, departure time) is given as input, the "arrival time" is calculated, and the obtained route is traced backward from "arrival time" to obtain "departure time". Is what you want. It is clear from the method of obtaining the departure time in the previous embodiment that the "departure time" is the optimal departure time for arriving at the "arrival time".

For example, in the above example, when the departure point “A company B building”, the destination point “E tower”, and the departure time “13:55” are given as inputs, the arrival time is obtained. Is determined to be 15:16 and the arrival time on the second route is 15:11. This time, the departure time on the first route where 15:16 is the arrival time, The departure time on the second route where 11 is the arrival time is obtained in the same manner.

First, the first route will be described. Since the time of arrival at E Tower is 15:16, it must arrive at Hamamatsucho Station on the Yamanote Line at 15:01. Referring to the time information, the latest Yamanote line arriving at Hamamatsucho Station before time 15:01 arrives at Hamamatsucho Station at 15:01.
This train arrives at Tokyo Station at time 14:
Departure for 55. 14:55 at Tokyo Station on the Yamanote Line
You must arrive at Tokyo Station on the Keiyo Line at 14:50 before you can leave. When you refer to the time information, time 1
There is a Keiyo line arriving at 4:50, and this train is at time 1
Departing Kaihin Makuhari Station at 4:06. Time 14:06
In order to depart from Kaihin Makuhari Station on the Keiyo Line, you must depart from Bldg. A at 13:56. Therefore, the required departure time is 13:56. Since the departure time is 13:56 and the arrival time is 15:16, the required time is required to be 1 hour and 20 minutes.

Next, the second route will be described. Since the arrival time at the E tower is 15:11, it is necessary to arrive at Hamamatsucho Station on the Yamanote Line at 14:56. Referring to the time information, the Yamanote Line, which arrives at Hamamatsucho Station latest before time 14:56, arrives at time 14:56, and this train leaves Tokyo Station at time 14:50. To depart from Tokyo Station on the Yamanote Line at 14:50, you must arrive at Tokyo Station on the Keiyo Rapid Service at 14:45. Referring to the time information, there is Keiyo Rapid Service arriving at time 14:43, and this train leaves Kaihin Makuhari Station at time 14:12. Time 14: 1
In order to depart from Kaihin Makuhari Station on the Keiyo Line in 2nd, you have to depart from Company A Building B at 14:02. Therefore, the required departure time is 14:02.
Since the departure time is 14:02 and the arrival time is 15:11, the required time is required to be 1 hour and 9 minutes.

From the above, the departure time entered first is 1
3:55, but 13: 5 if going on the first route
It turns out that it is in time to depart at time 6 even if it departs at 14:02 when going on the second route. In this way, an optimal departure time can be obtained.

As another application of the second embodiment, the time calculation unit refers to the time information storage unit to search for the train arriving and departing at the optimal time,
By determining the times when two slower trains and one or two faster trains are used, it is possible to confirm how the departure time, the arrival time, and the required time of the difference between them change. It is possible to delay or advance the train used at the station closest to the departure point, the station closest to the destination point, or at each transfer station, but usually delays the departure time at the station closest to the departure point It is thought that it is best to perform the calculation assuming that it arrives early or arrives and departs at the optimal time at other stations.

Further, as an application of the second embodiment, when the departure point “A company B building”, the destination point “E tower” and the departure time “13:55” are given as inputs in the above example, the arrival time Is obtained, the arrival time on the first route is 15:16, and the arrival time on the second route is 15:11.
However, what happens when one train at the station closest to the departure point is delayed by one train will be described for the two routes in this example.

In the first route, the building B of the company A is switched to the time 13: 5.
Departing at 5 and arriving at Kaihin Makuhari Station on the Keiyo Line at 14:05. When referring to the time information, time 14:
There is Keiyo Line departing from Kaihin Makuhari Station at 06, but one train will be delayed, so I will take the Keiyo Line departing Kaihin Makuhari at the next time 14:24. Then, we arrive at Tokyo Station on the Keiyo Line at 15:03, so transfer to the Yamanote Line. Since it takes 5 minutes to transfer, it is 15:08 to arrive at the platform on the Yamanote Line at Tokyo Station. Referring to the time information, there is a Yamanote Line departing from Tokyo Station at time 15:10, so when you get on it, you will arrive at Hamamatsucho Station at time 15:16. It takes 15 minutes from here to arrive at the E tower, so the time to arrive at the E tower is 15:31. Since the departure time is 13:55 and the arrival time is 15:31, the required time is required to be 1 hour and 36 minutes. When the arrival time is 15:31, the optimal departure time is 14: 1.
Since it is required to be 6, it takes one hour and fifteen minutes to get on the Keiyo Line at Kaihin Makuhari Station.

In the second route, the building B of the company A is set at the time 13:
Since it departs at 55, it arrives at Keiyo Rapid Kaihin Makuhari Station at 14:05. When you refer to the time information, time 1
At 4:12 there is Keiyo Rapid Service departing Kaihin Makuhari Station, but one train will be delayed, so we will take Keiyo Rapid Service departing Kaihin Makuhari Station at the next time 14:42. Then, at time 15:13
Arrives at Keiyo Rapid Tokyo Station, so transfer to the Yamanote Line there. It takes 5 minutes to transfer, so we arrive at the Tokyo Station Yamanote Line platform at 15:18. Referring to the time information, there is a Yamanote Line departing from Tokyo Station at 15:20, so when you get on it, you will arrive at Hamamatsucho Station at 15:26. Since it takes 15 minutes from here to arrive at the E tower, the time to arrive at the E tower is 15:41. Departure time is 13:55 and arrival time is 15:
Since it is 41, the required time is required to be 1 hour and 46 minutes. When the arrival time is 15:41, the optimal departure time is required to be 14:32.
It can be seen that the time required to get on at Keihin Makuhari Station with one Keiyo Rapid Service is one hour and nine minutes.

The route search device according to the present invention is capable of efficiently searching for a route such as a train connection and obtaining the number of times of transfer, the required time, the fare, the departure time, the arrival time, etc. of the route. . However, the required time obtained without time information cannot be said to be very accurate because the waiting time for connecting trains cannot be considered. Therefore, in an environment where time information can be obtained, it is preferable that the required time be obtained from the difference between the departure time and the arrival time with reference to the time information. However, since time information is enormous compared to time information, it seems difficult to store all data in a small system. In a small-scale system, it is practical to omit the time calculation or to have time information only in a specific area and to calculate the time only when the route is in the specific area. it is conceivable that.

In the route search apparatus of this embodiment, a route is searched for by repeatedly multiplying the departure point vector VS and the transfer information matrix T. This is because the transfer information matrix T and the destination point vector VD A route search can be performed by repeating the multiplication, or a route may be searched by combining VS · T and T · VD. In any case, the whole route A

[0064]

(Equation 1)

## EQU5 ## Here, if N = the total number of routes × 3, practically all routes can be obtained.

FIGS. 7 and 8 are diagrams showing specific output contents of the output unit 513 in the second embodiment of the present invention.

FIG. 7 shows, as an example, an output in a sentence format, which is convenient when providing guidance by voice output or the like.

FIG. 8 shows another example in which the emphasis is placed on ease of viewing, and the output is convenient for checking on a display.

In both figures, the "route XY" refers to the first station (Kahin Makuhari) in the X-th route.
It shows the route to the destination by getting on the train that arrived the second time. The obtained routes are output in the order of later departure time.

7 and 8, the time portion can be corrected by clicking the time portion with a mouse or the like, and when the time portion of the route is corrected, each portion of the entire route is corrected. If the configuration is made so that the times of the parts are recalculated, the route search device becomes easier to use.

FIG. 9 is a block diagram showing the configuration of a route search device according to the third embodiment of the present invention.

Referring to the figure, the route search device according to the present embodiment has a configuration similar to that of the first embodiment shown in FIG.
06 and the time calculation unit 207. The operations of these added components are the same as the operations of the corresponding components in the second embodiment shown in FIG. 4, and thus description thereof will not be repeated.

According to this embodiment, it is possible to easily search for the optimum route in consideration of the arrival time and the departure time.

FIG. 10 is a block diagram showing the configuration of a route search device according to a fourth embodiment of the present invention.

Referring to the figure, the route search device according to this embodiment has a configuration similar to that of the first embodiment shown in FIG.
06 and a time calculation unit 307. The operation of these added elements is the same as the operation of the corresponding elements in the second embodiment shown in FIG. 4, and the description thereof will not be repeated.

According to this embodiment, it is possible to easily search for an optimal route in consideration of the required time from the departure place to the destination place.

FIG. 11 is a block diagram showing the configuration of a route search device according to a fifth embodiment of the present invention.

Referring to the figure, the route search device according to this embodiment has a configuration similar to that of the first embodiment shown in FIG.
06 and the fare calculation unit 407. The operations of these added elements are the same as the operations of the corresponding elements in the second embodiment shown in FIG. 4, and thus description thereof will not be repeated.

According to this embodiment, it is possible to easily search for an optimal route in consideration of the required fare from the departure place to the destination place.

[0080]

According to the first aspect of the present invention, as described above,
Since the inner product of the first vector representing the departure point and the second vector representing the destination point is obtained, the existence of a route connecting the departure point and the destination point can be quickly determined.

[0081] As described claim 3 of the invention is more, Oh
The first or second vector is multiplied by an arbitrary number of times with a matrix representing transfer information between another route and another route, and the inner product of the multiplication result and the second or first vector is obtained. The existence of the route connecting the destination and the destination can be quickly determined in consideration of the connection status between the routes.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of a route search device according to a first embodiment of the present invention.

FIG. 2 is a diagram showing specific contents of a transfer matrix used in a route search calculation according to the first embodiment of the present invention.

FIG. 3 is a flowchart showing specific contents of a route search according to the first embodiment of the present invention.

FIG. 4 is a block diagram showing a configuration of a route search device according to a second embodiment of the present invention.

FIG. 5 is a flowchart showing specific contents of a transfer matrix used in a route search operation according to the second embodiment of the present invention.

6 is a diagram showing a specific content of time information stored in a time information storage unit 506 in FIG. 4;

FIG. 7 is a diagram illustrating an example of a display output from an output unit 513 in FIG. 4;

8 is a diagram showing another example of the display output from the output unit 513 in FIG.

FIG. 9 is a block diagram showing a configuration of a route search device according to a third embodiment of the present invention.

FIG. 10 is a block diagram showing a configuration of a route search device according to a fourth embodiment of the present invention.

FIG. 11 is a block diagram showing a configuration of a route search device according to a fifth embodiment of the present invention.

[Explanation of symbols]

 101 input unit 102 place information storage unit 103 place node correspondence unit 104 transfer information storage unit 105 route search unit 106 output unit 501 input unit 502 place information storage unit 503 place node correspondence unit 504 transfer information storage unit 505 route search unit 513 Output section

──────────────────────────────────────────────────続 き Continued on front page (58) Field surveyed (Int.Cl. ⁷ , DB name) B61L 25/02 G08G 1/005 G09B 29/00

Claims (4)

(57) [Claims] 1. A route search device for searching for a route between a start point and a destination point, wherein an arbitrary point is located at one or more nearest stations and a route between the nearest stations.
Storage means for storing location information associated with a pair with a line , based on the stored location information,
Pairs with one or more nearest stations of departure point and the routes of the nearest stations
Based on the stored location information, the departure point display means expressing the element as a first vector having the number of routes as the number of dimensions ,
A pair of one or more nearest stations at the destination and the line of the nearest station
A route search comprising: destination point display means for representing an element as a second vector having the number of routes as a dimension number; and inner product means for obtaining an inner product of the first vector and the second vector. apparatus. 2. The arrival time at each station for each line.
And timetable storage means for storing the departure time, wherein the storage means is a time required from any point to the nearest station.
The route search device according to claim 1, further comprising: 3. Search for a route between a starting point and a destination point.
A route search device that searches for an arbitrary point by selecting one or more nearest stations and a route between the nearest stations.
Storage means for storing location information associated with a pair with a line , based on the stored location information,
Pairs with one or more nearest stations of departure point and the routes of the nearest stations
Represents the element as
Starting point display means expressed in cuttle, and the destination point based on the stored location information,
A pair of one or more nearest stations at the destination and the line of the nearest station
, And the number of routes is the number of dimensions.
The destination point display means expressed by a vector and the transfer information between a certain route and another route are indicated by the type of route.
And columns, and the pairs of transitable stations as elements
A connection status display means represented by a matrix to perform, the first vector or the second vector,
A multiplying means for multiplying the matrix by an arbitrary number of times, a third vector obtained by the multiplying means,
Find the inner product of a second vector or the first vector
A route search device comprising: 4. The arrival time of each station for each line
And timetable storage means for storing the departure time, wherein the storage means is a time required from any point to the nearest station.
Is further stored, and the elements of the matrix of the connection status display means include the pair of the station.
4. The method according to claim 3, wherein the time required for transfer is also recorded.
Route search device.