JP6364432B2 - Method and apparatus for moving path estimation - Google Patents

Description

  The present invention relates to a method and apparatus for estimating a moving path of a moving object.

  Patent Document 1 discloses a position information analysis apparatus that performs analysis related to user movement based on position information of a mobile device carried by the user. This position information analysis device uses position data indicating the position of the user, information on the time when the position information was obtained, and point data including the user identification information of the user. In this position information analyzer, the moving speed between adjacent point data in time series is calculated, and each point is calculated based on the moving speed, the position information included in the point data, and the route map data of public transportation. The movement method (walking, bicycle, car, train or bus) between data is determined.

Japanese Patent No. 5225461

However, since the technique of Patent Document 1 determines the moving speed between the point data and the moving method between the point data from the position information and time information of the point data, the position data of the point data is accurate as GPS positioning data. Higher ones are required.

  The present invention has been made in view of the above points, and one of its purposes is to provide a method, apparatus, and computer program for estimating a moving path that can identify a moving path of a moving body even from position information with low accuracy. It is to provide.

  In order to solve the above-described problem, an aspect of the present invention is a moving route estimation method for estimating a moving route from a starting point of a moving object to a destination, wherein the object is determined from the starting point of the moving object. Receiving a set of position information relating to behavior to the ground; determining a plurality of route candidates from the starting point to the destination of the mobile; and comparing the plurality of route candidates with the position information set Thereby selecting one route candidate from the plurality of route candidates as the estimated route of the mobile object.

Another embodiment of the present invention is a computer program that causes a computer to execute the route estimation method.
Another aspect of the present invention is a route estimation device that estimates a route of travel from a starting point of a moving object to a destination, the position of the moving object relating to the action from the starting point to the destination Data storage means for storing a set of information, route candidate determination means for determining a plurality of route candidates from the starting point to the destination of the mobile body, and comparing the plurality of route candidates with the position information set By this, it is a movement path | route estimation apparatus containing the path | route selection means which selects one path | route candidate from the said some path | route candidate as an estimated path | route of the said mobile body.

  Another embodiment of the present invention is a computer program that causes a computer to function as the movement path estimation apparatus.

    According to the present invention, it is possible to estimate a moving path of a moving body even from position information with low accuracy such as position information of a base station.

It is a figure which shows the hardware constitutions of the movement route estimation apparatus which concerns on one Embodiment of this invention. It is a functional block diagram which shows the function of the movement route estimation apparatus of FIG. The figure which shows the data structure of the point data which show the action of the moving body utilized with the movement route estimation apparatus of FIG. The figure which shows notionally the action from the departure place to the destination of the mobile body which estimates a path | route using the movement path | route estimation apparatus 100. FIG. The flowchart which shows the whole operation | movement of the movement route estimation apparatus of FIG. The flowchart which shows in detail one specific example of the action area classification | category process in step 502 of FIG. FIG. 6 is a diagram for explaining one specific example of the action section classification process of FIG. 5, and shows a state of passing through a base station area during movement of a mobile object, and (A) is a diagram of action section classification. 1 illustrates the base station areas A1 to A4 that pass when the moving body moves for the purpose of explaining the determination method, and (B) shows when the moving body moves for the purpose of explaining the second determination method of action section classification. (C) shows the base station areas A12 to A14 that pass through when the mobile body moves for the purpose of explaining the third determination method of action section classification. 6 is a flowchart showing in detail one specific example of the transportation classification process in step 504 in FIG. 5. FIG. 9 is a diagram for describing one specific example of the transportation classification process of FIG. 8, and shows two railway lines R and bus lines B that run substantially parallel to each other in a certain movement section. 6 is a flowchart showing in detail one specific example of the nearest station specifying process in the route candidate extraction process in step 506 of FIG. 5. FIG. 11 is a diagram for explaining one specific example of the nearest station specifying process in FIG. 10, and shows a plurality of adjacent base station areas within a certain radius from the center of the base station area where the departure point is located. The flowchart which shows the detail of one specific example of the route candidate selection process in the route candidate extraction process of step 506 of FIG. The flowchart which shows the detail of one specific example of the route candidate selection process of step 508 of FIG. FIG. 14 is a diagram for explaining one specific example of the route candidate selection process of FIG. 13, and shows a moving route RT (shown by a dotted line) indicated by point data of a moving object and two candidate routes CRA and CRB (shown by a solid line). Show.

[Description of Embodiment of the Present Invention]
First, the contents of the embodiment of the present invention will be listed and described. One embodiment of the present invention has the following configuration.

(Item 1)
A moving route estimation method for estimating a moving route from a starting point of a moving object to a destination,
Receiving a set of location information regarding the behavior of the mobile body from the starting point to the destination;
Determining a plurality of route candidates from the starting point to the destination of the mobile;
Selecting one route candidate from the plurality of route candidates as an estimated route of the moving body by comparing the plurality of route candidates with the position information set;
A moving path estimation method including:

(Item 2)
In the method according to item 1, the step of selecting as an estimated route includes:
Detecting an error between the position information set and each of the plurality of route candidates;
Comparing the detected error and selecting the path candidate with the smallest error as the estimated path;
A moving path estimation method including:

(Item 3)
In the method according to item 1 or 2, the behavior of the mobile body includes movement and stay,
The step of determining a route candidate includes a step of classifying an action section of the mobile body, the step comprising:
Of the actions from the departure place to the destination of the mobile body, identifying the location information regarding stay;
Generating a position information set related only to movement by removing position information related to the stay from the received position information set;
A moving path estimation method including:

(Item 4)
4. The method according to any one of items 1 to 3, wherein the step of identifying location information related to a stay includes:
i) identifying the series of location information as related to a stay when the series of location information continuously indicates the same location for a certain number of times or more; and
ii) when the orientation of a given vector from one position in the series of position information to the next adjacent position changes by more than a certain threshold angle with both the immediately preceding vector and the immediately following vector; Identifying location information related to a vector of
iii) When the speed of movement from a certain first position to the next adjacent second position in the series of position information is less than a certain threshold speed, the position information related to the first position is A step of identifying as related to the stay;
A moving path estimation method including at least one of the following.

(Item 5)
The method according to any one of Items 1 to 4, wherein the step of determining a plurality of route candidates includes:
i) determining from a map data a departure station nearest to the departure place and a destination station nearest to the destination;
ii) selecting a plurality of route candidates from the departure station to the destination station based on the departure station and the destination station using route candidate data;
A moving path estimation method including:

(Item 6)
In the method according to any one of items 1 to 5,
The location information set is included in time-series point data related to the mobile object,
Each of the point data includes position information of a base station that has passed during the movement of the mobile body,
Moving path estimation method.

(Item 7)
A computer program that causes a computer to execute the route estimation method according to any one of items 1 to 6.

(Item 8)
A moving route estimation device for estimating a moving route from a starting point of a moving object to a destination,
Data storage means for storing a set of positional information relating to the behavior of the mobile body from the departure place to the destination;
Route candidate determining means for determining a plurality of route candidates from the starting point to the destination of the mobile;
Route selection means for selecting one route candidate from the plurality of route candidates as an estimated route of the mobile body by comparing the plurality of route candidates with the position information set;
A moving path estimation apparatus including:

(Item 9)
9. The apparatus according to item 8, wherein the route selection means is
Error detection means for obtaining an error between the position information set and each of the plurality of route candidates;
Comparing means for comparing the detected errors and selecting the path candidate with the smallest error as the estimated path;
A moving path estimation apparatus including:

(Item 10)
In the device according to item 8 or 9, the behavior of the mobile body includes movement and stay,
The route candidate determination means includes action section classification means, and the action section classification means includes:
Of the actions from the departure place to the destination of the mobile body, stay identification means for identifying position information regarding stay;
Generating means for generating a position information set related only to movement by removing position information related to the stay from the received position information set;
A moving path estimation apparatus including:

(Item 11)
The apparatus according to any one of items 8 to 10, wherein the stay identifying means includes:
i) identifying a series of location information as related to a stay when the series of location information indicates the same location consecutively for a certain number of times or more, or
ii) when the orientation of a given vector from one position in the series of position information to the next adjacent position changes by more than a certain threshold angle with both the immediately preceding vector and the immediately following vector; Identifying location information related to a vector of
iii) When the speed of movement from a certain first position to the next adjacent second position in the series of position information is less than a certain threshold speed, the position information related to the first position is Identifying as related to the stay,
A movement path estimation apparatus that performs at least one of the following.

(Item 12)
12. The apparatus according to any one of items 8 to 11, wherein the route candidate determination unit includes a route candidate extraction unit,
The route candidate extraction means
i) a nearest station determining means for determining a departure station nearest to the departure place and a destination station nearest to the destination from map data;
ii) Route candidate selection means for selecting a plurality of route candidates from the departure station to the destination station using route candidate data based on the departure station and the destination station;
A moving path estimation apparatus including:

(Item 13)
In the device according to any one of items 8 to 12,
The location information set is included in time-series point data related to the mobile object,
Each of the point data includes position information of a base station that has passed during the movement of the mobile body,
Moving path estimation device.

(Item 14)
14. A computer program that causes a computer to function as the movement path estimation device according to any one of items 8 to 13.

[Details of the embodiment of the present invention]
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 1 is a hardware configuration diagram of a movement path estimation apparatus 100 according to an embodiment of the present invention. The movement path estimation apparatus 100 includes at least a processor 102, a memory 104, an input / output interface 106, and a communication interface 108. The movement path estimation apparatus 100 can be realized as a personal computer, a server, or the like, for example. The memory 104 stores at least an operating system, a travel route estimation program, and various data used for travel route estimation. The operating system is a computer program for controlling the overall operation of the movement path estimation apparatus 100. The movement route estimation program is a computer program for realizing the functions of the movement route estimation processing described later by the movement route estimation device 100. The memory 104 can also temporarily or permanently store data generated by the operation of the movement path estimation apparatus 100. Specific examples of the memory 104 include a ROM (Read Only Memory), a RAM (Random Access Memory), a hard disk, a flash memory, and an optical disk.

  The processor 102 is configured to read a program stored in the memory 104 and execute processing according to the program. When the processor 102 executes the movement route estimation program stored in the memory 104, each function of the movement route estimation processing described later is realized. The processor 102 is, for example, a CPU (Central Processing Unit).

  The input / output interface 106 is configured to receive an input for operating the movement path estimation apparatus 100 from an operator of the movement path estimation apparatus 100 and to generate an output such as a display for the operator. Specific examples of the input / output interface 106 include a keyboard, a touch pad, a mouse, a display, and a printer.

  The communication interface 108 is a network interface for communicating with various servers via a network. For example, the movement path estimation apparatus 100 can obtain various data used for movement path estimation from various servers connected to the network 110 using the communication interface 108.

  FIG. 2 is a block diagram showing a functional configuration of the movement path estimation apparatus 100, which is implemented by a computer program executed by the computer hardware of FIG. The moving route estimation apparatus 100 includes a data storage unit 200, a route candidate determination unit 220, and a route selection unit 260, as illustrated. The data storage unit 200 stores point data of the moving body as a set of position information used for estimating the moving path of the moving body. An example of this point data will be described later with reference to FIG. The data storage unit 200 further stores other information used for route estimation, such as map data, route data such as railway lines and bus routes, and candidate data for routes from the departure station to the destination station. You can also. The route candidate determining unit 220 is configured to determine a plurality of route candidates for estimating the moving route of the moving object based on the point data of the moving object, and the action section classifying unit 230, the transportation system classifying unit 240, A route candidate extraction unit 250. The route selection unit 260 operates to select one route candidate from the plurality of route candidates determined by the route candidate determination unit 220 as an estimated route. For this purpose, the route selection unit 260 includes an error detection unit 262 and a comparison unit 264. Yes.

  Here, referring to FIG. 3, the point data of the mobile body includes at least a user ID such as a mobile phone, latitude / longitude information as position information, and a time stamp as time information when the position information is specified. . In one embodiment of the present invention, information with low position accuracy such as position information of a base station can be used as position information. In addition, when an area mesh is created by dividing the area into meshes (mesh) of the same size (for example, 1 kilometer) according to latitude and longitude, position information for each mesh can also be used. The point data can also include other information such as the user's gender and age group. Note that in this specification, the term “mobile body” includes not only a mobile device such as a mobile phone but also a user who uses such a mobile device.

  Next, with reference to FIG. 4, a behavior of a moving body that performs route estimation using the movement route estimation device 100 will be conceptually described. As shown in the figure, the movement from the departure point to the destination of the moving object is between the departure station TS1 which is the nearest station of the departure point, the destination station TD1 which is the nearest station of the destination, and between these stations. There are three travel sections M1 to M3 and stay sections S1 and S2 in adjacent travel sections. In addition, the number of moving sections and the number of stay sections are examples, and may be more or less than that. In each movement section, there is at least one route. As an example, in the movement section M1, there are two railway lines R1a and R1b, in the movement section M2, there are one railway line R2 and one bus line B2, and in the movement section M3, there are two bus lines B3a. And B3b. In FIG. 4, a series of positions indicated by the position information of the point data is indicated by dotted lines.

  FIG. 4 shows the second nearest departure station TS2 and destination station TD2 by way of example. As will be described later, a plurality of nearest departure stations and destination nearest stations are specified. Because there are cases. In this way, when there are a plurality of nearest stations, it is only necessary to examine the movement route between the departure station and the destination station for each different combination. In the following, only one of the movement paths will be described, but the same process may be performed for the other movement paths.

  Next, with reference to FIG. 5, the operation of the movement path estimation apparatus 100 shown in FIG. 2 will be described with reference to FIG. First, in step 500, the data storage unit 200 obtains and stores point data used for moving route estimation. The source is, for example, GPS positioning information of the user's mobile device using an application developed independently. The acquired point data is rearranged in time series for each user ID, so that time series point data as a set of position information for each user can be obtained. The data storage unit 200 may store map data, route data such as railway lines and bus routes, and route candidate data from the departure station to the destination station as other data for route estimation. it can. These data can also be obtained via various networks from various servers that provide a map database, route database, and accounting candidate database.

  In the next step 502, the action segment classification unit 230 of the route candidate determination unit 220 divides the behavior of the moving body into a stay segment (S1 and S2 in FIG. 4) and other travel segments (M1 to M3 in FIG. 4). ). In one embodiment of the present invention, it is assumed that the behavior of a moving object is composed of stay and movement, and only point data relating to movement is excluded as data used for estimation of the movement route, excluding the stay section. Generate. Thus, by using only movement data, extraction of route candidates can be facilitated. Here, stay includes, for example, shopping in a place near a certain station, such as a store, or eating in a restaurant. Such stay is excluded in the estimation of the travel route from the departure point to the destination. Therefore, it can be considered that there is no stop in the middle of movement, and it can be considered that the transportation means (railway or bus) of movement does not change in each movement section. By making such a premise, it becomes easier to estimate the route from the departure point to the destination. Details of this action section classification will be described later.

  Next, in step 504, the transportation system classification unit 240 of the route candidate determination unit 220 compares the position information in the point data of each moving section with route data such as a railway line and a bus route, thereby comparing each moving section. It is determined whether the transportation is a railway (R1a, R1b, R2 in FIG. 4) or a bus (B2, B3a, B3b in FIG. 4). The route data includes position information and time information of various railway and bus routes. Such route data can be obtained from, for example, a railway or bus operator. As a result, with respect to the movement from the departure place to the destination, at least one or more movement sections constituting the movement and the transportation system used in each movement section are specified. By specifying the transportation means, the departure station and the destination station in each moving section can be identified.

  Note that the execution of step 504 is arbitrary, and may be omitted because the number of point data necessary for discrimination of railway lines and bus lines may not be obtained. In that case, in step 506 described later, processing is performed based on at least one or more moving sections determined in step 502.

  In the next step 506, the route candidate extraction unit 250 of the route candidate determination unit 220 determines in step 504 for or in addition to the movement including at least one movement section determined in step 502. A plurality of route candidates for the movement are extracted with respect to the movement including the related identified transportation. For example, in the example of FIG. 4, departure station → railway line R1a → railway line R2 → bus route B3a, departure station → railway line R1b → railway line R2 → bus route B3a, departure station → railway line R1b → railway line R2 → bus route B3b, departure station → railway R1b → bus route B2 → bus route B3b. This route candidate extraction is performed using route candidate data. Such route candidate data can be obtained via a network from a server that provides a database such as a transfer guidance API provided by Jordan Co., Ltd., for example. In addition, the standard for extraction can be within a certain cost range, a certain required time range, or the like. As a result, it is possible to exclude routes that are connected on the route but are unlikely to normally select the transfer. For example, when the lowest fare is 300 yen, a route that takes a fare exceeding a certain multiple, for example, a fare exceeding twice, is excluded. Further, when the shortest required time is 1 hour, a route having a required time exceeding a certain fixed time, for example, a required time exceeding twice, is excluded.

  In the next step 508, the route selection unit 260 selects a route candidate that satisfies a certain criterion from the plurality of route candidates extracted in step 506 as an estimated route. As a certain standard, there is a condition that an error between a series of positions indicated by the actual position information indicated by the point data (indicated by a dotted line in FIG. 4) and the extracted route candidate is the smallest. Thereby, the movement route estimated as the movement route from the departure point of the moving body to the destination is specified.

  Next, with reference to FIG. 6, one specific example of the action section classification process in step 502 of FIG. 5 will be described in detail. Steps 600 to 602 are the first determination method based on the density at which the positions appear, steps 606 to 610 are the second determination method based on the vector, and steps 614 to 618 are the third determination method based on the moving speed. Classify whether or not you are staying with a judgment method.

  Here, in order to make it easy to understand the action section classification method according to the embodiment of the present invention, FIG. 7 shows a state where the mobile station passes through the base station area while moving. In FIG. 7, the position of the point in the base station area indicates the number of times the user has been in the area, and does not indicate the geographical position in the area. In addition, since the base station area is shown as a circle to simplify the illustration, there is an area that is not covered between adjacent areas, but this area is covered by any base station or a base station not shown. Note that this is also the case in FIG. 11 described later. First, FIG. 7A related to the first determination method shows base station areas A1 to A4 that pass through when the moving body moves. The base station area has a diameter of, for example, 500 meters. The number of points in the area conceptually indicates the number of times that the user has been in the base station area. This number of times corresponds to a number in which the point data continuously includes position information of the same latitude and longitude. As described above, when a certain number of times in a single base station area stays for a certain period of time, the point data indicating the position of the base station area continues, and the density per unit time increases. By using the density per unit time, it is possible to determine whether it is staying or moving. For example, when the base station area position continues three or more times in succession, it is determined as staying, and when it is less than that, it is determined as movement. As a result, in the illustrated example of FIG. 7A, since the base station area A2 is detected ten times continuously, it is determined that the stay is present. On the other hand, in the other base station areas A1, A3, and A4, since it is once, twice, and once, it is determined that it is not a stay and is therefore treated as a movement.

  Next, FIG. 7B related to the second determination method shows adjacent base station areas A5 to A11 through which the mobile body passes while moving. In this illustrated example, the mobile body is the base station area. From A5 to A6, A7, then from A8 to A9, return to A7, and then move to A10 and A11. At this time, when the vectors V1 to V7 between adjacent positions (centers of the base station area) in time series are obtained, the directions in the base station areas A6 to A10 greatly change between adjacent vectors as shown in the figure. . Such a movement may occur when there is a station in the base station area A7 and the user leaves the station and walks around a relatively narrow area near the station and returns to the original station. Therefore, when the direction of the vector changes by more than a certain threshold angle, the point data between them can be related to the stay. For example, when the angle changes between adjacent vectors, for example, by 60 degrees or more, it is determined that the object is staying, and when it is less than that, it is determined that it is not staying. In the illustrated example, there is no significant change in direction between the vectors V1 and V2, and then there is a large change between the vectors V2 and V3, between V3 and V4, between V4 and V5, and between V5 and V6, and the vectors V6 and V7. There is no significant change in the direction between Therefore, when considering a specific vector, there is no significant change in the direction of the immediately preceding and immediately following vectors, or there is no significant change in the direction of the immediately preceding vector, but the direction of the immediately following vector may be significantly different. Alternatively, when the direction of the immediately preceding vector changes greatly but the direction of the immediately following vector does not change greatly, it can be determined that this particular vector is not a stay. In the illustrated example, the vectors are V2 and V6. On the other hand, when the direction of the immediately preceding vector changes greatly and the direction of the immediately following vector changes greatly, it can be determined that this particular vector is related to the stay. In the illustrated example, the vectors are V3 to V5. In this way, it is possible to determine whether or not the stay is based on the change in the direction of the vector.

  Next, FIG. 7C related to the third determination method shows adjacent base station areas A12 to A14 through which the moving body passes while moving, and moves from A12 to A13 and A14. Yes. In this example, it has been detected that there has been one time in each area. Also, at the bottom of the figure, times tA12, tA13, and tA14 at which it was detected that they were in areas A12, A13, and A14 are shown. In the third determination method based on the speed, for each of the position point data arranged in time series, the speed between the previous point data, that is, the distance difference between the positions of the two adjacent point data is set to the two points. It is obtained by dividing by the time difference between the data times, and it is regarded as stay when the obtained speed is below a certain threshold speed. In the illustrated example of FIG. 7C, when the movement from the area A12 to A13 is compared with the movement from the area A13 to A14, the movement from the area A13 to A14 takes approximately 10 times longer. Therefore, the speed is slow and 1/10. Therefore, it can be determined that the area A12 is not staying but the area A13 is staying. This third determination method can cope with a case where there is only one point data in the place of stay such as area A13. Such a case may occur, for example, when the mobile device is turned off or when communication is not performed in the case of base station positioning.

  On the premise of the above passage mode, in step 600 of FIG. 6, the number of times that the same position continuously appears in the point data is calculated as the density. Next, in step 602, it is determined whether or not the density is greater than a certain threshold value. For example, assuming that the time resolution of the available point data is 10 minutes, this threshold value is set to 3, for example, to determine whether the same position appears for 30 minutes or more. If it is determined that the threshold value is 3 or more, it is determined in step 604 that the point data at that time is related to stay, and a first stay instruction bit (not shown in FIG. 3) indicating stay in the point data is determined. )). In the example of FIG. 7A, it is determined that the point data in the base station area A2 is a stay. On the other hand, when it is less than the threshold value, it is determined that it is not a stay, so that the first stay instruction bit is not set and it is handled as a movement. In the example of FIG. 7A, the point data in the base station areas A1, A3, A4 is treated as movement.

  In step 606, vectors between positions indicated by adjacent point data (V1 to V7 in FIG. 7B) are obtained. Next, in step 608, it is determined whether an angle AGa that changes from the direction of the immediately preceding vector and an angle AGb that changes the direction of the immediately following vector are greater than a certain threshold angle for a specific vector. When both AGa and AGb are greater than or equal to the threshold angle with respect to a specific vector, it is determined that the specific vector is related to stay, and in step 610, the second stay instruction of the point data related to the specific vector A bit (not shown in FIG. 3) is set. In the illustrated example, V3 to V5 are vectors related to stay, and the actions to the base station areas A8, A9 and A7 related to this vector are determined to be stays, and the second stay instruction bit of the point data related to this action Set. On the other hand, when both (i) AGa and AGb are less than the threshold angle, (ii) AGa is less than the threshold angle and AGb is greater than or equal to the threshold angle, or (iii) AGa is greater than or equal to the threshold angle. When AGb is less than the threshold angle, it is determined that the specific vector is not a stay, and the second stay instruction bit of the point data related to this vector is not set. In the illustrated example, it is determined that the vectors V1, V2, V6, and V7 are not related to the stay.

  Next, in step 614, the speed of movement between two adjacent point data is obtained. Next, in step 616, it is determined whether the obtained speed is less than the threshold speed. When the speed is less than the threshold speed, it is determined in step 618 that it is a stay, and a third stay instruction bit (not shown in FIG. 3) indicating stay in the source point data of the two adjacent point data. ) Is set. On the other hand, when the speed is not less than the threshold speed, it is determined that the vehicle is not staying, so that the third stay instruction bit is not set and it is handled as movement. In the example of FIG. 7C, the point data in the base station area A13 is determined as stay, for example, while the point data in the base station area A12 is determined as movement.

  In the next step 620, the point data in which at least one of the first, second, and third stay instruction bits is set is excluded as related to the stay, and the other point data are connected in time series to move only. Generate time-series point data for.

  Next, with reference to FIG. 8, one specific example of the transportation classification process in step 504 of FIG. 5 will be described in detail. In order to understand the processing here, the description will be made with reference to FIG. FIG. 9 shows two railway lines R and bus lines B that run substantially parallel to each other in a certain moving section. In addition, time-series point data PD1 to PD7 having positions on these routes are shown. Two or more routes may run in parallel or at some distance. In one embodiment of the present invention, even in such a case, which route was used to move? Estimation can be performed.

  First, in step 800 of FIG. 8, the railway lines and bus lines that can be used in a certain moving section are specified. In the illustrated example of FIG. 9, one railway line R and one bus line B are specified. Next, in step 802, it is determined whether there are two or more routes. If there are not two or more routes, that is, if there is only one route, the process proceeds to step 804. In step 804, one specified route is determined as a route used for movement. On the other hand, when it is determined that there are two or more, the process proceeds to step 806, where the number of point data falling on the two or more routes is obtained in order to determine which route is used. For that purpose, map data indicating the geographical position of each route is used. Further, whether or not the vehicle is on the route can be determined not only when it is completely located on the route but also based on whether or not it is closer to the route. Thus, the number of point data determined to be on each route is obtained. In the illustrated example of FIG. 9, in the illustrated range, five point data are dropped on the railway line and two point data are dropped on the bus route. In step 808, a route having a larger number of point data falling in the entire moving section is determined as a use route of the moving section. Also in the entire movement section, when there is a lot of point data falling on the railway line as in the illustrated example, the use route in this movement section is determined as this railway line. The distinction between the railway line and the bus line determined as described above indicates that the railway line is a railway line by setting a transportation instruction bit (not shown in FIG. 3) of point data in the moving section. It is not set for bus routes.

  As described above, the use route in each moving section is classified as a railway route or a bus route. In the example shown in FIG. 4, the route used in the moving section M1 is the railway route R1a, the route used in the moving section M2 is the bus route B2, and the route used in the moving section M3 is the bus route B3a.

  Next, with reference to FIG. 10, the details of the nearest station specifying process in the route candidate extraction process in step 506 of FIG. 5 will be described. In order to understand the processing here, a description will be given with reference to FIG. FIG. 11 shows a plurality of adjacent base station areas that are within a certain radius from the center of the base station area A20 where the departure point is located. Here, there are railway or bus stations in the adjacent base station areas A21 and A22, and these stations are shown as a first nearest station TS1 and a second nearest station TS2 as a departure point.

  First, in step 1000, the population density of the departure place is determined. This can be determined by, for example, the geographical location of the departure place, specifically, whether or not it is a city. In the next step 1002, the nearest station search range is determined according to the determined population density. For example, in a city, the radius is 250 meters, for example, and the search range is to the adjacent base station area. If it is not a city, the search range is a multiple of a radius of 250 meters. When the nearest station search range is determined in this way, in step 1004, a railway or bus station within the nearest search range is specified. Stations identified may include both railway stations and bus stations, as well as both. In the illustrated example of FIG. 11, it is specified that there are nearest stations in the base station areas A21 and A22 adjacent to the base station area A20 where the departure point is located.

FIGS. 10 and 11 described above relate to the identification of the nearest station of the departure point of the action, but the nearest station of the destination of the action can be identified by the same processing.
Next, details of one specific example of the route candidate selection process in the route candidate extraction process of step 506 of FIG. 5 will be described with reference to FIG. First, in step 1200, one or more combinations of the departure station and the destination station identified in FIG. 10 are identified. In the next step 1202, candidate routes between the stations are extracted from the route candidate data for each combination of the departure station and the destination station. This route candidate data can be obtained from the candidate route database as described above, thereby obtaining a plurality of candidate routes. In the example of FIG. 4, for example, (i) departure station → railway line R1a → railway line R2 → bus route B3a, (ii) departure station → railway line R1b → railway line R2 → bus route B3a, (iii) departure place Station → Railway R1b → Railway R2 → Bus route B3b, (iv) Departure station → Railway R1b → Bus route B2 → Bus route B3b.

  Next, a process of selecting one candidate from the plurality of route candidates identified in FIG. 11 and performing an estimated route will be described with reference to FIG. In order to understand the processing here, a description will be given with reference to FIG. In FIG. 14, a moving route RT (indicated by a dotted line) indicated by point data of a moving object and two candidate routes CRA and CRB (indicated by a solid line) are shown. In the illustrated example, point data PDi-1 to PDi + 2 are shown on the movement route RT. Correspondingly, points PAi-1 to RAi + 2 are shown on the candidate route CRA and points PBi-1 to RBi + 2 are shown on the candidate route CRB at certain distance intervals. In FIG. 14, it is shown that there is point data of the moving object on the smooth moving route RT. However, when the position information accuracy of the point data is low, such as the base station position, the position of the point data is moved. Note that there may be considerable deviation from the line of the route RT.

  First, in step 1300 of FIG. 13, the error detection unit 262 of the route selection unit 260 obtains an error between the actual movement route and a plurality of candidate routes. In the illustrated example of FIG. 14, an error between the movement route RT and the candidate routes CRA and CRB is obtained. Specifically, the distance between each point data RTi on the travel route RT and each point PAi on the candidate route CRA is calculated, and an error between the travel route RT and the candidate route CRA is obtained. An exemplary equation for determining the error is as follows:

Here, ai is the position of the point data on the moving route RT, and Bn is the position of the point on the candidate route CRA or CRB. Referring to the example of FIG. 14, for each of the i point data RTi on the moving route RT, the square of the distance to each of the n points on the candidate route is divided by n to obtain each point data An error Ai from the candidate route is obtained. Next, an error Ai for the obtained i pieces of point data is divided by i to obtain an overall error. There are various methods for obtaining an error between paths, and for example, a least square method can be used.

  In the next step 1302, the comparison unit 264 of the route selection unit 260 selects a candidate route with the smallest error obtained as described above as an estimated route. In the illustrated example of FIG. 14, the error with the candidate route CRA and the error with the route candidate CRB are compared with each other, and the candidate route with the smaller error is selected as the estimated route. When there are three or more candidate routes, the candidate route with the smallest error is selected as the estimated route. In this way, one estimated route can be selected from a plurality of candidate routes.

The travel route estimation apparatus according to the embodiment of the present invention has been described above. However, the present invention is not limited to this, and various modifications can be made without departing from the scope of the present invention.

100 Moving path estimation device
110 network
200 Data storage
220 Route candidate determination unit
260 Route selection unit
M1-M3 travel section
S1, S2 Stay section TS1, TS2 Nearest departure station
TD1, TD2 Nearest destination station
R1a, R1b, R2 Railway lines B2, B3a, B3b Bus lines A1 to A4, A5 to A11, A12 to A14 Base station area A20 to A22 Base station area V1 to V7 Vector AGa Immediately after angle AGb changing from the previous vector direction Angles PD1 to PD7 at which the direction of the vector changes Point data PAi-1 to RAi + 2 Points PBi-1 to RBi + 2 on the candidate route CRA Points PDi-1 to PDi + 2 on the candidate route CRB Point data on the moving route RT

Claims (14)

A moving route estimation method for estimating a moving route from a starting point of a moving object to a destination,
A step in which a data storage unit stores a position information set relating to the behavior of the mobile body from the starting point to the destination, wherein the behavior of the mobile body includes movement and stay;
The route candidate determining unit includes a step of determining a plurality of route candidates from the starting point to the destination of the moving body, the step including classifying action sections of the moving body,
Of the actions from the departure place to the destination of the mobile body, identifying the location information regarding stay;
Generating a position information set related only to movement by removing position information related to the stay from the stored position information set;
Including steps, and
A route selection unit selecting one route candidate from the plurality of route candidates as an estimated route of the moving body by comparing the plurality of route candidates with the position information set;
Including
Wherein said step of identifying the position information about the stay, the orientation of a given vector to the next adjacent positions from a location out of the location information of a series is, is with both of the immediately preceding vector and immediately after vector sill when changing value angle or more, the position information related to the given vector comprises steps for identifying and relating to stay, moving path estimation method. The method of claim 1, wherein the step of selecting as an estimated route comprises:
Detecting an error between the position information set and each of the plurality of route candidates;
Comparing the detected error and selecting the path candidate with the smallest error as the estimated path;
A moving path estimation method including: 3. The method according to claim 1 or 2, wherein the step of identifying location information regarding stays comprises:
The speed of the next moving to adjacent the second position from a first position in which certain of the location of a series is, when below a certain threshold speed, the position information relating to the first position stay A moving path estimation method further comprising the step of identifying as related to The method according to claim 1, wherein the step of determining a plurality of route candidates includes:
i) determining from a map data a departure station nearest to the departure place and a destination station nearest to the destination;
ii) selecting a plurality of route candidates from the departure station to the destination station based on the departure station and the destination station using route candidate data;
A moving path estimation method including: The method of claim 4, wherein
The step of determining from the map data the starting station nearest to the starting point and the destination station closest to the destination,
Determining the population density of the starting point and the destination;
In accordance with the determined population density, determining a nearest station search range of the departure place and a nearest station search range of the destination;
Identifying a station in the nearest station search range of the departure place and a station in the nearest station search range of the destination as the departure station and the destination station, respectively. The method according to any one of claims 1 to 5,
The location information set is included in time-series point data related to the mobile object,
Each said point data is a movement path | route estimation method containing the positional information on the base station which passed during the said movement of the said mobile body.   A computer program that causes a computer to execute the route estimation method according to claim 1. A route estimation device that estimates a route of travel from a starting point of a moving object to a destination,
Data storage means for storing a position information set related to the behavior of the mobile body from the starting point to the destination, wherein the behavior of the mobile body includes movement and stay;
Route candidate determination means for determining a plurality of route candidates from the starting point to the destination of the mobile body, including action section classification means, the action section classification means,
Of the actions from the departure place to the destination of the mobile body, stay identification means for identifying position information regarding stay;
Generating means for generating a position information set related only to movement by removing position information related to the stay from the received position information set;
Including route candidate determination means including:
Route selection means for selecting one route candidate from the plurality of route candidates as an estimated route of the mobile body by comparing the plurality of route candidates with the position information set;
Including
The stay identifying means, the orientation of a given vector to the next adjacent positions from a location out of the location information of a series is changed threshold angle or more with the both the immediately preceding vector and immediately after vector when performed to identify the position information related to the given vector is related to stay, movement path estimator. 9. The apparatus according to claim 8, wherein the route selection means is
Error detection means for obtaining an error between the position information set and each of the plurality of route candidates;
Comparing means for comparing the detected errors and selecting the path candidate with the smallest error as the estimated path;
A moving path estimation apparatus including: The apparatus according to claim 8 or 9, wherein the stay identifying means is
The speed of the next moving to adjacent the second position from a first position in which certain of the location of a series is, when below a certain threshold speed, the position information relating to the first position stay A movement path estimation apparatus that further performs identification to be related to the. The apparatus according to claim 8, wherein the route candidate determination unit includes a route candidate extraction unit,
The route candidate extraction means
i) a nearest station determining means for determining a departure station nearest to the departure place and a destination station nearest to the destination from map data;
ii) Route candidate selection means for selecting a plurality of route candidates from the departure station to the destination station using route candidate data based on the departure station and the destination station;
A moving path estimation apparatus including: The apparatus of claim 11.
The nearest station determining means is:
Determine the population density of the starting point and the destination,
According to the determined population density, determine the nearest station search range of the departure place and the nearest station search range of the destination,
A travel route estimation device configured to identify stations in the nearest station search range of the departure place and the nearest station search range of the destination as the departure station and the destination station, respectively. The device according to any of claims 8 to 12,
The location information set is included in time-series point data related to the mobile object,
Each of the point data includes position information of a base station that has passed during the movement of the mobile body,
Moving path estimation device.   A computer program for causing a computer to function as the movement path estimation apparatus according to claim 8.

Images