JP5221470B2 - Route searching apparatus, method and program - Google Patents

Description

  The present invention relates to route search using a computer.

  There is a so-called route search technique for calculating an optimum route from a specified starting point and destination in the field of web services on the Internet, car navigation devices, and the like. Route search is based on network data that represents the network structure of the road, using algorithms such as the Dijkstra method and the A * (A star) method to create a plurality of possible candidates and select the optimal route. It is what you want. Recently, discount services according to time zones (for example, ETC discounts) have been implemented on toll roads such as expressways, and route search technology considering these discounts has also been proposed.

  For example, in the case of immediately before the discount time zone, an option of taking a break somewhere and waiting for the time can be considered. In this regard, there are multiple proposals to search for routes based on the entered departure time and inform the information such as the break time and service area for that when the discounted time zone of the toll road is close to the time zone likely to pass there Exists (see, for example, Patent Documents 1, 2, and 3).

JP 2007-114008 A JP 2007-178220 A JP 2008-157732 A JP 2001-264097 A

  The pros and cons of incorporating a break into the process and waiting for the discount period as described above are not uniform depending on the user, time, and circumstances, but with conventional technology, setting and adjustment of the criteria for determining whether to incorporate a break is a discount. It was practically difficult because it was related to the profit balance between the monetary profit and the non-monetary factor break. In particular, the Dijkstra method and the A * method are to obtain the shortest route in principle based on the cost such as the required travel time set for a link representing a road section. When searching for other routes, there is a problem that it is difficult to set detailed conditions. In particular, the technique of Patent Document 3 has a problem that it is indispensable to input detailed settings such as a driver's break interval in addition to the departure point, the destination, and the departure time.

  Further, in a proposal for generating a plurality of routes based on the link cost of the network and adding a non-link cost such as an expressway or labor cost to the total cost (refer to Patent Document 4), the route based on the link cost is used. Cost elements such as tolls can be added, but there is a problem that calculation time is required because it is necessary to obtain multiple routes, and it is not assumed that break time is included as non-link cost It was not related to the above problem.

  The present invention solves the above-mentioned problems, and its purpose is to search for an optimal route by converting the total cost including time into a monetary amount in a route search, and to calculate a unit price per hour at the time of monetary conversion with a discount rate and a break. By varying based on the allowable time, a route that best suits the user and the situation is provided.

Based on the above object, according to one embodiment of the present invention, a computer presents an optimum route based on network data representing a network structure of a road and discount data representing a discount rate for each time zone of a toll road. A route search device for receiving a search condition including a departure point, a destination, and a departure time; a tolerance value setting unit for receiving a setting of a break allowable time; and Total when the discount rate is applied by including a break allowable time in the required time from the discount data corresponding to the straight line distance, the break allowable time and the departure time, and a straight line distance calculating means for calculating a straight line distance costs and the total cost in the absence of the break allowable time the application of the discount rate is not included in the required time, the unit price calculating means but to calculate the hourly rates to be substantially balanced, before It is the same route from the departure point to the destination, a route subject to the discount rate by incorporating assumption breaks length not exceeding the break allowable time, the path that does not incorporate the assumption breaks Route calculation means for searching and calculating the optimum route, which is the route with the minimum cost, by converting the cost into an amount of money using the unit price per hour, and a route for outputting the optimum route obtained by the search calculation Output means.

As an aspect captured from the viewpoint of the method, the computer presents an optimal route based on network data representing the network structure of the road and discount data representing the discount rate for each time zone of the toll road. A route search method for receiving a search condition including a departure point, a destination, and a departure time; a tolerance setting step for accepting a setting of a break allowable time; and A linear distance calculating step for calculating a straight line distance, and a total when there is an application of the discount rate including a break allowable time in a required time from the discount data according to the straight line distance, the break allowable time and the departure time The unit price of time or the balance of the cost and the total cost when the discount rate is not applied without including the break allowable time in the required time. Times and bids calculating step of calculating the hourly rate rounded to units in increments of a predetermined unit price, said the same route from the departure point to the destination, the break allowable length of the assumed resting time not exceeding the time The route having the minimum cost by converting the cost into a monetary amount using the unit price of time and comparing the route that receives the discount rate by incorporating the cost and the route that does not incorporate the assumed break time The computer executes a route calculation step for searching for an optimum route and a route output step for outputting the optimum route obtained by the search calculation.

As an aspect of capturing the above aspect from the viewpoint of a computer program, an optimal route is calculated based on network data representing a network structure of a road and discount data representing a discount rate for each time zone of a toll road. A route search program that presents a condition reception step for receiving an input of search conditions including a departure place, a destination, and a departure time by controlling the computer; From the value setting step, a linear distance calculation step for calculating a linear distance between the departure point and the destination, the linear distance, the allowable break time, and the discount data according to the departure time, the allowable break time is calculated as the required time. The total cost when the discount rate is applied, and the time allowed for the break And bids calculating step of calculating the total cost in the absence of application of the discount rate, the hourly rate rounded to units of predetermined increments and the time unit price or hourly rates to balance to balance not including, the from the departure point The cost for the same route to the destination, the route that is applied with the discount rate by incorporating the assumed break time that does not exceed the break allowable time, and the route that does not incorporate the assumed break time A route calculation step for searching and calculating an optimal route that is the route with the minimum cost by converting to a monetary amount using an hourly unit price, a route output step for outputting the optimal route obtained by the search calculation, Is executed.

  In this way, the route search is performed by converting all costs including toll road fee and time into monetary amounts, so that the route can be discounted by shifting the time at breaks, and the required time and toll for the user It is possible to easily search for an optimal route that is balanced. In addition, by varying the unit price of time used as a route search reference based on the discount rate for each time zone and the allowable break time specified by the user, it best suits the given conditions, especially individual users and situations. It becomes possible to search and present a route. In particular, a balanced route selection that is not biased toward one of the options can be realized by using a unit price of time at which each cost of each option when taking a break and receiving a discount and when there is no break or discount is used.

  According to another aspect of the present invention, in any one of the above aspects, the unit price calculation means (step) multiplies the discount rate by a predetermined highway fee that serves as a reference, and divides it by the allowable break time, The hourly unit price is calculated.

  In this way, when computing power is limited, such as in-vehicle navigation devices and portable information devices, by calculating the unit price per hour with a simple calculation of multiplying the highway toll by the discount rate and dividing by the allowable break time However, processing results can be obtained quickly with a small load.

  It should be noted that other categories such as methods or programs corresponding to the above aspects and more specific aspects described below are also included in the present invention.

  As described above, according to the present invention, in route search, the entire route including time is converted into a monetary amount to search for an optimum route, and the unit price at the time of monetary conversion varies based on the discount rate and the allowable break time. By doing so, it becomes possible to provide a route most suitable for the user and the situation.

The functional block diagram which shows the structure of embodiment of this invention. The figure which illustrates each information (data) in the embodiment of the present invention. The flowchart which shows the process sequence in embodiment of this invention. The flowchart which shows processing procedures, such as hour unit price setting in embodiment of this invention. The graph which shows an example of hour unit price calculation in the embodiment of the present invention. The graph which shows the other example of the time unit price calculation in embodiment of this invention. The flowchart which shows the process sequence of the charge calculation for every path | route in embodiment of this invention. The output example which illustrates the route guidance in embodiment of this invention. The output example which illustrates cost calculation by amount conversion in the embodiment of the present invention. The output example which illustrates the cost calculation by the amount conversion in the middle of the path | route in embodiment of this invention.

  Next, modes for carrying out the present invention (referred to as “embodiments”) will be described with reference to the drawings. It should be noted that assumptions common to those already described in the background art and problems are omitted as appropriate.

[1. Constitution〕
In the present embodiment, as shown in FIG. 1 (configuration diagram), the computer is optimized based on network data representing a network structure of a road and discount data representing a discount rate for each time zone of a toll road. The present invention relates to a route searching device (hereinafter also referred to as “this device”) 1 realized as a web server for presenting a route.

  First, the present apparatus 1 (FIG. 1) has a general computer configuration including at least an arithmetic control unit 5 such as a CPU, a storage device 6 such as an external storage device (HDD or the like) or a main memory, and a communication network ( Communication means 7 (such as a LAN adapter) with N. Further, the user terminal T2 is a personal computer, a mobile phone terminal device, or the like, and accesses the present device 1 with a built-in web browser or the like.

  In the apparatus 1, a predetermined computer program (not shown) stored (installed) in advance in the storage device 6 controls the arithmetic control unit 5 so that elements (20, 30,...) Shown in FIG. ). Of these elements, information storage means can be realized in the storage device 6 in any format such as various databases (also referred to as “DB”), files, variables such as arrays, system setting values, and the like.

  Of the storage means, the network data storage means 65 stores in advance network data representing the network structure of the road. The road network structure is expressed by connecting links representing road sections with nodes (nodal points) representing road intersections, branches, inflection points, and the like. Since the link is defined by the start point and the end point for each direction in which the road section can pass, one link is set for the one-way road section and two links are set in the opposite directions for the two-way road section. The

  As illustrated in FIG. 2A, the network data representing such a network structure includes, for each link ID of a link representing a road section, a cost such as a start point node ID and an end point node ID, a time required for passing, and a road type. Information.

  Further, the discount data storage means 55 stores beforehand discount data representing a discount rate for each time zone of the toll road in an appropriate format such as an ETC discount fee table illustrated in FIG. The ETC discount fee table in FIG. 2 (2) is data in which “ETC discount rate”, which is a discount rate at the time of using ETC, is associated with each “day of the week / time zone”. Remarks may be added. Note that each means other than the storage means is a processing means that implements and executes the functions and operations of information processing described below.

[2. Action)
In the apparatus 1 configured as described above, as shown in the flowchart of FIG. 3, first, the route calculation means 60 stores network data as illustrated in FIG. Reading from the means 65 to a predetermined work area (step S10). Subsequently, the condition receiving means 20 receives an input of search conditions including the departure place, the destination, and the departure time from the user terminal T2 via the communication network N (step S20). The departure time may be configured to be supplemented with a time such as a few minutes on the premise that the user will not leave the route search result immediately after the route search result is provided without an explicit designation operation.

  The straight line distance calculation means 30 calculates a straight line distance between the departure point and the destination, sets this straight line distance as an initial value of the A * method (step S30), and sets the straight line distance that is the initial value. In addition, a cost (time, distance, fee) that is a so-called heuristic item corresponding to the lower limit estimated value in the A * method is set (step S40).

[2-1. (Calculation of hourly unit price)
Here, in the route calculation, the costs of a plurality of candidate routes are generally compared, and the candidate with the lowest cost is determined as the optimum route. When the charge, that is, the amount conversion of the present invention is used as the cost at this time (step S45). ), The unit price calculation means 50 calculates the unit price per hour used for converting the amount of route cost. Specifically, as this calculation, a table storing the distance unit price and the unit time unit for converting the cost into the amount is acquired. (Step S50).

  The processing procedure for acquiring the table in this way is shown in the flowchart of FIG. That is, first, the distance unit price for converting the distance into the amount is set (step S51). The unit price of distance assumes a fuel cost (fuel consumption) and is, for example, 10 yen / km.

  Subsequently, if the hourly unit price is not changed according to the user setting or selection (step S52: “NO”), a fixed initial value prepared in advance as the hourly unit price is set (step S53). When the hourly unit price is a variable value (step S52: “YES”), the allowable value setting unit 40 accepts the setting of the allowable break time, that is, the allowable value of the break time (step S54). The unit price for the hour is calculated and set according to the content (typically the discount rate) corresponding to the ETC discount time zone read from the discount data storage means 55 (step S55).

  Here, “unit price per hour” is calculated based on the above-mentioned discount distance data for the toll road that may be used for the route within the predetermined area from the starting point and the purpose. It is a unit price for the time at which the total cost when the discount rate is applied in the required time and the total cost when the discount rate is not applied without including the break allowable time is approximately balanced. This corresponds to the labor cost unit price.

[2-2. Example of obtaining the hourly unit price in a graph]
For example, the graph in FIG. 5 is simplified for the purpose of explanation of the route from “Nakatajima dune” in Hamamatsu to “Higashiyama Park” in Nagoya, and it travels mainly on the Tomei Expressway and has a mileage of 115 km. In the case of assuming a charge of 2600 yen and a running time of 75 minutes as an example, in the case of the hourly unit price on the horizontal axis, it represents how much the total cost on the vertical axis is.

  As the distance, a linear distance between the starting point and the destination is originally used. However, in order to simplify the explanation, it is assumed that the traveling distance is equal to the straight distance as it is with a substantially straight route. Also, the average hourly speed is unified to 1 km / 1 minute (60 km / h).

The total cost here (“C”) is
<Formula 1>
C = (distance x distance unit price) + (time x unit price) + highway toll

As the total cost, the thick solid line in FIG. 5 is a normal cost with no break time and no discount, the fine broken line is the cost for a 30% discount including a break time of 20 minutes, and the rough broken line is The cost in the case of 50% discount including the break time of 20 minutes is shown (the dashed line indicates the cost in the case of a uniform holiday discount of 1000 yen for reference).

  Of these, for example, the point B1 where the cost of a 30% discount after a break (fine broken line) and the normal cost without a break or discount (thick solid line) are approximately balanced is indicated by a white circle, but from there The hourly unit price indicated by the arrow pointing to indicates between 2000 yen and 2500 yen. Similarly, for a point B2 where the normal cost (thick solid line) breaks and costs 50% discount (coarse broken line) and the point B2 that is substantially balanced, the unit price per hour indicated by the downward arrow indicates a little less than 4000 yen.

  For these balances, various unit costs are substituted at appropriate intervals, and the total costs are actually calculated and compared sequentially, or a graph such as that shown in FIG. 5 is actually drawn based on the total costs. However, it can also be calculated simply by using the following calculation formula.

[2-3. Example of obtaining unit price per hour)
For example,

d: Distance (= required fraction)
g: Unit price for distance j: Unit price for hour (minutes)
k: Normal highway fare w: Discount rate r: Allowable break time

And `` total cost when there is an application of the discount rate including the break allowable time in the required time, and total cost when the discount rate is not applied without including the break allowable time in the required time, Is substantially balanced ”by placing the above formula 1 on both sides <Formula 2>
dg + dj + k = dg + (d + r) j + k (1-w)

It can be expressed as.

Expand each term by removing the term dg from both sides,
<Formula 3>
dj + k = dj + rj + k−kw

The terms dj and k are also erased from both sides, the right side rj is moved to the left side, and the negative sign is removed from both sides.
<Formula 4>
rj = kw

This means
<Formula 5>
Allowable break r × hour unit price j = highway normal fare k × discount rate w

In other words, it means that the labor cost for the break allowable time is balanced with the discount of the expressway normal fare, and both sides are divided by r,
<Formula 6>
j = kw / r

That is,
<Formula 7>
Unit price per hour j = normal highway fare k x discount rate w / break time r

  This is because when the computing power is limited, such as in-vehicle navigation devices and portable information devices, by calculating the unit price per hour with a simple calculation of multiplying the normal highway toll by the discount rate and dividing by the allowable break time However, it means that processing results can be obtained quickly with a small load.

For example, if the expressway normal fare k = 2600 yen, the discount rate w = 0.3, and the break allowable time r = 20 (minutes) as the conditions of the graph (point B1) in FIG.
<Formula 8>
Unit price j = 2600 × 0.3 / 20 = 39 yen (per minute)

  This hourly unit price (39 yen / minute) is 2340 yen when converted to hourly wage per 60 minutes, and substantially matches the point B1 in the graph of FIG. Further, when the discount rate w = 0.5, it is 3900 yen, which substantially coincides with the point B2. The time unit price calculated in this way does not need to be used as it is. For example, an appropriate unit of time can be used according to various circumstances such as consideration of the characteristics of the A * method that can be used for the cost of the remaining route. It can be used by rounding, for example, by rounding it down to a good number (for example, 2250 yen, 3800 yen, 4000 yen, etc.) that is easy to handle.

  FIG. 6 is a graph in the same condition as FIG. 5 except that the break allowable time is halved to 10 minutes. The time unit price calculated by Equation 7 is 4680 yen corresponding to the point B3, The thing corresponding to the point B4 is 7800 yen, and these can also be used by rounding down to 4700 yen, 7700 yen or the like.

[2-4. (Route calculation and output)
Next, the route calculation means 60 searches and calculates the optimum route (FIG. 3: step S60), and the route output means 70 acquires the optimum route obtained by the search calculation as a search result (step S70) and outputs it (step S70). S75). And in this apparatus 1, when the route calculation means 60 performs search calculation of the optimal route (including the case of recalculation due to route deviation, etc.), it takes a break until the break allowable time (20 minutes, 10 minutes, etc.). For each route including the route to which the discount rate (30%, 50%, etc.) is applied by incorporating it, the cost (time, distance, fee) is converted into an amount using the hourly unit price and compared. Search for the optimal route.

  More specifically, in the search calculation of the optimum route, as shown in the flowchart of FIG. 7, when the route includes a toll road (step S61: “YES”), the discount is performed with the assumed travel time in the first place. If there is (step S62: “YES”), the fee is calculated from a predetermined ETC discount fee table (FIG. 2 (2)) (step S67).

  On the other hand, if the route includes a toll road (step S61: “YES”), but the discount is not applied with the assumed travel time (step S62: “NO”), a break within the allowable break time is incorporated. If the travel time is shifted, it is determined whether a discount is applied (step S63). If there is a discount applied within the break allowable time (step S63: “YES”) and there is a break facility in the route (step S64: “YES”), the travel time of the toll road is discounted. The time required for a break to be adapted to the time zone is calculated, the break time is added to the required time (step S65), and the fee is calculated from a predetermined ETC discount fee table (FIG. 2 (2)) (step S67). ).

  If there is no discount application even if the break allowable time is shifted (step S63: “NO”), if there is a break application within the allowable break time (step S63: “YES”), there is no break facility in the route (step S64: “NO”) calculates a road fee using a normal fee table similar to the conventional route search (step S66). Such a normal charge table is not shown, but a table according to the conventional method may be used. The resting facility is not limited to the so-called service area (SA) or parking area (PA) on the toll road, but may be a restaurant, convenience store, shopping center, scenic spot or the like other than the toll road.

  The specific method for determining the rest facility is free. For example, a service area (SA), a parking area (PA), a restaurant such as a family restaurant, a general road rest facility such as “Michi no Eki”, a convenience store, For POIs (facility information) such as shopping centers and scenic spots, if the type of business to be determined from existing facility information data is a predetermined type, it may be considered that a rest can be taken from 5 to 60 minutes. The data for each facility information may be used by appropriately providing attributes such as whether breaks are possible or assumed break times, or may be provided with dedicated information storage means that associates such attributes with information on each rest facility Good.

[2-5. Example of route search considering breaks)
Here, the same example as assumed in the graph of FIG. 5 (“Nakadajima dune” in Hamamatsu → “Higashiyama Park” in Nagoya, mileage 115 km, normal highway fare 2600 yen, travel time 75 minutes, break allowed An example in which a route is searched and guided in consideration of a break is shown. For example, when judging whether to apply a discount based on the passage time at the exit toll gate, if you depart at 15:30 and run without a break, you will see a commuter discount (Fig. 2 (2)) as shown in Fig. 8 (1). ) Since leaving Nagoya IC (interchange) at 16:59 just before 17:00 in the time zone, the high-speed toll is 2600 yen, a normal rate without discount. A route that does not include a break is referred to as “normal travel” or “no break”.

  On the other hand, as shown in Fig. 8 (2), if you take a 15-minute break (boxed in the figure) around the outbound Togo PA (parking area) on the way even if you depart at the same time (15:30) At the exit toll gate (Nagoya IC), the commuting discount time zone is past 17:00 (17:14), so the high-speed toll is 1300 yen with a 50% discount (underlined in the figure). A route including this break will be referred to as “with break”.

  In calculating the route search, the cost calculation for determining which of these two candidates “normal driving” and “with a break” should be guided to the user is performed according to the above-mentioned formula 1, FIG. Compared to “No break”, “With break” takes an extra 15 minutes, but the total cost of money conversion is 8450 yen and 300 yen cheaper, so “With break” (Fig. 9 (2 )) Is selected to guide the user.

The cost calculation as described above may be performed not only at the time of departure but also according to a user operation or the like in the middle of the route. Here, since the route calculation algorithm is the A * method, each route selection in the middle of calculation is <Formula 9>
(A. Actual cost to a certain point) + (b. Remaining cost to the destination)

Is determined to be minimum. Where <Equation 10>
(A) Cost actually taken to a certain point = Distance from starting point to certain point × Distance unit price + Time taken from starting point to certain point × Unit price per hour + Toll road fee to that point

However, here, the toll road charge when on the toll road is calculated by the nearest IC (which is a toll gate in this case) that gets off next. Also,
<Formula 11>
(B) Remaining cost to destination = Remaining distance to destination x Distance unit price + Estimated remaining time to destination x Unit price per hour

Thus, the route selection may be a smaller value, so the remaining cost here does not include the toll road fee.

  An example in which such calculation is performed at the Tomei Miyoshi IC at a point 100 km along the route is as shown in FIG. In this case as well, if there is a resting facility on the way, there will be a break and the passage time of the exit toll gate will be advanced, “with break” (FIG. 10 (2)) compared to “without break” (FIG. 10 (1)). , 15 minutes extra time, but the cost to the 100km point is cheaper (Figure 10 (2): 2350 yen ⇒ 1200 yen) and the total cost of money conversion is also cheaper (Figure 10 (2): 7350 yen) ⇒ 7200 yen (underlined part)), “There is a break” (FIG. 10 (2)) is selected to guide the user.

  When using the ferry route, if the route includes a link indicating the ferry route, the waiting time and required time are obtained from the ferry information data indicating the departure time prepared in advance, and the waiting time and Add the cost of the required time to the cost of the route. In addition, if the cost criterion is not time / distance, but the total cost converted to the amount of money as described above, the fee for the applicable car model of the ferry is added to the amount of the route, and The target of comparison and selection may be used.

[3. effect〕
As described above, in this embodiment, the route search is performed by converting all costs including the toll road fee and time into the amount of money, so that the user can select a route to receive a discount by shifting the time at a break. Therefore, it is possible to easily search for an optimum route in which the required time and toll are balanced. In addition, by changing the unit price of time for the route search based on the discount rate for each time zone and the allowable break time specified by the user, it is possible to meet the given conditions, especially for individual users and situations during use. It becomes possible to search and present the most suitable route.

  In particular, by using a unit price per hour where the costs of each option when taking a break and when there is no break or discount are approximately balanced, it is possible to realize a balanced route selection that is not biased to one option. .

[4. Other embodiments]
In addition, said each embodiment is only an illustration, and this invention includes what is illustrated below and other embodiment other than that. For example, in the present invention, elements such as each means may be realized not only by an arithmetic control unit of a computer but also by an electronic circuit based on wired logic or the like, or a non-Neumann type information processing mechanism that will appear in the future. Further, each configuration diagram, data diagram, flowchart diagram, and the like are merely examples, and the presence / absence of each element, its order, specific contents, and the like can be changed as appropriate.

  For example, this device can be realized by a plurality of server devices, or can be grasped as a system of the present invention including each terminal, or an external platform can be identified by API (Application Program Interface) or network computing depending on functions. The configuration can be changed flexibly, for example, by calling. Moreover, although the said embodiment presupposed the client server system of the communication network, this invention may be stand-alone like a car navigation apparatus.

  Furthermore, the present invention can be realized as a computer program installed and used on various computers represented by personal computers and so-called smartphones, and of course, such programs can be downloaded and provided for free of charge. Websites and servers to be included are also included in the embodiments of the present invention.

T2 User terminal 1 Route search device 5 Arithmetic control unit 6 Storage device 7 Communication unit 20 Condition receiving unit 30 Straight line distance calculation unit 40 Allowable value setting unit 50 Unit price calculation unit 55 Discount data storage unit 60 Route calculation unit 65 Network data storage unit 70 Route output means

Claims (4)

A route search device for presenting an optimal route based on network data representing a network structure of a road and discount data representing a discount rate for each time zone of a toll road,
Condition accepting means for accepting input of search conditions including a departure place, a destination, and a departure time;
Tolerance setting means for accepting the setting of the break tolerance time,
A linear distance calculating means for calculating a linear distance between the starting point and the destination;
From the discount data according to the linear distance, the break allowable time, and the departure time, the total cost when the discount rate is applied including the break allowable time in the required time, and the break allowable time as the required time. A unit price calculation means for calculating a unit price of time in which the total cost when not including the discount rate is not applied and the unit price of time balanced or the unit price of time balanced is rounded to a predetermined unit;
The same route from the starting point to the destination, the route receiving the application of the discount rate by incorporating the assumed break time having a length not exceeding the break allowable time, and the route not incorporating the assumed break time A route calculation means for searching for and calculating an optimal route that is the route with the minimum cost by converting the cost into an amount using the hourly unit price and comparing the cost,
Route output means for outputting the optimum route obtained by the search calculation;
A route search device characterized by comprising:   2. The route search according to claim 1, wherein the unit price calculation means calculates the unit price per hour by multiplying a predetermined highway fare to be a reference by the discount rate and dividing by the allowable break time. apparatus. A route search method in which a computer presents an optimum route based on network data representing a network structure of a road and discount data representing a discount rate for each time zone of a toll road,
A condition receiving step for receiving an input of search conditions including a departure place, a destination, and a departure time;
A tolerance setting step for accepting a setting of a break tolerance time;
A linear distance calculating step for calculating a linear distance between the starting point and the destination;
From the discount data according to the linear distance, the break allowable time, and the departure time, the total cost when the discount rate is applied including the break allowable time in the required time, and the break allowable time as the required time. A unit price calculation step of calculating a unit price of time in which the total cost when the discount rate is not included and the balance is not applied, or a unit price of the unit of time in which the unit price of equilibrium is rounded to a predetermined unit;
The same route from the starting point to the destination, the route receiving the application of the discount rate by incorporating the assumed break time having a length not exceeding the break allowable time, and the route not incorporating the assumed break time A route calculation step of searching for and calculating an optimal route that is the route with the minimum cost by converting the cost into an amount using the hourly unit price and comparing the cost,
A route output step for outputting the optimum route obtained by the search calculation;
The route search method, wherein the computer executes A route search program for causing a computer to present an optimal route based on network data representing a road network structure and discount data representing a discount rate for each time zone of a toll road,
The program controls the computer,
A condition receiving step for receiving an input of search conditions including a departure place, a destination, and a departure time;
A tolerance setting step for accepting a setting of a break tolerance time;
A linear distance calculating step for calculating a linear distance between the starting point and the destination;
From the discount data according to the linear distance, the break allowable time, and the departure time, the total cost when the discount rate is applied including the break allowable time in the required time, and the break allowable time as the required time. A unit price calculation step of calculating a unit price of time in which the total cost when the discount rate is not included and the balance is not applied, or a unit price of the unit of time in which the unit price of equilibrium is rounded to a predetermined unit;
The same route from the starting point to the destination, the route receiving the application of the discount rate by incorporating the assumed break time having a length not exceeding the break allowable time, and the route not incorporating the assumed break time A route calculation step of searching for and calculating an optimal route that is the route with the minimum cost by converting the cost into an amount using the hourly unit price and comparing the cost,
A route output step for outputting the optimum route obtained by the search calculation;
A route search program characterized by causing

Images