JP6282890B2 - Route search apparatus and route search method - Google Patents

Description

  The present invention relates to a route search apparatus.

  As a route search device for searching for a route from a current position to a destination, a car navigation system, a mobile phone, a portable game machine, a PND (Personal Navigation Device) and a PDA (Personal Digital Assistant) mounted on a car are known. .

  For example, as described in Patent Document 1, when a route connecting a current position of a vehicle and a destination is searched, a link as a road where another vehicle is currently located, or a current position in another vehicle 2. Description of the Related Art Traffic management devices that reduce traffic congestion by taking into account traffic conditions such as links that make up a route from a destination to a destination are known.

JP 2010-210284 A

  However, in the technique described in Patent Document 1, when a car that has traveled along the travel route from the current position searched for by route guidance to the departure place is congested, the next scheduled link is congested. In order to avoid traffic congestion at the next link, there is a case where the link proceeds to a link different from the link constituting the movement route. If a plurality of automobiles travels on a link different from the links constituting the travel route in this way, the traffic situation cannot be accurately predicted, and there is a possibility that the traffic jam of the automobile cannot be alleviated sufficiently. In addition, these problems are not limited to the route search apparatus, but are common to information processing apparatuses for grasping traffic conditions. In addition, in the route search device and the information processing device, in order for the user to accurately grasp the traffic situation, improvement in convenience and usability for the user has been desired.

  SUMMARY An advantage of some aspects of the invention is to solve at least a part of the problems described above, and the invention can be implemented as the following forms.

(1) According to an aspect of the present invention, there is provided a route search device that searches for a route connecting two nodes on a network. The route search device includes a data storage unit that stores network information that identifies a plurality of nodes on a network, a plurality of links, and a link cost set for each of the plurality of links; and at least one other An information acquisition unit for acquiring information for specifying a departure node and a destination node set in the device; a plurality of nodes connecting the departure node and the destination node set in the other device; Among the first movement paths, the accumulated value of the link costs of the first optimum path having the smallest accumulated value of the link costs of the links constituting the first movement path, and the above-mentioned of the first optimum path A cumulative value of the link cost of at least one first sub-optimal route having a cumulative value of the link cost equal to or less than a value obtained by adding a first allowable cost to the cumulative value of the link cost, and A cost adjusting unit that adjusts the link cost of the network information stored in the data storage unit; a point setting unit that sets a starting node and a destination node; and using the network information in which the link cost is adjusted A route search unit that searches for at least one second movement route that connects the departure node and the destination node set by the point setting unit. According to the route search device of this aspect, in addition to the case where another user passes the first sub-optimal route other than the first optimum route among the first movement routes set in other devices, Thus, the second movement route connecting the departure point and the destination is searched. Therefore, the user of the route search apparatus can arrive at the destination while avoiding the traffic jam that occurs on the network based on the links that other users pass.

(2) In the route search device according to the above aspect, the cost adjustment unit is configured to link based on a cumulative value of the link cost of the first optimal route and a cumulative value of the link cost of the first sub-optimal route. You may adjust the link cost of the said network information by adding the variable cost set for every to the link cost of the link which comprises the said 1st optimal path | route and the said 1st suboptimal path | route. According to the route search device of this aspect, the variable cost is determined based on the route cost of the first optimal route and the first sub-optimal route as well as the one first movement route set in another device. Is calculated. Therefore, the second travel route of the user of the route search device is searched after the user of the other device sees the degree of congestion of the next scheduled link and predicts the situation when the route is changed. Therefore, the user of the route search apparatus can arrive at the destination more quickly, and convenience for the user is improved.

(3) In the route search device according to the above aspect, the cost adjustment unit may obtain a value obtained by subtracting the cumulative value of the link cost of the first optimal route from the cumulative value of the link cost of the first sub-optimal route. You may set the said variable cost large, so that it is small. According to the route search device of this aspect, since the variable cost is calculated to be larger as the link estimated to be highly likely to be passed by the user of another device, it is based on the situation based on the actually estimated congestion degree. Thus, the second movement route of the user of the route search device can be searched.

(4) In the route search device according to the above aspect, the cost adjustment unit includes: a node at the departure point set in the other device; a first optimum node that is a node included in the first optimum route; , At least other than the first minimum cost halfway route, and the first minimum cost halfway route where the cumulative value of the link costs constituting the first halfway route is the smallest. One first non-minimum cost midway path is identified; for each of the first midway paths, set to the first non-minimum cost midway path, the first optimal node, and the other device A route composed of a route connecting to the destination node that is overlapped with the first optimum route may be set as the first sub-optimal route. According to the route search device of this aspect, if only the information specifying the starting point and the destination set in the other device is acquired, the first movement route can be estimated and less than that set in the other device. Even with the route information, the second movement route can be searched.

(5) In the route search device according to the above aspect, the route search unit includes a second optimum route that has a minimum cumulative value of the link cost that constitutes the first movement route, among the second movement routes, And searching for at least one second sub-optimal route having a cumulative value of the link cost equal to or less than a value obtained by adding a second allowable cost to the cumulative value of the link cost of the second optimal route. Good. According to the route search device of this aspect, a plurality of second travel routes are searched within a range equal to or less than the predetermined cumulative value of the link cost. Therefore, the user of the route search device can select a favorite from the plurality of second travel routes. The route can be selected, and convenience for the user is improved.

(6) In the route search device according to the above aspect, the route search unit includes: a node at the departure point set by the point setting unit; and a second optimum node that is a node included in the second optimum route. Of the second halfway paths to be connected, at least one other than the second minimum cost halfway path having a minimum cumulative value of the link costs constituting the second halfway path and the second minimum cost halfway path Identifying a second non-minimum cost midway route; for each of the second midway routes, the second non-minimum cost midway route, the second optimal node, and the purpose set by the point setting unit A route constituted by a route that overlaps the second optimum route in a route connecting to a ground node may be set as the second sub-optimum route. According to the route search device of this aspect, when searching for the second sub-optimal route, the route from the departure point to the destination is not searched one by one, but the second minimum cost midway route at the second optimum node. And the second non-minimum cost midway route, the second moving route can be searched quickly, and the processing load of the route searching device can be reduced.

(7) According to another aspect of the present invention, an information processing apparatus is provided. The information processing apparatus includes a data storage unit that stores network information for specifying a plurality of nodes on the network, a plurality of links, and a link cost set for each of the plurality of links; and at least one apparatus An information acquisition unit that acquires information for specifying a departure node and a destination node set in the above; a movement route that connects the departure node and the destination node is included in the movement route A cumulative value of the link cost of the optimum route having the smallest cumulative value of the link cost of the link, and a cumulative value of the link cost equal to or less than a value obtained by adding an allowable cost to the cumulative value of the link cost of the optimal route. The link cost of the network information stored in the data storage unit is adjusted based on the cumulative value of the link cost of one sub-optimal route. That a cost adjustment portion; comprises an adjusting information generator link cost generates an adjustment path information representing the network information has been adjusted, the. According to the information processing apparatus of this aspect, the optimal path and the sub-optimal path are searched for in the movement path based on information set in another apparatus, and the link cost is adjusted. Therefore, the adjusted link cost does not have a locally high value as compared with the prior art, and suppresses the occurrence of local congestion. Further, by generating the adjustment route information, the user can grasp the degree of congestion on the network at a glance and can travel along a route avoiding traffic jams, thereby improving convenience for the user.

(8) In the information processing apparatus according to the above aspect, the adjustment information generation unit generates the adjustment route information so as to distinguish between the link cost specified by the network information and the adjusted link cost. Also good. According to this form of the information processing apparatus, the user can visually recognize how much the link is crowded compared to the case where the user is not crowded, so the traffic situation can be easily recognized, and convenience for the user is improved. To do.

(9) In the information processing apparatus according to the above aspect, the cost adjustment unit may set a variation for each link based on the cumulative value of the link cost of the optimal route and the cumulative value of the link cost of the semi-optimal route. You may adjust the link cost of the said network information by adding cost to the link cost of the link which comprises the said optimal path | route and the said semi-optimal path | route. According to the information processing apparatus of this aspect, the variable cost is calculated based on the route cost of the optimum route and the sub-optimal route as well as one movement route set in at least one device. Therefore, the user who set the starting point and the destination looks at the congestion level of the next scheduled link and predicts the situation such as when the route is changed, and then adjusts considering the congestion level on the network. Since the route information is generated, the user of the information processing apparatus can quickly reach the destination by selecting a route that avoids the degree of congestion, and convenience for the user is improved.

(10) In the information processing apparatus of the above aspect, the cost adjustment unit decreases the variable cost as the value obtained by subtracting the cumulative value of the link cost of the optimal route from the cumulative value of the link cost of the semi-optimal route is smaller. You may set large. According to the information processing apparatus of this aspect, since the fluctuation cost is calculated to be larger for a link that is estimated to be likely to be passed by a user of at least one apparatus, the situation is more in line with the actually estimated congestion level. Since the adjustment route information is generated based on this, the user of the information processing apparatus can arrive at the destination more quickly by avoiding the degree of congestion, and the convenience for the user is further improved.

(11) In the information processing apparatus of the above aspect, the adjustment information generation unit distinguishes between a link cost specified by the network information and the variable cost, and specifies and represents a link to which the variable cost is added. As described above, the adjustment route information may be generated. According to the information processing apparatus of this aspect, since the user can visually recognize which link is subjected to what variable cost, the traffic situation can be recognized more easily, and convenience for the user is further improved.

(12) In the information processing apparatus of the above aspect, the cost adjustment unit configures the halfway route among halfway routes connecting the departure node and the optimum node that is a node included in the optimum route. One minimum cost intermediate path having a minimum cumulative link cost and a non-minimum cost intermediate path other than the minimum cost intermediate path; and for each of the intermediate paths, the non-minimum cost intermediate path A route composed of a route connecting the optimum node and the destination node that overlaps the optimum route may be set as the semi-optimum route. According to the information processing apparatus of this aspect, if only the information specifying the departure place and the destination set in at least one apparatus is acquired, the movement route can be estimated, and the degree of congestion on the network can be estimated with less route information. Can be estimated.

  The present invention can be realized in various modes. For example, a route search device, a route search method, an information processing device, an information terminal device, an information transmission device, an information transmission method, a portable terminal device, information processing The present invention can be realized in the form of a server, a route search server, a computer program for realizing these devices, methods, and systems. Further, these computer programs may be recorded on a computer-readable recording medium (for example, a flexible disk, a CD-ROM, a DVD-ROM, a magneto-optical disk, a memory card, a hard disk, etc.).

It is explanatory drawing which shows schematic structure of the route search system in embodiment of this invention. It is explanatory drawing which shows the flow of a route search process. It is explanatory drawing which shows the movement path | route which connects a departure place and the destination. It is explanatory drawing which shows the relationship between the variable cost in a link, and the various index values for calculating a variable cost. It is explanatory drawing which shows the flow of the production process of variable cost data. It is explanatory drawing which shows a part of network information including a departure place and a destination. It is explanatory drawing which shows an example of the movement path | route which connects the departure place set to the other user, and the destination. It is explanatory drawing which shows an example of the variable cost added to the object link contained in the movement path | route which connects a departure place and the destination. It is explanatory drawing which shows the movement path | route which connects the departure point set to the other user, and the destination. It is explanatory drawing which shows an example of the variable cost added to the object link contained in the movement path | route which connects a departure place and the destination. It is explanatory drawing which shows an example of the network information which shows the link cost to which the variable cost was added. It is explanatory drawing which shows the variable cost added to the object link contained in the movement path | route which connects a departure place and the destination. It is explanatory drawing which shows an example of the movement path | route which connects the departure place set to the other user, and the destination. It is explanatory drawing which shows an example of the variable cost added to the object link contained in the movement path | route which connects a departure place and the destination. It is explanatory drawing which shows the flow of the search process of a movement route group. It is explanatory drawing which shows the flow of a label provision process. It is explanatory drawing which shows the flow of a label provision process. It is explanatory drawing which shows the state by which the candidate label was provided to the node of a departure place. It is explanatory drawing which shows the state in which the new label was provided to the adjacent node of the departure place to which the label of the fixed label was provided. It is explanatory drawing which shows the state in which the new label was provided to the adjacent node of the node to which the label of the definite label was provided. It is explanatory drawing which shows the state in which the new label was provided to the adjacent node of the node to which the label of the definite label was provided. It is explanatory drawing which shows the state by which the new label was provided to the adjacent node of the destination based on the label of the fixed label provided to the destination. It is explanatory drawing which shows an example in the state where the candidate label provided to the node on a network was lost. It is explanatory drawing which shows the relationship between the path | route cost about each of the definite label and the losing label provided to the node on a network, and a last label. It is explanatory drawing which shows the relationship between the path | route cost about each of the definite label and the losing label provided to the node on a network, and a last label. It is explanatory drawing which shows an example of the optimal path | route which connects a departure place and the destination. It is explanatory drawing which shows the flow of a search process of a similar route group. It is explanatory drawing which shows an example of the searched similar path group. It is the schematic which shows an example of the estimated congestion degree of the link on the network in 2nd Embodiment. It is explanatory drawing which shows an example of the congestion degree estimated of the link on the network in a comparative example.

Next, embodiments of the present invention will be described in the following order.
A. First embodiment:
A-1. Configuration of route search system:
A-2. Route search process:
A-3. Creating variable cost data:
A-4. Travel route group search processing:
B. Second embodiment:
C. Variations:

A. First embodiment:
A-1. Configuration of route search system:
FIG. 1 is an explanatory diagram showing a schematic configuration of a route search system 10 according to an embodiment of the present invention. The route search system 10 of the present embodiment includes a server 100 and a mobile phone 200 as a mobile terminal device. Although only one mobile phone 200 is shown in FIG. 1, the route search system 10 includes various mobile phones 200 and mobile game machines, PND (Personal Navigation Device), PDA (Personal Digital Assistant), and the like. A mobile terminal device may be included.

  The mobile phone 200 includes a main control unit 210, a GPS unit 201, a display panel 202, an audio output unit 203, a wireless communication circuit 205, an operation unit 206, and a call control unit 220.

  The main control unit 210 controls each unit of the mobile phone 200. The main control unit 210 includes a CPU 211, a RAM 212, and a ROM 213. The CPU 211 functions to execute various processes to be described later by loading a program stored in the ROM 213 into the RAM 212 and executing the program.

  The GPS unit 201 receives a radio wave indicating the position of an artificial satellite from GPS (Global Positioning System / Global Positioning System). The main control unit 210 specifies the current position (latitude, longitude) of the mobile phone 200 using the position of the artificial satellite received by the GPS unit 201, and indicates the current position of the mobile phone 200 specified at regular intervals. Generate information.

  The display panel 202 includes a liquid crystal display and a drive circuit that drives the liquid crystal display. The display panel 202 is not limited to a liquid crystal display, and various display devices such as an organic EL display can be employed. The main control unit 210 controls the display panel 202 to display, for example, a map image, a recommended route, a current position, and the like. The audio output unit 203 includes a speaker for outputting audio, a drive circuit for driving the speaker, and the like.

  The wireless communication circuit 205 wirelessly performs data communication or voice communication with the base station BS. The main control unit 210 controls the wireless communication circuit 205 to communicate with the server 100 on the Internet INT via the base station BS (more specifically, via the transmission / reception antenna, the base station BS, and the exchange). To do.

  The operation unit 206 is an input device that includes a numeric keypad 206a, a cursor key 206b, a touch panel, and the like. The operation unit 206 receives a destination setting input by the user. The destination setting received by the operation unit 206 and the position information generated by the GPS unit 201 are transmitted to the server 100 via the Internet INT. The call control unit 220 performs incoming calls and calls for voice calls, conversion of voice signals and electric signals, and the like.

  The server 100 includes a communication unit 102 that performs communication with the mobile phone 200 via the Internet INT, a control unit 150, and an information storage unit 110. The information storage unit 110 is a storage device that stores information, and includes, for example, a hard disk device. The information storage unit 110 includes a map information database (DB) 114 and a traffic information database (DB) 115. The map information DB 114 stores network information that is link information and node information constituting a network on the map, and map image data as image data. The map information DB 114 stores, as link information, the time required for the user to pass the link as the link cost. The link cost of a link is set as the time (minutes) for passing through the link.

  The traffic information DB 115 stores route information including the departure point and the destination set in the mobile phone 200 transmitted from each of the plurality of mobile phones 200 received by the control unit 150 via the communication unit 102. The route information includes information for specifying the current position and destination as the departure point, and information on the movement route connecting the departure point and the destination. In addition, the route information includes information at a specific time in the future (for example, at the scheduled travel time) than the current time. Based on the network information of the map information DB 114 and the route information of the plurality of mobile phones 200, the traffic information DB 115 stores traffic information indicating how many users are on which link at what time. That is, by using the traffic information stored in the traffic information DB 115, the number of users existing on a specific link is specified, or the future position of the user is estimated based on the set travel route, The degree of congestion can be determined. The server 100 in the present embodiment corresponds to the route search device in the claims, and the information storage unit 110 corresponds to the data storage unit in the claims. The network information stored in the map information DB 114 corresponds to the network information in the claims.

  The control unit 150 includes a CPU, a RAM, and a ROM, and controls the communication unit 102 and the information storage unit 110. The control unit 150 includes a route search unit 120 and a cost adjustment unit 130. When the user sets the destination and the arrival time at the destination when the user sets the mobile phone 200, the route search unit 120 is set as the current position of the mobile phone 200 within a range in which the user can arrive at the destination by the arrival time. The travel route connecting the destination is searched. Details of the route search will be described later. The route search unit 120 corresponds to the route search unit and the point setting unit in the claims.

  As illustrated in FIG. 1, the route search unit 120 includes an optimal route search unit 123 and a similar route search unit 124. The optimum route searching unit 123 searches for the optimum route based on the network information stored in the map information DB 114, the link cost information stored in the cost adjusting unit 130 described later, and the received position information and destination information. To do. The optimum route is a route in which the total value of the link costs obtained by adding the link costs of the links constituting the moving route is the minimum. Hereinafter, the cumulative value of the link costs of the links constituting the route is also referred to as “route cost”.

  Based on the network information, the link cost information, and the route cost of the optimum route, the similar route search unit 124 selects a similar route that is a movement route that is equal to or less than the route cost obtained by adding the set allowable cost to the route cost of the optimum route. Explore. The allowable cost is a time obtained by subtracting the current time from the arrival time, or an arbitrary value set by a user operation. The route search unit 120 transmits route information indicating an optimum route and a similar route to the mobile phone 200 via the communication unit 102. Details of the search for the optimum route and the similar route will be described later. The travel route connecting the starting point and the destination searched by the route search unit 120 corresponds to the second travel route in the claims. The optimum route searched by the optimum route searching unit 123 corresponds to the second optimum route in the claims. The similar route searched by the similar route search unit 124 corresponds to the second sub-optimal route in the claims. The allowable cost set by the user's operation or the like corresponds to the second allowable cost in the claims.

  The cost adjustment unit 130 includes a variable cost calculation unit 135 and a link cost information database (DB) 136. The variable cost calculation unit 135 calculates each of the variable costs to be added to the link costs of some links specified by the map information DB 114 based on the traffic information specified by the traffic information DB 115. The link cost information DB 136 adjusts the link cost by adding the variable cost calculated by the variable cost calculation unit 135 to each link cost of the corresponding link, and based on the network information of the map information DB 114, the search network Generate information. Further, the link cost information DB 136 converts the generated search network information into traffic information data that can be easily recognized by the user and transmits the data to the mobile phone 200 via the Internet INT. The mobile phone 200 causes the user to recognize the transmitted search network information using the display panel 202 or the audio output unit 203. The cost adjustment unit 130 corresponds to a cost adjustment unit and an adjustment information generation unit in the claims. Details of the search network information for the user to recognize will be described later in the second embodiment.

A-2. Route search process:
FIG. 2 is an explanatory diagram showing a flow of route search processing. The route search process is a process of searching for a moving route connecting the set departure node and destination node using route information set in the mobile phones 200 of a plurality of other users. In the route search process, first, the route search unit 120 of the server 100 acquires information specifying the departure point and the destination set by the mobile phone 200 (step S10). In the present embodiment, the current position of the mobile phone 200 acquired by the GPS unit 201 is set as the departure point, and the destination is set by operating the operation unit 206 by the user.

  Next, the cost adjustment unit 130 of the server 100 selects a target link that is a target link to which the variable cost is added based on the set departure point and destination, and includes the target link in the travel route. Route information is acquired (step S12). In the present embodiment, the cost adjustment unit 130 sets a link included in a predetermined distance from the set destination as a target link, and acquires route information of other users including the target link in the travel route from the traffic information DB 115. To do.

  Next, the cost adjustment unit 130 uses the acquired other user's route information to create variable cost data that specifies the variable cost to be added to the link cost of the link specified by the network information (step S20). The variable cost data creation process will be described later. When the variable cost data is created, the route search unit 120 searches for a travel route group that is a travel route that is one or more routes, using the search network information created using the variable cost data ( Step S40). The search process for the movement route group will be described later.

A-3. Creating variable cost data:
The variable cost data is data that specifies a variable cost to be added to each link cost of the target link based on the movement route of another user. First, a method for calculating the variable cost will be described.

  FIG. 3 is an explanatory diagram showing a travel route connecting the departure point S1 and the destination GL. FIG. 3 shows three routes R11, R12, R13 connecting the departure point S1 and the destination GL. Also, in FIG. 3, the link costs of the links constituting the three routes are indicated by numerical values surrounded by squares. Here, a method for calculating the variable cost applied to the link L01 connecting the departure point S1 and the node N11 constituting the route R11 and the route R12 will be described.

  FIG. 4 is an explanatory diagram showing the relationship between the variable cost in the link LN01 and various index values for calculating the variable cost. As shown in FIG. 4, the variable cost added to one link includes the link cost of the link stored in the network information, a passability index value indicating the possibility of passing the link, and the congestion level in the link. It is calculated by multiplying the number of people to represent. That is, the variable cost has a small value for a link that is unlikely for other users to pass, and has a large value when the link is congested. In this way, a route that avoids a congested link can be presented to the user during route search. In addition, links that are unlikely to be passed by other users are more likely to be searched for links that constitute a travel route compared to links that are likely to be passed by other users. The passage possibility is calculated by ordering the square of the value obtained by subtracting the route cost difference of the route including the target link from the cost difference allowable value by the sum of the squares of the route cost difference. The route cost difference is a value obtained by subtracting the route cost of the route including the target link from the route cost of the optimum route.

  For example, in the example shown in FIG. 3, among the routes connecting the departure point S1 and the destination GL, the optimum route with the lowest route cost is the route R11 with a route cost of 15. Here, when the target link is set to the link LN01, the link LN01 is a link constituting the route R11 and the route R12. The route R12 is a similar route having a route cost of 16 connecting the departure point S1 and the destination GL. When one target link is included in two routes, the variable cost is calculated as included in the route with the smaller route cost. That is, the variable cost of the link LN01 that is the target link is calculated as the link that forms the route R11 of the optimum route. In this case, as shown in FIG. 4, the route cost difference is 0, which is a value obtained by subtracting 15 of the route cost of the same route R11 as the optimum route from 15 of the route cost of the route R11. The square of the route cost difference is also 0.

  The sum of the squares of the path cost differences is the sum of the squares of integers that are less than or equal to the set cost difference tolerance. Specifically, in the example shown in FIGS. 3 and 4, the cost difference allowable value is set to 3. Therefore, the square of the value obtained by subtracting 0 of the path cost difference from the cost difference allowable value of 3 is 9 of the square of 3. Next, when the cost difference allowable value is 3, the integer below the cost difference allowable value can take four numbers of 0, 1, 2, and 3. Therefore, the sum of the squares of the path cost difference is 14 obtained by adding 0 of the square of 0, 1 of the square of 1, 2 of the square of 2, and 9 of the square of 3. Therefore, the passage possibility of the link LN01 is 0.64 (64 percent (%)) obtained by dividing 9 by 14. Since the route cost difference is set to be equal to or less than the cost difference allowable value, the variable cost is calculated using only links included in routes having a route cost difference of 3 or less as target links. In the example illustrated in FIG. 3, the route cost of the route R12 and the route R13 that are similar routes is 16, and the route cost difference is 1 with respect to 15 of the route cost of the route R11 of the optimum route. Therefore, the link included in the route R12 and the route R13 of the similar route is calculated as the target link, and the variable cost is calculated.

  Next, a method for calculating the number of people coefficient will be described. The number of people coefficient is a value obtained by dividing the number of people who may pass the target link based on the acquired route information of other users by a preset index value of the reference congestion degree. In the present embodiment, the number of persons who may pass the target link is set as one, and the reference congestion level is set as 20. Therefore, the number of people coefficient in the link LN01 of the target link is 0.05 obtained by dividing 1 by 20. As shown in FIG. 3, since the link cost of the link LN01 is 5, the variable cost of the link LN01 is multiplied by the link cost of 5, the passability of 0.64, and the number of people coefficient of 0.05. 0.16. As described above, each variable cost of the target link is calculated.

  FIG. 5 is an explanatory diagram showing the flow of variable cost data creation processing. In the process of creating the variable cost data, first, the variable cost calculation unit 135 of the cost adjustment unit 130 sets the reference congestion level and the allowable traffic value (step S21). The traffic allowance is a threshold for determining how much congestion is allowed for each link. In the present embodiment, the variable cost calculation unit 135 sets the reference congestion degree to 20, and sets the permissible traffic value of each link to a value twice the link cost specified by the network information. When the traffic allowance is set to twice the link cost, details will be described later. For example, in a link with a link cost of 5, the link cost after adding the variable cost is 10 which is twice the link cost of 5. If the value is larger than 10, the traffic allowance value is reset.

  When the reference congestion level and the allowable traffic value are set, the variable cost calculation unit 135 sets a cost difference allowable value for each route information of one other user (step S23). In the initial stage of the variable cost data creation process, the variable cost calculation unit 135 sets the cost difference allowable value to a small value in order to grasp the traffic situation near the destination in more detail. In the present embodiment, the variable cost calculation unit 135 first sets the cost difference allowable value to 3. The optimum route in the route information of other users corresponds to the first optimum route in the claims, and the similar route in the route information of other users corresponds to the first sub-optimal route in the claims.

  When the cost difference allowable value is set, the variable cost calculation unit 135 uses the cost difference allowable value for the possibility of passage with respect to all links constituting the movement route of the other user included in the acquired route information. Is calculated (step S25). In the present embodiment, when the passability is calculated, the decimal part is rounded off. As shown in FIG. 3 and FIG. 4, when the passability is calculated in the same manner, the passability of a link constituting a similar route having a route cost difference of 1 is obtained by dividing 2 square 4 by 14 29%. The possibility of passage of a similar route having a route cost difference of 2 is 7%, and the possibility of passage of a similar route having a route cost difference of 3 is 0%.

  When the passability is calculated, the variable cost calculation unit 135 calculates the variable cost to be added to all the target links that constitute the movement route in which the route cost difference is equal to or less than the cost difference allowable value (step S27). FIG. 6 is an explanatory diagram showing a part of network information including a departure place and a destination. In FIG. 6, the starting points S1 and S2 that are the nodes of the respective other two users, the destination GL that is the node of the same destination of the two other users, and a black circle And a plurality of links connecting two nodes indicated by straight lines. Moreover, in FIG. 6, the link cost of each link specified by the network information before the variable cost is added is indicated by a number.

  FIG. 7 is an explanatory diagram illustrating an example of a travel route that connects the departure point S1 and the destination GL set by another user. In each figure using the same network described later in FIG. 7 and later, the link cost of each link is the same as that in FIG. FIG. 7 shows three routes R11, R12, and R13 connecting the departure point S1 and the destination GL as route information of other users. As shown in FIG. 7, the route R11 is a route that leaves the departure point S1, passes through the node N11 and the node N12, and arrives at the destination GL. The route R12 is a route that leaves the departure point S1, passes through the node N11 and the node N15, and arrives at the destination GL. The route R13 is a route that leaves the departure point S1, passes through the node N14 and the node N15, and arrives at the destination GL.

  FIG. 8 is an explanatory diagram showing an example of the variable cost added to the target link included in the travel route connecting the departure place S1 and the destination GL. FIG. 8 shows the variable cost added when one other user passes the target link included in the routes R11, R12, and R13 in FIG. In the present embodiment, the variable cost is a value added to the link cost of the target link, and therefore always has a positive value. FIG. 8 shows variable costs added to the target links included in the routes R11, R12, and R13 calculated in the same manner. Note that the third and subsequent decimal places in the variable cost are rounded off, including the rest.

  FIG. 9 is an explanatory diagram showing a travel route connecting the departure point S2 and the destination GL set by another user. FIG. 9 shows a route R14 as a travel route connecting the departure point S2 and the destination GL set by another user different from the users shown in FIG. 7 and FIG. As shown in FIG. 9, the route R14 is a route that leaves the departure point S2, passes through the node N13, the node N14, and the node N15 and arrives at the destination GL. The route cost of the route R14 is 30. As shown in FIG. 9, in this user's route information, only the route R14 is set as the moving route including the target link. Naturally, the route R14 is an optimum route connecting the departure point S2 and the destination GL.

  FIG. 10 is an explanatory diagram showing an example of the variable cost added to the target link included in the travel route connecting the departure point S2 and the destination GL. FIG. 10 shows a variable cost added when one other user passes the target link included in the route R14 in FIG. Similar to the example shown in FIG. 8, in the example shown in FIG. 10, for example, the variable cost of the link LN02 connecting the departure place S2 and the node N13 is 3 (FIG. 6) of the link cost specified by the network information. , Multiplied by 64% (optimum route) of traffic possibility and 0.05 of the number of people coefficient. FIG. 10 shows the variable cost added to the target link included in the calculated route R14 in the same manner.

  When the variable cost to be added to all target links is calculated (step S27 in FIG. 5), the variable cost calculation unit 135 adds the calculated variable cost to the link cost of the link specified by the network information (step S29). ). FIG. 11 is an explanatory diagram illustrating an example of network information indicating a link cost to which a variable cost is added. FIG. 11 shows the route information of one other user whose travel route is the route connecting the departure point S1 and the destination GL, and one other person whose travel route is the route connecting the departure point S2 and the destination GL. The link cost to which the variable cost calculated based on the user's route information is added is shown. As shown in FIG. 11, for example, the link cost of the link L03 connecting the node N15 and the destination GL is different from 6 specified by the network information, and is based on the travel route of another user leaving the departure place S1. The variable cost 0.09 calculated in FIG. 8 (FIG. 8) and the variable cost 0.19 calculated based on the travel route of the other user leaving the departure point S2 (FIG. 10) are added. 6.28.

  When the variable cost is added to the link cost (step S29 in FIG. 5), the variable cost calculation unit 135 determines whether or not there is a link exceeding the set allowable traffic value in the link included in the network information ( Step S31). In the example shown in FIG. 11, since there is no link cost exceeding the traffic allowance that is twice the link cost before the variable cost is added (step S31: NO), the link cost information DB 136 of the cost adjustment unit 130 is The link cost to which the variable cost is added is stored as variable cost data, and the cost adjustment unit 130 ends the variable cost data creation process.

  In the process of step S31 in FIG. 5, when it is determined that there is a link exceeding the allowable traffic value (step S31: YES), the variable cost calculating unit 135 displays route information including the link exceeding the allowable traffic value. Extract (step S33). FIG. 12 is an explanatory diagram showing the variable cost added to the target link included in the travel route connecting the departure point S1 and the destination GL. FIG. 12 shows the calculated variable cost based on 40 other users who set the route connecting the departure point S1 and the destination GL as the travel route. Note that the variable cost shown in FIG. 12 is calculated using the same standard congestion degree and passability as in FIG. 9, and the number of people coefficient is based on 40 (persons) due to the difference in the number of users. It is calculated using 2 divided by the degree of congestion of 20. Therefore, the variable cost shown in FIG. 12 is a value 40 times the variable cost shown in FIG. In this case, for example, the link cost of the link LN01 before adding the variable cost is 5, and when the variable cost 6.4 is added, it becomes 11.4. Since the variable cost 11.4 exceeds 10, which is twice the link cost before the variable cost set as the traffic allowance is added (step S31 in FIG. 5: YES), the variable cost calculation unit 135 The variable cost calculated based on the route information of 40 users connecting the departure point S1 and the destination GL exceeding the allowable value is deleted (step S35).

  Next, the variable cost calculation unit 135 newly sets 6 as an allowable traffic value that is higher than the allowable traffic value of 3 before deleting the variable cost (step S37), and repeats the processing after step S25. FIG. 13 is an explanatory diagram illustrating an example of a travel route that connects the departure place S1 and the destination GL set by another user. A route R15 illustrated in FIG. 13 is a route that departs from the departure point S1, passes through the node N11, the node N12, the node N16, and the node N17 and arrives at the destination GL. When calculated using the link cost of each link shown in FIG. 6, the route cost of the route R15 is 20. Unlike the case of FIG. 7, the traffic allowance value is set to 6. Therefore, in the example shown in FIG. 13, in addition to the routes R <b> 11, R <b> 12, R <b> 13 shown in FIG. As a similar route, the route R15 is set as a moving route including the target link.

  Next, the variable cost calculation unit 135 calculates the traffic possibility based on the newly set allowable traffic value (step S25 in FIG. 5). The route cost difference of the route R15 with respect to the route R11 of the optimum route is 5 obtained by subtracting 15 from 20. Therefore, the sum of the squares of the path cost differences for determining the passability is as follows: 0 square, 1 square, 2 square, 3 square, 4 square, 5 square, The sum of squares and 91 is 91. Therefore, the possibility of passage of the target link included in the route R11 having the route cost difference of 0 is 40% obtained by dividing 36, which is the square of 6 obtained by subtracting the route cost difference from the cost difference allowable value, by 91. Similarly, the possibility of passage of the target links included in the route R12 and the route R13 having the route cost difference of 1 is 27% obtained by dividing the square 25 obtained by subtracting the route cost difference from the cost difference allowable value by 91. Further, the passability of the target link included in the route R15 is 1% obtained by dividing 1 squared 1 obtained by subtracting the route cost difference from the cost difference allowable value by 91.

  When the passability is calculated, the variable cost calculation unit 135 calculates the variable cost to be added to all the target links using the calculated passability (step S27 in FIG. 5). FIG. 14 is an explanatory diagram showing an example of the variable cost added to the target link included in the travel route connecting the departure place S1 and the destination GL. FIG. 14 shows the variable cost added to the target link included in the travel route connecting the departure point S1 and the destination GL when the newly set allowable traffic value is 6. FIG. 14 shows the variable cost calculated based on the movement route of 40 users. For example, the variable cost added to the link LN01 is 4.0 obtained by multiplying the link cost 5 (FIG. 6) by 40% of the possibility of passage (the route R11 of the optimum route) and the number of people coefficient 2. . FIG. 14 shows the variable cost added to the target links included in the calculated routes R11, R12, R13, and R15 in the same manner.

  When the variable cost is calculated, the variable cost calculation unit 135 adds the variable cost to the link cost of the target link (step S29 in FIG. 5), and determines whether there is a link exceeding the allowable traffic value (step S31). ). As described above, the cost adjustment unit 130 performs the process of creating the variable cost data until there is no link exceeding the allowable traffic value.

A-4. Travel route group search processing:
When the variable cost data creation process is performed (step S20 in FIG. 2), the route search unit 120 uses the created variable cost data to search for a user's travel route connecting the departure point and the destination ( Step S40). FIG. 15 is an explanatory diagram showing the flow of the search process for the movement route group. In the travel route group search process, first, the route search cost that the route search unit 120 adds to the route cost of the optimum route is set (step S41). Although details will be described later, the route search unit 120 searches for a similar route that is equal to or less than a value obtained by adding the route search cost to the route cost of the optimum route. In the present embodiment, the route search unit 120 sets the route search cost to 3. Next, the route search unit 120 performs processing for assigning various labels to nodes on the network (step S50). Details of the label applying process will be described later. Next, the optimum route searching unit 123 of the route searching unit 120 searches for the optimum route that minimizes the route cost of the route connecting the departure point and the destination based on the label given to the node (step S43). . Next, the similar route search unit 124 of the route search unit 120 searches for a similar route group based on the label and the route search cost given to the nodes included in the searched optimum route (step S90). Details of the similar route group search processing will be described later. Next, the route search unit 120 sets the searched optimum route and similar route group together as a movement route group (step S45).

  16 and 17 are explanatory diagrams showing the flow of label attaching processing. In the label assignment process, a label for identifying a label immediately before the node to which the label is assigned and a route cost for moving from the node at the departure point to the node to which the label is assigned is assigned to a node on the network. It is a process to give. In the label assigning process, first, a candidate label is assigned to the departure node (step S51).

  FIG. 18 is an explanatory diagram showing a state where a candidate label is assigned to the node of the departure place S2. FIG. 18 shows a state in which the label A0 of the candidate label is given to the node at the departure place S2. There are four types of labels to be given to nodes: candidate labels, confirmed labels, new labels, and losing labels. The optimum route and the similar route are searched by using the four types of labels properly. As shown in FIG. 18, in the label A0 of the candidate label, since there is no immediately preceding label, the immediately preceding label is indicated by “−”, and since no link is passing, the route cost is indicated by “0”. Has been. Further, in FIG. 18, the link cost of the link connecting the nodes is indicated by a numerical value, and the numerical value enclosed by the square is the link cost to which the variable cost is added. In the present embodiment, the user of the mobile phone 200 searches for a group of travel routes from the departure point S2 to the destination GL.

  When the candidate label is assigned to the departure place S1, the route search unit 120 determines whether there is a candidate label assigned to the node on the network (step S53 in FIG. 16). When it is determined that there is no candidate label assigned to the node (step S53: NO), the route search unit 120 ends the label assignment process. In the process of step S53, as shown in FIG. 18, since the label A0 of the candidate label is given to the departure place S1 (step S53 of FIG. 16: YES), the route search unit 120 has the candidate with the lowest route cost. The label A0, which is a label, is changed to a confirmed label (step S55).

  Next, the route search unit 120 determines whether or not a confirmed label has already been assigned to the node of the destination GL (step S57). As shown in FIG. 18, since the final label is not given to the destination GL (step S57: NO), the route search unit 120 is connected by a link from the node having the label A0 changed to the final label. A new label is given to the adjacent node that can be passed (step S61).

  FIG. 19 is an explanatory diagram showing a state in which a new label is assigned to the adjacent node of the departure place S1 to which the final label A0 is assigned. FIG. 19 shows a state in which new labels are assigned to the nodes N13, N16, and N18 of three adjacent nodes connected to the departure place S2 based on the label A0 of the confirmed label assigned to the departure place S2. It is shown. As a new label, a label A1 is assigned to the node N13, a label A2 is assigned to the node N16, and a label A3 is assigned to the node N18. As for label A1, the label A0 is the immediately preceding label (hereinafter also simply referred to as “preceding label”), and the link cost of the link LN02 through which the route cost has passed is 5. Similarly, the label A2 is the link cost 5 of the link LN04 that connects the departure point S2 through which the route cost is passed and the node N16, the label A0 being the immediately preceding label. The label A3 is the link cost 15 of the link LN05 that connects the departure point S2 and the node N18, where the immediately preceding label is the label A0 and the route cost passes.

  When a new label is assigned to the adjacent node, the route search unit 120 selects the node N13 to which the label A1 is assigned as one target node from one or more adjacent nodes to which the new label is assigned (FIG. 17). Step S63). Next, the route search unit 120 determines whether or not a confirmed label has already been assigned to the node N13 that is the target node (step S65). As shown in FIG. 19, the node N13 has not been given a definitive label (step S65: NO in FIG. 17), so that the route search unit 120 has one or more new assignments given to the node N13 of the node of interest. The label A1 is selected as one processing target label from the label (step S67). Next, the route search unit 120 determines whether or not a candidate label is assigned to the node N13 (step S69). As shown in FIG. 19, since no candidate label is given to the node N13 (step S69 of FIG. 17: NO), the route search unit 120 uses the label A1 of the new label that is the processing target label as the candidate label. Change (step S75). Next, the route search unit 120 determines whether there is an adjacent node that has not been selected as the node of interest among the adjacent nodes to which a new label has been assigned (step S81). As shown in FIG. 19, since the node N16 and the node N18 are not selected as the target nodes among the adjacent nodes of the departure place S2 (step S81 in FIG. 17: YES), the route search unit 120 changes the node N13 to Similarly to the case where the node of interest is selected, the node N16 is selected as the node of interest (step S63), and the processing after step S65 is performed. Thereby, the label A2 given to the node N16 is changed to a candidate label, and the label A3 given to the node N18 is changed to a candidate label.

  When there is no node that is not selected as the target node among the adjacent nodes of the departure place S2 (step S81: NO), the route search unit 120 determines whether there is a candidate label assigned to the node on the network. (Step S53 in FIG. 16). Since candidate labels are assigned to the nodes N13, N16, and N18 (step S53: YES), the route search unit 120 changes one label A1 of the labels having the minimum route cost of 5 to a confirmed label. (Step S55). Since the final label is not assigned to the destination GL (step S57: NO), the route search unit 120 assigns a new label to the adjacent node of the node N13 to which the final label A1 is assigned (step S61). .

  FIG. 20 is an explanatory diagram showing a state in which a new label is assigned to the adjacent node of the node N13 to which the final label A1 is assigned. FIG. 20 shows a state in which new labels are assigned to the nodes N17, N14, N19 and the departure place S2, which are adjacent nodes of the node N13, based on the label A1 of the confirmed label given to the node N13. . As a new label, a label A4 is given to the node N17, a label A5 is given to the departure place S2, a label A6 is given to the node N14, and a label A7 is given to the node N19. The immediately preceding label and the route cost of these four labels are as shown in FIG. 20, for example, the label A4 has the label A1 as the immediately preceding label and the route cost 5 as the route cost of the label of the label A1. The link cost 4 of the link LN06 connecting N13 and the node N17 is added to 9.

  Based on the final label A0 assigned to the departure place S2, the new labels A4, A6, A19 assigned to the nodes N17, N14, N19 are provided in the same manner as the candidate labels A1, A2, A3 are assigned. A7 is changed to a candidate label. Here, the process of the label A5 given to the departure place S2 will be described. The route search unit 120 selects the departure point S2 as one target node among the adjacent nodes to which the new label is assigned (step S63 in FIG. 17). Since the departure point S2 which is the target node has the label A0 of the confirmed label (step S65: YES), the route search unit 120 changes the label A5 of the new label given to the departure point S2 to the losing label ( Step S77). Then, the route search part 120 performs the process after step S81.

  When there is no node that is not selected as the target node among the adjacent nodes of the node N13 (step S81), the route search unit 120 determines whether there is a candidate label assigned to the node on the network (FIG. 16 step S53). Since candidate labels are assigned to the nodes N16, N18, N17, N14, and N19 (step S53: YES), the route search unit 120 changes the label A2 having the minimum route cost of 5 to a confirmed label ( Step S55). Since the final label is not given to the destination GL (step S57: NO), the route search unit 120 gives a new label to the adjacent node of the node N16 to which the final label A2 is assigned (step S61). .

  FIG. 21 is an explanatory diagram showing a state in which a new label is assigned to the adjacent node of the node N16 to which the final label A2 is assigned. FIG. 21 shows a state where a new label is assigned to the node N17 that is an adjacent node of the node N16 and the departure place S2, based on the label A2 of the confirmed label assigned to the node N16. As a new label, a label A8 is assigned to the node N17, and a label A9 is assigned to the departure place S2. For label A8, the immediately preceding label is label A2 and the path cost is 8. For label A9, the immediately preceding label is label A2, and the path cost is 10.

  Based on the label A1 of the confirmed label assigned to the node N13, the label A9 of the new label assigned to the departure place S2 is changed to the losing label in the same manner as the loss label A5 is assigned to the departure place S2. Be changed. Here, the route search unit 120 selects the node N17 as the target node from the adjacent nodes of the node N16 (step S63 in FIG. 17). Since the confirmed label is not given to the node N17 (step S65: NO), the route search unit 120 selects the label A8 of the new label given to the node N17 as the processing target label (step S67). Next, the route search unit 120 determines whether or not a candidate label is assigned to the node N17 that is the node of interest (step S69). As shown in FIG. 21, since the label A4 is assigned as a candidate label to the node N17 (step S69 in FIG. 17: YES), the route search unit 120 has the route cost of the candidate label assigned to the node N17. It is determined whether or not the route cost of the new label given to the node N17 is greater (step S71). As shown in FIG. 21, the route cost of the label A4 of the candidate label is 9 and is larger than 8 of the route cost of the label A8 of the new label (step S71: YES). Label A4 is changed to a losing label (step S73). Thereafter, the route search unit 120 changes the label A8 of the new label to a candidate label (step S75), and performs the processing after step S81. In the process of step S71, when the route cost of the candidate label is not larger than the route cost of the new label (step S71: NO), the route search unit 120 changes the new label to a losing label.

  FIG. 22 is an explanatory diagram showing a state where a new label is assigned to an adjacent node of the destination GL based on the label A48 of the confirmed label given to the destination GL. In FIG. 22, after the label assignment processing for the nodes on the network proceeds and the label A48 of the candidate label assigned to the destination GL is changed to the confirmed label, the nodes N15 and N21 that are adjacent nodes of the destination GL are displayed. , N20, and N12 are shown with new labels. In FIG. 22, only the label name of each label is shown, and the route cost of the labels related to the new label labels A60, A61, A62, and A63 assigned to the adjacent nodes of the destination GL is shown in the table. . In the node N15, the route cost of the label A60 of the new label is 46.4, which is larger than the route cost 24.4 of the label A15 of the fixed label, so the label A60 is changed to a losing label. Similarly, the label A61 of the new label given to the node N21 is changed to a losing label. Also, the new label A63 given to the node N12 is changed to a losing label. In node 20, since the route cost 35.8 of the label A62 of the new label is larger than the route cost 35.4 of the label A56 of the candidate label, the label A62 is changed to a losing label.

  When the final label A48 is assigned to the destination GL, the route search unit 120 determines whether there is a candidate label assigned to a node on the network (step S53 in FIG. 16). As shown in FIG. 22, since there are a label A56 given to the node N20 and a label A53 given to the node N22 as candidate labels (step S53 in FIG. 16: YES), the route search unit 120 determines the route cost. The label A56 of the candidate label given to the node N20 having the smallest 35.4 is changed to a confirmed label (step S55). Next, since the final label GL is assigned to the destination GL (step S57: YES), the route search unit 120 determines that the route cost of the changed final label A56 is the final label of the destination GL. It is determined whether or not the value is larger than the value obtained by adding the route cost and the route search cost (step S61). The route cost of the label A56 of the confirmed label is 35.4, and is not larger than 37.8 obtained by adding 3 of the route search cost to 34.8 of the route cost of the label A48 of the confirmed label of the destination GL ( Step S59: NO), the route search unit 120 performs the processing after Step S61. When the route cost of the changed confirmed label is larger than the value obtained by adding the route cost of the confirmed label given to the destination GL and the route search cost (step S59: YES), the route search unit 120 Then, the label assignment process is terminated.

  FIG. 23 is an explanatory diagram illustrating an example of a state in which the candidate labels assigned to the nodes on the network disappear. 24 and 25 are explanatory diagrams showing a list of the relationship between the route cost and the immediately preceding label for each of the confirmed label and the losing label given to the node on the network. FIG. 23 shows only the label names of the definite label and the losing label given to the nodes on the network. 24 and 25 show the route cost, the immediately preceding label, and the label type indicating the final label or the losing label for each of the labels shown in FIG. For example, as shown in FIG. 24, the label A10 is a label given to the node N16, the path cost is 11, and the immediately preceding label is a losing label of the label A8. As described above, when there is no candidate label assigned to a node on the network (step S53 in FIG. 16: NO), the route search unit 120 ends the label assignment process.

  When the label assignment process ends, the optimum route search unit 123 of the route search unit 120 searches for the optimum route based on the label assigned to the node (step S43 in FIG. 15). In the label assigning process, since the label for specifying the immediately preceding label and the route cost is assigned to the node, one label given to the specific node includes the route connecting the departure place S2 and the specific label, The route cost of the route can be specified. Therefore, the route based on the confirmed label given to the destination GL is specified as the route having the lowest route cost connecting the departure point S2 and the destination GL, and the optimum route search unit 123 searches the route concerned. Is set as the optimum route. Hereinafter, the route specified by the specific label is also simply referred to as “route based on the specific label”.

  FIG. 26 is an explanatory diagram showing an example of the optimum route connecting the departure point S2 and the destination GL. FIG. 26 shows a route R21 that is the optimum route searched using FIGS. 23 and 25 based on the label A48 of the finalized label given to the destination GL.

  When the optimum route is searched and set, the similar route search unit 124 of the route search unit 120 performs a similar route group search process based on the confirmed label and the loss label given to the nodes on the network ( Step S90 in FIG. 15). FIG. 27 is an explanatory diagram showing the flow of the similar route group search process. In the similar route group search processing, first, the similar route search unit 124 determines whether or not there is a node to which a losing label is assigned to the optimal node that is a node included in the optimal route (step S91). . As shown in FIG. 26, since the losing label is assigned to all the optimal nodes included in the route R21 of the optimal route (step S91: YES), the similar route search unit 124 determines the optimal node to which the losing label is assigned. The destination GL is selected as one determination target node from (Step S93). Next, the similar route search unit 124 determines whether or not the route cost difference between the losing label assigned to the destination GL and the confirmed label is equal to or less than the route search cost (step S95). When it is determined that the route cost difference is equal to or less than the route search cost (step S95: YES), the similar route search unit 124 sets a route based on the losing label as one similar route (step S97). When a similar route is set, or when it is determined in the process of step 95 that the route cost difference is not less than or equal to the route search cost (step S95: NO), the similar route search unit 124 determines the determination target node. It is determined whether there is an optimal node that has not been selected as (step S99). If there is an optimum node that has not been selected as the determination target node (step S99: YES), the similar route search unit 124 selects a new determination target node (step S93), and performs the processing from step S95 onward. .

  FIG. 28 is an explanatory diagram of an example of the searched similar route group. FIG. 28 shows a route R22 and a route R23 that are similar routes included in the searched similar route group in addition to the route R21 that is the optimum route. In FIG. 28, regarding the confirmed label given to the destination GL that is the optimum node selected as the determination target node and the losing label that is the basis of the similar route, in addition to the label name, the immediately preceding label and the route cost It is shown. As shown in FIG. 28, the value obtained by subtracting 34.8 of the route cost of the label A48 of the final label of the destination GL from 36 of the route cost of the label A43 of the loss label of the destination GL is 1.2. Since the route search cost is 3 or less, the route based on the label A43 is set as a similar route. 24 and 25, the similar route based on the label A43 is a route R22 shown in FIG. Similarly, the value obtained by subtracting 34.8 of the route cost of the label A48 of the destination GL from 36.4 of the route cost of the label A65 that is the losing label of the destination GL is 1.6. Since the route search cost is 3 or less, the route based on the label A65 is set as a similar route. A similar route based on the label A65 is a route R23 shown in FIG. Note that the optimum node included in the route R21 of the optimum route corresponds to the second optimum node in the claims. Further, the movement route connecting the departure point S2 and the specific optimum node corresponds to the second intermediate route in the claims. The route based on the definite label assigned to the specific optimal node corresponds to the second minimum cost midway route, and the route based on the loss label assigned to the specific optimal node is the second non-minimum cost midway route. Equivalent to.

  If it is determined in step S99 in FIG. 27 that there is no optimal node not selected as a determination target node (step S99: NO), the similar route search unit 124 temporarily sets the set similar route. Is set as the optimum route (step S101). Next, the similar route search unit 124 performs the processing from step S93 onward for the losing label given to the optimum node included in the newly temporarily set optimum route. That is, the similar route search unit 124 searches for further similar routes for all of the losing labels assigned to the nodes included in the similar route. In this embodiment, as shown in FIG. 24 and FIG. 25, there is no route set as a further similar route in the route R22 and the route R23 of the similar route group. The search process is terminated.

  When the similar route group search process is performed, the route search unit 120 sets the searched optimum route and similar route group as the movement route group (step S45 in FIG. 15). As described above, in the present embodiment, the route R21 of the optimum route, the route R22 and the route R23 of the similar route are set as movement routes that connect the departure point S2 and the destination GL, and are transmitted via the mobile phone 200. Presented to the user.

  As described above, in the server 100 according to the present embodiment, the cost adjustment unit 130 can pass based on the optimum route and the similar route included in the route information transmitted from each of the plurality of mobile phones 200 and the like. Etc. is used to adjust the link cost of the link specified by the network information. The route search unit 120 searches for at least one moving route group connecting the departure point and the destination by using a search network that identifies the adjusted link cost. Therefore, in the server 100 of this embodiment, even when another user passes a similar route other than the optimum route as the searched travel route depending on the traffic situation on the network, the traffic of the other user passing the similar route In consideration of the situation, the user's travel route connecting the starting point and the destination is searched. Therefore, the user can arrive at the destination while avoiding traffic jams based on the future traffic situation that other users may pass through.

  Further, in the server 100 according to the present embodiment, the cost adjustment unit 130 is based on a route cost difference calculated by the route cost of the optimum route and the route cost of the similar route, which is information included in the route information of other users. The variable cost is calculated using an index value such as the possibility of passing. Therefore, in the server 100 of the present embodiment, not only one movement route of another user, but also a plurality of movement routes including the route cost of the optimum route and a similar route that is the route cost of the difference between the predetermined link costs. Fluctuating costs based on the degree of congestion based on this are calculated. Therefore, since the user's movement route is searched after predicting the situation such as when another user changes the route by looking at the traffic congestion of the link scheduled to pass next, the user may occur The traffic can be avoided, the destination GL can be reached more quickly, and the convenience for the user is improved.

  Further, in the server 100 according to the present embodiment, the cost adjustment unit 130 increases the passability as the difference in route cost obtained by subtracting the route cost of the optimum route from the route cost of the similar route in the route information of other users. Thus, the variable cost is greatly calculated. Therefore, in the server 100 according to the present embodiment, since the variable cost is calculated to be larger as the link is more likely to be passed by another user, the user's travel route can be searched based on the traffic situation according to the actual congestion degree. .

  In the server 100 according to the present embodiment, the optimum route searching unit 123 of the route searching unit 120 searches for the optimum route having the smallest route cost among the moving routes connecting the departure point S2 and the destination GL. The similar route search unit 124 of the route search unit 120 searches for at least one similar route having a route cost equal to or less than a value obtained by adding the route search cost to the route cost of the optimum route. Therefore, in the server 100 of the present embodiment, a plurality of travel routes are searched for within a predetermined route cost or less, so that the user can select a favorite route from the plurality of travel routes, and convenience for the user is improved. .

B. Second embodiment:
In the first embodiment, the travel route connecting the user's departure point and the destination is searched based on the route information of the other user, but the user's travel route is not necessarily searched. Various changes can be made to the method of using the user's route information.

  FIG. 29 is a schematic diagram illustrating an example of an estimated congestion degree of a link on the network in the second embodiment. FIG. 29 shows the estimated traffic situation on the network in which the search network information generated by the cost adjustment unit 130 is displayed on the display panel 202 of the mobile phone 200 using the variable cost data of the first embodiment. It is shown. In the example shown in FIG. 29, variable cost data is created based on route information of a plurality of users that depart from the departure points S1, S2, and S3 toward the destination GL2 as three departure points. In FIG. 29, the distribution AR1 and the distribution AR2 indicate the estimated degree of congestion according to the magnitude of the variable cost added to the link cost of each link based on the variable cost data. In FIG. 29, the variable cost of each link included in the distribution AR1 is 50% of the link cost stored in the network information. Further, the variable cost of each link included in the distribution AR2 is 75% of the link cost stored in the network information. That is, in the search network information to which the variable cost is added, the link cost of the link included in the distribution AR1 is 150% of the link cost specified by the network information, and the link cost of the link included in the distribution AR2 Is a value of 175% specified by the network information. The search network information corresponds to the adjustment route information in the claims.

  FIG. 30 is an explanatory diagram illustrating an example of the estimated congestion degree of the link on the network in the comparative example. FIG. 30 shows the estimated traffic situation on the network based on only the optimum route, which is one of the travel routes of other conventional users, without creating variable cost data of similar routes. In this comparative example, the variable cost of each link included in the distribution AR3 is 50% of the link cost stored in the network information. In addition, the variable cost of each link included in the distribution AR4 is 75% of the link cost stored in the network information. The variable cost of each link included in the distribution AR5 is 100% of the link cost stored in the network information. That is, in the search network information, the link cost of the link included in the distribution AR3 is 150% of the link cost specified by the network information, and the link cost of the link included in the distribution AR4 is specified by the network information. Is 175% of the link cost. In the search network information, the link cost of the link included in the distribution AR5 is 200% of the link cost specified by the network information.

  As described above, in the server 100 according to the second embodiment, the cost adjustment unit 130 generates search network information using the variable cost data with the link cost adjusted, and transmits the search network information to the mobile phone 200. To do. Therefore, in the server 100 of the second embodiment, the optimum route and the similar route are searched for the movement routes of a plurality of users, and the link cost is adjusted and calculated. Therefore, the adjusted link cost does not become a locally high value compared to the comparative example, and suppresses the occurrence of local traffic congestion. In addition, the user can grasp the degree of congestion around the destination GL2 at a glance, and can go to the destination GL2 while avoiding traffic congestion without performing a route search, which improves convenience for the user. .

  Further, in the server 100 in the second embodiment, the variable cost added by the variable cost data with respect to the link cost stored in the network information is distinguished and displayed by the distribution AR1 and the distribution AR2. Therefore, in the server 100 of the second embodiment, since the user can visually recognize how much congestion is present compared to the case where the user is not crowded, the traffic situation can be easily recognized, and convenience for the user is improved. .

  Further, in the server 100 in the second embodiment, the cost adjustment unit 130 generates search network information in which the links to which the variable cost is added are distinguished by the distribution AR1 and the distribution AR2. Therefore, in the server 100 according to the second embodiment, the user can visually recognize which link is charged with how much the variable cost, so that the traffic situation can be recognized more easily and the convenience for the user is further improved. .

C. Variations:
In addition, this invention is not limited to the said embodiment, It can implement in a various aspect in the range which does not deviate from the summary, For example, the following deformation | transformation is also possible.

C1. Modification 1:
In the above embodiment, the server 100 has acquired information including the movement route of the other user as the other user's route information, but does not necessarily need to acquire the route information including the movement information. Information can be variously modified. For example, the server 100 may acquire the departure point and the destination set in the mobile phone 200 or the like by another user as the route information of the other user, and may not acquire the movement route. In this case, the cost adjustment unit 130 of the server 100 assigns various labels to the nodes on the network in the same way as the label assignment processing performed by the route search unit 120 as the travel route of other users. The optimum route and the similar route may be searched. In the server 100 of this modified example, if only information specifying the departure point and the destination of another user is acquired, the movement route of the other user can be estimated. Even if the departure location of another user is unknown, the current location of the other user is identified by the GPS unit 201 such as the mobile phone 200 carried by the other user, and the location is determined as the departure location. Thus, it is possible to estimate the travel route of other users, and to search for routes that take into consideration the degree of congestion even with less route information of other users.

C2. Modification 2:
In the first embodiment, as shown in FIG. 28, the route R22 and the route R23 of similar routes are searched based on the route cost difference between the definite label and the losing label given to the destination GL. A similar route may be searched based on the confirmed label and the losing label given to the optimum node other than the destination GL. For example, when a route search cost larger than the route search cost of the first embodiment is set, a similar route is searched based on the confirmed label and the losing label given to the node N14. In this case, the similar route is a route based on the losing label given to the node N14 from the departure point S2 to the node N14, and a route overlapping the optimum route from the node N14 to the destination GL. Therefore, in this modified example, when searching for a similar route, instead of searching for the route from the departure point S2 to the destination GL one by one, it is possible to search based on the confirmed label and the losing label given to the node. The route search can be performed quickly, and the processing load of the route search device can be reduced.

C3. Modification 3:
In the above embodiment, the current position acquired by the GPS unit 201 is set as a starting point when searching for a route. However, various methods can be used for setting the starting point and the destination. For example, the departure point may be set by operating the operation unit 206 by the user, or the departure point or the destination may be set by designating a future date and time in a scheduled trip. Also, various methods can be used for inputting the departure point and the destination. For example, the current position, the destination, and the like may be set by voice recognition by the call control unit 220 of the mobile phone 200.

  In the above embodiment, the link included in the predetermined distance from the set destination is set as the target link. However, the method for selecting the target link is not limited to this, and various modifications can be made. For example, not the destination but a link included in a predetermined distance from the departure place may be set as the target link. Further, after the optimum route as the user's travel route is searched, a link that constitutes another user's travel route including the link that constitutes the searched optimum route may be set as the target link. Further, when the user operates the operation unit 206, a specific link may be set as the target link.

  In the above embodiment, the index values for calculating the variable cost have been described with specific values. However, the values for each of these index values can be variously modified. For example, the cost difference allowable value set initially may be a value other than 3, and the reference congestion degree may be a value other than 20, or a value using a decimal point. . In addition, when calculating the traffic possibility, the square value of the value obtained by subtracting the route cost difference from the cost difference tolerance value or the sum of the squares of the route cost difference was used, but the value is not limited to the square, but the value of the first power Or a multiplier greater than or equal to the third power may be used. Further, the passability may be calculated using other exponential functions, quadratic functions, or the like. Also, the decimal point processing is not limited to rounding, and the fraction may be rounded down, and the decimal point unit to be rounded down can be variously modified.

  Moreover, in the said embodiment, although the fluctuation cost calculation part 135 added the fluctuation cost calculated to the link cost of the link memorize | stored in map information DB114, the adjustment method of link cost is not restricted to this, Various modifications are possible. For example, the variable cost calculation unit 135 may adjust the link cost by subtracting the variable cost from links other than the target link. Further, the variable cost calculation unit 135 calculates some coefficient instead of the variable cost without adding or subtracting the variable cost to the link cost, and multiplies the link cost stored in the map information DB 114 by the coefficient to thereby calculate the link cost. May be adjusted. Moreover, you may designate the link which adds a variable cost to a specific link.

C4. Modification 4:
Further, in the above embodiment, the optimum route and the similar route as the user's moving route are searched using the label given to the node. However, the method for searching the moving route is not limited to this, and various modifications are made. Is possible. For example, the route search unit 120 may search for a similar route using network information excluding some links included in the optimal route after searching for the optimal route by the Dijkstra method. Further, the route searching unit 120 may search for a moving route using an aster (A ^* ) search algorithm instead of the Dijkstra method, or may search for a moving route by other methods.

  In the above embodiment, the value 3 is used as the route search cost, and a similar route is searched. However, the route search cost can be variously modified. For example, the value may be a value other than 3, and the route search unit 120 may set a value of what percentage of the route cost of the optimum route as the route search cost.

  Further, in the above embodiment, after a similar route is searched, a similar route is temporarily set as the optimum route and then a further similar route is searched. However, the similar route search process is not limited to this. Various modifications are possible. For example, the route search unit 120 may not temporarily set the searched similar route as the optimum route. In addition, the route search unit 120 may set an upper limit for the number of similar routes to be searched in advance, and may not search for similar routes exceeding the upper limit.

  In the above embodiment, the smaller the route cost difference is, the larger the passability index value is. Therefore, the variable cost is calculated to be a large value, but the relationship between the route cost difference and the variable cost is It is not limited and can be variously modified. For example, the variable cost value may be uniformly set to the same value regardless of the index value such as the passability. Also, only two values that are different between the optimum route and the similar route may be set.

C5. Modification 5:
In the second embodiment, as shown in FIG. 29, the link to which the variable cost is added and the link to which the variable cost is not added are displayed separately according to the distributions such as the distribution AR1 and the distribution AR2. The display method for distinguishing whether or not is added is not limited to this, and various modifications can be made. For example, the link to which the variable cost is added may be distinguished by changing the color of the link itself. Further, the variable cost value itself may be displayed on the displayed link.

C6. Modification 6:
In the above embodiment, the link cost is the time (minute) for passing through the link, but the relationship between the time for passing the link and the link cost is not limited to this, and various modifications can be made. For example, for the specified link cost, the link cost may be converted into time (for example, in minutes) according to the user's moving means set via the mobile phone 200. Also, the link cost may be a time in seconds passing through the link instead of a minute unit.

  In the above embodiment, the link cost is the same for each link regardless of the direction, but the setting of each link can be variously modified. For example, when the user is in a car, the link may reflect a restriction that the user knows that one-way traffic or right turn is prohibited. As for the link cost of the link, for example, in the case of a link on a slope, the link cost may be changed according to the passing direction. In addition, the user is not limited to a vehicle, and for example, the user's moving means may be walking, a bicycle, or other moving means.

  In the above embodiment, the server 100 includes the information storage unit 110 and the route search unit 120 as illustrated in FIG. 1, but the apparatus including the information storage unit 110 and the route search unit 120 is not limited to this mode. Various modifications are possible. For example, the information storage unit 110 and the route search unit 120 may be provided in different servers, or the route search unit 120 may be mounted on the mobile phone 200.

  The present invention is not limited to the above-described embodiments, examples, and modifications, and can be realized with various configurations without departing from the spirit of the present invention. For example, the technical features in the embodiments, examples, and modifications corresponding to the technical features in the angular form described in the summary section of the invention are to solve some or all of the above-described problems, or In order to achieve part or all of the above-described effects, replacement or combination can be performed as appropriate. Further, if the technical feature is not described as essential in the present specification, it can be deleted as appropriate.

DESCRIPTION OF SYMBOLS 10 ... Route search system 20 ... Node 100 ... Server 102 ... Communication part 110 ... Information storage part 114 ... Map information DB
115 ... Traffic information DB
DESCRIPTION OF SYMBOLS 120 ... Route search part 123 ... Optimal route search part 124 ... Similar route search part 130 ... Cost adjustment part 135 ... Fluctuation cost calculation part 136 ... Link cost information DB
DESCRIPTION OF SYMBOLS 150 ... Control part 200 ... Mobile telephone 201 ... GPS unit 202 ... Display panel 203 ... Audio | voice output part 205 ... Wireless communication circuit 206 ... Operation part 206a ... Numeric keypad 206b ... Cursor key 210 ... Main control part 211 ... CPU
220 ... Call control unit S1, S2 ... Departure point GL, GL2 ... Destination INT ... Internet

Claims (5)

A route search device for searching for a route connecting two nodes on a network,
A data storage unit for storing network information for identifying a plurality of nodes on the network, a plurality of links, and a link cost set for each of the plurality of links;
An information acquisition unit for acquiring information for identifying a departure node and a destination node set in at least one other device;
The cumulative value of the link costs of the links constituting the first movement path among the plurality of first movement paths connecting the starting node and the destination node set in the other device is the smallest. A cumulative value of the link cost of the first optimal route, and a cumulative value of the link cost equal to or less than a value obtained by adding a first allowable cost to the cumulative value of the link cost of the first optimal route. The variable cost set for each link based on the cumulative value of the link cost of the first sub-optimal route is used as the link cost of the link constituting the first optimum route and the first sub-optimal route. and cost adjustment unit for adjusting the link cost of the network information stored in the data storage unit by adding the,
A point setting unit for setting a departure node and a destination node;
A route search unit that searches for at least one second movement route that connects the starting node and the destination node set by the point setting unit using the network information in which the link cost is adjusted. Huh,
The cost adjustment unit sets the variable cost to be larger as the value obtained by subtracting the cumulative value of the link cost of the first optimal route from the cumulative value of the link cost of the first sub-optimal route is smaller. Search device. The route search device according to claim 1 ,
The cost adjusting unit is
Of the first halfway route connecting the starting node set in the other device and the first optimum node that is a node included in the first optimum route, the first halfway route Identifying a first minimum cost midway path that has a minimum cumulative value of the link costs and constituting at least one first non-minimum cost midway path other than the first minimum cost halfway path,
The first non-minimum cost midway route and a route that overlaps the first optimum route in a route connecting the first optimum node and the destination node set in the other device. A route search device that sets a route connecting the destination node to the destination node as the first sub-optimal route. The route search device according to claim 1 or 2, wherein
The route search unit includes a second optimum route having a minimum cumulative value of the link costs constituting the second movement route, and the link of the second optimum route among the second movement routes. A route search device that searches for at least one second sub-optimal route having a cumulative value of the link cost equal to or less than a value obtained by adding a second allowable cost to a cumulative value of cost. The route search device according to claim 3 ,
The route search unit
Of the second halfway route connecting the departure node set by the point setting unit and the second optimum node that is a node included in the second optimum route, the second halfway route is Identifying a second minimum cost midway path that constitutes a cumulative value of the link costs that is the minimum and at least one second non-minimum cost midway path other than the second minimum cost midway path;
Is composed of a front Stories second non-minimum cost middle path, a path which overlaps with the second best path in the path connecting the nodes of the second best node and the point setting unit is set destination, A route search device that sets a route connecting the departure node to the destination node as the second sub-optimal route. Using a storage device comprising a data storage unit for storing network information for specifying a plurality of nodes on the network, a plurality of links, and a link cost set for each of the plurality of links, two on the network A route search method for searching for a route connecting two nodes,
Obtaining information identifying a starting node and a destination node set in at least one other device;
The cumulative value of the link costs of the links constituting the first movement path among the plurality of first movement paths connecting the starting node and the destination node set in the other device is the smallest. A cumulative value of the link cost of the first optimal route, and a cumulative value of the link cost equal to or less than a value obtained by adding a first allowable cost to the cumulative value of the link cost of the first optimal route. The variable cost set for each link based on the cumulative value of the link cost of the first sub-optimal route is used as the link cost of the link constituting the first optimum route and the first sub-optimal route. Adjusting the link cost of the network information stored in the data storage unit by adding to
Setting a departure node and a destination node;
Using the network information link cost is adjusted, e Bei and a step of searching at least one second movement path connecting the set of departure node and the destination node,
In the step of adjusting the link cost, the variable cost is set to be larger as the value obtained by subtracting the cumulative value of the link cost of the first optimal route from the cumulative value of the link cost of the first sub-optimal route is smaller. A route search method.

Images