JP2016133386A - Map matching system and map matching method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To appropriately estimate the moving route of a probe car by parallely evaluating and integrating path findings in respective WP sections.SOLUTION: The map matching system includes: a data storage part for storing probe data having a plurality of pieces of WP position information for a probe car and digital road map data; a WP section setting part for setting a plurality of WP sections of the probe car based on the probe data and the digital road map data; a vicinity link setting part for setting one or more vicinity links for connecting the WP sections based on the probe data and the digital road map data; a reliability information calculation part for calculating reliability information for each of the plurality of WP sections; a path finding order determination part for weighting each of the plurality of WP sections to determine the order of path findings; and a path finding part for executing path finding by linking each of the plurality of WP sections via one or more vicinity links with determined path finding order.SELECTED DRAWING: Figure 10

Description

  The present invention relates to a map matching system and a map matching method, and more particularly to a map matching system and a map matching method that evaluate and integrate a route search between each waypoint in parallel for each waypoint section using probe data. .

  2. Description of the Related Art Conventionally, there is a probe car system called a probe car that collects position information and measurement time from an automobile functioning as a sensor. In the probe car system, in addition to position data indicating the position of the probe car measured using a GPS (Global Positioning System) function at a certain time from the probe car, the probe car system is measured by an acceleration sensor and / or a gyro sensor. Vehicle behavior data (for example, front / rear / left / right acceleration, probe car direction, etc.), event information (ABS (Antilock Brake System) operation signal, wiper operation signal, etc.) that occurred at a certain point, business vehicle attributes, etc. Probe data including various information such as information (taximeter information, etc.) is transmitted to the center. The center side receives the transmitted probe data and reuses it as various information.

  The position of the probe car at a certain time, that is, the waypoint of the probe car is called a waypoint (WP: Way-Point), and the position data indicating the WP is called WP information. The WP information includes probe car identification information (user ID, vehicle ID), positioning time, latitude information and longitude information, and data such as the behavior data, event information, and attribute information described above.

  For example, a traffic jam situation and a traffic accident point can be estimated from vehicle behavior data, and a rainfall amount and a rainfall area can be estimated from an operation signal of a wiper. The probe car system is regarded as one of the most effective means for monitoring traffic conditions from the viewpoint of cost and area coverage.

  The information obtained from the probe car is just one sample, and it does not show its effect with a single car, but by gathering a lot of information, it becomes so-called big data and its reliability increases, and a route that avoids traffic congestion This is considered to contribute to smooth road traffic conditions. There are various types of probe cars, but in this application, the main object is discrete probe data collected by business vehicles such as taxis, buses and trucks.

  In the probe car system described above, a map matching method using probe data is used for various road traffic services. Map matching is a technique for estimating a route traveled by a probe car on a road network based on measured WP information of the probe car.

  When executing map matching, digital road map data obtained by converting a road network into digital data is used. Digital road map data is based on roads by nodes (intersections and other nodes on the road network and attribute changes (for example, changes from expressways to general roads)) and links (road sections between nodes). This data represents the network topology and road shape. Each node and link is assigned an identification number, and corresponding position data is also attached. Therefore, in map matching using probe data, the position of the WP of the probe car and its route on the digital road map data. Can be shown. When performing map matching on the digital road map data, candidate routes are searched on the digital road map data based on WP information at a plurality of points received from an arbitrary probe car.

  A specific example of probe car movement path estimation in map matching will be described below with reference to FIG.

  FIG. 1A is an example in which the position of the received WP information (three points) is superimposed and displayed on the digital road map data (at this stage, the map matching process is not executed). FIG. 1B shows a point on the neighboring road and its traveling direction selected from the position and orientation of the WP information. Further, in FIG. 1C, a route between points on the road selected in the previous step is selected by a known shortest route search algorithm such as Dijkstra method.

  As the “shortest route” here, “the route with the minimum total cost” is selected based on the “link cost” set for each link and the “right / left turn cost” added at the time of right / left turn. . The link cost is determined on the basis of the link length (link distance), taking into account various circumstances such as road type, the number of lanes, and the like as necessary, and performing some corrections.

  By such processing, the travel route of the probe car can be estimated. In the conventional map matching method, the moving path of the probe car is estimated in the time series order from the upstream to the downstream of the WP.

JP 2012-103947 A JP 2013-210905 A

  In the above map matching method, route links are identified in order of time series from upstream to downstream of the WP section. Therefore, when selecting a plurality of neighboring links, an appropriate route link can be selected even if one-way traffic is taken into consideration. There are cases that cannot be identified. FIG. 2 shows that when a route link is specified from a plurality of neighboring links, an appropriate route link is caused by the fact that the traveling direction of the probe car cannot be determined from the positional relationship between the position of the WP information and the road. An example of a case in which cannot be specified is shown.

  As described above, in the conventional map matching method, the route link of each WP section is specified in the time series order from the upstream to the downstream of the WP section. That is, in the example of FIG. 2, after specifying the route link in the WP section 1-2, the route link is specified in the WP section 2-3. As shown in FIG. 2, there are two neighboring links NL1 and NL2 within a predetermined range of WP1 and WP2 in the WP section 1-2. Both NL1 and NL2 do not have special considerations that are excluded as route links, such as one-way traffic.

  When NL1 and NL2 are compared, the link length and the number of left / right turns are almost the same, and it is impossible to determine which neighboring link is appropriate as a route link unless there are consideration factors such as one-way traffic. . In such a situation, for example, when NL1 is specified as the route link, when specifying the route link in the subsequent WP section 2-3, WP3 exists between WP1 and WP2 in NL1, and the loopback is performed. As a result, NL1 is found to be inappropriate as a route link in the WP section 1-2. In such a case, an unnatural result is obtained as the travel route, or the process returns to the route link specifying process in the WP section 1-2 again, and NL2 is specified as the route link, and then the route in the WP section 2-3. The link needs to be specified. This cannot be said to be estimating the moving path of the probe car efficiently.

  3 and 4 identify an appropriate route link due to the fact that each of the plurality of neighboring links is running parallel to each other when the route link is identified from among the plurality of neighboring links. An example of a case that cannot be done is shown.

  In the example of FIG. 3, after specifying the route link in the WP section 1-2, the route link in the WP section 2-3 and then the route link in the WP section 3-4 are specified. As shown in FIG. 3, there are two neighboring links NL1 (main line side) and NL2 (connection path side) within a predetermined range of WP1 and WP2 in the WP section 1-2. Both NL1 and NL2 do not have special considerations that are excluded as route links, such as one-way traffic.

  NL1 and NL2 are running side by side, and as shown in FIG. 5, NL1 is a straight-only link (that is, it cannot make a left turn). In the WP section 2-3, the neighboring link NL3 exists alone within a predetermined range of WP2 and WP3. However, since NL3 needs to make a left turn when proceeding from WP2, NL1 and NL3 cannot be connected. Regardless of the travel route, in the route link specifying process in the WP section 1-2, it is determined which neighboring link is appropriate as the route link unless there is a consideration element such as one-way traffic. Cannot judge. Also in this case, when NL1 is specified as a route link, NL1 becomes a route link in the WP section 1-2 only after a downstream link link specifying process (a route link specifying process in the WP section 2-3). As a result, it becomes clear that it is not appropriate, and the process returns to the route link specifying process in the upstream WP section again.

  In the example of FIG. 4, there are two neighboring links NL1 and NL2 overlapping on the map within a predetermined range of WP1 and WP2 in the WP section 1-2. NL1 and NL2 run in parallel up and down, NL1 is a highway, and NL2 is a general road installed directly under NL1. Since the neighboring link NL3 that exists independently within a predetermined range of WP2 and WP3 in the WP section 2-3 is a general road, NL1 and NL3 cannot be connected. Nevertheless, in the route link specifying process in the WP section 1-2, it is not possible to determine which neighboring link is appropriate as the route link. Also in this example, which of the neighboring links NL1 and NL2 is appropriate as the route link can be determined only by the route link specifying process in the subsequent WP section 2-3.

  The problem described above is caused by specifying the route link from the upstream of the WP section. For example, in the example of FIG. 3, only the neighboring link NL3 exists in the WP section 2-3, and only the neighboring link NL4 exists in the WP section 3-4. In such a situation, the path link in the WP section 1-2 is identified by specifying the path link in the WP section 2-3 (that is, NL3) or the path link in the WP section 3-4 (that is, NL4) first. It can be determined that the neighboring link NL2 is appropriate.

  Patent Document 1 discloses an information processing apparatus that can accurately identify a travel link from time-series position information included in probe information. The information processing apparatus according to Patent Document 1 traces the travel link upstream even if the travel link can be specified as one of the links connected downstream of the plurality of candidate links in map matching. And the plurality of candidate links are connected, the problem that one of these candidate links cannot be specified as the traveling link is solved (paragraphs 0002 to 0009). Then, the information processing apparatus according to Patent Document 1 (1) determines whether or not there is one candidate link in the time-series position information included in the probe information. (2) In (1), the candidate link is 1 If there is one candidate link, it is determined whether or not there is one candidate link in the information of the previous position, and when there is one candidate link, the link between both links is specified as a traveling link, and (3) (1 ), If there are multiple candidate links, it is determined whether or not a roadside communication device is included in a predetermined area of the link connecting the previous position. If included, the link is specified as a traveling link. (FIGS. 5 to 9).

  As shown in the above configuration, when there is one candidate link, the information processing apparatus according to Patent Document 1 specifies the travel link between the two links as the travel link, and accurately identifies the travel link. However, when there are a plurality of link candidates, the information processing apparatus according to Patent Document 1 only returns to the previous position and determines each candidate link, and does not solve the above-described problem. Absent.

  Patent Document 2 discloses a probe information statistical system that generates traffic information by setting reliability for probe information according to reliability. As specific examples of the reliability setting, (1) the reliability of the probe information PI for the traveling lane including only the straight traveling direction as the leaving direction, rather than the probe information PI regarding the traveling lane including the direction other than the straight traveling direction as the leaving direction. Set high. (2) The reliability of the probe information PI for the traveling lane where the lanes do not merge is set higher than the probe information PI for the traveling lane where the lanes merge. (3) The exit direction includes the predetermined direction as the exit direction, and includes the predetermined direction as the exit direction, and includes the predetermined direction as the exit direction, and includes the predetermined direction as the exit direction. As described above, the reliability of the probe information PI is set to be low for the traveling lane in which the additional lane including the predetermined direction is not added (paragraphs 0033 to 0039).

  As shown in the above configuration, the probe information statistical system according to Patent Document 2 is configured such that at each point of the probe information, the branch point has a lower reliability than the non-branch point, and the traffic information of the probe information statistical system is Increased reliability. However, the probe information statistical system according to Patent Document 2 merely determines whether or not the total sum of reliability set according to the above-described criteria exceeds a predetermined threshold and statisticalizes probe information (No. 0041). Paragraph and Paragraph 0042) still do not solve the problem described above.

  The present invention has been made in view of such a problem, and the object of the present invention is to evaluate the route links of each WP section in parallel for each WP section, not in chronological order, and have high reliability. And a map matching system and method for appropriately estimating a moving path of a probe car.

  In order to solve the above problems, a first aspect of a map matching system and a map matching method according to the present invention is a map matching system for estimating a moving path of a probe car, and a plurality of WP positions with respect to the probe car. A data storage unit that stores probe data having information and digital road map data; a WP section setting unit that sets a plurality of WP sections of the probe car based on the probe data and the digital road map data; and Based on probe data and the digital road map data, a neighboring link setting unit for setting one or a plurality of neighboring links connecting the WP sections, and reliability information for calculating reliability information for each of the plurality of WP sections. Based on the calculation unit and the reliability information, the plurality of WPs Each of the plurality of WP sections is connected by the one or a plurality of neighboring links in a route search order determination unit that determines the route search order by weighting each of the intervals, and in the determined route search order. And a route search unit for executing a route search.

  Further, a second aspect of the map matching system and map matching method according to the present invention is the first aspect of the map matching system and map matching method according to the present invention, wherein the reliability information calculation unit further includes the route search. The reliability information is updated based on a result of the route search executed by the unit, and the route search unit further executes the route search based on the updated reliability information. .

  Further, a third aspect of the map matching system and map matching method according to the present invention is the second aspect of the map matching system and map matching method according to the present invention, wherein the route search order determination unit is further updated. The route search order is changed based on the reliability information.

  Further, a fourth aspect of the map matching system and map matching method according to the present invention is the reliability information calculation unit according to any one of the first to third aspects of the map matching system and map matching method according to the present invention. Further calculates the reliability information for each of the neighboring links, and the route search unit further performs the route search by evaluating each of the neighboring links based on the reliability information. It is characterized by doing.

  Further, a fifth aspect of the map matching system and map matching method according to the present invention is the fourth aspect of the map matching system and map matching method according to the present invention, in which the route search unit further includes the reliability information. Based on this, each of the neighboring links is weighted to determine the order of the evaluation, and each of the neighboring links is evaluated in the determined order of evaluation.

  Further, a sixth aspect of the map matching system and map matching method according to the present invention is the fourth or fifth aspect of the map matching system and map matching method according to the present invention. Each of the neighboring links is evaluated in association with the neighboring link evaluated in the section.

  Further, a seventh aspect of the map matching system and map matching method according to the present invention is the map matching system and map matching method according to any one of the first to seventh aspects, wherein the reliability information is: It includes an evaluation value for at least one of the distance of the neighboring link, the presence / absence of a parallel road with respect to the neighboring link, the position error of the neighboring link, the azimuth error of the neighboring link, and the number of the neighboring links.

  An eighth aspect of the map matching system and the map matching method according to the present invention is a method executed by a computer device for estimating a moving path of a probe car, the computer device corresponding to the probe car. Comprising a data storage unit storing probe data having a plurality of WP position information and digital road map data, and setting a plurality of WP sections of the probe car based on the probe data and the digital road map data; Setting one or more neighboring links connecting the WP sections based on the probe data and the digital road map data; calculating reliability information for each of the plurality of WP sections; Based on reliability information, previous A step of determining a route search order by weighting each of a plurality of WP intervals, and connecting each of the plurality of WP intervals with the one or more neighboring links in the determined route search order. And a step of executing a route search.

  Further, a ninth aspect of the map matching system and map matching method according to the present invention is the eighth aspect of the map matching system and map matching method according to the present invention, on the basis of the result of executing the route search. The method further comprises a step of updating reliability information, wherein the route search is further performed based on the updated reliability information.

  Further, a tenth aspect of the map matching system and map matching method according to the present invention is the ninth aspect of the map matching system and map matching method according to the present invention based on the updated reliability information. The method further includes a step of changing a route search order.

  An eleventh aspect of the map matching system and map matching method according to the present invention is the map matching system and map matching method according to any of the eighth to tenth aspects of the present invention, wherein the reliability information is further Calculated for each of the neighboring links, and the route search is further performed by evaluating each of the neighboring links based on the reliability information.

  Further, a twelfth aspect of the map matching system and map matching method according to the present invention is the eleventh aspect of the map matching system and map matching method according to the present invention based on the reliability information. The method further comprises the step of weighting each to determine the order of the evaluation, wherein each of the neighboring links is evaluated in the determined order of evaluation.

  Further, a thirteenth aspect of the map matching system and map matching method according to the present invention is the eleventh or twelfth aspect of the map matching system and map matching method according to the present invention, wherein each of the neighboring links is adjacent. It is characterized by being evaluated in association with a neighboring link evaluated in the WP section.

  Further, a fourteenth aspect of the map matching system and map matching method according to the present invention is any one of the eighth to thirteenth aspects of the map matching system and map matching method according to the present invention. It includes an evaluation value for at least one of the distance of the neighboring link, the presence / absence of a parallel road with respect to the neighboring link, the position error of the neighboring link, the azimuth error of the neighboring link, and the number of the neighboring links.

  A fifteenth aspect of the map matching system and map matching method according to the present invention causes a computer to execute the method according to any of the eighth to fourteenth aspects of the map matching system and map matching method according to the present invention. Is a program characterized by

  According to a sixteenth aspect of the map matching system and map matching method of the present invention, the program according to the fifteenth aspect of the map matching system and map matching method of the present invention is recorded. It is.

  According to the map matching system and method of the present invention, even when there are a plurality of neighboring links, the travel route of the probe car is appropriately determined without executing the route link specifying process in the upstream WP section again. Can be estimated.

It is a figure which shows the example of the conventional map matching method. It is a figure which shows the example of the case where an appropriate path | route cannot be specified in the conventional map matching method. It is a figure which shows another example of the case where an appropriate path | route cannot be specified in the conventional map matching method. It is a figure which shows another example of the case where an appropriate path | route cannot be specified in the conventional map matching method. It is a figure which shows the example of NL1 and NL2 which run in parallel. It is a block diagram which shows the example of a structure of the whole map matching system which concerns on one Embodiment of this invention. It is a block diagram which shows the example of a function structure of the map matching server and vehicle equipment which concern on one Embodiment of this invention. It is a block diagram which shows the example of a detailed functional structure of the map matching part which concerns on one Embodiment of this invention. It is a figure which shows the example of the format of the probe car data which concerns on one Embodiment of this invention. It is a figure which shows the example of the outline | summary of the map matching method which concerns on one Embodiment of this invention. It is a flowchart which shows the example of the detail of the map matching method which concerns on one Embodiment of this invention. It is a figure which shows the example of the format of the reliability information which concerns on one Embodiment of this invention. It is a flowchart which shows the example of the route search process which concerns on one Embodiment of this invention.

  Hereinafter, embodiments of a map matching system according to the present invention will be described with reference to the accompanying drawings.

<Definition of terms>
The term “candidate link” means all routes existing on the digital road map data that connect adjacent WPs. The term “neighboring link” means a route existing in a predetermined range of WP among candidate links. The term “route link” means a route determined as a route connecting adjacent WPs in the map matching process. Originally, a link means a road section connecting nodes, and therefore there may be a plurality of links on one route connecting adjacent WPs (when a plurality of nodes exist on one route). However, hereinafter, in the present specification, for the sake of easy understanding, one route connecting adjacent WPs is referred to as a “link”.

<System configuration>
FIG. 6 is a block diagram showing the overall configuration of the map matching system according to one embodiment of the present invention. The map matching system according to the present invention includes a map matching server 10 and an in-vehicle device 20. The map matching server 10 and the vehicle-mounted device 20 communicate via the network 30 using a radio communication technology such as DSRC (Dedicated Short Range Communications). The map matching server 10 may be implemented by a single computing device or multiple computing devices.

  The map matching server 10 is a computing device that implements the main functions of the map matching system according to the present invention. The map matching server 10 receives probe data from the in-vehicle device 20, and executes map matching processing using the probe data.

  The map matching server 10 includes a communication unit 11, a control unit 12, a main storage unit 13, and an auxiliary storage unit 14, and these elements are coupled to each other via a system bus.

  The communication unit 11 transmits and receives data to and from other devices such as the in-vehicle device 20 via the network 30.

  The control unit 12 is also called a central processing unit (CPU), and controls various components such as a map matching unit and a probe data utilization unit, which will be described later, data calculation, and various programs stored in the auxiliary storage unit 14. Read to the storage unit 13 and execute.

  The main storage unit 13 is also referred to as a main memory, and stores probe data transmitted from the vehicle-mounted device 20, computer-executable instructions, data after arithmetic processing by the instructions, and the like.

  The auxiliary storage unit 14 is a storage device represented by a hard disk (HDD) or the like, and has a data storage unit (database table) 14a that stores digital road map data and the like. Further, the auxiliary storage unit 14 stores a program (not shown) for causing the control unit 12 to execute various processes according to the present embodiment.

  The in-vehicle device 20 is a wireless device that is installed in a probe car and transmits probe data to the map matching server 10. There are a plurality of in-vehicle devices 20, and probe data is transmitted from each of the plurality of in-vehicle devices 20. The probe data is transmitted at a predetermined interval at a predetermined distance and / or time. The probe data is also transmitted when predetermined attribute information changes (for example, in the case of a taxi, when a state such as an empty / full state changes).

  Next, the functional configuration of the map matching server and the vehicle-mounted device will be described in detail with reference to the block diagram of FIG.

  The map matching server 10 includes a map matching unit 15 and a probe data utilization unit 16. In the present embodiment, the map matching server 10 includes the map matching unit 15 and the probe data utilization unit 16, but one of the map matching unit 15 and the probe data utilization unit 16 is included in a device different from the map matching server 10. May be configured.

  As will be described later, the map matching unit 15 executes map matching processing using the probe data received from the in-vehicle device 20, and generates map matching result data. The generated map matching result data is accumulated in the data storage unit 14a. A detailed functional configuration of the map matching unit 15 will be described later.

  The probe data utilization unit 16 receives the map matching result generated based on the probe data from the map matching unit 15, and generates various traffic information using the map matching result data stored in the data storage unit 14a. To do.

  The in-vehicle device 20 includes a positioning unit 21, a generation unit 22, a transmission unit 23, a vehicle speed sensor 24, a GPS receiver 25, a gyro sensor 26, and an attribute information sensor 27 such as a taxi meter.

  The positioning unit 21 controls operations of the vehicle speed sensor 24, the GPS receiver 25, and the gyro sensor 26, and generates information that is a source for generating probe data. The vehicle speed sensor 24 is a sensor that detects the traveling speed of the probe car, and can determine an accurate vehicle speed from the speed pulse. The GPS receiver 25 receives the data (latitude, longitude, height, and time (time of the atomic clock mounted on the GPS satellite) information) transmitted from the GPS satellite with an antenna, and the position, approximate traveling direction, Calculate the approximate speed. The gyro sensor 26 detects the acceleration, direction, and the like of the probe car in the front-rear and left-right directions. The positioning unit 21 calculates an accurate position (latitude / longitude / altitude), traveling direction, and measurement time of the probe car based on the detected information. Note that positioning may be executed only by the GPS receiver 25 or by the GPS receiver 25 and any one of the vehicle speed sensor 24 and the gyro sensor 26.

  The generation unit 22 generates probe data based on the positioning information generated by the positioning unit 21 and the information collected from the attribute information sensor 27 (when the probe car is a specific probe car). The probe data includes a probe car identification ID and WP information. The WP information includes at least the latitude, longitude, and time of the positioning point, and in some cases includes traveling direction information and attribute information. The attribute information indicates various states of the probe car. For example, when the probe car is a taxi, information such as an empty car, an actual car, or forwarding is included.

  The transmission unit 23 transmits the probe data generated by the generation unit 22 to the map matching server 10. The timing at which the probe data is transmitted from the transmission unit 23 is defined by a predetermined distance and / or time unit. For example, in the former example, there are timings such as a pitch of 300 m (probe data transmission every 300 m of travel distance), a pitch of 500 m and 800 m, and in the latter example, a pitch of 10 seconds (probe every 10 seconds of travel time) Data transmission), 30-second pitch, 120-second pitch, and the like. This interval changes variously depending on the radio wave reception environment, communication congestion status, and changes in vehicle operation status (empty / actual).

  Next, a detailed functional configuration of the map matching unit 15 will be described with reference to the block diagram of FIG. The map matching unit 15 includes a route search order determination unit 151, a route search unit 152, a link end determination unit 153, a reliability information calculation unit 154, a digital road map data table 155, and a probe data table 156.

  The route search order determination unit 151 uses the reliability information created by the reliability information calculation unit 154 for a section between WPs (hereinafter referred to as WP sections) indicated by a plurality of WP information included in the probe data received from the in-vehicle device 20. Based on the above, weighting is performed according to a predetermined criterion and prioritized. The route search is executed in the order of the prioritized WP sections.

  Based on the probe data read from the probe data table 156 and the digital road map data read from the digital road map data table 155, the route search unit 152 is in the order of the WP sections prioritized by the route search order determination unit 151. , Route search for neighboring links connecting WP sections is executed. The route search unit 152 may search for the shortest link from neighboring links using, for example, a Dijkstra algorithm.

  When the route search by the route search unit 152 is successful, the link end determination unit 153 determines the start point and end point in the WP section for the successful route search. That is, the neighboring link is determined as the route link.

  The reliability information calculation unit 154 calculates the reliability information for the start and end points and / or the neighboring links in the WP section based on a predetermined standard from the position information of each WP. The route search order determination unit 151 prioritizes WP sections based on the reliability information calculated by the reliability information calculation unit 154. Details of the reliability information will be described later.

  The digital road map data table 155 is a database table that stores digital road map data. Digital road map data is a digital road map that expresses the topology and shape of the road network by nodes (intersections and other traffic nodes and attribute changes in the road network representation) and links (road sections between nodes). It is data. A unique number is assigned to each node and link, and corresponding position data (latitude, longitude) and a connection node number are also assigned.

  The probe data table 156 is a database table that stores probe data received by the communication unit 11 from the in-vehicle device 20. FIG. 7 is a diagram showing an example of a format of probe data stored in the probe data table 156. As shown in FIG. As shown in the probe data format of FIG. 9, the probe data includes a probe car identification ID 901, a positioning time 902, a latitude 903, a longitude 904, a front / rear / left / right acceleration 905, a probe car direction 906, a speed 907, and attribute information 908. However, it is not limited to these data items, and may include other types of data that can be measured by the in-vehicle device 20.

<Overview of WP Route Search Order Determination>
Next, the details of the map matching process executed by the map matching system according to the present invention will be described. Referring to FIG. 10, the WP of the WP executed by the route search order determination unit 151 of the map matching server 10 described above An outline of route search order determination will be described.

  As shown in FIG. 10, in the map matching process in the present embodiment, there are seven WP1 to WP7, and the route search from WP1 as the start point to WP7 as the end point is targeted. The start point nodes SP1-1 and SP1-2 existing within a predetermined range of WP1 and the end point nodes EP1-1 and EP1-2 existing within a predetermined range of WP2 are connected to neighboring links NL1-1, NL1-2, NL1-3 and NL1-4 can be connected to each other (SP1-1 → EP1-1 is NL1-1, SP1-1 → EP1-2 is NL1-2, SP1-2 → EP1-1 is NL1-3 , And SP1-2 → EP1-2 NL1-4).

  Further, the start point nodes SP2-1 and SP2-2 existing within a predetermined range of WP2 and the end point nodes EP2-1 and EP2-2 existing within a predetermined range of WP3 are connected to the neighboring links NL2-1 and NL2-. 2 can be tied together.

  Further, the start point node SP3 existing within the predetermined range of WP3 and the end point node EP4 existing within the predetermined range of WP4 can be connected by the neighboring link NL3 (the link connecting EP2-2 is the end point thereof) Are excluded because they are not within the predetermined range of WP3).

  Further, the start point node SP4 existing within the predetermined range of WP4 and the end point node EP5 existing within the predetermined range of WP5 can be connected by the neighboring link NL4.

  Further, the start point node SP5 existing within the predetermined range of WP5 and the end point node EP6 existing within the predetermined range of WP6 can be connected by the neighboring link NL5.

  Further, the start point nodes SP6-1 and SP6-2 existing within a predetermined range of WP6 and the end point nodes EP6-1 and EP6-2 existing within a predetermined range of WP7 are connected to neighboring links NL6-1 and NL6-. 2 can be tied together. The determination of the neighboring links in these WP sections has been described in the order of time series from WP1 to WP7. However, since each WP section is processed independently, the order is arbitrary and can be processed in parallel.

  In the conventional map matching method, the route search is executed in the order of time series from upstream to downstream, that is, in the order of WP section (WP section 1-2) between WP1 and WP2 to WP section 6-7. . In the WP section 1-2, there are neighboring links NL1-1, NL1-2, NL1-3, and NL1-4. That is, there are four neighboring links, and the neighboring links NL1-1 and NL1-2 are running in parallel. If the route search in the WP section 1-2 is started, it is impossible to determine whether any of the neighboring links NL1-1, NL1-2, NL1-3, and NL1-4 is appropriate as a route link.

  In the map matching method according to the present invention, the reliability information calculation unit 154 of the map matching unit 15 calculates the reliability information for each WP section as follows, and the route search order determination unit 151 calculates the reliability information. Based on this, prioritization of each WP section is executed.

  For example, the reliability information calculation unit 154 evaluates information for calculating the reliability of each WP section according to the items shown in Table 1 of each WP section. The method of each evaluation is as follows.

  For example, as shown in FIG. 10, it can be said that the distance of TR1 in the WP section 1-2 is short. Therefore, the section distance of the WP section 1-2 in Table 1 is “short”.

  Moreover, since WP1 in the WP section 1-2 is far away from the nearest point of the neighboring links NL1-3, it can be said that the position error is large. Therefore, the position error of the WP section 1-2 in Table 1 is “large”. When there are a plurality of neighboring links in the WP section, the position error is targeted only for the neighboring link farthest from the WP among the plurality of neighboring links (evaluated at the nearest point of the neighboring links).

  Also, since the deviation absolute value of the azimuth (section azimuth) of the straight line connecting WP1 and WP2 with respect to the neighboring link NL1-3 is large, it can be said that the azimuth error is large. Therefore, the azimuth error in the WP section 1-2 in Table 1 is “large”. When there are a plurality of neighboring links in the WP section, the azimuth error is targeted only for the neighboring links having the largest deviation absolute value with respect to the section azimuth among the plurality of neighboring links.

  Further, since there are four neighboring links in the WP section 1-2, the number of neighboring links in the WP section 1-2 in Table 1 is “4”, and the neighboring links NL1-1 and NL1-2 run in parallel. Therefore, the presence / absence of the parallel road is “Yes”.

  In this way, the reliability information calculation unit 154 generates reliability information for each WP section. In this overview, reliability information is simply calculated, but a specific method for calculating reliability information will be described later. When the reliability information is calculated, the route search order determination unit 151 performs prioritization (weighting) of each WP section based on the weight values shown in Table 2. The calculation of the reliability information and the weighting process are also independent processes in each WP section, and can be performed in parallel in an arbitrary order as in the above-described determination of neighboring links.

  According to the weight values shown in Table 2, each WP section is weighted in the reverse order of reliability. For weighting, for example, when the position error is “large”, the reliability is low, so the weight value 7 is added. When the position error is “small”, the reliability is high. Do the same. Since the reliability is low when the section distance is “long”, the weight value 3 is added, and when the section distance is “short”, the reliability is high, so no addition is made. Since the reliability is low when the presence / absence of the parallel road is “present”, the weight value 7 is added, and when it is “none”, the reliability is high, and therefore no addition is performed. As the number of neighboring links increases, the uncertainty of the WP section increases. Therefore, the number of neighboring links is multiplied by a weight value. Table 3 shows the weight values calculated for each WP section according to the above method.

  From the calculated weight total values shown in Table 3, the route search order of each WP section can be determined. That is, the route search order is the order from the WP section having a high reliability and the small total weight value, and the WP section 3-4, the WP section 5-6, the WP section 4-5, the WP section 6-7, and the WP section 2 -3 and WP section 1-2. Since the neighboring link is only NL3 in the WP section 3-4, the neighboring link is only NL5 in the WP section 5-6, and the neighboring link is only NL4 in the WP section 4-5, the neighboring links NL3, NL5, and NL4 Are determined as route links.

  In WP section 6-7, there are neighboring links NL6-1 and NL6-2, but when one of them cannot be connected to NL5, the neighboring link that can be connected may be determined as the route link. it can. In WP section 2-3, there are neighboring links NL2-1 and NL2-2, but since NL2-2 can be connected to NL3, NL2-2 can be determined as a route link. .

  In the WP section 1-2, there are four neighboring links NL1-1, NL1-2, NL1-3, and NL1-4. At least NL1-1, NL1-3, and NL2-2 are connected. If NL1-2 or NL1-4 cannot connect to NL2-2 (for example, NL2-2 is a general road and NL1-4 is a highway, NL1- Only 2 can be connected to NL2-2), and a neighboring link that can be connected can be determined as a route link.

  As described above, the outline of the map matching method according to the present invention has been described. As described above, in the plurality of WP sections, the route search is performed in the order of priority based on the calculated reliability information, so that the WP Even when there are a plurality of neighboring links in the section, it is possible to determine a neighboring link suitable as a route link.

<Map matching process>
Next, details of the map matching processing according to the present invention will be described with reference to the flowchart of FIG.

  First, the reliability information calculation unit 154 of the map matching server 10 refers to the probe data table 156 to extract WP information that is a target of the route search (in this embodiment, WP1 to WP7 are extracted). Then, with reference to the digital road map data table 155 in the order of the WP section 1-2 to the WP section 6-7, the start point SP and the end point EP existing within a predetermined range of each WP are set, and SP and EP A neighboring link NL connecting the two is extracted (step S1001). In this case, the neighboring link NL includes one or a plurality of NLs in one WP section.

  Next, the reliability information calculation unit 154 calculates reliability information for the start point SP, the end point EP, and the neighboring link NL in each WP section (step S1002). Here, the reliability information includes, for example, items shown in the data format of FIG. 12, but is not limited to such items.

  FIG. 12 shows WP candidate information 1201 and WP section information 1202 as reliability information. The WP candidate information 1201 includes WP information 1203, route search result information 1204, neighboring link confirmation information 1205, and neighboring link information 1206. The neighboring link information 1206 includes the number of neighboring links 1207, the link ID 1208 corresponding to each of the neighboring links existing in the target WP section, the neighboring link distance 1209, the position error 1210, the heading error 1211, the parallel path candidate presence / absence 1212, and the neighboring links. Priority level 1213 is included.

  In the WP candidate information 1201, the value of the WP information stored in the probe data table 156 is set. The number of neighboring links 1207 is set to the number of neighboring links NL in the target WP section extracted in step S1001. As the link ID 1208, an arbitrary ID is set for the neighboring link NL extracted in step S1001 (for example, a serial number). As the neighborhood link distance 1209, the distance information of the neighborhood link NL read from the digital road map data table 155 is set.

  The position error 1210 is based on the latitude and longitude indicated by the WP information, the latitude and longitude of the neighboring link NL read from the digital road map data table 155, and the like between the target WP and the nearest point of the neighboring link NL. It is set by calculating the distance. The azimuth error 1211 is set by calculating the azimuth difference (absolute angle absolute value) between the section azimuth and the nearby link NL in the target WP section. The position error 1210 and the azimuth error 1211 may be set by calculating a distance / azimuth difference between the target WP and the start point and / or end point of the neighboring link NL.

  The parallel road candidate presence / absence 1212 is determined by determining whether or not there is an NL running in parallel with the target NL based on the route information used by each neighboring link NL read from the digital road map data table 155. Is set. Since the route search result information 1204, the neighborhood link confirmation information 1205, and the neighborhood link priority 1213 are not set in this step, details will be described later.

  The WP section information 1202 includes an upstream WP pointer address 1214, a downstream WP pointer address 1215, a WP section straight line distance 1216, route search execution presence / absence 1217, and route information 1218.

  In the upstream WP pointer address 1214 and the downstream WP pointer address 1215, the upstream and downstream WP pointer addresses of the target WP are set. For example, the upstream WP pointer address 1214 and the downstream WP pointer address 1215 of WP2 are set with the pointer address of WP1 and the pointer address of WP3, respectively. The WP section straight line distance 1216 is set by calculating a straight line distance connecting two WPs in the corresponding WP section based on latitude, longitude, and the like. Since the route search presence / absence 1217 and the route information 1218 are not set in this step, details will be described later.

  Returning to the flowchart of FIG. 11, in step S1003, the route search order determination unit 151 determines the order in which the route search of each WP section is executed based on the reliability information calculated in step S1002. In determining the execution order of the route search, each item is weighted from the reliability information calculated in step S1002 by the method shown in the penalty value calculation table 1 in Table 4 below.

For example, the evaluation item “neighboring link distance” is evaluated from the value set in the neighboring link distance 1209 included in the reliability information created in step S1002. Specifically, the value of the neighborhood link is set in the variable L, Lmin is a predetermined lower limit threshold for the neighborhood link distance, and Lmax is a prescribed upper limit threshold for the neighborhood link distance. If L is greater than or equal to Lmax, a value of 100 is added as a penalty, and the added value is further multiplied by a weight value of 3. If L is greater than Lmin and less than Lmax,
100 * ((L-Lmin) / (Lmax-Lmin)) ^ Lpow Equation 1
The value calculated by is multiplied by the weight value 3. Evaluation of the neighborhood link distance is executed for each neighborhood link existing in the target WP section.

  The evaluation item “presence / absence of parallel road” is evaluated from the value set in the parallel road candidate presence / absence 1212 included in the reliability information created in step S1002. When the value set in the parallel path candidate presence / absence 1212 is “None”, the penalty value is not added, and when it is “Yes”, a value of 100 is added as a penalty, and the weight value 7 is added to the added value. Is multiplied. The evaluation for the presence or absence of the parallel road is performed for each of the neighboring links existing in the target WP section.

The evaluation item “position error” is evaluated from the value set in the position error 1210 included in the reliability information created in step S1002. Specifically, the variable D is set to a value set in the position error 1210, Dmin is a predetermined lower limit threshold for the position error, and Dmax is a predetermined upper limit threshold for the position error. If D is less than or equal to Dmin, the penalty value is not added. If it is greater than or equal to Dmax, a value of 100 is added as a penalty, and the added value is multiplied by a weight value of 7. If D is greater than Dmin and less than Dmax,
100 * ((D−Dmin) / (Dmax−Dmin)) ^ Dpow Equation 2
The value calculated by is multiplied by the weight value 7. The evaluation for the position error is performed for each of the neighboring links existing in the target WP section.

The evaluation item “azimuth error” is evaluated from the value set in the azimuth error 1211 included in the reliability information created in step S1002. Specifically, the value set in the azimuth error 1211 is set in the variable A, Amin is a predetermined lower limit threshold for the azimuth error, and Amax is a predetermined upper limit threshold for the azimuth error. When A is less than or equal to Amin, no penalty value is added, and when it is greater than or equal to Amax, a value of 100 is added as a penalty, and the added value is multiplied by a weight value of 5. If A is greater than Amin and less than Amax,
100 * ((A-Amin) / (Amax-Amin)) ^ Apow Formula 3
The value calculated by is multiplied by a weight value of 5. The evaluation for the azimuth error is performed for each of the neighboring links existing in the target WP section.

The evaluation item “number of neighboring links” is evaluated from the value set in the number of neighboring links 1207 included in the reliability information created in step S1002. Specifically, the variable N is set to the value set for the number of neighboring links 1207, Nmin is a predetermined lower threshold for the number of neighboring links, and Nmax is a predetermined upper threshold for the number of neighboring links. If N is less than or equal to Nmin, no penalty value is added. If N is greater than or equal to Nmax, a value of 100 is added as a penalty, and the added value is multiplied by a weight value of 10. If N is greater than Nmin and less than Nmax,
100 * ((N−Nmin) / (Nmax−Nmin)) ^ Npow Equation 4
The value calculated by is multiplied by a weight value of 10. The evaluation for the number of neighboring links is executed for the target WP section.

  By the method described above, each evaluation item is evaluated (weighted) for each WP section or each neighboring link in each WP section. For the items to be evaluated for each of the neighboring links, the highest value is adopted from the penalty values calculated for the plurality of neighboring links. For example, if there are neighboring links NL1 and NL2 in the WP section 1-2 and the penalty values of the position error calculated for NL1 and NL2 are 66 and 81, respectively, the position error of the WP section 1-2 The penalty value is 81.

  In addition, when calculating the reliability information, if the position error 1210 and the azimuth error 1211 are calculated for each of the start point and end point of the target neighboring link, the penalty value of the start point or end point of the same neighboring link Adopt the higher one.

  Finally, the penalty values calculated for each evaluation item are aggregated in units of WP sections, and the route search execution order is determined in the order from the lowest total value. In the present embodiment, the order is WP section 3-4, WP section 5-6, WP section 4-5, WP section 6-7, WP section 2-3, and WP section 1-2.

  Instead of the method described above, the average value of penalty values calculated for the start / end points of a plurality of neighboring links / neighboring links may be simply adopted, or calculated for a plurality of neighboring links. The average value of the calculated penalty values may be adopted only when all of the penalty values that are set are within a certain range.

  Next, in step S1004, a route search is executed for each WP section in the order determined in step S1003. Hereinafter, the processing from step S1004 to step S1008 is repeatedly executed in the order described above for each of all target WP sections. Details of the route search processing in step S11004 will be described with reference to FIG.

  First, in step S1301, the route search unit 152 determines the order in which subsequent route evaluation is performed for each neighboring link NL in the target WP section. The order is determined based on the penalty values calculated for the items “neighboring link distance”, “parallel path presence / absence”, “position error”, and “azimuth error” weighted for each neighboring link in step S1003 of FIG. The order is determined. That is, when there are a plurality of neighboring links in the target WP section, the order of the neighboring links is determined in the order of small penalty values based on factors such as no parallel road and small positional error. In this step, if a route link has already been established in an adjacent WP section, a neighboring link that can be connected to the route link may be given priority (from the digital road map data table 155). , By referring to the connection node number). Hereinafter, the processing in steps S1302 to S1305 is repeatedly executed in the order described above for each of the target neighboring links.

  Next, the route search unit 152 performs route evaluation of each neighboring link in the order determined in step S1301 (step S1302). In the route evaluation, in addition to the route search result in the adjacent WP section (for example, whether the link is a neighboring link that can be established in the adjacent WP section), the neighboring link distance, the position error, etc., the number of right / left turns and the U Items such as the presence or absence of a turn may be evaluated by adding weighted values (for example, a penalty value is added). In the case of a neighboring link that cannot be connected to a route link determined in the adjacent WP section, the maximum penalty value may be added.

  Next, the route search unit 152 determines whether the neighboring links evaluated in step S1302 are good neighboring links, that is, whether the calculated weighted total value exceeds a predetermined threshold (step S1303). . If the target neighboring link is good, the process proceeds to the subsequent step (Yes in Step S1303), and if not (No in Step S1303), the process proceeds to Step S1305.

  In step S1304, the route search unit 152 adds the neighboring link determined to be good in step S1303 to the good neighboring link list. The good neighborhood link list is a set list of neighborhood links to be determined as appropriate neighborhood links in the WP section. From this good neighborhood link list, an appropriate neighborhood link is selected in subsequent processing.

  In step S1305, the route search unit 152 determines whether route evaluation of all neighboring links in the target WP section has been completed. If the route evaluation of all neighboring links has been completed (Yes in step S1305), the process proceeds to the subsequent process. If not (No in step S1305), the process returns to step S1302.

  Next, the route search unit 152 determines whether or not there is at least one good neighborhood link in the good neighborhood link list to which the good neighborhood link is added in step S1304 (step S1306). If one or more good neighbor links exist (Yes in step S1306), the process proceeds to the subsequent process. If not (No in step S1306), the process proceeds to step S1308.

  In step S1307, the route search unit 152 selects a neighboring link with the highest evaluation value (best neighboring link) from the good neighboring link list to which the good neighboring link is added in step S1304. The neighboring link with the highest evaluation value is, for example, the neighboring link with the lowest total penalty value calculated in the route evaluation in step S1302.

  In step S1308, it is determined that route search for the target WP section has failed, and the process proceeds to step S1309. After the process of step S1309, the process of FIG. 13 will be complete | finished as a route search failure.

  In step S1309, the reliability information calculation unit 154 updates the reliability information calculated in step S1002 of FIG. 11 (step S1307). Specifically, the items of route search result information 1204 of the WP candidate information 1201, the neighborhood link confirmation information 1205, and the neighborhood link priority order 1213 that have not been set in step 1002 are set.

  In the route search result information 1204, “success” is set when it is determined in step S 1305 that one or more good neighbor links exist, and “failure” is set otherwise.

  The neighborhood link confirmation information 1205 is set with the identification ID of the best neighborhood link selected in step S1307 when “success” is set in the route search result information 1204.

  In the neighboring link priority order 1213, the order of the order from the neighboring link having a high evaluation value is set for each neighboring link evaluated in step S1302.

  Next, returning to the flowchart of FIG. 11, in step S1105, it is determined whether or not the route search process in step S1104 is successful. This determination is the same as the determination in step 1206 of FIG. If the route search is successful (Yes in step S1105), the process proceeds to the subsequent process. If not (No in step S1105), the process proceeds to step S1107.

  In step S1106, the link end determination unit 153 determines the neighboring link selected as the best neighboring link list in step S1307 in FIG. 13 as the route link in the target WP section.

  Next, the reliability information calculation unit 154 updates the reliability information calculated in step S1102 (step S1307). Specifically, the items of the route search execution presence / absence 1217 and the route information 1218 of the WP section information 1202, which have not been set in step 1002, are set.

  In the route search execution presence / absence 1217, a value indicating the determination result in step S1105 is set, for example, “success” or “failure”.

  In the route information 1218, the identification ID of the route link determined in step S1307 is set.

  Next, the route search order determination unit 151 determines the route for the remaining WP sections, that is, the WP sections excluding the WP sections to be processed in steps S1104 to S1107, for the route search execution order of the WP sections determined in step S1103. Change the search execution order. Here, the reason why the route search execution order is changed is that the route link in the preceding WP section is determined in the processing of steps S1104 to S1107, and the determination result is reflected in the route search execution order. In changing the route search execution order, each item is weighted from the reliability information updated in step S1107 by the method shown in the penalty value calculation table 2 in Table 5 below.

  Since the penalty value calculation in Table 5 substantially overlaps with the penalty calculation described in Table 4, the description of the overlapping portion is omitted. When the evaluation item “route search result” is a WP section adjacent to the WP section determined to have failed in the route search in the determination of step S1105 (determined by referring to the path search execution presence / absence 1217 in the reliability information), the penalty As a result, a value of 100 is added, and the added value is multiplied by a weight value of 10.

  In addition, the evaluation items “presence / absence of parallel road”, “position error”, “direction error”, and “neighboring link” are all WP sections adjacent to the WP section having the route link determined in step S1106 (reliability). (Determined by referring to the information route information 1218), the penalty value is not added.

  In step S1109, the route search order determination unit 151 determines whether route search for all WP sections has been completed. If the route search for all WP sections has been completed (Yes in step S1109), the process ends. If not (No in step S1109), the process returns to step S1104.

  As described above, the map matching system according to the present invention has been described. However, the present invention is not limited to the above embodiment, and various modifications can be made without departing from the spirit of the present invention.

Claims (16)

A map matching system for estimating the travel path of a probe car,
A data storage unit storing probe data having a plurality of WP position information for the probe car and digital road map data;
A WP section setting unit that sets a plurality of WP sections of the probe car based on the probe data and the digital road map data;
Based on the probe data and the digital road map data, a neighboring link setting unit that sets one or a plurality of neighboring links connecting the WP sections;
A reliability information calculation unit for calculating reliability information for each of the plurality of WP sections;
A route search order determination unit that determines a route search order by weighting each of the plurality of WP sections based on the reliability information;
A map matching system comprising: a route search unit that performs route search by connecting each of the plurality of WP sections with the one or more neighboring links in the determined route search order. . The reliability information calculation unit further updates the reliability information based on a result of the route search performed by the route search unit,
The map matching system according to claim 1, wherein the route search unit further performs the route search based on the updated reliability information.   The map matching system according to claim 2, wherein the route search order determination unit further changes the order of the route search based on the updated reliability information. The reliability information calculation unit further calculates the reliability information for each of the neighboring links,
The route search unit further performs the route search by evaluating each of the neighboring links based on the reliability information. Map matching system.   The route search unit further weights each of the neighboring links based on the reliability information, determines the evaluation order, and evaluates each of the neighboring links in the determined evaluation order. 5. The map matching system according to claim 4, wherein   6. The map matching system according to claim 4, wherein the route search unit evaluates each of the neighboring links in association with neighboring links evaluated in adjacent WP sections.   The reliability information includes an evaluation value for at least one of the distance of the neighboring link, the presence / absence of a parallel road with respect to the neighboring link, the position error of the neighboring link, the azimuth error of the neighboring link, and the number of the neighboring links. The map matching system according to any one of claims 1 to 6, wherein: A method executed by a computer device for estimating a travel route of a probe car, the computer device storing probe data having a plurality of WP position information for the probe car and digital road map data Part
Setting a plurality of WP sections of the probe car based on the probe data and the digital road map data;
Setting one or more neighboring links connecting the WP sections based on the probe data and the digital road map data;
Calculating reliability information for each of the plurality of WP sections;
Weighting each of the plurality of WP sections based on the reliability information to determine a route search order;
Performing a route search by connecting each of the plurality of WP sections with the one or more neighboring links in the determined route search order. Further comprising the step of updating the reliability information based on a result of performing the route search;
The method according to claim 8, wherein the route search is further performed based on the updated reliability information.   The method according to claim 9, further comprising changing the order of the route search based on the updated reliability information. The reliability information is further calculated for each of the neighboring links,
The method according to any one of claims 8 to 10, wherein the route search is further performed by evaluating each of the neighboring links based on the reliability information. Further comprising the step of weighting each of the neighboring links based on the reliability information to determine the order of the evaluation,
The method according to claim 11, wherein each of the neighboring links is evaluated in the determined order of evaluation.   The method according to claim 11 or 12, wherein each of the neighboring links is evaluated in association with a neighboring link evaluated in an adjacent WP section.   The reliability information includes an evaluation value for at least one of the distance of the neighboring link, the presence / absence of a parallel road with respect to the neighboring link, the position error of the neighboring link, the azimuth error of the neighboring link, and the number of the neighboring links. 14. A method according to any one of claims 8 to 13, characterized in that   A program that causes a computer to execute the method according to any one of claims 8 to 14.   A computer-readable storage medium in which the program according to claim 15 is recorded.