JP2010267000A - Path estimation device, path estimation method and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To solve a problem in the conventional path estimation device that a vehicle travel path cannot be estimated with high accuracy. <P>SOLUTION: The path estimation device is connected to an onboard device mounted on the vehicle via a network, and estimates the travel path from the vehicle start point to the arrival point based on the position of the vehicle. The path estimation device includes: an acquisition unit for acquiring position information which is transmitted from the onboard device and indicative of the vehicle position at predetermined time intervals; a recording unit for recording map information including road and intersection positions; a map matching unit for deciding road-by-road passing probability indicative of the possibility that the vehicle has traveled on each road, based on positional relationship between the vehicle position, indicated by the position information acquired by the acquisition unit, and the road and the intersection positions recorded by the recording unit; and a path estimation unit for estimating the vehicle travel path, based on the road-by-road passing probability decided by the map matching unit. <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention relates to a route estimation device, a route estimation method, and a program for estimating a travel route of a vehicle.

  In order to estimate information on traffic conditions from position information indicating the position of the vehicle, information on the attributes of the vehicle, etc., which is probe car data acquired from the traveling vehicle, it is based on the acquired position information of the vehicle, etc. It is necessary to estimate the travel route of the vehicle.

  In general, position information indicating the position of the vehicle is acquired at predetermined time intervals, the position of the vehicle indicated by the acquired position information is compared with the position of the road on the map, and the road on which the vehicle has traveled is specified. Thus, the travel route of the vehicle is estimated.

  Here, the vehicle position information can be acquired by GPS (Global Positioning System) or the like, but the acquired position information often includes measurement errors.

  Due to measurement errors, the road on which the vehicle has traveled may not be able to be specified due to reasons such as the position of the vehicle indicated by the position information deviating from the road or a plurality of roads in the vicinity. .

  Therefore, usually, even when the position information includes a measurement error, in order to estimate the travel route of the vehicle based on the position information, the road on which the vehicle has traveled is specified from the position of the vehicle indicated by the position information. Map matching processing is performed.

  Patent Document 1 describes a route estimation device that identifies a road on which a vehicle has traveled by performing a map matching process.

  The route estimation device described in Patent Literature 1 calculates the probability that the vehicle has traveled based on the position of the vehicle indicated by the position information for each road that the vehicle may have traveled, and based on the calculated probability, Map matching processing is performed to identify the road on which the vehicle has traveled.

  Specifically, the route estimation device described in Patent Document 1 is a vehicle when it is assumed that the vehicle has moved from the position of the own vehicle at a predetermined time to a road existing within a predetermined range from the position of the vehicle indicated by the position information. For each road existing within a predetermined range.

  Then, the route estimation device described in Patent Document 1 calculates the probability that the vehicle has traveled for each road based on the obtained moving direction of the vehicle, and the vehicle travels on the road with the highest calculated probability. Identified as a road.

JP-A-5-216407

  However, the route estimation device described in Patent Document 1 is calculated based on the moving direction of the vehicle when it is assumed that the vehicle has moved from the position of the own vehicle to a road existing within a predetermined range from the position of the vehicle indicated by the position information. Therefore, it is difficult to specify the road on which the vehicle has traveled with high accuracy since the road on which the vehicle has traveled is only specified.

  As a result, the route estimation device described in Patent Document 1 has a problem that it is not possible to accurately estimate the travel route of the vehicle.

  An object of the present invention is to provide a route estimation device, a route estimation method, and a program capable of estimating a travel route of a vehicle with high accuracy.

In order to achieve the above object, the route estimation apparatus of the present invention provides:
A route estimation device that is connected to a vehicle-mounted device mounted on a vehicle via a network and estimates a travel route from the departure point to the arrival point of the vehicle based on the position of the vehicle,
An acquisition unit that acquires position information transmitted from the in-vehicle device and indicating the position of the vehicle at a predetermined time interval;
A recording unit for recording map information including road and intersection positions;
The possibility that the vehicle has traveled for each road based on the positional relationship between the position of the vehicle indicated by the position information acquired by the acquisition unit and the position of the road and the intersection recorded by the recording unit. A map matching unit for determining a road-by-road passage probability,
A route estimation unit that estimates a travel route of the vehicle based on the road-by-road probability determined by the map matching unit.

In order to achieve the above object, the route estimation method of the present invention includes:
A route estimation method applied to a route estimation device that is connected to an in-vehicle device mounted on a vehicle via a network and estimates a travel route from a departure point to an arrival point of the vehicle based on the position of the vehicle. ,
An acquisition step of acquiring position information indicating the position of the vehicle transmitted from the in-vehicle device at a predetermined time interval;
A recording step for recording map information including road and intersection positions;
The possibility that the vehicle has traveled for each road based on the positional relationship between the position of the vehicle indicated by the position information acquired in the acquisition step and the position of the road and the intersection recorded in the recording step. A determination step of determining a road-by-road passage probability indicating:
A route estimation step of estimating a travel route of the vehicle based on the road-specific passage probability determined in the determination step.

In order to achieve the above object, the program of the present invention
A route estimation device that is connected to an in-vehicle device mounted on a vehicle via a network and estimates a travel route from the departure point to the arrival point of the vehicle based on the position of the vehicle.
A procedure for acquiring position information indicating the position of the vehicle transmitted from the in-vehicle device at predetermined time intervals;
A procedure to record map information including the location of roads and intersections;
Based on the positional relationship between the position of the vehicle indicated by the position information acquired by the acquisition procedure and the position of the road and the intersection recorded by the recording procedure, the vehicle traveled for each road. A procedure for determining the probability of passing by road indicating the possibility;
And a procedure for estimating a travel route of the vehicle based on the passage probability determined by the determination procedure.

  According to the present invention, the route estimation device is provided for each road based on the position of the vehicle indicated by the position information transmitted from the vehicle-mounted device mounted on the vehicle and the positional relationship between the road and the position of the intersection. The probability of passing by road indicating the possibility that the vehicle has traveled is determined.

  Then, the route estimation device estimates the travel route of the vehicle based on the determined road-specific passage probability.

  Therefore, even when the position information includes a measurement error, the route estimation device estimates the travel route of the vehicle based on the road-by-road probability indicating the possibility that the vehicle has traveled. Estimation can be performed.

It is a figure which shows an example of a structure of the route estimation system with which the route estimation apparatus of one Embodiment of this invention is applied. It is a block diagram which shows an example of a structure of the route estimation apparatus shown in FIG. It is a flowchart which shows an example of operation | movement of the map matching part shown in FIG. It is a figure explaining the determination process of the pass probability according to road by the map matching part shown in FIG. It is a figure which shows the result of the pass probability determination according to road by the map matching part shown in FIG. It is a flowchart which shows an example of operation | movement of the route estimation part shown in FIG. It is a flowchart which shows an example of operation | movement of the route estimation apparatus shown in FIG.

  EMBODIMENT OF THE INVENTION Below, the form for implementing this invention is demonstrated with reference to drawings.

  FIG. 1 is a diagram illustrating an example of a configuration of a route estimation system to which a route estimation device 10 according to an embodiment of the present invention is applied.

  The route estimation system according to the present embodiment includes on-vehicle devices 1-1 to 1-N (hereinafter referred to as “on-vehicle device 1”) mounted on each vehicle, and a route estimation connected to the on-vehicle device 1 via the wireless network 2. Device 10.

  The in-vehicle device 1 acquires information such as the vehicle position information and the traveling direction at a predetermined time interval, and associates the time when the information is acquired with the acquired positional information and information such as the traveling direction. Is transmitted to the route estimation device 10 via the wireless network 2.

  The route estimation device 10 estimates a travel route of a vehicle on which the in-vehicle device 1 is mounted based on the vehicle information data transmitted from the in-vehicle device 1 via the wireless network 2.

  Next, the configuration of the route estimation apparatus 10 will be described.

  FIG. 2 is a block diagram illustrating an example of the configuration of the route estimation apparatus 10.

  The route estimation apparatus 10 shown in FIG. 2 includes a vehicle information data acquisition unit 11, a vehicle information data recording unit 12, a road network data recording unit 13, a trip series data creation unit 14, a map matching unit 15, and a route estimation. Unit 16 and travel time calculation unit 17.

  The vehicle information data acquisition unit 11 acquires vehicle information data transmitted from the in-vehicle device 1 via the wireless network 2, and outputs the acquired vehicle information data to the vehicle information data recording unit 12.

  The vehicle information data recording unit 12 records the vehicle information data output from the vehicle information data acquisition unit 11.

  The road network data recording unit 13 records road network data that is map information including the positions of roads (links) on which vehicles travel and intersections (nodes) at which roads intersect.

  The trip series data creation unit 14 groups the vehicle information data recorded in the vehicle information data recording unit 12 for each vehicle in a time series in the order of the time when the information included in the vehicle information data is acquired. Create data.

  When there is a time zone in which the position of the vehicle indicated by the position information does not change, the trip series data creation unit 14 creates trip series data excluding the vehicle information data in that time zone.

  If there is no change in the position of the vehicle indicated by the position information for a predetermined time or more, it is considered that the vehicle is likely to be parked or stopped. By removing the vehicle information data in the time zone in which the vehicle is parked and stopped from the trip series data, it is possible to calculate an accurate travel time in calculating the travel time of the vehicle, which will be described later.

  The trip series data creation unit 14 outputs the trip series data created for each vehicle to the map matching unit 15 and the travel time calculation unit 17.

  Based on the road network data recorded in the road network data recording unit 13 and the trip series data output from the trip series data creation unit 14, the map matching unit 15 creates a vehicle for each road included in the road network data. The road-by-road passage probability indicating the passage probability is determined.

  Specifically, the map matching unit 15 specifies the position of the vehicle indicated by the position information included in the trip series data based on the road network data.

  And the map matching part 15 extracts the road which exists in the predetermined range from the specified position from road network data.

  Then, the map matching unit 15 determines the road-specific passage probability for each extracted road, and outputs road-specific passage probability data indicating the determined road-specific passage probability to the route estimation unit 16.

  The route estimation unit 16 estimates the travel route of the vehicle based on the road network data recorded in the road network data recording unit 13 and the road-specific passage probability data output from the map matching unit 15, and the estimated travel route Is output to the travel time calculation unit 17.

  The travel time calculation unit 17 is based on the trip sequence data output from the trip sequence data creation unit 14 and the travel route data output from the route estimation unit 16, and each road included in the travel route indicated by the travel route data. The travel time required for the vehicle to travel is calculated.

  Then, the travel time calculation unit 17 grasps the road congestion status by using the travel route data and the travel time data indicating the time required for the vehicle to travel on each road included in the travel route indicated by the travel route data. Output to other devices.

  Next, the operation of the map matching unit 15 will be described.

  FIG. 3 is a flowchart showing an example of the operation of the map matching unit 15.

  First, the map matching unit 15 specifies the position of the vehicle indicated by the position information included in the trip series data output from the trip series data creation unit 14 based on the road network data recorded in the road network data recording unit 13. .

  And the map matching part 15 extracts the road which exists in the predetermined range from the specified position (step S31).

  FIG. 4 is a diagram illustrating the road-by-road passage probability determination process performed by the map matching unit 15.

  In FIG. 4, white circles indicate intersections (nodes), and solid lines indicate roads (links).

  The black circles indicate the position of the vehicle indicated by the position information.

  In the following description, for example, a road connecting the intersection A and the intersection B is referred to as a road AB.

  In the example of FIG. 4, the map matching unit 15 extracts a road AB and a road AC that exist within a predetermined range from the vehicle position a indicated by the position information.

  Note that if there is no road within a predetermined range from the vehicle position indicated by the position information, the map matching unit 15 processes the position information because the position information is likely to contain a measurement error. Exclude from

  Next, the map matching unit 15 extracts a target road for which the pass probability for each road is determined from roads existing within a predetermined range from the vehicle position indicated by the position information extracted in step S31 (step S31). S32).

  Specifically, first, the map matching unit 15 draws a perpendicular to the road extracted in step S31 from the position of the vehicle indicated by the position information, the position of the vehicle indicated by the position information, and the extracted road Find the shortest point of.

  In the example of FIG. 4, the map matching unit 15 draws a perpendicular to the extracted road AB and road AC and obtains the shortest points a-1 and a-2 between the position a, the road AB, and the road AC. .

  Then, the map matching unit 15 determines the position of the road extracted in step S31 based on the position of the obtained shortest point and the positional relationship with the intersection having the shortest distance from the shortest point on the road where the shortest point exists. From, the road of the object which judges the passage probability according to road is extracted.

  Examples of roads for which the passage probability for each road is determined include the following.

  For example, when the obtained shortest point does not exist near the intersection, or even if it exists near the intersection, the number of roads connected to the intersection is less than or equal to a predetermined number (in this embodiment, 2 or less) In this case, the map matching unit 15 extracts the road where the shortest point exists as a road for which the pass probability for each road is determined.

  In addition, even if the calculated shortest point exists near the intersection and the number of roads connected to the intersection is greater than a predetermined number, the vehicle information data arranged in the time series of trip series data, When the road on which the vehicle has traveled is clear at the position of the vehicle indicated by the position information included in the vehicle information data acquired at the previous time, and the road on which the vehicle traveled connects to the intersection The map matching unit 15 extracts a road connected to the intersection as a road for which the pass probability for each road is determined.

  When there is no road that exists within a predetermined range from the position of the vehicle indicated by the position information, the position information is excluded from processing targets.

  In the example of FIG. 4, as a result of obtaining the shortest point between the position a indicated by the position information and the extracted road AB and road AC, the shortest point a-1, indicated by a black triangle mark, near the intersection A. Since a-2 exists and there are two roads connected to the intersection A, the road AB and the road AC are extracted as the roads for which the pass probability by road is determined.

  Next, the map matching unit 15 determines whether or not the process of step S32 has been performed on all roads extracted in step S31 (step S33).

  When the process of step S32 is not performed for all the roads extracted in step S31 (step S33: NO), the map matching unit 15 returns to step S32 and performs the process of step S32 for all the roads. The same process is repeated until the process ends.

  When the process of step S32 is performed on all the roads extracted in step S31 (step S33: YES), the map matching unit 15 determines each road extracted as a target road for determining the pass probability by road. Next, the pass probability by road is determined (step S34).

  Here, in the present embodiment, the road-by-road probability is divided into “confirmed” and “candidate”.

  Further, a road whose road-specific passage probability is determined to be “determined” is referred to as a fixed road, and a road whose road-specific passage probability is determined to be “candidate” is referred to as a candidate road.

  The confirmed road is a road where it is clear that the vehicle has traveled on the road, for example, there is one road subject to pass probability determination for each road extracted in step S32 corresponding to the position of the vehicle indicated by the position information. is there.

  The candidate road is selected from the plurality of roads when there are a plurality of roads subject to road-by-road pass probability determination extracted in step S32 corresponding to the position of the vehicle indicated by the position information. The number of roads is equal to or less than a predetermined number (in this embodiment, 2).

  The candidate roads are selected from a plurality of roads in order of increasing distance from the vehicle position indicated by the position information.

  In the example of FIG. 4, two roads (road AB and road AC) corresponding to the position a of the vehicle indicated by the position information are extracted as roads for which the pass probability for each road is determined. The road-by-road passage probability of the road AC is determined as a “candidate”.

Then, the map matching unit 15 outputs road-specific passage probability data indicating the determined road-specific passage probability to the route estimation unit 16.
FIG. 5 is a diagram illustrating the result of road-by-road pass probability determination by the map matching unit 15.

  In FIG. 5, white circles, black circles, black triangles, and solid lines have the same meaning as in FIG.

  In FIG. 5, white triangle marks indicate the shortest point from the position of the vehicle indicated by the position information on the road whose road-specific passage probability is “determined”.

  In the example of FIG. 5, it is assumed that the vehicle information data included in the trip series data is acquired in the order of position b, position c, position d, and position e from position information corresponding to position a.

  In the example of FIG. 5, the position a of the vehicle indicated by the position information is in the vicinity of the intersection A, and there are the shortest points a-1 and a-2 with the road AB and the road AC existing in the vicinity. The road-by-road passage probability of the road AC is “candidate”.

  Similarly, since the vehicle positions b and c indicated by the position information are near the intersections B and D, respectively, the road BC, road BD, and road DE passing probability by road, where the shortest point exists, is “Candidate”.

  Further, since there is no intersection near the vehicle position d indicated by the position information and the only road existing in the vicinity is the road EF, the passage probability of the road EF by road is “determined”.

  Further, since there is no road existing within a predetermined range from the vehicle position e indicated by the position information, it is excluded from the processing target.

  Next, the operation of the route estimation unit 16 will be described.

  FIG. 6 is a flowchart illustrating an example of the operation of the route estimation unit 16.

  First, the route estimation unit 16 determines, for each road, a link cost for route search that is added every time the road passes based on the road-specific passage probability determined by the map matching unit 15 (step S41). ).

  Specifically, the route estimation unit 16 determines a link cost that decreases in value in the order of a confirmed road, a candidate road, a confirmed road, and other roads other than the candidate road.

  In the present embodiment, for example, the link cost of the fixed road is 1, the link cost of the candidate road is 2, and the link cost of the other roads is 5.

  In addition, in this embodiment, although demonstrated using the example which determines the link cost of each road only based on the passage probability according to road, it is not restricted to this, for example, the length of the road It is also possible to determine the link cost in consideration of the time required for passing the traffic.

  Next, the route estimation unit 16 sums the link cost determined in step S41 for the roads included in the route from the departure road that is the departure point to the arrival road that is the arrival point through the confirmed road. And a route that minimizes the calculated total link cost is searched (step S42).

  For the search for the route with the minimum total link cost, for example, the Dijkstra method, which is an algorithm for efficiently obtaining the shortest route between two points, is used.

  Depending on the position of the vehicle indicated by the position information, there may be a plurality of roads as departure roads and arrival roads corresponding to the departure point and the arrival point.

  For example, in the example of FIG. 5, there are a road AB and a road AC that are candidate roads as departure roads corresponding to the position a that is the departure point.

  In this case, the route estimation unit 16 searches for two candidate routes that are travel route candidates, that is, the route from the road AB to the road EF that is the arrival point and the route from the road AC to the road EF that is the arrival point. To do.

  In the example of FIG. 5, when the road AB is the departure road, the route that passes in the order of the road AB, the road BD, the road DE, and the road EF has a total link cost of 7 and the minimum.

  When the road AC is the departure road, the route passing through the road AC, the road CE, and the road EF in this order has a total link cost of 8 and is the minimum.

  In the example of FIG. 5, since the road EF that is the arrival point is a fixed road, only the two routes of the route from the road AB to the road EF and the route from the road AC to the road EF are searched. When there are a plurality of departure points, departure roads, and arrival roads, the route search unit 16 searches for candidate routes for each combination.

  Further, the route from the departure point to the arrival point is searched in consideration of the information on the traveling direction of the vehicle included in the vehicle information data.

  Next, the route estimation unit 16 determines whether a candidate route that minimizes the total link cost has been searched for all combinations of departure roads and arrival roads (step S43).

  When the candidate route is not searched for the combination of all departure roads and arrival roads (step S43: NO), the route estimation unit 16 returns to step S42, and the candidate route is searched for all the combinations. The process is repeated until the search is completed.

  When the candidate route is searched for all combinations of the departure road and the arrival road (step S43: YES), the route estimation unit 16 estimates the travel route of the vehicle from the searched candidate routes (step S43). S44).

  Specifically, the route estimation unit 16 obtains the average travel speed of the vehicle from the travel distance of the candidate route searched for each combination of the departure road and the arrival road and the travel time of the vehicle obtained from the trip series data. Then, candidate routes that are clearly abnormal, such as the average traveling speed being extremely fast or extremely slow, are excluded.

  As described above, in the trip series data, the vehicle information data of the time zone in which the vehicle is considered parked / stopped has been deleted, so the accurate average traveling speed can be obtained without being affected by parking / stopping. Can be sought.

  Then, the route estimation unit 16 calculates, for each candidate route, the shortest distance from each position of the vehicle indicated by the plurality of position information to the road included in the remaining candidate route, and the total value of the calculated shortest distances The candidate route that minimizes is estimated as the travel route of the vehicle.

  In the example of FIG. 5, the route passing in the order of road AB, road BD, road DE, and road EF is routed from each position indicated by the position information rather than the route passing in order of road AC, road CE, and road EF. Since the total value of the distances up to is small, the route that passes in the order of the road AB, the road BD, the road DE, and the road EF is estimated as the travel route of the vehicle.

  Finally, the operation of the route estimation apparatus 10 will be described.

  FIG. 7 is a flowchart illustrating an example of the operation of the route estimation apparatus 10.

  First, the trip series data creation unit 14 sequentially reads vehicle information data of each vehicle transmitted from the in-vehicle device 1 and recorded in the vehicle information data recording unit 12 (step S51).

  And trip series data creation part 14 creates trip series data for every vehicle based on the read vehicle information data (Step S52).

  As described above, when creating trip series data, if there is a time zone in which the position of the vehicle indicated by the location information has not changed for a predetermined time or longer, the vehicle information data for that time zone is deleted. It is desirable to create trip series data.

  Then, the trip series data creation unit 14 outputs the created trip series data to the map matching unit 15 and the travel time calculation unit 17.

  Next, the map matching unit 15 performs the process shown in FIG. 3 based on the road network data recorded in the road network data recording unit 13 and the trip series data output from the trip series data creating unit 14. Another pass probability is determined (step S53).

  Then, the map matching unit 15 outputs road-specific passage probability data indicating the determined road-specific passage probability to the route estimation unit 16.

  Next, the route estimation unit 16 performs the process shown in FIG. 6 based on the road-specific network data recorded in the road network data recording unit 13 and the road-specific passage probability data output from the map matching unit 15. The travel route of the vehicle is estimated (step S54).

  Then, the route estimation unit 16 outputs travel route data indicating the estimated travel route of the vehicle to the travel time calculation unit 17.

  The travel time calculation unit 17 is based on the trip sequence data output from the trip sequence data creation unit 14 and the travel route data output from the route estimation unit 16, and each road included in the travel route indicated by the travel route data. The travel time required for the vehicle to travel is calculated (step S55).

  And since the route estimation apparatus 10 performs the processing from step S53 to step S55 for each trip series data created by the trip series data creation unit 14, from step S53 to all of the created trip series data. It is determined whether the processing up to step S55 has been performed (step S56).

  If there is trip series data that has not been processed from step S53 to step S55 (step S56: NO), the process returns to step S53, and the process is repeated until the travel route is estimated for all trip series data. .

  As described above, according to the present embodiment, the route estimation device 10 is based on the positional relationship between the position of the vehicle indicated by the positional information and the position of the road and the intersection transmitted from the in-vehicle device 1 mounted on the vehicle. Based on each road, the pass probability for each road is determined.

  Then, the route estimation device 10 estimates the travel route of the vehicle based on the determined road-specific passage probability.

  Therefore, since the route estimation device 10 estimates the travel route of the vehicle based on the road-by-road probability indicating the possibility that the vehicle has traveled even when the position information includes a measurement error, a highly accurate travel route Can be estimated.

  In addition, when there are a plurality of departure roads and arrival roads corresponding to the departure point and the arrival point, the route estimation device 10 can select candidates from the departure point to the arrival point for each combination of the plurality of departure roads and arrival roads. The route is searched, and the traveling route of the vehicle is estimated from the plurality of searched candidate routes.

  Therefore, the route estimation device 10 can estimate the traveling route of the vehicle with high accuracy even when there are a plurality of departure roads and arrival roads corresponding to the departure point and the arrival point.

  In addition, you may apply the method performed in the route estimation apparatus 10 of this invention to the program for making a computer perform. In addition, the program can be stored in a storage medium and can be provided to the outside via a network.

DESCRIPTION OF SYMBOLS 1 Vehicle equipment 2 Wireless network 10 Route estimation apparatus 11 Vehicle information data acquisition part 12 Vehicle information data recording part 13 Road network data recording part 14 Trip series data creation part 15 Map matching part 16 Path estimation part 17 Travel time calculation part

Claims (17)

A route estimation device that is connected to a vehicle-mounted device mounted on a vehicle via a network and estimates a travel route from the departure point to the arrival point of the vehicle based on the position of the vehicle,
An acquisition unit that acquires position information transmitted from the in-vehicle device and indicating the position of the vehicle at a predetermined time interval;
A recording unit for recording map information including road and intersection positions;
The possibility that the vehicle has traveled for each road based on the positional relationship between the position of the vehicle indicated by the position information acquired by the acquisition unit and the position of the road and the intersection recorded by the recording unit. A map matching unit for determining a road-by-road passage probability,
A route estimation device comprising: a route estimation unit that estimates a travel route of the vehicle based on the road-specific passage probability determined by the map matching unit. The map matching unit
Extracting the road existing within a predetermined range from the position of the vehicle indicated by the position information acquired by the acquisition unit;
For each of the extracted roads, the positional relationship between the shortest point with the shortest distance to the vehicle position on the road and the position of the shortest intersection with the shortest point among the intersections on the road The route estimation apparatus according to claim 1, wherein the passage probability of the road is determined based on the road.   The route estimation apparatus according to claim 2, wherein the map matching unit determines a passing probability for each road of a predetermined number or less of the extracted roads. The route estimation unit
Based on the road-specific passage probability determined by the map matching unit, for each road, determine a link cost that is a value for the travel route estimation,
Searching for a first candidate route that is a candidate for the vehicle's travel route;
For each of the searched first candidate routes, calculate a total value of the link costs of the roads included in the first candidate route,
4. The route estimation device according to claim 1, wherein the first candidate route that minimizes the total value of the link costs is estimated as a travel route of the vehicle. 5.   The route estimation device according to claim 4, wherein the route estimation unit determines the cost so that the value decreases as the road-specific passage probability determined by the map matching unit increases. The route estimation unit
When there are a plurality of combinations of a candidate for a departure road that is a road corresponding to the departure point and a candidate for an arrival road that is a road corresponding to the arrival point,
For each combination of the departure road candidate and the arrival road candidate, the travel route of the vehicle that passes through the departure road candidate and the arrival road candidate is searched as the first candidate route, and searched. A second candidate route that minimizes the total value of the link costs is estimated from the first candidate routes,
For each second candidate route, a shortest distance from each position of the vehicle indicated by a plurality of position information to a road included in the second candidate route is calculated, and a total value of the calculated shortest distances is calculated. Calculate
6. The route estimation device according to claim 4, wherein the second candidate route having the minimum value of the shortest distance is estimated as a travel route of the vehicle. The acquisition unit further acquires time information transmitted from the in-vehicle device and indicating time when the position information of the vehicle is acquired;
For each vehicle, trip series data is created by grouping vehicle information data in which the position information acquired by the acquisition unit is associated with the time information in time order indicated by the time information. A creation section to
Based on the travel route of the vehicle estimated by the route estimation unit and the trip sequence data created by the trip sequence creation unit, the vehicle travels on a road included in the estimated travel route. The route estimation device according to any one of claims 1 to 6, further comprising a travel time calculation unit that calculates a required time.   When there is a time zone in which the position of the vehicle indicated by the location information acquired by the acquisition unit does not change, the creation unit, except for the vehicle information data in which the location information is acquired in the time zone, The route estimation apparatus according to claim 7, wherein the trip series data is created. A route estimation method applied to a route estimation device that is connected to an in-vehicle device mounted on a vehicle via a network and estimates a travel route from a departure point to an arrival point of the vehicle based on the position of the vehicle. ,
An acquisition step of acquiring position information indicating the position of the vehicle transmitted from the in-vehicle device at a predetermined time interval;
A recording step for recording map information including road and intersection positions;
The possibility that the vehicle has traveled for each road based on the positional relationship between the position of the vehicle indicated by the position information acquired in the acquisition step and the position of the road and the intersection recorded in the recording step. A determination step of determining a road-by-road passage probability indicating:
A route estimation method comprising: a route estimation step of estimating a travel route of the vehicle based on the road-by-road probability determined in the determination step. In the determination step,
Extracting the road existing within a predetermined range from the position of the vehicle indicated by the position information acquired by the acquisition step;
For each of the extracted roads, the positional relationship between the shortest point with the shortest distance to the vehicle position on the road and the position of the shortest intersection with the shortest point among the intersections on the road The route estimation method according to claim 9, wherein the passage probability of the road is determined based on the road.   The route estimation method according to claim 10, wherein, in the determining step, a passage probability for each road of a predetermined number or less of the extracted roads is determined. In the route estimation step,
Based on the road-specific passage probability determined in the determination step, for each road, determine a link cost that is a value for the travel route estimation,
Searching for a first candidate route that is a candidate for the vehicle's travel route;
For each of the searched first candidate routes, calculate a total value of the link costs of the roads included in the first candidate route,
The route estimation method according to claim 9, wherein the first candidate route that minimizes the total value of the link costs is estimated as a travel route of the vehicle.   The route estimation method according to claim 12, wherein in the route estimation step, the cost is determined such that the higher the passage probability determined by the determination step is, the smaller the value is. In the route estimation step,
When there are a plurality of combinations of a candidate for a departure road that is a road corresponding to the departure point and a candidate for an arrival road that is a road corresponding to the arrival point,
For each combination of the departure road candidate and the arrival road candidate, the travel route of the vehicle that passes through the departure road candidate and the arrival road candidate is searched as the first candidate route, and searched. A second candidate route that minimizes the total value of the link costs is estimated from the first candidate routes,
For each second candidate route, a shortest distance from each position of the vehicle indicated by a plurality of position information to a road included in the second candidate route is calculated, and a total value of the calculated shortest distances is calculated. Calculate
The route estimation method according to claim 12 or 13, wherein the second candidate route having the minimum sum of the shortest distances is estimated as a travel route of the vehicle. In the acquisition step, time information indicating the time when the position information of the vehicle acquired from the in-vehicle device is acquired is further acquired,
For each vehicle, trip series data is created by grouping vehicle information data in which the position information acquired in the acquisition step is associated with the time information in time order indicated by the time information. A creation step to
Based on the travel route of the vehicle estimated by the route estimation step and the trip sequence data created by the trip sequence creation step, the vehicle travels on a road included in the estimated travel route. The route estimation method according to any one of claims 9 to 14, further comprising a travel time calculation step of calculating a required time.   In the creation step, when there is a time zone in which the position of the vehicle indicated by the location information acquired in the acquisition step has not changed, except for the vehicle information data in which the location information is acquired in the time zone, The route estimation method according to claim 15, wherein the trip series data is created. A route estimation device that is connected to an in-vehicle device mounted on a vehicle via a network and estimates a travel route from the departure point to the arrival point of the vehicle based on the position of the vehicle.
A procedure for acquiring position information indicating the position of the vehicle transmitted from the in-vehicle device at predetermined time intervals;
A procedure to record map information including the location of roads and intersections;
Based on the positional relationship between the position of the vehicle indicated by the position information acquired by the acquisition procedure and the position of the road and the intersection recorded by the recording procedure, the vehicle traveled for each road. A procedure for determining the probability of passing by road indicating the possibility;
A program for executing a procedure for estimating a travel route of the vehicle based on the passage probability determined by the determination procedure.

Images