JPH02304587A - Calculator for shortest distance, shortest time and lowest transportaion charge - Google Patents

Abstract

PURPOSE: To realize circulation without the waste of time, labor, energy and cost with a suitable route by obtaining the optimum solution of a place visiting order by which a distance becomes the shortest, time becomes shortest and transportation cost becomes the most inexpensive, when all places are visited based on the method of a neural network. CONSTITUTION: A selection means M4 selects data on the shortest distance, shortest time and the most inexpensive cost of the inputted places from data stored in a storage means M3. A user only touches the visiting places on a map and gives an indication. Thus, data based on the actual route is automatically prepared and an operation means M5 speedily obtains the optimum solution of the place visiting order by which the distance, and time become the shortest and transportation cost becomes the most inexpensive based on the method of the neural network. Thus, the economic and power saving route based on the actual route can automatically be obtained and the suitable visiting order can be obtained by using data.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a device for calculating the shortest distance, shortest time, or lowest transportation cost, and particularly to a device for calculating the shortest distance, shortest time, or lowest transportation cost using a neural network. Regarding a calculation device.

[Prior Art] Conventionally, there has been a problem that shows the limits of computer processing, which is the so-called salesman's traveling problem. For example, If,
- If a salesman is touring 10 cities and looking for the shortest route, if he simply performs permutation combinations, all combinations are 10! /2:1,814,40
There are 0 routes, and checking and storing all of these routes requires a huge amount of time and memory, which is impractical. Such devices are only useful if they are carried, but for the reasons mentioned above, it is important to make them smaller and lighter.
Although the need for this method is acknowledged, it is rarely used because it takes time to obtain a solution and lacks quick response. Therefore, not only salesmen but also various local consultants, campaign speech venues, campaign cars, and other types of patrols waste time, money, labor, and energy. A method using neural networks has been proposed as a method for quickly finding solutions using computers (Takeshi Miyazawa: Practical! Neural Networks, ASCII VOL
, 13, No. 1.1989, Aihara-Koji Dual Computer.

Tokyo Denki University Press, 1988, etc.).

These are conducted using simulations using a Neumann digital computer. In other words, a synaptic load is set for each neuron based on each city and the visit order, and the state of each neuron is changed based on the connection of the neural network, and finally the neuron fires from the converged state. The purpose is to obtain the optimal cyclic order by finding the following. h Such neural networks are known as Hopfield, Boltzmann machine, or Gaussian machine models.

With this model, it is not necessary to consider a huge number of combinations, and the optimal solution can be output in an extremely short time.Therefore, this model can be applied to a small computer (f-, weight, size It is considered that this device will be practically usable in terms of processing time and processing time.

[Problem to be solved by the invention] However, in order to use it for actual patrolling, it was necessary to solve the following problem. Therefore, you must input not only the location of the patrol points but also the distance between the points.Furthermore, the route is not limited to just one.This task involves measuring the distance of the curved road from the actual map. This means that the user has to enter the value after setting the distance, which requires the user to perform an extremely complicated and time-consuming task. Yes, there is no point in using neural networks in this case.

The present invention solves this problem, and the distance between the visited positions and the distance between them is
Eliminate the difficulty of entering time or travel expense data.
The objective is to provide a device for calculating the shortest distance, shortest time, or lowest transportation cost that will demonstrate the usefulness and speed of neural networks.

[Means for Solving the Problems] The configuration of the present invention adopted to solve the above problems is as follows. That is, as illustrated in FIG. 1, there is a map M1, a position input means M2 that allows inputting position data of any point by touching the map M1, and route data on the map M1, its distance, time, or traffic. a storage means M3 for storing cost data; a selection means M4 for selecting the shortest distance, shortest time, or minimum transportation cost data between input points from the data stored in the storage means M3; Based on the neural network method, we calculate the optimal solution for the order of visiting points that will result in the shortest route 1, shortest time, or lowest transportation cost when visiting all points using the distance and time or transportation cost data between each point selected. The present invention is characterized by comprising: a calculation means M5 for calculating the optimal solution, and a display means M6 for displaying the order of visiting the points determined as the optimum solution on the map M1 together with a route adapted to the actual road.

[Function] In particular, the selection means M4 selects the shortest distance between each input point from the data stored in the storage means M3.
You have selected the shortest time or lowest travel cost data. Therefore, when the user (friend) of this device simply touches and indicates a visiting point on the map, data corresponding to the actual route will be automatically prepared. The user can quickly find the optimal solution for the order of visiting points that results in the shortest distance, shortest time, or lowest transportation cost, and as described in 2. Even if you do not find the tag, you can automatically get a realistic, economical and labor-saving route. Using that data, you can get an appropriate visit sequence.

[Embodiment] FIG. 2 shows a first embodiment of the shortest distance, shortest time or lowest transportation cost calculation device of the present invention. This device is configured as a card type for portable use.

This shortest distance, shortest time or lowest transportation cost calculation device 1 (
It has a flexible sheet 3 on one side so that it can be filed in a so-called system notebook.

Since this sheet 3 has an engagement hole 3a for a binder, it can be bound into a system organizer, providing long-term portability.

This calculation device 1 (other side 1: a liquid crystal panel (LCD) 5 for display, keys 78 to 7m for instruction input, and a power switch 9 are arranged. Also, on the surface of the LCD 5, a transparent touch panel 11 is located.

As shown in the block diagram of FIG. 3, this internal configuration is configured as a microcomputer 12.
3. ROM15. It is equipped with a RAM 17° and a ROM card 19, as well as instruction input keys 7a to 7m, and an LCD 5.
and an input/output circuit 2 for the touch panel 11].

These components are connected via a bus 23 so that they can transmit and receive data.

The zero process that is conventional in the first embodiment shown in the flowchart of FIG. 4 is repeatedly executed after the power switch 9 is turned on.

When the process starts, first, initial values of various variables and flags are set (step 110). Next, the system waits for a key input (step 120). When the map selection key 7 is pressed here, a regional menu is displayed on the LCD 5 (step 130). When a predetermined area is selected based on the menu, a map of the area is displayed on the LCD 5 (step 140), and then a key input is awaited (step 150). Now press scroll key 7c.

When 7f, 7i, and 7m are pressed, the map displayed on the LCD 5 scrolls in the direction of the arrow displayed on the key (step 160). Therefore, the LCD 5 itself can only display a limited area at a time, By scrolling, you can check a map of as wide an area as you like, and enter precise instructions.

Next, when the visitor key 7a is pressed, the touch panel 1
Reading of points from point 1 is started (step 170).

The map display position on the LCD 5 and the detection area range on the touch panel 11 are calculated so that they always match, so while looking at the map, press the corresponding position with the pen (
ヱ Points on the map will be input as visiting points. Of course, even during the process of step 170, the map can be scrolled using the scroll keys 7c, 7f, 7i, and 7m.

Until the end key 7g is pressed, it is possible to enter the visited points. When the end key 7g is pressed (step 180), a display is displayed to confirm the inputted point (step 190). If there is a correction, the user presses the correction key 7h (step 200) and reading of the point from the touch panel 11 is started again (step 170).

Next, an indication of the type of processing is requested (step 210).
). That is, a menu indicating whether to seek the shortest distance, shortest time, or lowest transportation cost is displayed on the LCD 5. Press the shortest distance key 7b. The shortest distance for traveling between each point entered in step 170 is checked from the route data stored in the ROM 15 or ROM card 19 to check the actual road connecting each point. Then, the route with the shortest distance is searched and stored.This search is carried out, for example, as follows.

In other words, the two points P in Figure 8 whose route is represented by a solid line and a broken line,
, When finding the shortest route between P2, divide the route T, -T2 where P exists into two at P, and determine which route approaches P2 in terms of point P. In the 0 diagram, there is no big difference in whether P + -T + or P, -T2 approach or leave, so both are selected. Next, it is determined whether the end of the route exiting from the route terminals T, Ta approaches P2. By making selections in this way, as shown by the solid line, ■p, -T
, -T 3-T a -T, -P2. ■P+-T+
=T3-Ts-T, Ta-P 2+ ■ P +-
Three routes are selected: T e - T v - T s - T o - P 2. Among these, the shortest distance is 1 ■P, -T+-
It is found that T3=T4 Ta P2 by adding the distances of each route.

Similarly, press the shortest time key 7d or the lowest transportation cost 7e (
One or more routes for traveling between each location are determined, and the route with the shortest time or lowest transportation cost is found and memorized (steps 230 and 240).
). For example, if there are 10 points, there are 10×9/2=45 combinations between these two points, and 45 search processes are required, so the processing time can be shortened. Furthermore, it is only necessary to store 45 pieces of data in the memory, and the memory capacity is also small.

Next, based on these data, a neural network is constructed (step 250), based on Hopfield's model as follows.

Of course, other models such as the Boltzmann machine or the Gaussian machine may be applied. However, since the derivation of the arithmetic formula using this model is well known, detailed calculations for deriving the formula will be omitted in the following explanation. do. However, since the calculation formula itself is determined in advance and stored in the R2M 17 or the ROM card 19, the number of neurons and each constant may be determined as necessary when configuring the neural network.

The output Vi of the i1th neuron is expressed as follows.

V+= (1/2) ・(1+ tanh (x/
μs) l − (1) However, X=ΣT +, iV
4+1 +I-i N: Because of neurons For example, if there are 10 points, the 10 points correspond to the rows, and the visit order corresponds to the columns, 10×10
We use 100 neurons represented by a matrix of .

King, 9. : Synaptic load L from the j-th neuron to the j-th neuron where T, , =O0l, :
Threshold specific to the j-th neuron (LLμa: constant that determines the input-output relationship of the neuron) Furthermore, if the synaptic load has symmetry, then T, , = ■4, 1, and each neuron can change its state asynchronously. Then, the energy E is defined as follows.

Hopfield has proven that this energy E has the property of spontaneously decreasing as the state of the neuron changes.

When Expression (2) is expressed as a two-dimensional array of neurons having an X component and a Y component, the energy E is expressed as follows.

Next, the following evaluation function is calculated based on the conditions that ``each point is visited only once'' and ``two points are never visited at the same time.''

2 X+ Here, A, B, and C are constants.

Furthermore, the total sum of the itinerary route is expressed by the following formula.

2×IY ...(5) However, dxx=o, D is a constant.

Therefore, assuming E EE E I 0 E 2, the intermediate processing will be omitted, but the equation will be organized as shown below.

"x+, vl=Aδxy(1-δ1j)-Bδ1.(1
−δ8. ) C Ddxv(δj, +41+δJ, 1-1)... (6
) l X, :Cn -(7) However-
When ≠j, δ,,==Q, When i=j, δ1j=1
It is.

1: Next, to apply to digital computers.

When temporally discretized and a digital model is obtained, the above equation (1) becomes as follows.

Vx+(k)=(1/2) ・(1+tanh(U
x+(k)/us) 1...(9) By substituting the above equations (6) and (7) into the above equations (8) and (9), the following equation is obtained.

−DΣdx”v (VY, l−1(k 1) +V
y, 1-+ (k I) 1... (10) Vx+(k)= (1/2) ・(1+tanh
(tJx+(k)/us) 1... (11) In this way, the neural network input/output function for circulation is completed.

This n vx+(k), Ux+(k) (7) Initial value VX+(O).

1 for U x + (0) Since there is no established method, you can set a value that you think is appropriate, or you can actually perform the calculation and determine in advance a value that you think is appropriate. . Constant n, A, B, C, D.

The same applies to μ9.

And 20 neural network input/output functions (10),
While incrementing k in (11), the calculations are performed sequentially to detect convergence of the state V□(k) of each neuron (step 260). After incrementing and calculating k a predetermined number of times, the value O'/(V
x+(k)>0. 8), it is determined that convergence has occurred (step 270). If it has not converged (L), each constant is changed appropriately according to the firing status of the neuron (step 280), and the calculation is performed again.

If converged, each column 1 is read in order, and the visiting place numbers X firing in each column 1 are stored in sequence in the array in RAM11 to obtain the visiting order of the visited places (step 290).

Next, an identifiable mark is displayed at the visited place on the map displayed on the LCD 5. For example, ■■■... is displayed in the order of visits. Furthermore, steps 220 to 24 are performed between the visited locations.
Only the routes with the shortest distance, shortest time, or lowest transportation cost that have been searched for in step 0 are displayed in the order of visit (step).

Next, the system waits for a key input (step 310), and the "1st process" key 7k is pressed, 1fS Step 120
Return to processing. If the "end" key 7g is pressed, the process ends.

In this way, the optimal route is determined and it becomes possible to travel around the route without wasting effort, energy, or expense.

A second embodiment includes a step of selecting a means of transportation,
The shortest distance, shortest time, or lowest transportation cost data between each point using the means of transportation may be selected.

For example, between step 200 and step 210 in the flowchart of FIG. 4, by carrying out the process shown in FIG. Display a menu such as transportation (bus, train, etc.) on the LCD 5 and press the scroll key 7c.
, 7f, 7i, and 7m to select one (step 510). Depending on the result, the pointer of the data group in the ROM 15 or ROM card 19 used in steps 220 to 240 is switched ( Steps 520 to 540), so that in subsequent steps 220 to 240, the distance between each point when traveling on foot, by car or by public transportation is 1 hour r81 transportation cost (
Walking is usually free) data is used and the shortest/lowest value is selected.

In this way, according to the second embodiment, various means of transportation can be accommodated, and by simply selecting, not only automobiles but also walking,
An optimal solution can also be obtained by moving by electric flux bus.

As a third embodiment, a limit data input step for inputting distance, time, or monetary data may be provided, and points that can be reached within this limit data may also be displayed. For example, by executing the process shown in FIG. 6 between step 290 and step 300 in the flowchart of FIG. 4 or immediately after step 300, it is possible to display points that can be reached within the limit data.

That is, the user is prompted to input through the menu whether the restriction data is distance or transportation fee, and its value (step 610). If it is [distance J], the distance from the starting point to the current visited place is accumulated following the order determined in step 290 (step 620). If it is determined that the current cumulative distance is within the distance limit (step 630), it is determined whether there is a next place to visit (step 640). If there is, the distance between the current visited place and the next visited place is added to the previous integrated value (step 620). In this way, when the visited place ends at or before reaching a point exceeding the limit distance, a point within the limit is displayed (step 650). This display may change the display pattern and color of the route depending on whether it is within or outside the restricted distance. Visited places that cannot be reached within a limited distance may be identified by a blinking display.

The same applies when other restriction data is set, and if there is a time restriction, the places visited that cannot be visited due to time are found through the processing in steps 660 to 680. In addition, if there are restrictions on transportation expenses, by processing steps 690 to 710,
The destinations that cannot be visited due to cost are identified. This selection of restriction data and previously performed steps 210-24
This is different from the selection of 0, and after finding the shortest route (step 220), you can check the points that can be reached according to the cost on that route.Steps 690 to 710
, 650), and after determining the route with the lowest transportation cost (step 240), it is possible to check the points that can be reached within a predetermined time using that route (steps 660 to 680. 650).
. You can also choose other combinations.

This allows you to plan your visit according to your own abilities, such as the amount of time you have or the money you have.

As a fourth embodiment, a step of selecting some routes may be provided, and a specific route may be set to be passed without fail, or conversely, a specific route may be set not to be passed. Parable It No. 7
Processing as shown in the figure (steps 750 to 770) is provided between step 200 and step 210 to specify a route to be forcibly excluded or passed. That is, whether or not there is a route instruction and which points are to be specified are input using the menu (step 750). Yes 1
i Display the route between the points and scroll key 7c
, 7f, 7i, and 7m to select a route and at the same time indicate whether to exclude or pass (step 7
60). If further instructions need to be given between other points (step 770), the process returns to step 760. If there is no selection, the process moves to the next "type of processing" selection (step 210).

In this way, it is possible to instruct routes to be excluded or passed through, so it is possible to obtain an appropriate route that avoids routes that are closed due to construction, etc., and to respond flexibly to the situation. In addition, if the vehicle also serves as a promotional vehicle, it can be ensured that the vehicle always passes through a route where advertising is effective.

Although the point is specified in step 170 above, if the specified point is not a position on the route, the subsequent processing may be performed using the closest point on the route closest to the specified point.

In each of the embodiments described above, the shortest distance, shortest time, or minimum transportation cost required between each point or all points may be displayed separately from the route display on the map.

Further, the above embodiments can be implemented in various combinations unless there is a contradiction.

Further, in this embodiment, the neural network is simulated using a Neumann type digital computer, but it is also possible to use an LSI or the like which is an analog hardware version of the neural network.

In each of the above embodiments, the LCD 5 corresponds to the map M] and the display means M6, and the touch panel 11 corresponds to the position input means M2.
The microcomputer 12 corresponds to the selection means M4 and the calculation means M5, and the ROM 15 or ROM card 19 corresponds to the storage means M3.

According to the present invention, by simply inputting a location on a map, the shortest distance, shortest time, or lowest transportation cost can be easily and quickly calculated in light of the actual route.

[Brief explanation of drawings]

Fig. 1 shows an example of the basic configuration of the present invention. Fig. 2 shows a perspective view of the external appearance of the embodiment device. Fig. 3 shows its block text. Fig. 4 shows a flowchart of the processing contents of the first embodiment. FIG. 6 is a flowchart showing part of the processing content of the third embodiment; FIG. 7 is a flowchart showing part of the processing content of the fourth embodiment; The figure represents an explanatory diagram of shortest route search. Ml...Map M2...Position input means M3...Storage means M4...Selection means M5
...Calculating means M6...Display means 5...
Liquid crystal panel (LCD) 11...touch panel 12
...Microcomputer 15...ROM19.
-・ROM card

Claims (1)

[Claims] 1. A map, a location input means that allows inputting location data of any point by touching the map, and a memory that stores route data on the map and its distance, time, or transportation cost data. a selection means for selecting the shortest distance, shortest time, or lowest transportation cost data between each input point from data stored in the storage means; and distance and time between each point selected by the selection means. or calculation means for calculating the optimal solution of the order of visiting points that will result in the shortest distance, shortest time, or lowest transportation cost when visiting all the points based on the neural network method using transportation cost data; 1. A shortest distance, shortest time or lowest transportation cost calculation device, comprising: a display means for displaying the determined order of visiting points on a map together with a route adapted to the actual road;