JP3019015B2 - Multi-destination route assembly device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multi-destination route assembling apparatus for finding a route that can make a quick turn around a plurality of destinations specified by a user.

[0002]

2. Description of the Related Art In recent years, a car navigation system that obtains a route from a current position to a destination and combines and displays the route on a map has been increasingly used.
Conventional car navigation systems generally seek directions to one destination specified by a user. For this reason, when it is necessary to go all around a plurality of destinations in the shortest time, the following is necessary.

[0003] First, the user himself / herself determines the order in which to go in consideration of the order in which the required time can be minimized if the user goes around the destination. After that, the first destination to be visited is input to the car navigation system. As a result, the car navigation system obtains a route from the current position to the first destination, and combines and displays the route on the map. When the directions to the first destination are displayed, the user moves to the first destination according to the directions. Thereafter, the user inputs the second destination to the car navigation system, and moves to the second destination according to the displayed route. Hereinafter, the user repeats the same operation until the user goes around all the destinations.

[0004]

As described above, the conventional car navigation system merely seeks a route to a single input destination, so that the user can travel around a plurality of destinations in the shortest time. Is necessary, the user himself must decide the order in which to go to the destination in consideration of the fact, and there is a problem that the user is burdened. There was a problem that the destination could not be reached. Incidentally, Japanese Patent Laid-Open No. 7-
No. 72234 discloses that, even when the position of the nearest parking lot is not known, the current position is transmitted from the car navigation system to the guide base station so that the route to the nearest parking lot can be displayed. A technique is described in which a base station searches for an optimum parking lot at a current position, obtains a route to the searched parking lot, and sends the route to a car navigation system. However, this technique also cannot solve the above-mentioned problem because it only seeks directions to a single destination.

[0005] Therefore, an object of the present invention is to provide a plurality of destinations.
Destinations, and destinations for which the time limit for arrival is specified
If there is a destination, the destination
Arriving before the specified arrival time limit
And travel around all destinations in the shortest possible time
For directions that can be done without burdening the user
It is an object of the present invention to provide a multi-destination route assembling apparatus which can be used .

[0006]

Since the present invention SUMMARY OF THE INVENTION The To achieve the above object, a departure point, destination input means for inputting in accordance with an instruction from the user a starting point and a plurality of destinations, the departure point
Departure time and departure destination
And the time limit for arrival at the destination according to the user's instruction.
Input means, a map information storage area in which map information is stored, a directions storage area in which directions are stored,
By inputting a departure place and a plurality of destinations from the departure place / destination input means, a route from the departure place to each of the destinations is obtained based on the map information, and each of the obtained directions is respectively obtained. Then, every time the starting point destination is specified, the distance from the specified starting point destination is determined.
All undetermined destinations for the starting destination
Route assembling means for determining a route based on the map information and determining a distance for each determined route;
By means the distance between said departure point and each said destination is
By being determined, each of the determined distances and the output
Arriving at each of the above destinations based on departure time and traveling speed
The expected time is determined, and then the route is assembled by the route assembling means.
Every time the distance between a point destination and each undetermined destination is determined
Next, the obtained distances and the arrival schedule at the starting point destination are described.
To each of the undetermined destinations based on the desired time and the traveling speed
Means for estimating the expected time of arrival of
Departure from said departure place at said departure time by means of time prediction
Expected arrival time at each of the above destinations at the time of arrival
The arrival limit within each of the obtained expected arrival times
Specify the expected arrival time corresponding to the destination where the time is specified
Check if the time limit has been passed
If there is, perform error processing.
Destinations with the shortest distance from the departure point among destinations
To the route assembling means to make the next starting point destination
And from the departure point to the destination with the shortest distance
Store the directions in the directions storage area, and then
The estimated time of arrival at each undetermined destination
Each time it is requested, of each of the obtained expected arrival times,
Estimated arrival time corresponding to the destination with specified arrival time limit
Check if the time has passed the specified arrival time limit.
If not, the start of each of the undetermined destinations
The undetermined destination with the shortest distance to the point destination is the next starting point
Instruct the route assembling means to be the destination
And the undetermined destination with the shortest distance from the start destination
Store the directions to the ground in the directions storage area,
The starting point in the latest instructions to the route assembling means
The destination that was ordered to be the destination and one time before it
The destination instructed to be the starting point destination by the instruction of
And the route between and is deleted from the route storage area,
To the destination that was instructed to be the starting destination one time before
To determine if there is an undetermined destination.
If a destination exists, the destination among the undetermined destinations
One time before the destination
The undetermined destination with the shortest distance between them is the next starting destination
To the route assembling means,
From the destination that instructed to be the starting point one time before
The route to the undetermined destination where the distance becomes the shortest is the route
If it is stored in the storage area and there is no undetermined destination,
For the starting destination of the destination where the undetermined destination does not exist,
Of undetermined destinations, the distance from the starting destination is
That the shortest undetermined destination is the next starting destination
Instructs the route assembling means and stores the route storage area.
Removed the latest directions between two locations stored in the area
And an undetermined destination having the shortest distance from the starting destination
And a condition discriminating means for storing a route to the vehicle.

[0007]

[0008]

[0009]

In the above configuration, when a departure place and a plurality of destinations are inputted from the departure place / destination input means, the route assembling means obtains a route from the departure place to each destination, Find the distance for each direction. Thereafter, the arrival time estimating means obtains an estimated time of arrival at each destination based on the distance of each route obtained by the route assembling means, the departure time, and the moving speed. Next, the condition determining unit determines whether the expected arrival time corresponding to the destination having the specified arrival time limit has passed the specified arrival time among the expected arrival times obtained by the arrival time estimating means. Find out. If it has not passed, instruct the route assembling means to set the destination having the shortest distance from the departure point to the departure point as the next start point destination, and to indicate the distance from the departure point. Stores the route to the shortest destination in the route storage area, and performs error processing if it has passed.

The route assembling means, when the starting destination is designated by the condition judging means, all the undetermined destinations for the starting destination from the starting destination (the driving directions from the starting destination are stored in the driving direction storage area). A route to a destination which has never been stored and a route to which the route to the destination is not stored in the route storage area) and a distance of the route are calculated. Thereafter, the arrival time estimating means calculates the estimated time of arrival at each undetermined destination based on each distance obtained by the route assembling means, the estimated time of arrival at the starting destination already determined, and the traveling speed. Ask for.

Next, the condition discriminating means designates an expected arrival time corresponding to the destination having the designated arrival time limit among the estimated arrival times at the undetermined destinations obtained by the arrival time estimating means. Check if the arrival time limit has passed. If it is not past, while instructing the route assembling means to make the undetermined destination having the shortest distance to the starting destination among the undetermined destinations the next starting destination, The route between the starting destination and the undetermined destination having the shortest distance is stored in the route storage area.

If there is an estimated arrival time past the designated arrival time limit, the latest instruction to the route assembling means indicates that the destination instructed to be the starting point destination and the destination which is instructed to be the starting destination. The route between the destination and the destination instructed to be the start destination by the previous instruction is deleted from the route storage area. Check whether a confirmed destination exists. If there is an undetermined destination, the undetermined destination whose distance from the destination that has been instructed to be the start destination one time earlier is shortest among the undetermined destinations is determined. To the next starting destination to the route assembling means, and the route from the destination instructed to be the starting destination one time before to the undetermined destination where the distance becomes the shortest is determined. Store in the route storage area. Also,
If there is no undetermined destination, the undetermined destination with the shortest distance from the above-mentioned starting destination is the next starting point among the undetermined destinations of the destination where no undetermined destination exists. After instructing the route assembling means to be the destination and deleting the route between the latest two points stored in the route storage area, the undetermined destination having the shortest distance from the starting point destination Store directions to

Further, according to the present invention, when there are a plurality of destinations, and there is a destination for which the arrival time limit and the stop time are designated, even if the stop is performed at the destination for the designated stop time. For destinations for which the arrival time limit is specified, in order to be able to arrive before the specified arrival time limit, and to obtain a route that can travel all destinations in the shortest possible time The condition input means includes a destination for which a stop time is specified, and a stop time at the destination in accordance with a user's instruction, wherein the arrival time estimating means includes: The distance between the departure place and each of the destinations is obtained, and the estimated time of arrival at each of the destinations is obtained based on each of the obtained distances, the departure time, and the moving speed. , Each time the recording order assembling means obtains the distance between the starting destination and each undetermined destination for the starting destination, the obtained distances, the estimated arrival time at the starting destination, the traveling speed, And an estimated time of arrival at each of the undetermined destinations based on the stop time input from the condition input means.

In the above configuration, when the distance between the starting destination and each of the undetermined destinations with respect to the starting destination is determined by the route assembling means, the arrival time estimating means determines the calculated distance. And an estimated time of arrival at each undetermined destination based on the estimated time of arrival at the starting point destination, the moving speed, and the stop time input from the condition input means. The condition determining means performs the same processing based on the estimated arrival time in consideration of the stop time.

[0016]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 explains the technology on which the present invention is based .
FIG. 3 is a block diagram for the input unit 1a
And an optimal route assembling unit 3a and a route output unit 4.

The input unit 1a includes a departure place / destination input means 11 for inputting a departure place and a plurality of destinations in accordance with a user's instruction.

The storage unit 2a stores a departure / destination storage area 2
1, a map information storage area 22, a distance storage area 23,
And a route storage area 24.

The departure place / destination storage area 21 stores the departure place inputted from the departure place / destination input means 11 and a plurality of destinations. The map information storage area 22 stores map information in advance. The distance storage area 23 stores the distance between the departure place and each destination and the distance between the destinations determined by the optimum route assembling unit 3a. The route storage area 24 stores a route from an origin to each destination by the optimal route assembling unit 3a.

The optimal route assembling section 3a includes a route assembling means 31.
a and condition determining means 32a.

The route assembling means 31a instructs the function of obtaining the directions from the departure place to the respective destinations based on the map information stored in the map information storage area 22 or the starting point by the condition judging means 32a. A function to find a route to each destination (unprocessed destination) for which the route from the destination (starting point destination) to the destination has not yet been determined, and a distance storage by finding the distance of each found route It has a function of storing data in the area 23 and the like.

The condition discriminating means 32a includes the route assembling means 31.
The function of storing, in the route storage area 24, the route when the destination having the shortest distance among the destinations for which the distance from the departure place has been obtained by a, as the next destination, The route assembling means 31 makes the shortest destination the starting point destination.
Among the unprocessed destinations whose distance to the starting point destination is determined by the function to instruct a or the route assembling means 31a, the unprocessed destination having the shortest distance is set as the next destination. It has a function of storing the route at the time in the route storage area 24 and a function of instructing the route assembling means 31a to set the unprocessed destination having the shortest distance as the next start point destination.

FIG. 2 is a flowchart showing a processing example of the optimum route assembling section 3a. The operation will be described below with reference to the drawings.

In order to obtain a route that goes around a plurality of destinations in the shortest time, the user inputs a departure place and a plurality of destinations from the departure place / destination input means 11. Departure place entered,
The plurality of destinations are stored in the departure / destination storage area 21. Now, for example, if A is inputted as the departure place and B, C, D and E are inputted as the destinations, the contents of the departure place / destination storage area 21 are as shown in FIG.

When the information as shown in FIG. 3 is stored in the departure / destination storage area 21, the route assembling means 31a outputs the destinations B and D stored in the departure / destination storage area 21.
An unprocessed destination is selected from C, D, and E, and one of them is noted (S1, FIG. 1). At first, all the destinations B, C, D and E are unprocessed destinations.

Thereafter, the route assembling means 31a returns to the starting point A
, A route A → B to an unprocessed destination of interest (for example, B) is obtained based on the map information stored in the map information storage area 22 (S3). Thereafter, the route assembling means 31a determines the distance Lab of the route A → B determined in S3, and stores the determined distance Lab and the destination B in the distance storage area 23.
(S4). Hereinafter, the route assembling means 31a repeats the above-described processing of S1 to S4 until there is no unprocessed unprocessed destination (until S2 becomes NO).

By performing the above processing, the destinations B, C, and D are stored in the distance storage area 23 as shown in FIG.
D, E and distances Lab, Lac, Lad, Lae between departure point A and destinations B, C, D, E are stored in association with each other.

Thereafter, the condition determining means 32a refers to the distance storage area 23 and selects the destination having the shortest distance from the departure point A (S5). Now, for example, if Lac is the shortest, the condition determining means 32a selects the unprocessed destination C. Thereafter, the condition determining means 32a
The route assembling means 31a is instructed to obtain a route from the departure point A to the selected destination C. When the route assembling means 31a obtains the route A → C in accordance with the instruction, the route assembling is stored in the route storage area 24. It is stored (S6, S7). Thus, the contents of the route storage area 24 are as shown in FIG.

When the processing in S7 is completed, the condition determining means 3
2a, after initializing the distance storage area 23 (S9),
Instruct the route assembling means 31a to set the destination C whose distance selected in Step 5 is the shortest as the start destination (S1).
0).

When this instruction is received, the route assembling means 31a
Focuses on one of the unprocessed destinations (S11). In this example, since the route to the destination C has already been determined and stored in the route storage area 24, attention should be paid to one of the remaining three unprocessed destinations B, D, and E. become. Now, for example, if attention is paid to the unprocessed destination B in S11, the route assembling means 31a determines in S13 that the current destination is not focused from the starting destination C specified by the condition determination means 32a. Directions C to processing destination B
→ Find B, and in the next S14, the distance Lc of the route C → B
b is obtained, and the distance Lcb and the destination B are stored in the distance storage area 23. Hereinafter, the route assembling means 31a
Until no unprocessed unprocessed destinations remain (S12 is N
Until it becomes O), S11 to S14 are repeated. As a result, the distance storage area 23 stores the destinations B, D, and E, and the distances Lcb, L from the starting destination C to each of the destinations B, D, and E.
cd and Lce are stored in association with each other.

If S12 is NO, the condition discriminating means 32
A refers to the distance storage area 23 and selects the destination having the shortest distance from the destinations B, D, and E (S5). Now, for example, assuming that the distance Lcb stored corresponding to the destination B is the shortest, the condition determining means 32a selects the destination B. Thereafter, the condition determining means 32a
It instructs the route assembling means 31a to obtain a route from the starting point destination C to the selected destination B, and in accordance with this instruction, the route assembling means 31a moves from the starting point destination to the destination B.
When the route C → B is obtained, the route is stored in the route storage area 2
4 (S7).

The above processing is repeated until there is no unprocessed destination (until S8 becomes NO).

When there are no more destinations for which the route has not been determined (NO in S8), the condition determining means 32a
Starts the route output unit 4 (S15). This allows
The route output unit 4 combines and displays the routes stored in the route storage area 24 on a map.

Next, a first embodiment of the present invention will be described.

Referring to FIG. 6, the first embodiment of the present invention includes an input unit 1b, a storage unit 2b, an optimum route assembling unit 3b, and a route output unit 4.

The input unit 1b includes a moving method input unit 12 and an arrival time input unit 13 in addition to the configuration of the input unit 1a shown in FIG.

The moving method input means 12 has a function of inputting a method of moving around a destination according to a user's instruction. Here, examples of the moving method include walking, a car, a motorcycle, and a bicycle.

The arrival time input means 13 has a function of inputting a departure time of a departure place in accordance with a user's instruction, and of inputting a destination which must arrive by a predetermined time and an arrival limit time there. .

The storage unit 2b stores a departure / destination storage area 2
1, a map information storage area 22, a route storage area 24,
It has a moving speed storage area 25, an expected distance / arrival time storage area 26, and an arrival limit time storage area 27.

The same information as described above is stored in the departure / destination storage area 21, the map information storage area 22, and the route storage area 24.

The moving speed storage area 25 stores the moving speed for each moving method. The distance / expected arrival time storage area 26 stores the distance between the two points and the estimated arrival time at the destination obtained by the optimum route assembling unit 3b. The arrival limit time storage area 27 stores the departure time from the departure place and the arrival limit time to the destination specified by the user.

The optimal route assembling section 3b includes a route assembling means 31.
b, condition determining means 32b, and moving speed input means 33
And arrival time estimating means 34.

The route assembling means 31b has a function of obtaining a route from the departure place to each destination based on the map information stored in the map information storage area 22, and a starting destination designated by the condition determining means 32b. And a function of obtaining a route to each undetermined destination with respect to the starting point destination, a function of obtaining a distance of each obtained route, and storing the distance in the estimated distance / arrival time storage area 26. Here, the undetermined destination is a destination whose route from the starting point destination has never been stored in the route storage area 24, and the route up to the destination is not stored in the route storage area 24. The destination.

The moving speed input means 33 has a function of inputting the moving speed corresponding to the moving method input from the moving method input means 12 from the moving speed storage area 25.

The arrival time estimating means 34 determines each of the distances based on the distance between the starting point destination and the undetermined destination, the estimated time of arrival at the starting point destination, and the moving speed input by the moving speed input means 33. It has a function of obtaining an estimated time of arrival at an undetermined destination.

If the estimated time of arrival at the undetermined destination determined by the arrival time estimating means 34 has not passed the arrival limit time specified by the user, the condition determining means 32b determines whether It instructs the route assembling means 31b that the undetermined destination having the shortest distance from the start destination is set as the next start destination, and the route from the start destination to the undetermined destination having the shortest distance is determined. If there is a function to store the route in the route storage area 24, or if there is an estimated time of arrival at the undetermined destination determined by the arrival time estimating means 34 that exceeds the arrival time limit specified by the user, And a function of instructing the route assembling means 31b to set the destination designated as the start point by the instruction one time before the latest instruction again as the start point destination.

FIGS. 7 and 8 are flowcharts showing a processing example of the optimum route assembling section 3b. The operation will be described below with reference to the drawings.

First, the user inputs a departure place and a plurality of destinations from the departure place / destination input means 11. The input departure place and a plurality of destinations are the departure place / destination storage area 2
1 is stored. For example, if A is input as a departure place and B, C, D, and E are input as destinations, the contents of the departure place / destination storage area 21 are as shown in FIG.

Next, the user enters the arrival time input means 13
From, the user inputs the departure time to depart from the departure place A, and if there is a destination that must arrive by a predetermined time, inputs the destination and the arrival limit time. The input departure time, destination, and arrival limit time are stored in the arrival limit time storage area 27. For example, if "10:00" is input as a departure time, D is input as a destination that must arrive by a predetermined time, and "11:00" is input as a time limit for arrival at destination D, The contents of the arrival limit time storage area 27 are as shown in FIG.

Thereafter, the user enters the moving method input means 12
Enter the moving method from.

When a moving method is input from the moving method input means 12, the moving speed input means 33 inputs a moving speed corresponding to the moving method input from the moving speed storage area 25. Now, for example, “walk” is input as the moving method from the moving method input unit 12 and the moving speed storage area 25 is input.
Travel speed "5km / h" corresponding to the travel method "walk"
Is stored, the moving speed input means 33
The moving speed “5 km / h” is input from the moving speed storage area 25, and the input moving speed “5 km / h” is passed to the arrival time predicting means 34 (FIG. 7, S21).

Thereafter, the route assembling means 31b determines whether or not the
Destinations B, C, stored in the destination storage area 21
An undetermined destination is selected from D and E, and attention is paid to one of them (S21). At first, all destinations B,
C, D, and E are undetermined destinations.

Next, the route assembling means 31b outputs the starting point A
, A route A → B to an undetermined destination (eg, B) of current interest is determined based on the map information stored in the map information storage area 22 (S24). Thereafter, the route assembling means 31b obtains the distance of the route A → B obtained in S24, and stores the obtained distance, the destination B, and the starting point (departure point A) in the distance / arrival expected time storage area 26 (S25). ). Hereinafter, the route assembling means 31b performs the above-described S2 until there is no undetermined destination that has not been noticed (until S23 becomes NO).
Steps 2 to S25 are repeated.

By performing the above processing, the distance
In the expected arrival time storage area 26, as shown in FIG.
Distances “2.5”, “2.” between the starting point A, the destinations B, C, D, and E, and the departure point A and each of the destinations B, C, D, and E.
Information including “0”, “3.5”, and “4.0” is stored.

When the distance between the departure point A and each of the destinations B, C, D and E is stored in the distance / arrival expected time storage area 26, the arrival time estimation means 34 has already entered the moving speed input means. 33 and the departure point A stored in the estimated distance / arrival time storage area 26.
And the departure times “10: 0” stored in the arrival time limit storage area 27, and the distances between the destinations B, C, D, and E.
0, "10:30", "10:24", "10: 4", estimated arrival times at the destinations B, C, D, and E, respectively.
2 "and" 10:48 ", and store them in the expected distance / arrival time storage area 26 (S26). As a result, the contents of the expected distance / arrival time storage area 26 are as shown in FIG.

Thereafter, the condition discriminating means 32b operates the destination (arrival limit time storage) designated as the arrival limit time among the estimated arrival times at each destination stored in the distance / arrival time storage area 26. It is determined whether or not all the destinations corresponding to the arrival times stored in the area 27 satisfy the arrival restriction time (S27). If there is at least one estimated arrival time that does not satisfy the condition (S2
(NO at 7) instructs the route output unit 4 to display an error, and notifies the user that a route satisfying the specified condition (arrival time limit) cannot be created (S28). When all the estimated arrival times satisfy the arrival limit time (S27: YES), the process of S29 is performed.

In this example, the destination for which the arrival restriction time is specified is only the destination D as shown in FIG. 10, and the arrival restriction time for the destination D stored in the arrival restriction time storage area 27. , The estimated arrival times for the destination D stored in the distance / expected arrival time storage area 26 are “11:00” and “10:42”, respectively.
Is YES.

If the decision result in the step S27 is YES, the condition judging means 32b sets the distance / expected arrival time storage area 26
The destination having the shortest distance is selected from the destinations B, C, D, and E stored in (S29). In this case,
Destination C is selected.

Thereafter, the condition discriminating means 32b instructs the route assembling means 31b to obtain the route A → C from the starting point A to the destination C, and the route assembling means 31b selects according to the instruction. When the route A → C to the destination C is obtained, it is stored in the route storage area 24 (S29,
S30). Thus, the contents of the route storage area 24 are as shown in FIG.

Thereafter, the condition determining means 32b determines whether or not there remains a destination for which the route is not determined (S
31). When it is determined that there is no remaining, the route output unit 4 is started (S50), and when it is determined that there is remaining, the process of S32 shown in FIG. 8 is performed. In this case,
Since destinations B, D, and E remain as destinations for which the directions have not been determined, the process of S32 in FIG. 8 is performed.

In S32, the condition determining means 32b
It instructs the route assembling means 31b to set the destination C whose distance selected in S29 of FIG. 7 is the shortest as the start destination.

When this instruction is received, the route assembling means 31b
Focuses on one of the undetermined destinations (S33). In this example, since there are three undetermined destinations B, D, and E, one of them will be noted. Now, for example, if attention is paid to the undetermined destination B, the route assembling means 31b determines in step S35 the undetermined destination B currently focused on from the start destination C specified by the condition determination means 32b. The route C → B to the destination is obtained, and the distance of the route C → B is obtained in the next S36, and the obtained distance, destination B, and start point (destination C) are added to the distance / expected arrival time storage area 26. . Hereinafter, the route assembling means 31b continues to execute S3 until there is no undetermined destination that has not been noticed (until S34 becomes NO).
33 to S36 are repeated. By performing the above processing, the distance / expected arrival time storage area 26 stores the start point C, the destinations B, D, and E, and the information between the start point destination C and each of the destinations B, D, and E. Distance "1.5", "4.0",
"3.0" is added (see FIG. 13).

If the answer in S34 is NO, the arrival time predicting means 34 stores the moving speed "5 km / h" already passed from the moving speed input means 33 and the distance / expected arrival time storage area 26. The distance between the starting point destination C and each of the destinations B, D, and E, and the expected arrival time at C when the starting point stored in the distance / arrival expected time storage area 26 is defined as the departure point A 10:24 "(see FIG. 11), the estimated time of arrival at each of the destinations B, D, and E is obtained, and is added to the distance / estimated time storage area 26 (S3).
7). As a result, the information shown in FIG. 13 is additionally written in the distance / arrival expected time storage area 26.

After that, the condition discriminating means 32b sets the destination specified in the arrival limit time among the estimated arrival times when the starting point destination stored in the estimated distance / arrival time storage area 26 is the destination C. It is determined whether or not all items corresponding to the ground satisfy the arrival time limit (S38). If there is at least one estimated arrival time that does not satisfy the arrival time limit (S38: NO), the process of S40 is performed, and if all the arrival time limits are satisfied (S38).
Is YES), the process of S39 in FIG. 7 is performed.

In the case of this example, as shown in FIG. 13, the expected arrival time at the destination D is “11:12” and the arrival limit time “11:00” specified by the user has passed. The condition determining means 32b performs the process of S40.

In S40, it is determined whether or not the flag F is "1". Note that the flag F is "1" in the initial state, and the result of the determination in S40 is YES.

If the result of the determination in S40 is YES, the condition determining means 32b deletes the latest route A → C among the routes between the two points stored in the route storage area 24, and starts the starting point of the route. It is checked whether or not an undetermined destination exists for the point (departure point A) that has become (S41, S42). When it is determined that there is no undetermined destination (S42)
NO), it is determined whether or not the starting point is the departure point (S47). As a result, if it is the departure place, the error display of S28 in FIG. 7 is performed, and if it is not the departure place, the process of S41 is performed. That is, the starting point destination is further returned by one. If it is determined in S42 that an undetermined destination exists, the process of S43 is performed.

In this example, since the undetermined destinations B, D, and E exist for the starting point A (S42
S), the condition determining means 32b sets the flag F to "0" (S43). Thereafter, the condition determining means 32b
Selects the destination having the shortest distance from the undetermined destinations B, D, and E with respect to the departure point A (S44). In the case of this example, as shown in FIG. 11, since the distance of the destination B among the undetermined destinations B, D, and E is the shortest, the condition determining means 32
b selects the destination B.

Thereafter, the condition discriminating means 32b instructs the route assembling means 31b to the starting point A and the selected destination B
Is obtained, and the departure / destination input means 11 obtains the route A → B in accordance with the instruction, and stores the route A → B in the route storage area 24 ( S45). As a result, the contents of the route storage area 24 are as shown in FIG.

Thereafter, the condition determining means 32b instructs the route assembling means 31b to set the destination B as the start destination (S46).

When this instruction is received, the route assembling means 31b
Performs the same processing as described above on the undetermined destinations C, D, and E for the starting point destination B (S33 to S3).
6) In the distance / arrival expected time storage area 26, as shown in FIG. 15, the destination B as the starting point and the destinations C, D, and E
And the distance “1.5” from the starting point destination B to each destination,
“3.0” and “3.5” are added.

When this process is completed, the arrival time estimating means 34 calculates the estimated arrival times at the destinations C, D and E,
This is added to the distance / arrival expected time storage area 26 (S
37).

Thereafter, the condition judging means 32b judges whether or not the expected arrival time at the destination D at which the arrival restriction time is specified has passed the specified arrival restriction time in the same manner as described above. (S38). In this example, the specified arrival limit time is “11:00”, and the estimated arrival time at the destination D is “11:” as shown in FIG.
06 ", the result of determination in S38 is NO.

If the decision result in the step S38 is NO, the condition judging means 32b judges whether the condition stored in the route
The latest route A → B in the route between the points is deleted, and it is checked whether or not an undetermined destination exists at the point (departure point A) that is the start point of the route (S41, S42). In this example, since there are undetermined destinations D and E, the condition determination unit 32b sets the flag F to “0” (S43), and then selects from the undetermined destinations D and E for the departure place A. The destination with the shortest distance is selected (S44). In the case of this example, FIG.
As shown in (5), among the undetermined destinations D and E, the distance to the destination D is the shortest, so the condition determining means 32b selects the destination D.

Thereafter, the condition discriminating means 32b sends the starting point A and the selected destination D to the
Is obtained, and the departure / destination input means 11 obtains the route A → D in accordance with the instruction, and stores the route A → D in the route storage area 24 ( S45). As a result, the contents of the route storage area 24 are as shown in FIG.

Thereafter, the condition determining means 32b instructs the route assembling means 31b to set the destination D as the start destination (S46).

When this instruction is received, the route assembling means 31b
Performs the same processing as described above on the undetermined destinations B, C, and E for the start point destination D (S33 to S3).
6) In the distance / arrival expected time storage area 26, as shown in FIG. 17, the destination D as the starting point and the destinations B, C, E
And the distance “3.0” from the start destination B to each destination,
"2.5" and "2.0" are added.

When this processing is completed, the arrival time estimating means 34 calculates the estimated arrival times at the destinations B, C, and E,
This is added to the distance / arrival expected time storage area 26 (S
37). As a result, the information shown in FIG. 17 is additionally written in the distance / arrival expected time storage area 26.

Thereafter, the condition determining means 32b determines whether or not any of the expected arrival times shown in FIG. 17 has passed the arrival limit time specified by the user (S38). In this example, since there is no expected arrival time for the destination for which the arrival restriction time has been specified, the condition determining means 32b sets the flag to "1" (S39), and then sets the destination E of the shortest distance. (Fig. 7, S
29). Thereafter, the condition determining means 32b instructs the route assembling means 31b from the starting destination D to the selected destination E.
The route D → E obtained by the route assembling means 31b in accordance with this instruction is stored in the route storage area 24.
(S30). As a result, the contents of the route storage area 24 are as shown in FIG.

Thereafter, the same processing as described above is repeated until there are no more destinations for which the route has not been determined (until S31 becomes NO in FIG. 7). As a result, the contents of the route storage area 24 are as shown in FIG.

When the result of the determination in S31 is NO, the condition determining means 32b activates the route output unit 4. Thus, the route output unit 4 combines and displays the routes A → D, D → E, E → B, and B → C stored in the route storage area 24 on the map.

Referring to FIG. 20, the second embodiment of the present invention comprises an input unit 1c, a storage unit 2c, an optimum route assembling unit 3c, and a route output unit 4.

The input unit 1c includes a stop time input unit 14 in addition to the configuration of the input unit 1b shown in FIG. The stop time input means 14 has a function of inputting a stop time at each destination in accordance with a user's instruction.

The storage section 2c has an arrival limit time / stop time storage area 28 instead of the arrival limit time storage area 27 of the storage section 2b shown in FIG. The arrival time input means 1 is stored in the arrival time limit / stop time storage area 28.
The stop time at each destination inputted from the stop time input means 14 and the arrival limit time at each destination inputted from 3 are stored.

The optimal route assembling unit 3c includes an arrival time estimating unit 34c instead of the arrival time estimating unit 34 provided in the optimal route assembling unit 3b shown in FIG. The arrival time estimating means 34c is provided by the arrival time estimating means 34 shown in FIG.
It has almost the same function as that described above, except that the estimated time of arrival at the destination is determined in consideration of the stop time at the destination stored in the arrival time limit / stop time storage area 28. Means 34 are different.

Next, the operation will be described. The operation of the optimum route assembling unit 3c in the second embodiment is shown in FIG.
8 is almost the same as the operation in the first embodiment, and only the processing in S37 shown in FIG. 8 is different.

Now, for example, in the state where the determination result of S34 shown in FIG. 8 is NO at first, as shown in FIG. 13, the destination C is stored in the distance / arrival expected time storage area 26 as the starting point. , B, D, and E as destinations, and “1.5” and “4.
It is assumed that “0” and “3.0” are stored.

When the result of the determination in S34 is NO, the arrival time estimating means 34c first estimates the arrival at the destination C when the starting point stored in the distance / arrival expected time storage area 26 is the starting point A. Departure at the destination C based on the time "10:24" (see FIG. 11) and the stop time (for example, 30 minutes) at the destination C stored in the arrival time limit / stop time storage area 28. The time “10:54” is obtained. Next, the moving speed (for example, 5 km / h) passed from the moving speed input means 33, the starting destination C, and each destination B,
Distances between D and E "1.5", "4.0", "3.
Based on “0”, the travel times “18 minutes”, “48 minutes”, and “36 minutes” from the start destination to each of the destinations B, D, and E are obtained. Thereafter, at the departure time "10:54" of the starting point destination C obtained earlier, the travel time "1" to each of the destinations B, D and E is "1".
By adding “8 minutes”, “48 minutes”, and “36 minutes”, the expected arrival times “11: 1” at the destinations B, D, and E are obtained.
2 "," 11:42 ", and" 11:30 ". The above is the processing performed in S37. Hereinafter, the same operation as in the first embodiment described above is performed, and a route from the starting point A to each of the destinations B, C, D, and E is obtained.

[0090]

FIG. 21 is a block diagram of an embodiment of the present invention, which comprises a keyboard 101, a disk device 102, a central processing unit 103, a display device 104, and a printer 105.

[0091] Figure 6, the input unit 1 b shown in Figure 20, 1c
Is constituted by a keyboard 101, and a storage unit 2b,
2c is configured by the disk device 102. The optimal route assembling units 3b and 3c are provided by the central processing unit 103.
The route output unit 4 is configured by the display device 104 or the printer 105.

[0092]

The first effect is that an efficient route can be obtained in which a plurality of destinations can be traveled in the shortest time. The reason is that the route assembling means for obtaining the route and the distance of each route from the starting destination to each unprocessed destination, and the condition determination for making the unprocessed destination having the shortest distance from the starting destination the next starting destination. This is because it has means.

The second effect is that the burden on the user can be reduced. The reason is that the user only needs to specify a plurality of destinations and does not need to consider the order in which to go around the destinations as in the related art.

The third effect is that, when there are a plurality of destinations and there is a destination for which the arrival time limit is specified, the destination for which the arrival time limit is specified is as follows.
The point is that the driver can arrive before the designated arrival time limit and can get directions to all destinations in the shortest possible time. The reason is that there is provided an arrival time estimating means for obtaining an estimated arrival time at the destination, and a condition judging means for determining a destination to be the next starting point in consideration of the relationship between the estimated arrival time and the designated arrival time limit. Because it is.

The fourth effect is that if there are a plurality of destinations and there is a destination for which the arrival time limit and the stop time are designated, even if the stop is performed at the destination for the designated stop time. A destination where the arrival time limit is specified can be arrived before the specified arrival time limit, and a route that can travel all destinations in a short time is obtained. . The reason is that there is provided an arrival time estimating means for obtaining an estimated time of arrival at the destination in consideration of the stop time.

[Brief description of the drawings]

FIG. 1 is a block diagram of a technique on which the present invention is based .

FIG. 2 is a flowchart showing a processing example of an optimum route assembling unit 3a.

FIG. 3 is a diagram showing an example of the contents of a departure place / destination storage area 21;

FIG. 4 is a diagram showing an example of the contents of a distance storage area 23;

FIG. 5 is a diagram showing an example of the contents of a route storage area 24;

6 is a block diagram of a first implementation of the embodiment of the present invention.

FIG. 7 is a flowchart showing a processing example of the optimum route assembling unit 3b.

FIG. 8 is a flowchart showing a processing example of the optimum route assembling unit 3b.

FIG. 9 is a diagram showing an example of the contents of a departure place / destination storage area 21;

FIG. 10 is a diagram showing an example of the contents of an arrival limit time storage area 27;

11 is a diagram showing an example of the contents of a distance / expected arrival time storage area 26. FIG.

FIG. 12 is a diagram showing an example of the contents of a route storage area 24;

FIG. 13 is a diagram showing an example of information additionally written in a distance / arrival expected time storage area 26;

FIG. 14 is a diagram showing an example of the contents of a route storage area 24;

FIG. 15 is a diagram showing an example of information additionally recorded in a distance / arrival expected time storage area 26;

FIG. 16 is a diagram showing an example of the contents of a route storage area 24;

FIG. 17 is a diagram illustrating an example of information additionally written in a distance / arrival expected time storage area 26;

FIG. 18 is a diagram showing an example of the contents of a route storage area 24.

FIG. 19 is a diagram showing an example of the contents of a route storage area 24.

FIG. 20 is a block diagram of a second embodiment of the present invention.

FIG. 21 is a block diagram of an embodiment of the present invention.

[Explanation of symbols]

 1a, 1b, 1c input unit 11 departure / destination input means 12 travel method input means 13 arrival time input means 14 stop time input means 2a, 2b, 2c storage unit 21 departure place / destination Storage area 22 ... Map information storage area 23 ... Distance storage area 24 ... Route storage area 25 ... Moving speed storage area 26 ... Distance / arrival expected time storage area 27 ... Arrival limited time storage area 28 ... Arrival limited time / stop time storage area 3a, 3b, 3c optimal route assembling unit 31a, 31b route assembling means 32a, 32b condition discriminating means 33 moving speed input means 34, 34c arrival time estimating means 4 road output unit 101 keyboard 102 disk device 103 central processing unit 104 display device 105 printer

Claims (3)

(57) [Claims] 1. A departure place / destination input means for inputting a departure place and a plurality of destinations in accordance with a user's instruction; a departure time departure from the departure place; Condition input means for inputting the time limit for arrival at the destination in accordance with a user instruction; a map information storage area in which map information is stored; a route storage area in which directions are stored; and a departure / destination input. By inputting a departure place and a plurality of destinations from the means, a route from the departure place to each of the destinations is determined based on the map information, and a distance of each of the determined routes is determined. Each time the start destination is specified, the directions from the specified start destination to all the undetermined destinations for the start destination are determined based on the map information, and the determined respective routes are respectively determined. Route assembling means for determining a distance; and a distance between the departure place and each of the destinations is determined by the route assembling means. Based on the determined distances, the departure time, and the moving speed, The estimated time of arrival at each of the destinations is then determined, and each time the distance between the starting destination and each of the undetermined destinations is determined by the route assembling means, the determined distances and the starting point are calculated. Arrival time estimating means for obtaining an estimated time of arrival at each of the undetermined destinations based on the estimated time of arrival at the destination and the traveling speed; and departure of the departure place at the departure time by the arrival time estimating means. The expected time of arrival at each of the destinations at the time is obtained, and of the obtained expected times of arrival,
It is checked whether or not the estimated arrival time corresponding to the destination with the specified arrival time limit has passed the specified arrival time limit, and if so, error processing is performed. And instructing the route assembling means that the destination having the shortest distance from the departure point is the next starting point destination, and determining a route from the departure point to the destination having the shortest distance. Stored in the directions storage area,
Each time the expected time of arrival at each undetermined destination is determined by the arrival time predicting means, the expected time of arrival corresponding to the destination with the specified arrival time limit among the determined expected times of arrival is determined. It checks whether the specified arrival time limit has passed or not, and if it has not passed, among the undetermined destinations, the undetermined destination having the shortest distance from the starting destination is the next starting destination. The route assembling means is instructed to the route assembling means, and a route from the starting point destination to the undetermined destination having the shortest distance is stored in the route storage area. The route between the destination instructed to be the start destination in the latest instruction to the destination and the destination instructed to be the start destination by an instruction one time earlier than the destination is stored in the route storage area. Delete and one time before The destination was instructed to be the starting point destination, examine whether or not the undetermined destination exists,
If there is an undetermined destination, the next undetermined destination whose distance to the destination instructed to be the start destination one time ago is shortest among the undetermined destinations is as follows. The route assembling means is instructed to be the starting point destination, and the route from the destination instructed to be the starting point one time ago to the undetermined destination where the distance is the shortest is indicated. Stored in the route storage area, if there is no undetermined destination, the distance from the starting destination is the shortest of the undetermined destinations to the starting destination of the destination where the undetermined destination does not exist. After instructing the route assembling means to make the undetermined destination the next start point destination, deleting the route between the latest two points stored in the route storage area, From the shortest distance to the undetermined destination with the shortest distance Multiple purpose steady order assembling apparatus being characterized in that a condition determining means for. 2. The undetermined destination for the start destination is a destination whose route from the start destination has not been stored in the route storage area, and the route to the destination is the destination. multiple purpose steady order assembling apparatus according to claim 1, wherein the directions of the destination that is not stored in the storage area. 3. The condition input means includes a configuration for inputting a destination having a designated stop time and a stop time at the destination in accordance with a user's instruction. The distance between the departure place and each of the destinations is obtained by the assembling means, and the estimated time of arrival at each of the destinations is obtained based on the obtained distances, the departure time, and the traveling speed. Then, each time the route assembling means obtains the distance between the starting destination and each of the undetermined destinations with respect to the starting destination, the obtained distances and the estimated time of arrival at the starting destination are obtained. 3. The multi-destination road according to claim 2, further comprising: a configuration for obtaining an estimated time of arrival at each of the undetermined destinations based on a travel speed, and a stop time input from the condition input means. Order assembly equipment.