JP2023039925A - Method, computer device, and computer program for predicting congestion propagation of road using pattern matching - Google Patents

Abstract

To provide a method, a computer device, and a computer program for predicting congestion propagation of a road using pattern matching.SOLUTION: A congestion propagation predicting method comprises: a step of searching for at least one past speed pattern similar to a recent speed pattern at an accident time on an accident road using pattern matching; and a step of predicting a congestion propagation pattern due to the accident road from a past speed pattern of at least one peripheral road that is accessible to the accident road for a time corresponding to the past speed pattern.SELECTED DRAWING: Figure 4

Description

The following description relates to techniques for predicting road congestion.

The occurrence of road congestion and the resulting propagation of congestion is one of the traffic problems faced by most large cities around the world.

Such traffic congestion is roughly divided into recurrent congestion and non-recurrent congestion caused by accidental information such as accidents, worsening weather, and gatherings. .

Methods for predicting traffic jam times on a particular road are generally based on the number of vehicles that the road can accommodate. The number of vehicles that can be accommodated on a road is set, and when the number of vehicles that can be accommodated reaches the limit, a traffic jam will occur on that road. Speed drops sharply.

It is possible to statistically predict the arrival time of repetitive road congestion.

One study proposes a STO (spatio-temporal outliers) tree algorithm and a frequent subtree algorithm for searching frequent propagation trees of abnormal traffic flows between regions. Other studies have proposed visual interfaces for exploring traffic congestion and propagation patterns, and still others have stochasticized repetitive congestion propagation patterns in the form of propagation graphs called Pro-Graphs. It predicts traffic jam propagation for the future.

Existing research focuses on identifying traces (signatures) of frequently repeated congestion propagation in the past.

However, it is impossible to predict when and where traffic congestion that occurs non-repetitively, such as traffic accidents, is difficult to generate a congestion propagation prediction model that corresponds to the congestion situation.

It predicts traffic congestion propagation patterns in real time by pattern matching without the need for training.

After identifying past speed patterns that are similar to the current speed pattern of the accident road, the congestion propagation situation of surrounding roads is predicted based on the past speed patterns.

1. A traffic congestion prediction method implemented on a computing device, said computing device including at least one processor configured to execute computer readable instructions contained in a memory, said traffic congestion prediction method comprising: searching, by the at least one processor, for the accident road for at least one past speed pattern similar to a recent speed pattern at the time of the accident using pattern matching; and predicting, by a processor, a congestion propagation pattern due to the accident road from past speed patterns of at least one peripheral road that can enter the accident road for time points corresponding to the past speed patterns. Provide forecasting methods.

According to one aspect, the searching includes setting a first time range for the pattern matching based on the time of the accident for the accident road; searching past speed patterns of the accident road from the speed time-series data of the accident road based on the pattern similarity of .

According to another aspect, the step of setting, for the accident road, determines the first time based on at least one of an accident occurrence time when an accident condition occurred and an accident reporting time when an accident condition was reported. You can set the range.

According to another aspect, in the setting step, the accident occurrence of the accident situation is detected by using speed time-series data for a certain time before the accident report time at which the accident situation was reported for the accident road. Predicting a time point; and setting the first time range as a time range that includes the accident occurrence time.

According to another aspect, the setting step may set the first time range based on a degree of congestion due to vehicle movement on the accident road.

According to another aspect, the searching step extracts the past speed pattern of the accident road from the speed time-series data of the accident road based on pattern similarity between data using DTW (Dynamic Time Warping). you can explore.

According to another aspect, the predicting step may predict the future congestion situation of the peripheral road from the past speed pattern of the accident road and the corresponding past speed pattern of the peripheral road.

According to another aspect, the step of predicting includes setting a second time range, which is a time range in which congestion propagation between roads is expected; confirming traffic congestion conditions within the second time range from past speed patterns; generating a matrix patterning the traffic congestion conditions of the peripheral roads with respect to the past speed patterns of the accident road; Based on this, the method may include predicting future congestion conditions on the surrounding roads with respect to recent speed patterns on the accident roads.

According to another aspect, the step of generating includes, if a plurality of matrices are generated for past speed patterns of the accident road, voting the plurality of matrices, and determining the voting results. deriving a final matrix based on.

According to yet another aspect, the step of setting includes, for the accident road, the second accident road based on at least one of an accident occurrence time when an accident situation occurred and an accident reporting time when the accident situation was reported. A time range is set, and the second time range may be set based on the degree of congestion due to the movement amount of vehicles on the peripheral road or the accident road.

A computer program recorded on a computer-readable recording medium for causing the computer device to execute the congestion propagation prediction method is provided.

A computing device, comprising at least one processor configured to execute computer readable instructions contained in a memory, the at least one processor utilizing pattern matching to generate an accident signal for an accident road. searching for at least one past speed pattern similar to a recent speed pattern at a point in time; A computer device is provided for processing a process of predicting a congestion propagation pattern due to the accident road from a speed pattern.

According to the embodiment of the present invention, pattern matching is used to predict surrounding roads on which traffic jams on accident roads will propagate, thereby providing optimal detour road guidance during route search.

According to the embodiment of the present invention, it is possible to improve the prediction performance of congestion propagation based on the speed pattern of the accident road, which becomes clearer with the passage of time, based on the time of the accident.

According to the embodiment of the present invention, since the prediction model based on pattern matching does not require a learning process, resources and time required for prediction of congestion propagation can be saved. can predict road congestion propagation.

1 is a diagram showing an example of a network environment in one embodiment of the present invention; FIG. 1 is a block diagram illustrating an example of a computing device, in accordance with one embodiment of the present invention; FIG. It is a figure showing an example of a road network in one embodiment of the present invention. 1 is a flowchart illustrating an example of a method that may be performed by a computing device in accordance with one embodiment of the present invention; FIG. 10 is an exemplary diagram for explaining the process of grasping the time of occurrence of an accident in one embodiment of the present invention; FIG. 5 is an exemplary diagram for explaining a process of setting a time range required for pattern matching in one embodiment of the present invention; FIG. 5 is an exemplary diagram for explaining a process of searching for past speed patterns similar to recent speed patterns by pattern matching in one embodiment of the present invention; FIG. 5 is an exemplary diagram for explaining a process of searching for past speed patterns similar to recent speed patterns by pattern matching in one embodiment of the present invention; FIG. 5 is an exemplary diagram for explaining a process of searching for past speed patterns similar to recent speed patterns by pattern matching in one embodiment of the present invention; FIG. 4 is an exemplary diagram for explaining the process of setting a time range in which congestion propagation is expected in one embodiment of the present invention; FIG. 4 is an exemplary diagram for explaining a process of predicting a traffic congestion situation for surrounding roads based on an accident road in one embodiment of the present invention; FIG. 4 is an exemplary diagram for explaining a process of predicting a traffic congestion situation for surrounding roads based on an accident road in one embodiment of the present invention;

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

Embodiments of the present invention relate to techniques for predicting road congestion.

Embodiments including what is specifically disclosed herein use pattern matching to predict surrounding roads on which congestion on accident roads propagates, thereby determining optimal detour roads in appropriate situations. can be done.

A congestion prediction apparatus according to an embodiment of the present invention may be implemented by at least one computer device, and a congestion prediction method according to an embodiment of the present invention may be implemented by at least one computer device included in the congestion prediction device. may be executed. At this time, a computer program according to an embodiment of the present invention may be installed and executed in the computer device, and the computer device predicts congestion propagation according to the embodiment of the present invention under control of the executed computer program. the method may be carried out. The computer program described above may be recorded in a computer-readable recording medium in order to combine with a computer device and cause the computer to execute the congestion propagation prediction method.

FIG. 1 is a diagram showing an example of a network environment in one embodiment of the present invention. The network environment of FIG. 1 illustrates an example including multiple electronic devices 110 , 120 , 130 , 140 , multiple servers 150 , 160 , and a network 170 . Such FIG. 1 is merely an example for explaining the invention, and the number of electronic devices and the number of servers are not limited as in FIG. Also, the network environment in FIG. 1 is merely an example of an environment applicable to this embodiment, and the environment applicable to this embodiment is not limited to the network environment in FIG.

The plurality of electronic devices 110, 120, 130, 140 may be fixed terminals or mobile terminals implemented by computing devices. Examples of the plurality of electronic devices 110, 120, 130, and 140 include smartphones, mobile phones, navigation systems, PCs (personal computers), notebook PCs, digital broadcasting terminals, PDAs (Personal Digital Assistants), and PMPs (Portable Multimedia Players). ), and tablets. As an example, FIG. 1 shows a smart phone as an example of the electronic device 110, but in embodiments of the present invention, the electronic device 110 substantially utilizes a wireless or wired communication scheme and communicates with other devices via the network 170. may refer to one of a variety of physical computing devices capable of communicating with the electronic devices 120, 130, 140 and/or servers 150, 160 of the server.

The communication method is not limited, and not only the communication method using the communication network that can be included in the network 170 (eg, mobile communication network, wired Internet, wireless Internet, broadcasting network), but also the short distance between devices. Wireless communication may be included. For example, the network 170 includes a PAN (personal area network), a LAN (local area network), a CAN (campus area network), a MAN (metropolitan area network), a WAN (wide area network), a BBN (broadband network), and the Internet. Any one or more of the networks may be included. Additionally, network 170 may include any one or more of network topologies including, but not limited to, bus networks, star networks, ring networks, mesh networks, star-bus networks, tree or hierarchical networks, and the like. will not be

Each of servers 150, 160 is implemented by one or more computing devices that communicate with a plurality of electronic devices 110, 120, 130, 140 over network 170 to provide instructions, code, files, content, services, etc. good. For example, server 150 may be a system that provides services (eg, navigation services, etc.) to a plurality of electronic devices 110 , 120 , 130 , 140 connected via network 170 .

FIG. 2 is a block diagram illustrating an example computing device, in accordance with one embodiment of the present invention. Each of the plurality of electronic devices 110, 120, 130 and 140 and each of the servers 150 and 160 described above may be realized by the computer device 200 shown in FIG.

Such a computing device 200 may include memory 210, processor 220, communication interface 230, and input/output interface 240, as shown in FIG. The memory 210 is a computer-readable storage medium and may include random access memory (RAM), read only memory (ROM), and permanent mass storage devices such as disk drives. Here, a permanent mass storage device such as a ROM or disk drive may be included in computer device 200 as a separate permanent storage device separate from memory 210 . Also stored in memory 210 may be an operating system and at least one program code. Such software components may be loaded into memory 210 from a computer-readable medium separate from memory 210 . Such other computer-readable recording media may include computer-readable recording media such as floppy drives, disks, tapes, DVD/CD-ROM drives, memory cards, and the like. In other embodiments, software components may be loaded into memory 210 through communication interface 230 that is not a computer-readable medium. For example, software components may be loaded into memory 210 of computing device 200 based on computer programs installed by files received over network 170 .

Processor 220 may be configured to process computer program instructions by performing basic arithmetic, logic, and input/output operations. Instructions may be provided to processor 220 by memory 210 or communication interface 230 . For example, processor 220 may be configured to execute received instructions according to program code stored in a storage device, such as memory 210 .

Communication interface 230 may provide functionality for computer device 200 to communicate with other devices (eg, the recording device described above) via network 170 . As an example, processor 220 of computing device 200 can transmit requests, commands, data, files, etc. generated according to program code recorded in a recording device such as memory 210 to other devices via network 170 under the control of communication interface 230 . device. Conversely, signals, instructions, data, files, etc. from other devices may be received by computing device 200 through communication interface 230 of computing device 200 over network 170 . Signals, instructions, data, etc. received through the communication interface 230 may be transmitted to the processor 220 and the memory 210, and files may be stored in a recording medium (the permanent recording device described above) that the computing device 200 may further include. may be recorded.

Input/output interface 240 may be a means for interfacing with input/output device 250 . For example, input devices may include devices such as a microphone, keyboard, or mouse, and output devices may include devices such as displays, speakers, and the like. As another example, input/output interface 240 may be a means for interfacing with a device that integrates functionality for input and output, such as a touch screen. Input/output device 250 may be one device with computing device 200 .

Also, in other embodiments, computing device 200 may include fewer or more components than the components of FIG. However, most prior art components need not be explicitly shown in the figures. For example, computing device 200 may be implemented to include at least some of the input/output devices 250 described above, and may also include other components such as transceivers, databases, and the like.

Specific embodiments of methods and apparatus for predicting road congestion propagation using pattern matching are described below.

FIG. 3 is a diagram showing an example of a road network in one embodiment of the invention.

The main external factors involved in non-repetitive congestion on roads are traffic accidents, assemblies, and road construction. It greatly affects the traffic volume and speed of surrounding roads entering the congested road.

Referring to FIG. 3, when traffic congestion occurs on A road due to a traffic accident, the congestion spreads over time to at least some of the surrounding roads that enter A road, and the traffic congestion propagates ( Traffic Congestion Propagation) occurs.

For example, assume a navigation service has guided a route that includes I, F, D, and A roads. If traffic congestion on Road A propagates to Roads D and F over time, if an attempt is made to maintain the existing route, there will be a significant delay in travel time for users traveling on that route. .

If the navigation service can predict the roads on which traffic congestion will occur, the optimal route (e.g., a route including I, H, G, A roads, etc.) that bypasses D roads and F roads on which traffic congestion is expected to propagate. ) can be guided to the user.

This embodiment proposes an analysis technology capable of predicting congestion propagation patterns in real time through pattern matching without the need for a learning process when traffic congestion occurs in an accident situation.

In the following, this will be explained in detail, exemplifying a traffic accident as a representative accident situation that causes non-repetitive congestion.

The present embodiment can respond to accident situations in real time by pattern matching without having to go through a learning process. Pattern matching is a methodology that identifies past patterns that are similar to the current pattern, and hypothesizes that near-future patterns will progress based on the identified past patterns.

In this embodiment, pattern matching is used to identify past speed patterns similar to the current speed pattern observed on the accident road, and based on this, the propagation of congestion on surrounding roads is predicted.

FIG. 4 is a flowchart illustrating an example method that may be performed by a computing device in accordance with one embodiment of the present invention.

The computing device 200 according to the present embodiment may provide navigation services to clients through a dedicated application installed on the client or by connecting to a web/mobile site associated with the computing device 200 . The computer device 200 may include a traffic congestion prediction device realized by a computer.

The processor 220 of the computer device 200 may be implemented with components for executing the congestion propagation prediction method according to FIG. Depending on the embodiment, components of processor 220 may be selectively included or excluded from processor 220 . Also, depending on the embodiment, the components of processor 220 may be separated or merged to represent the functionality of processor 220 .

Such processor 220 and components of processor 220 may control computing device 200 to perform steps 410-450 included in the congestion propagation prediction method of FIG. For example, processor 220 and components of processor 220 may be implemented to execute instructions according to the code of an operating system and the code of at least one program contained in memory 210 .

Here, the components of processor 220 may represent different functions performed by processor 220 according to instructions provided by program code recorded in computing device 200 .

Processor 220 may read the necessary instructions from memory 210 loaded with instructions associated with the control of computing device 200 . In this case, the read instructions may include instructions for controlling processor 220 to perform steps 410-450 described below.

The steps 410-450 described below may be performed in a different order than shown in FIG. 4, some of the steps 410-450 may be omitted, or additional steps may be included. may

Referring to FIG. 4, at step 410, the processor 220 may ascertain the time when the accident occurred based on the time when the accident was reported on the accident road. The processor 220 may use a system, platform, or the like that can work with the computer device 200 to obtain, maintain, and manage speed time-series data from the actual traveling speed of the vehicle on the road. Also, the processor 220 may receive reports of accident information, such as road accidents, using a system or platform that can interface with the computer device 200 .

The time t _rpt at which the accident was reported is necessarily located after the time t _a at which the accident actually occurred. Since the congestion propagation starts from the time t _a when an accident occurs on the accident road, it is important to know the time t _a of the accident occurrence in addition to the accident reporting time t _rpt . Unlike the information about the accident reporting time _trpt , there is no information about the accident occurrence time t _a , so we can estimate the expected accident occurrence prior to the accident reporting time _trpt using the speed data available from the navigation service. Find the time t _a .

Let us assume that an accident on accident road _eo was reported at time _trpt . As an example, the processor 220 determines that the first point in time at which _{predetermined} conditions C1, C2, and C3 are continuously satisfied within a certain period of time (for example, two hours) before the point in time trpt is the accident point in time _ta . can be defined.

For example, referring to FIG. 5, the first condition (C1) means that the 5-minute speed exponential moving average (EMA) is lower than the average speed within 2 hours before the accident report time t _rpt . do. The second condition (C2) means that the 5-minute speed index moving average (EMA) is lower than the 30-minute speed index moving average (EMA). (C1) and (C2) are conditions for trend changes where the short-term trend in velocity is lower than the long-term trend. This makes it possible to sense a rapid trend change in speed. The third condition (C3) relates to sudden speed reduction situations. If the speed drops below the standard deviation range of the previous 10 minutes, it is determined that a sudden drop in speed has occurred and is reflected as a sudden drop in speed caused by an accident. A point at which the above three conditions (C1), (C2), and (C3) are continuously satisfied for 10 minutes is regarded as the accident occurrence point _ta .

Referring back to FIG. 4, at step 420, the processor 220 may set a first time range for pattern matching based on at least one of the accident report time _trpt and the accident occurrence time _ta . . The first time range means a time range indicating a pattern matching section, that is, a time window. As an example, the processor 220 considers only the accident report time _trpt without considering the accident occurrence time t _a , and selects a previous fixed time (for example, 2 hours) relative to the accident report time t _rpt as a first May be set as a time range. As another example, the processor 220 may set the first time range to be a certain period of time (for example, two hours) before the accident report time _trpt , but set the time range including the accident occurrence time _ta as the first time range. May be set as a time range. In other words, the processor 220 may set the time including the accident occurrence time t _a and the accident report time t _rpt as the first time range.

In order to compare the recent speed pattern at the time of the accident with past speed patterns, it is necessary to rationally set the first time range, which is the length of the pattern. The first time range is hereinafter referred to as SW (Searching Window). SW may be set by Equation (2).

Here, PT (previous time) is a hyper-parameter that determines how far in the past from the accident occurrence time t _a to search. Referring to FIG. 6, the processor 220 includes the PT in the SW in order to add the situation before the accident to the analysis range, and reflects the normal traffic situation before the accident, thereby representing a clearer accident situation. be able to.

SW may be set by the navigation service operator. As an example, the normal congestion degree of the accident road may be used as a reference, and the congested road on which the amount of movement of vehicles is large may be set shorter. SW is a hyperparameter that is determined according to the target of the service, and may be set to an optimum value based on experiments in consideration of road characteristics and the like.

SW may be updated every unit time period as time passes, and may reflect the real-time situation on this basis.

Referring to FIG. 4 again, at step 430, the processor 220 extracts a similar past speed from the speed time-series data of the corresponding road for the recent speed pattern corresponding to SW, which is the first time range of the accident road. You can search for patterns. In other words, processor 220 may search for past speed patterns that are similar to recent speed patterns in SW for accident roads.

After setting SW, which is the pattern length to be compared, the processor 220 may perform a search on the speed data for the same road for a period of time in the past. As an example, the processor 220 calculates the degree of similarity between the recent speed pattern existing within the SW range of the speed time series data of the accident road and all past speed patterns by DTW (Dynamic Time Warping), and calculates the degree of similarity As a reference, the top N past speed patterns may be extracted.

DTW means an index for measuring similarity between two pieces of time-series data, and the processor 220 may analyze pattern similarity between data while considering curve similarity of time-series data according to DTW.

For example, referring to FIG. ₇ , the time series data (71) X={x ₁ , x ₂ , . ₌ {y ₁ , y ₂ , . The (i,j) element of DTW matrix 700 indicates the distance value between x _i and y _i . Among paths from (1, 1) to (n, m) of the DTW matrix 700, a path with the shortest sum of elements of the DTW matrix 700 is defined as a warping path 710. FIG. At this time, the sum of the distances of the paths defined as the warping path 710 is the DTW distance, and it can be said that the smaller this value is, the higher the similarity between the two pieces of time-series data 71 and 72 is.

As shown in FIG. 8, the processor 220 obtains DTW distances in SW units 801 for all past speed patterns in the speed time series data 800 of the accident road, and arranges the DTW distances in ascending order to obtain the most recent Past speed patterns can be arranged in order of similarity to the speed pattern. At this time, the processor 220 may extract N independent patterns that do not temporally overlap between past speed patterns as similar pattern candidates.

Referring to FIG. 9, the processor 220 applies the DTW distance-based pattern matching described with reference to FIG. past speed patterns 920 are searched.

Referring again to FIG. 4, at step 440, the processor 220 may establish a second time range in which congestion propagation to at least one surrounding road is expected based on the accident road. The second time range is a time range in which congestion on the accident road is expected to propagate to surrounding roads, and is called PW (Propagation Window). PW may be set by Equation (3).

The processor 220 may set PW, which is the predicted time range of traffic jam propagation to surrounding roads, based on at least one of the accident occurrence time _ta and the accident report time _trpt . Referring to FIG. 10, F is a hyperparameter that indicates how far in the future the congestion of the accident road is transmitted from the accident reporting time point _trpt of the accident road to the user of the navigation service. For example, the processor 220 may set a certain time (for example, two hours) after the accident report time _trpt of the accident road as the second time range. As another example, the processor 220 may set a certain time (eg, 3 hours) after the accident occurrence time _t a on the accident road as the second time range. The reason why the accident occurrence time t _a is reflected at the start time of PW is to reflect the possibility that congestion on the surrounding roads of k-hop may start from the accident occurrence time t _a based on the accident road. .

PW, like SW, may be set by the operator of the navigation service, and may be set shorter for congested roads where the amount of vehicle movement is greater, based on the usual degree of congestion on accident roads and surrounding roads. Depending on the embodiment, PW may be set to an optimum value obtained through experiments in consideration of road characteristics and the like.

Referring back to FIG. 4, in step 450, the processor 220 calculates the past speed pattern of the accident road and the corresponding past speed patterns of the surrounding roads for k-hop surrounding roads based on the accident road. , the past speed pattern corresponding to the second time range (PW) may be used to predict the congestion propagation pattern.

The processor 220 may check the congestion status of all surrounding roads up to k-hops from the accident road for past speed patterns similar to the recent speed pattern of the accident road. By analyzing the speed pattern of the PW range as the speed data of the surrounding road at the time corresponding to the past speed pattern searched for the accident road in step 430, the traffic congestion condition of the surrounding road can be confirmed. For example, traffic congestion on surrounding roads may be defined as in Equation (4).

For each peripheral road, if the maximum speed of the road falls below the 0.7 level with respect to the speed limit ff(e) within the PW range, it is determined that congestion has occurred within the PW range.

Referring to FIG. 11, the processor 220 applies the condition of Equation (4) to the speed patterns 1130 of all surrounding roads within k-hops included at the time corresponding to the N past speed patterns 920 of the accident road. By doing so, the congestion status of the surrounding roads for each of the past speed patterns 920 may be obtained. The processor 220 generates N propagation matrices 1140 by patterning congestion conditions of surrounding roads for N past speed patterns 920 of the accident road. Here, the propagation matrix 1140 is a matrix that indicates the congestion status of each route of the peripheral roads connecting from the accident road to k-hops.

Based on the N propagation matrices 1140, the processor 220 predicts congestion propagation patterns on surrounding roads for recent speed patterns on accident roads. For example, referring to FIG. 12, voting is performed for each element in a state in which N propagation matrices 1140 are given, and a predicted propagation matrix (Predicted Propagation Matrix), which is one predicted value based on the results of the voting, is obtained. 1250 may be derived.

Based on the prediction propagation matrix 1250, the processor 220 predicts the traffic congestion propagation pattern of the surrounding road due to the accident road from the past speed pattern within the PW range of the surrounding road with respect to the accident road.

Therefore, the processor 220 can identify a past speed pattern similar to the recent speed pattern of the accident road, and predict the future traffic congestion propagation situation from the past congestion pattern of the surrounding roads corresponding to the past speed pattern. . The processor 220 repeats the processes 410 to 450 with the unit time period as time elapses, thereby reflecting the real-time situation of the accident road and predicting the congestion propagation situation.

According to an embodiment of the present invention, it is possible to predict the pattern of congestion propagation on an accident road where a non-repetitive congestion situation has occurred. In this embodiment, by predicting an inflow road that will cause congestion due to the impact of an accident, it is possible to guide a route that bypasses the road when searching for a route.

Further, according to the embodiment of the present invention, by updating the SW with a period of unit time and predicting the congestion propagation situation, it is possible to deal with the situation in real time. Predictability of congestion propagation can be increased by using the speed patterns of accident roads that become more distinct over time relative to the time the accident is reported.

Furthermore, according to embodiments of the present invention, by using pattern matching to predict road congestion propagation, the learning process required by machine learning, deep learning, etc. can be omitted, and only road networks can be used. By applying pattern matching, it is possible to predict the congestion propagation situation. Since no learning process is required, it is possible to save resources and time required for predicting congestion propagation.

The apparatus described above may be realized by hardware components, software components, and/or a combination of hardware and software components. For example, the devices and components described in the embodiments include processors, controllers, arithmetic logic units (ALUs), digital signal processors, microcomputers, field programmable gate arrays (FPGAs), programmable logic units (PLUs), microprocessors, Alternatively, it may be implemented using one or more general purpose or special purpose computers, such as various devices capable of executing and responding to instructions. The processing unit may run an operating system (OS) and one or more software applications that run on the OS. The processor may also access, record, manipulate, process, and generate data in response to executing software. For convenience of understanding, one processing device may be described as being used, but those skilled in the art will appreciate that a processing device may include multiple processing elements and/or multiple types of processing elements. You can understand that. For example, a processing unit may include multiple processors or a processor and a controller. Other processing configurations are also possible, such as parallel processors.

Software may include computer programs, code, instructions, or a combination of one or more of these, to configure a processor to operate at its discretion or to independently or collectively instruct a processor. You can Software and/or data may be embodied in any kind of machine, component, physical device, computer storage medium, or device for interpretation by, or for providing instructions or data to, a processing device. good. The software may be stored and executed in a distributed fashion over computer systems linked by a network. Software and data may be recorded on one or more computer-readable recording media.

The method according to the embodiments may be embodied in the form of program instructions executable by various computer means and recorded on a computer-readable medium. Here, the medium may record the computer-executable program continuously or temporarily record it for execution or download. In addition, the medium may be a variety of recording means or storage means in the form of a combination of single or multiple hardware, and is not limited to a medium that is directly connected to a computer system, but distributed over a network. It may exist in Examples of media include magnetic media such as hard disks, floppy disks, and magnetic tapes, optical media such as CD-ROMs and DVDs, magneto-optical media such as floptical disks, and ROM, RAM, flash memory, etc., and may be configured to store program instructions. Other examples of media include recording media or storage media managed by application stores that distribute applications, sites that supply or distribute various software, and servers.

As described above, the embodiments have been described based on the limited embodiments and drawings, but those skilled in the art will be able to make various modifications and variations based on the above description. For example, the techniques described may be performed in a different order than in the manner described and/or components such as systems, structures, devices, circuits, etc. described may be performed in a manner different from the manner described. Appropriate results may be achieved when combined or combined, opposed or substituted by other elements or equivalents.

Accordingly, different embodiments that are equivalent to the claims should still fall within the scope of the appended claims.

110, 120, 130, 140: electronic equipment 150, 160: server 170: network

Claims (20)

A congestion propagation prediction method executed by a computer device, comprising:
The computing device includes at least one processor configured to execute computer readable instructions contained in memory;
The congestion propagation prediction method includes:
searching by the at least one processor for at least one past speed pattern similar to a recent speed pattern at the time of the accident for the accident road using pattern matching; and predicting, by a processor, a congestion propagation pattern due to the accident road from past speed patterns of at least one peripheral road that can enter the accident road for time points corresponding to the past speed patterns. Forecast method. The searching step includes:
setting a first time range for the pattern matching based on the time of the accident for the accident road; and determining the accident road based on pattern similarity between data corresponding to the first time range. 2. The congestion propagation prediction method according to claim 1, comprising: searching past speed patterns of said accident road from speed time series data of . The setting step includes:
The first time range is set for the accident road based on at least one of an accident occurrence point in time when the accident situation occurred and an accident report point in time when the accident situation was reported. 2. The congestion propagation prediction method according to 2. The setting step includes:
Predicting the accident occurrence time at which the accident situation occurred on the accident road using speed time-series data for a certain period of time before the accident report time at which the accident situation was reported; and 3. The congestion propagation prediction method according to claim 2, comprising: setting said first time range as a time range. The setting step includes:
3. The congestion propagation prediction method according to claim 2, wherein the first time range is set based on a degree of congestion based on the movement amount of vehicles on the accident road. The searching step includes:
2. The method according to claim 1, wherein, as the speed time-series data of the accident road, a past speed pattern of the accident road is searched based on pattern similarity between data using DTW (Dynamic Time Warping). congestion propagation prediction method. The predicting step includes:
2. The traffic congestion prediction method according to claim 1, wherein a future congestion situation of said peripheral road is predicted from a past speed pattern of said accident road and a corresponding past speed pattern of said peripheral road. The predicting step includes:
setting a second time range, which is the time range in which congestion propagation between roads is expected;
confirming the traffic congestion situation within the second time range from the past speed pattern of the accident road and the past speed pattern of the corresponding peripheral road;
Generating a matrix patterning congestion conditions of the peripheral roads with respect to past speed patterns of the accident road; and future congestion conditions of the peripheral roads with respect to recent speed patterns of the accident road based on the matrix. 2. The method of predicting congestion propagation according to claim 1, comprising the step of predicting . The generating step includes:
9. if multiple matrices are generated for past speed patterns of the accident road, voting the multiple matrices and deriving a final matrix based on the voting results. The congestion propagation prediction method described in . The setting step includes:
setting the second time range for the accident road based on at least one of an accident occurrence time when the accident situation occurred and an accident reporting time when the accident situation was reported;
9. The traffic congestion prediction method according to claim 8, wherein the second time range is set based on a degree of congestion due to the movement amount of vehicles on the peripheral road or the accident road. A computer program, which, when executed by a computer device, causes the computer device to execute the congestion propagation prediction method according to any one of claims 1 to 10. A computer device,
at least one processor configured to execute computer readable instructions contained in memory;
The at least one processor
searching for at least one past speed pattern similar to a recent speed pattern at the time of the accident for an accident road using pattern matching; A computer device for processing a process of predicting a congestion propagation pattern due to the accident road from past speed patterns of at least one peripheral road that can enter the road. The at least one processor
setting a first time range for the pattern matching on the accident road based on the time of the accident;
13. The method according to claim 12, wherein the past speed pattern of the accident road is searched from the speed time-series data of the accident road based on the pattern similarity between the data corresponding to the first time range. computer equipment. The at least one processor
The first time range is set for the accident road based on at least one of an accident occurrence point in time when the accident situation occurred and an accident report point in time when the accident situation was reported. 14. The computer device according to 13. The at least one processor
Predicting the accident occurrence time at which the accident situation occurred on the accident road using speed time series data for a certain period of time before the accident report time at which the accident situation was reported;
14. The computer apparatus according to claim 13, wherein said first time range is set as a time range including said accident occurrence point. The at least one processor
14. The computer device according to claim 13, wherein the first time range is set based on a degree of congestion due to the movement amount of vehicles on the accident road. The at least one processor
13. The computer device according to claim 12, wherein the past speed pattern of the accident road is searched from the speed time-series data of the accident road based on pattern similarity between data using DTW. The at least one processor
13. The computer device according to claim 12, wherein the future traffic congestion situation of the peripheral road is predicted from the past speed pattern of the accident road and the corresponding past speed pattern of the peripheral road. The at least one processor
setting a second time range that is a time range in which congestion propagation between roads is expected;
confirming the traffic congestion situation within the second time range from the past speed pattern of the accident road and the past speed pattern of the corresponding peripheral road;
Generating a matrix patterning the traffic congestion situation of the peripheral road with respect to the past speed pattern of the accident road,
13. The computer device according to claim 12, wherein the computer device predicts future traffic congestion conditions of the peripheral roads with respect to recent speed patterns of the accident roads based on the matrix. The at least one processor
When a plurality of matrices are generated for past speed patterns of the accident road, voting is performed on the plurality of matrices, and a final matrix is derived based on the voting results. Item 20. The computer device according to Item 19.

Images