CN114589343A - Path optimization method of multilayer nested contours - Google Patents
Path optimization method of multilayer nested contours Download PDFInfo
- Publication number
- CN114589343A CN114589343A CN202210425783.2A CN202210425783A CN114589343A CN 114589343 A CN114589343 A CN 114589343A CN 202210425783 A CN202210425783 A CN 202210425783A CN 114589343 A CN114589343 A CN 114589343A
- Authority
- CN
- China
- Prior art keywords
- cutting
- contour
- contours
- overall
- group
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 62
- 238000005457 optimization Methods 0.000 title claims abstract description 20
- 238000005520 cutting process Methods 0.000 claims abstract description 307
- 238000012163 sequencing technique Methods 0.000 claims abstract description 52
- 230000001174 ascending effect Effects 0.000 claims abstract description 11
- 239000003016 pheromone Substances 0.000 claims description 16
- 241000257303 Hymenoptera Species 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000002372 labelling Methods 0.000 description 1
- 239000000463 material Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
Images
Classifications
-
- B—PERFORMING OPERATIONS; TRANSPORTING
- B23—MACHINE TOOLS; METAL-WORKING NOT OTHERWISE PROVIDED FOR
- B23D—PLANING; SLOTTING; SHEARING; BROACHING; SAWING; FILING; SCRAPING; LIKE OPERATIONS FOR WORKING METAL BY REMOVING MATERIAL, NOT OTHERWISE PROVIDED FOR
- B23D19/00—Shearing machines or shearing devices cutting by rotary discs
-
- B—PERFORMING OPERATIONS; TRANSPORTING
- B23—MACHINE TOOLS; METAL-WORKING NOT OTHERWISE PROVIDED FOR
- B23D—PLANING; SLOTTING; SHEARING; BROACHING; SAWING; FILING; SCRAPING; LIKE OPERATIONS FOR WORKING METAL BY REMOVING MATERIAL, NOT OTHERWISE PROVIDED FOR
- B23D33/00—Accessories for shearing machines or shearing devices
- B23D33/02—Arrangements for holding, guiding, and/or feeding work during the operation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/004—Artificial life, i.e. computing arrangements simulating life
- G06N3/006—Artificial life, i.e. computing arrangements simulating life based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/30—Computing systems specially adapted for manufacturing
Landscapes
- Engineering & Computer Science (AREA)
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Strategic Management (AREA)
- Economics (AREA)
- Mechanical Engineering (AREA)
- Data Mining & Analysis (AREA)
- Artificial Intelligence (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Evolutionary Computation (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Computational Linguistics (AREA)
- Biophysics (AREA)
- Biomedical Technology (AREA)
- General Health & Medical Sciences (AREA)
- Development Economics (AREA)
- Life Sciences & Earth Sciences (AREA)
- Game Theory and Decision Science (AREA)
- Health & Medical Sciences (AREA)
- Entrepreneurship & Innovation (AREA)
- Marketing (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- General Business, Economics & Management (AREA)
- Numerical Control (AREA)
Abstract
The invention discloses a path optimization method of a multilayer nested contour, which comprises the following steps: acquiring all cutting outlines of a layout to be cut; all cut contours are traversed for group numbering and tier numbering labels as follows: judging whether the current cutting contour is the outermost contour, marking group numbers and level numbers on the outermost contour, and executing in a circulating manner until all cutting contours are traversed; dividing the cutting profiles with the same group number into an integral profile; carrying out level numbering ascending order marking and then carrying out reverse order arrangement on each overall outline from outside to inside; judging whether the type of the cutter is more than one, if not, grouping all the overall outlines into one group, if so, grouping all the overall outlines according to the type of the cutter, traversing each group of overall outlines and sequencing; and finishing the cutting operation of the layout to be cut according to the sequencing of the data points in the cutting contour set. The method can reduce unnecessary cutter idle running stroke and cutter changing influence, greatly improve cutting efficiency, save cutting time and have wide application range.
Description
Technical Field
The invention belongs to the technical field of cutting beds, and particularly relates to a path optimization method for a multilayer nested contour.
Background
With the development of automation technology and computer technology, automatic cutting machines have already formed automatic products, and have fused advanced mechanical technology, computer technology, automatic control technology, etc., and cutting precision and cutting efficiency have all had very big promotion relatively in the past. The cutting tool is commonly used for cutting various products such as clothes, billboards and the like, and has strong applicability, wide application range and large quantity.
In the advertisement and clothing cutting industry, a plurality of outlines needing to be cut often exist on a sample, if the outlines are not sequenced before being cut but are cut randomly according to an original unarranged sequence, the idle running time (the time for not cutting the outlines) is often long except the time for cutting the outlines in the whole time of the cutter movement, and the cutting efficiency of the cutter is greatly reduced. In order to improve the efficiency and reduce unnecessary idle running strokes of the cutter as much as possible, a path optimization method of a multi-layer nested contour is provided.
Disclosure of Invention
The invention aims to provide a path optimization method of a multilayer nested contour, which can reduce unnecessary cutter idle running stroke and cutter changing influence, greatly improve cutting efficiency, save cutting time and have a wide application range.
In order to achieve the purpose, the technical scheme adopted by the invention is as follows:
the invention provides a path optimization method of a multilayer nested contour, which comprises the following steps:
s1, acquiring all cutting outlines of the layout to be cut;
s2, traversing all the cutting outlines, and marking the cutting outlines by group numbers and hierarchy numbers, wherein the method comprises the following specific steps:
s21, a preset first variable number1 ═ i, and a second variable number2 ═ k;
s22, judging whether a parent contour of the current cutting contour exists in the rest cutting contours based on a ray method, if so, judging that the current cutting contour is not the outermost contour, otherwise, judging that the current cutting contour is the outermost contour, setting i as i +1 and number1 as i, and marking the group number of the current outermost contour as number1 and the hierarchy number as number 2;
s23, updating the current cutting contour to be the next cutting contour, and returning to execute the step S22 until all cutting contours are traversed;
s24, acquiring the sub-contours of the outermost layer contours based on a ray method, marking the group numbers of the sub-contours as the group numbers corresponding to the outermost layer contours, and dividing the cutting contours with the same group numbers into an integral contour;
s25, marking all cutting outlines of all overall outlines from outside to inside in an ascending order by means of ray method, and then arranging the hierarchical numbers of all cutting outlines of all overall outlines in an inverted order;
s3, judging whether the type of the cutter is more than one, if not, grouping all the overall outlines into one group and sequencing each group of overall outlines, if so, grouping all the overall outlines according to the type of the cutter, traversing each group of overall outlines, sequencing each group of overall outlines, and sequencing each group of overall outlines, wherein the method specifically comprises the following steps:
s31, obtaining the initial position of the cutter of the current group of overall outlines, if the current group of overall outlines is the first group, judging whether the layout to be cut has a preset site, if so, the initial position of the cutter is a preset positioning point, if not, the initial position of the cutter is the origin of coordinates of the layout to be cut, and if the current group of overall outlines is not the first group, the initial position of the cutter is the terminal point of the last cutting outline of the previous group of overall outlines;
s32, storing the initial position of the cutter and the starting point of the outermost layer contour of each overall contour into a first data set, and performing path optimization on data points in the first data set based on an ant colony algorithm from the initial position of the cutter to obtain an optimized path;
s33, removing the initial position of the cutter in the optimized path, and then the sequencing of the rest data points in the optimized path is the cutting sequence of the corresponding overall contour;
s34, sequencing all the cutting contours in the overall contours according to the cutting sequence of the overall contours, which is specifically as follows:
s341, sorting the starting points of the first layer of cutting contours based on a greedy algorithm by taking the starting position of the cutter as the starting point of the first overall contour, and adding the corresponding cutting contours into a cutting contour set according to the sequence of the sorted data points;
s342, updating the starting point to be the end point of the last cutting contour in the cutting contour set, sequencing the starting points of the next layer of cutting contours based on a greedy algorithm, adding the corresponding cutting contours into the cutting contour set according to the sequence of the sequenced data points, and executing in a circulating manner until all cutting contours in the current overall contour are traversed;
s343, updating the starting point as the end point of the last cutting contour in the cutting contour set, and sequencing all cutting contours in the next overall contour until the current group of overall contours is traversed;
and S4, obtaining the cutting contour set which is sequenced, and completing the cutting operation of the to-be-cut layout according to the sequencing of the data points in the cutting contour set.
Preferably, in step S22, it is determined whether there is a parent contour of the current cutting contour in the remaining cutting contours based on a ray method, which is as follows:
and taking a contour point of the current cutting contour, making a ray from the contour point along any direction, matching the contour point with any selected cutting contour in the other cutting contours, judging the number of intersection points of the ray and the selected cutting contour, if the number is an odd number, considering that the current cutting contour is positioned in the selected cutting contour, and considering that the selected cutting contour is a father contour of the current cutting contour, and if the number is an even number, considering that the current cutting contour is positioned outside the selected cutting contour, and not considering that the selected cutting contour is the father contour of the current cutting contour.
Preferably, in step S25, the overall cutting contour of each overall contour is marked in ascending order of hierarchy number from outside to inside based on ray method, which is as follows:
and acquiring the outermost layer contour of all unmarked layer numbered cutting contours in the whole contour based on a ray method, setting k to be k +1 and number2 to be k, marking the layer number to be number2, and executing in a circulating way until all cutting contours of the whole contour are traversed.
Preferably, in step S32, starting from the start position of the tool, performing path optimization on data points in the first data set based on the ant colony algorithm to obtain an optimized path, which is as follows:
s321, sequencing data points in the first data set based on a greedy algorithm from the initial position of the cutter to obtain an initial path;
s322, updating pheromone based on the shortest path length L obtained in the nth iteration of the ant colony algorithm;
s323, comparing the initial path length BestL with the shortest path length L, updating the initial path length BestL ═ min { BestL, L }, updating the path to the corresponding path, and setting n ═ n +1, returning to execute step S322 until the iteration is completed, thereby obtaining the optimized path.
Preferably, the ant colony algorithm uses the following parameters:
the initialization pheromone concentration is 5, the ant number m is the outline number multiplied by 1.5, the pheromone factor is equal to 1, the heuristic function factor beta is 5, the pheromone volatilization factor rho is 0.1, and the iteration frequency is 50 times.
Compared with the prior art, the invention has the beneficial effects that:
according to the method, the nested contours are layered, all the layered contours are ranked according to the ant colony algorithm and the greedy algorithm, and the cutting contours corresponding to different cutters are grouped and ranked, so that the sum of the idle running path distances of the cutters is minimum in the process from the beginning to the completion of cutting all the contours, unnecessary idle running strokes and cutter changing influences of the cutters are reduced, the cutting efficiency is greatly improved, the cutting time is saved, the application range is wide, and the method is particularly suitable for the advertisement cutting industry and the clothing cutting industry.
Drawings
FIG. 1 is a flow chart of a path optimization method of a multi-layer nested contour according to the present invention;
FIG. 2 is a numbering diagram after ascending order labeling of hierarchy numbering in step S25 according to the present invention;
FIG. 3 is a numbering diagram of the step S25 according to the present invention after the hierarchical numbering is arranged in reverse order.
Detailed Description
The technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application, and it is obvious that the described embodiments are only some embodiments of the present application, and not all embodiments. All other embodiments obtained by a person of ordinary skill in the art based on the embodiments in the present application without making any creative effort belong to the protection scope of the present application.
It is to be noted that, unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this application belongs. The terminology used in the description of the present application herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the application.
As shown in fig. 1-3, a method for optimizing a path of a multi-layer nested contour includes the following steps:
and S1, acquiring all cutting outlines of the layout to be cut.
All the contours to be cut are stored in the form of point coordinates. In cutting, all point profiles may be cut with the same knife, but in some cases, different profiles are cut with different knives. According to the input cutting file, the cutting tool required by each cutting profile can be analyzed.
S2, traversing all cutting outlines, and marking each cutting outline with a group number and a hierarchy number, wherein the steps are as follows:
s21, a preset first variable number1 ═ i, and a second variable number2 ═ k;
s22, judging whether a parent contour of the current cutting contour exists in the rest cutting contours based on a ray method, if so, judging that the current cutting contour is not the outermost contour, otherwise, judging that the current cutting contour is the outermost contour, setting i as i +1 and number1 as i, and marking the group number of the current outermost contour as number1 and the hierarchy number as number 2;
s23, updating the current cutting contour to be the next cutting contour, and returning to execute the step S22 until all cutting contours are traversed;
s24, acquiring the sub-contours of the outermost contours based on a ray method, marking the group numbers of the sub-contours as the group numbers corresponding to the outermost contours, and dividing the cutting contours with the same group numbers into an integral contour;
and S25, marking all the cutting contours of each overall contour in ascending order by level numbers based on a ray method, and arranging the level numbers of all the cutting contours of each overall contour in an inverted order.
In an embodiment, in step S22, it is determined whether there is a parent contour of the current cutting contour in the remaining cutting contours based on a ray method, which is as follows:
and taking a contour point of the current cutting contour, making a ray from the contour point along any direction, matching the contour point with any selected cutting contour in the other cutting contours, judging the number of intersection points of the ray and the selected cutting contour, if the number is an odd number, considering that the current cutting contour is positioned in the selected cutting contour, and considering that the selected cutting contour is a father contour of the current cutting contour, and if the number is an even number, considering that the current cutting contour is positioned outside the selected cutting contour, and not considering that the selected cutting contour is the father contour of the current cutting contour.
In one embodiment, in step S25, the overall cut contour of each overall contour is marked in ascending order of hierarchy number from outside to inside based on ray method, which is as follows:
and acquiring the outermost layer contour of all unmarked layer numbered cutting contours in the whole contour based on a ray method, setting k to be k +1 and number2 to be k, marking the layer number to be number2, and executing in a circulating way until all cutting contours of the whole contour are traversed.
Wherein the cutting profiles are generally closed and the cutting profiles do not intersect, either independently or in contained relation. In many cases, a plurality of cutting profiles are nested together, and the nested profiles also have requirements on the cutting sequence, namely, the innermost profile must be cut firstly, then the innermost profile extends outwards, the outer profile is cut again, and the cutting is carried out sequentially from inside to outside until the outermost profile is cut, so that the integral cutting of the nested profiles is completed. The nested contours are cut inside-out-after-outside because: the whole layout is fixed on the workbench, accurate cutting can be guaranteed only by cutting from inside to outside, and large errors are avoided. If the outer layer is cut firstly, because the outline is closed, after the outer layer is cut, the outline of the inner layer is still in the outline of the outer layer and is cut off from the layout along with the outline of the outer layer, when the cutter cuts the outline of the inner layer again, the material is unfixed, the problems of no cutting or incorrect cutting position and the like are likely to occur, and therefore the nested cutting outline must be ensured to be cut from inside to outside. All cut contours should first be distinguished and divided, grouping nested contours into a set and dividing into levels, before sorting. And (3) marking each cutting contour by group numbering and hierarchy numbering, wherein the specific process is as follows:
1) the cut contours are grouped and divided into inner and outer levels.
1. Firstly, variables of number1 and number2 are set, numerical values are stored, for example, the initial value of number1 is equal to 0, the initial value of number2 is equal to 1, number1 represents the group number of the whole contour, number2 represents the hierarchy number of the cutting contour, the whole contour, namely all the contours with nesting relation, are combined to form a whole contour, also called a nested contour, the whole contour number is started from 1, and the variables are set to give the group number and the hierarchy number to each whole contour, so that the cutting sequence can be arranged subsequently.
2. And traversing all the cutting outlines, finding out the outermost layer outline in the whole outline, and marking the group number and the level number. When each cutting contour is traversed, the following judgment and operation are carried out:
2.1) judging whether the currently traversed contour is the outermost contour
Before the determination, it is first known how to determine whether the cutting profile a is contained in the cutting profile B (i.e., determine whether the cutting profile B is a parent profile of the cutting profile a). Because the cutting contour does not intersect, only one contour point of the cutting contour A needs to be taken out, and whether the cutting contour A is contained in the cutting contour B can be judged by judging the relationship between the contour point and the cutting contour B. If the contour point is inside the cutting contour B, the cutting contour a is considered to be inside the cutting contour B, otherwise, the cutting contour a is considered to be outside the cutting contour B. Whether the contour point is inside the closed cutting contour B or not is judged by using a ray method (odd-even point method). Firstly, rays are taken from the contour point along any direction, then the number of intersection points of the rays and the cutting contour B is obtained, if the number of the intersection points is an odd number, the contour point is inside the cutting contour B, and if the number of the intersection points is an even number, the contour point is outside the cutting contour B. By doing so, it can be determined whether or not the cut contour B is a parent contour of the cut contour a.
Judging whether a certain cutting contour in all the remaining cutting contours is a father contour of the current cutting contour in sequence by adopting the method, if so, finishing the judgment, and judging whether the next cutting contour is the outermost contour, wherein the cutting contour is not the outermost contour; and if the parent contour of the current cutting contour does not exist in the residual cutting contours, the current cutting contour is the outermost contour, and the process is continued downwards.
2.2) the current outermost contour is labeled with level number1, representing that it is the first layer contour from the outside to the inside of the overall contour. The existing value of number1 is added by 1, the group number of the overall outline is marked as number1, and the current outermost outline belongs to the overall outline with the group number of 1. And judging whether the next cutting contour is the outermost contour or not after the marking is finished.
After traversing all the cut outlines by the method, all the outermost layer outlines are found out and marked with the level numbers and the group numbers of the whole outlines.
3. A sub-profile of the outermost profile is found.
The entire outermost profile has been found above, and the remaining cutting profiles are necessarily sub-profiles of the respective outermost profiles. And finding all sub-contours of the outermost layer contour from the rest sub-contours in sequence, namely judging which contours in the rest sub-contours are contained in a certain outermost layer contour. After finding, the group numbers of the sub-outlines are marked as the group numbers of the corresponding parent outlines. After all the sub-contour marks are finished, the purpose of dividing all the cutting contours into the whole contour according to the group numbers is achieved.
4. The number of levels of all cut profiles is marked.
The overall profiles have been divided, and operations are performed on each overall profile. Knowing the outermost layer contour of a certain overall contour (the layer number of the outermost layer contour is marked as 1), finding the next outermost layer contour, namely, finding the outermost layer contour of all the unmarked layer cutting contours in the overall contour, and finding the outermost layer contour by the method and the step 2, judging whether a certain cutting contour has a father contour, if so, the outermost layer contour is not necessarily the outermost layer contour, and if not, the outermost layer contour is the outermost layer contour. After all the next-to-outer contours are found, their level numbers are labeled 2 (representing that they are the second-level contours of the overall contour from the outside to the inside). Next, the 3 rd level cut contour (i.e. the third level contour from the outside to the inside of the global contour) is found, and the outermost level contour of all the unmarked levels in the global contour is still found, and the level number marked with them is found to be 3. All the cutting outlines of the whole outline are searched, and the layer outlines of the whole outline are sequentially found backwards by adopting the same method and are marked with level numbers. And (3) carrying out the operation of marking the layer levels on all the overall outlines, and after marking is finished, representing that all the cutting outlines of the layout to be cut are subjected to overall outline dividing and layering operation, namely the initial marking of the group numbers and the level numbers is finished. As shown in fig. 2, the overall contour is divided into an overall contour and a layer by the above steps, ON represents the number of the overall contour (group number), and OC represents that the cut contour belongs to the number of the layer (layer number).
5. The hierarchical numbering of each overall contour is arranged in reverse order.
Currently, the individual cut profiles of all the overall profiles have been numbered in increasing levels from the outside to the inside, but considering that the cuts are cut from the inside to the outside, and for the convenience of the following operation, the overall profiles need to be numbered in levels from the inside to the outside, the innermost layer being the first layer, and the number of layers increasing in order from the outside. Therefore, the current level numbers of all the overall profiles need to be arranged in a reverse order, and are sequentially increased from the inner level to the outer level, and the profiles are cut into groups and divided into the inner level and the outer level. As shown in fig. 3, the hierarchy of fig. 2 is arranged in reverse order.
In actual cutting, different cutting profiles on one layout are cut by using different cutters, and sometimes, a layout is cut by using multiple cutting cutters. According to the input cutting file, the cutting tools required by each cutting profile can be analyzed, and the cutting tools of the general nested integral profiles are the same. Therefore, if the parsed file finds that a plurality of cutting tools are required for profile cutting, after all cutting profiles are grouped and marked, all overall profiles should be firstly grouped according to different cutting tools, and then each group of overall profiles should be sorted. The operation is to ensure that one cutter is used for cutting all the corresponding cutting profiles, and then the other cutter is used for cutting the other cutting profiles. Therefore, two cases are considered when performing the cutting sequence arrangement: firstly, only one cutter is used for contour cutting, and secondly, a plurality of cutters are used for contour cutting.
S3, judging whether the type of the cutter is more than one, if not, grouping all the overall outlines into one group and sequencing each group of overall outlines, if so, grouping all the overall outlines according to the type of the cutter, traversing each group of overall outlines, sequencing each group of overall outlines, and sequencing each group of overall outlines, wherein the method specifically comprises the following steps:
s31, obtaining the initial position of the cutter of the current group of overall outlines, if the current group of overall outlines is the first group, judging whether the layout to be cut has a preset site, if so, the initial position of the cutter is a preset positioning point, if not, the initial position of the cutter is the origin of coordinates of the layout to be cut, and if the current group of overall outlines is not the first group, the initial position of the cutter is the terminal point of the last cutting outline of the previous group of overall outlines;
and S32, storing the initial position of the cutter and the starting point of the outermost layer contour of each overall contour into a first data set, and performing path optimization on data points in the first data set based on an ant colony algorithm from the initial position of the cutter to obtain an optimized path.
In an embodiment, in step S32, starting from the start position of the tool, performing path optimization on data points in the first data set based on the ant colony algorithm to obtain an optimized path, which is as follows:
s321, sorting data points in the first data set from the initial position of the cutter based on a greedy algorithm to obtain an initial path;
s322, updating pheromone based on the shortest path length L obtained in the nth iteration of the ant colony algorithm;
s323, comparing the initial path length BestL with the shortest path length L, updating the initial path length BestL ═ min { BestL, L }, updating the path as a corresponding path, setting n ═ n +1, and returning to execute step S322 until the iteration is completed, thereby obtaining an optimized path.
In one embodiment, the ant colony algorithm uses the following parameters:
the initialization pheromone concentration is 5, the ant number m is the outline number multiplied by 1.5, the pheromone factor is equal to 1, the heuristic function factor beta is 5, the pheromone volatilization factor rho is 0.1, and the iteration frequency is 50 times.
S33, removing the initial position of the cutter in the optimized path, wherein the sequencing of the rest data points in the optimized path is the cutting sequence of the corresponding overall contour;
s34, sequencing all the cutting contours in the overall contours according to the cutting sequence of the overall contours, which is specifically as follows:
s341, sorting the starting points of the first layer of cutting contours based on a greedy algorithm by taking the starting position of the cutter as the starting point of the first overall contour, and adding the corresponding cutting contours into a cutting contour set according to the sequence of the sorted data points;
s342, updating the starting point to be the end point of the last cutting contour in the cutting contour set, sequencing the starting points of the next layer of cutting contours based on a greedy algorithm, adding the corresponding cutting contours into the cutting contour set according to the sequence of the sequenced data points, and executing in a circulating manner until all cutting contours in the current overall contour are traversed;
and S343, updating the starting point to be the end point of the last cutting contour in the cutting contour set, and sequencing all the cutting contours in the next overall contour until the current group of overall contours are traversed.
The following is a detailed description of contour cutting using only one cutter and contour cutting using a plurality of cutters, respectively:
1. if only one cutting tool for the profile is available, the sequence of cutting the profile is arranged, and the specific steps are as follows:
1.1) acquiring the initial position of the cutter.
The starting position of the cutter is the position of the cutter before all cutting contour cutting processes of the whole layout are carried out, an idle running stroke exists between the position and the first cutting contour, and the idle running stroke needs to be counted into the total idle running stroke. According to the actual cutting situation, the initial position of the cutter is related to whether the cutting layout has the preset position point. If no preset positioning point exists, the cutter starting position startPoint is usually considered as the coordinate origin position of the cutting layout; if the preset positioning point exists, the cutter starting position startPoint is the preset positioning point of the current layout.
1.2) finding the outermost layer contour according to the group number and sequencing by an ant colony algorithm.
Firstly, the outermost layer of contours are sequenced, and an ant colony algorithm is selected to sequence the outermost layer of contours.
The ant colony algorithm is an algorithm capable of searching for an optimized path, and the optimized path from one city to all the cities visited (each city can only be visited once) can be solved according to the ant colony algorithm, namely, the DSP problem can be solved. The cutter cuts a contour from the starting point of the contour to the end point of the contour, and the contour is a closed contour, and the starting point and the end point are the same point, so that the cutter idle running path is actually generated from the end point of one cutting contour to the starting point of the next cutting contour. The start of each contour may represent the location of this cut contour, and in the ant colony algorithm the location of a city. Therefore, startPoint can be added into the city set as the first city, the first points (starting points) of all the outermost layer profiles can be added into the city set as the coordinates of other cities, and the problem of the shortest free-run path between the outermost layer profiles can be solved by using the ant colony algorithm to solve the DSP problem.
When using the ant colony algorithm, it needs to be explicit that: when searching for the optimal path, the first city must be startPoint, because startPoint is the position from which the cutter starts, and is fixed. Then, a path is searched out from the startPoint position by using an ant colony algorithm, and the last city is searched without returning to the starting city startPoint.
Before searching for a path by using the ant colony algorithm, an initial path needs to be searched out from a given first city startPoint by a greedy algorithm to obtain an initial path length BestL. Then, the ant colony algorithm is used for optimizing the cutting sequence according to the city set, and the parameters of the ant colony algorithm are set as follows: the initialization pheromone concentration is 5, the ant number m is the outline number × 1.5, the pheromone factor oc is 1, the heuristic function factor β is 5, the pheromone volatilization factor ρ is 0.1, and the iteration number is 50. All ants must start in the same city startPoint in order to ensure that the initial city of the searched path is always startPoint. It has been emphasized that if the last city is searched and no return is made to the starting city startPoint, the path length used for comparison in the iteration is the unclosed path length. Each iteration of the ant colony algorithm is performed, m ants search m paths, all the paths are compared, the path L with the shortest length is selected, pheromone is updated, the L is compared with the BestL (the shortest path in the past), the shortest distance is assigned to the BestL, and the path is updated to be the corresponding urban path. The number of iterations is increased by 1 and then the next iteration is performed. And after all iterations are completed, obtaining an optimized path BestList.
1.3) removing the initial city startPoint in the optimized path BestList, and obtaining the cutting sequence of all the overall contours.
Step 1.2) above, a sorted BestList of the outermost contour is obtained, and the initial city startPoint in the optimized path BestList is removed, which is the cutting sequence of all the overall contours. Next, the cutting order of all the cut contours in a single overall contour is to be arranged in the order of the overall contour.
1.4) sorting the overall contours in the sequence according to the sequence of the outmost contours sorted by the ant colony algorithm by a greedy algorithm, and then adding the overall contours into the cut contour set cutFigures one by one in sequence.
And cutting the BestList according to the outermost layer outline obtained by the ant colony algorithm, and sequencing the whole outline where each outermost layer outline is positioned according to layers. Since the overall profile is a nested profile, the cutting must follow the order of cutting from the inner layer profile to the outer layer profile, so the overall profile should be arranged from the inner layer to the outer layer. In each overall contour, only one outermost contour is necessary, but a plurality of contours belonging to the same layer in the inner contour are possible, and in order to reduce the empty running path, the contours of the same layer need to be sequenced. That is, the principle that should be followed to rank a single overall contour is: (1) the different layer profiles are to be arranged from the inner layer to the outer layer; (2) the same layer of profiles should be arranged to minimize the empty path during cutting. Because the number of contours is generally not large at the same level, a greedy algorithm may be used for ordering.
The specific process of ordering the individual global contours in the order in BestList is:
1.4.1) all the cut profiles in the overall profile corresponding to the first outermost profile are first arranged in ascending order of the hierarchical order.
The layer 1 contours are ordered first. Still starting from the tool starting position startPoint, taking all contours of the current overall contour, which are positioned on the 1 st layer, enabling the contour starting points to represent the positions of the corresponding contours to sequence the selected 1 st layer contours, taking the starting points of the contours to form point sets points, sequencing the data points in the point sets points by taking the startPoint as the starting point according to a greedy algorithm, adding the corresponding cutting contours into the cutting contour set cutFigures according to the sequence of the sequenced data points after sequencing is completed, and finishing sequencing the 1 st layer contours.
Then the layer 2 contours are ordered. And assigning the end point of the last cutting contour in the cutting contour set cutFigures to startPoint as a new sequencing start point, sequencing the contours of the layer 2 by taking the startPoint as a start point by using a greedy algorithm, sequencing the points of the point set by taking the start points of all the contours of the layer 2 as the same as the sequencing method of the contours of the layer 1, sequencing the points of the point set by using the startPoint as the start point by using the greedy algorithm, adding the corresponding cutting contours into the cutting contour set cutFigures according to the sequence of the sequenced data points after sequencing is finished, and finishing sequencing the contours of the layer 2.
The remaining layer profile ordering method is the same. It should be noted that: before the sequencing of each layer starts, the sequencing starting point startPoint needs to be updated, so that the starting point startPoint is the end point of the last cutting contour of the current cutting contour set cutfixures. Then, taking startPoint as a starting point, sequencing the cutting contours of the layer by using a greedy algorithm, and finally adding the cutting contours into the cutting contour set cutFigures according to the sequenced sequence.
Through the above operations, all layer profiles are sorted and added to the cut profile set cutconfigurations, that is, the overall profile corresponding to the first outermost profile is sorted.
1.4.2) then all the cut profiles in the global profile corresponding to the second outermost profile are arranged in ascending order of the hierarchical order.
The sorting method is substantially the same as the sorting method of the first overall contour, except that startPoint needs to be updated to the end point of the last cutting contour in the cutting contour set cutfixures before sorting. And then sorting according to a sorting method of the first overall contour.
1.4.3) all cut profiles in the third and all following global profiles are sorted in ascending order in hierarchical order in the order in BestList. The alignment method is the same as that of the second overall profile.
And after all the cutting outlines are sequenced, obtaining a cutting outline set cutFigures sequenced by all the cutting outlines on the layout, and finishing the sequencing of the cutting.
2. If the cutting knives of the profile have various types, the sequence of cutting the profile is arranged, and the specific steps are as follows:
2.1) grouping all the overall profiles differently according to the cutting tools.
If the analysis file finds that various cutting tools are needed for cutting the contours, all the cutting contours need to be grouped according to different cutting tools, and then all the contours in each group are sequenced. The operation is to ensure that one cutter is used for cutting all the corresponding cutting profiles, and then the other cutter is used for cutting the other cutting profiles.
2.2) traversing a plurality of groups of overall profiles which are grouped according to different cutters, sequencing each group of overall profiles, and adding the sequenced cutting profiles into a cutting profile set cutFigures in sequence. Each group of overall profiles comprises at least one overall profile, and the specific sorting method of each group of overall profiles is as follows:
2.2.1) obtaining the ordering starting point of the whole contour of the group.
If the first group of overall profiles is selected, the sequencing starting point is the starting position of the cutter. According to the actual cutting situation, the initial position of the cutter is related to whether the cutting layout has the preset position point. If no preset positioning point exists, the cutter starting position startPoint is usually considered as the coordinate origin position of the current layout; if the preset positioning point exists, the cutter starting position startPoint is the preset positioning point of the current layout.
If not, the ordering starting point is the end point of the last cutting contour of the cutting contour set cutfixures, and the end point is assigned to startPoint as the ordering starting point.
2.2.2) finding out all the outermost layer outlines of the group according to the group number and sequencing the outlines by an ant colony algorithm. And cutting the BestList according to the outermost layer outline cut sequence discharged by the ant colony algorithm, and sequencing the whole outline where each outermost layer outline is positioned according to layers. After traversing, the whole outlines of the group (groups divided by different cutters) are sorted and finished finally. The sorting method is the same as the above-described specific process of sorting the individual global profiles in the order in the BestList using a cutter, and is not repeated here.
After the group of overall outlines are subjected to hierarchical sequencing according to the sequence in the BestList, all the outlines in the group of overall outlines are sequenced, the sequenced outlines are added into the cut outline set cutFigures, and the sequencing of the group of overall outlines is completed. And starting to sort the next group of overall outlines until all groups of overall outlines are traversed.
And S4, obtaining the cutting contour set which is finished by sequencing, and finishing the cutting operation of the layout to be cut according to the sequencing of the data points in the cutting contour set.
And after all the groups are traversed, obtaining a sequenced cutting outline set cutFigures, and completing the cutting operation of the to-be-cut page according to the sequencing of the data points in the cutting outline set to obtain the required product.
According to the method, the nested contours are layered, all the layered contours are ranked according to the ant colony algorithm and the greedy algorithm, and the cutting contours corresponding to different cutters are grouped and ranked, so that the sum of the idle running path distances of the cutters is minimum in the process from the beginning to the completion of cutting all the contours, unnecessary idle running strokes and cutter changing influences of the cutters are reduced, the cutting efficiency is greatly improved, the cutting time is saved, the application range is wide, and the method is particularly suitable for the advertisement cutting industry and the clothing cutting industry.
The technical features of the embodiments described above may be arbitrarily combined, and for the sake of brevity, all possible combinations of the technical features in the embodiments described above are not described, but should be considered as being within the scope of the present specification as long as there is no contradiction between the combinations of the technical features.
The above-mentioned embodiments only express the more specific and detailed embodiments described in the present application, but not be construed as limiting the claims. It should be noted that, for a person skilled in the art, several variations and modifications can be made without departing from the concept of the present application, which falls within the scope of protection of the present application. Therefore, the protection scope of the present patent shall be subject to the appended claims.
Claims (5)
1. A path optimization method of a multi-layer nested contour is characterized by comprising the following steps: the path optimization method of the multilayer nested contours comprises the following steps:
s1, acquiring all cutting outlines of the layout to be cut;
s2, traversing all cutting outlines, and marking each cutting outline with a group number and a hierarchy number, wherein the steps are as follows:
s21, a preset first variable number1 ═ i, and a second variable number2 ═ k;
s22, judging whether a parent contour of the current cutting contour exists in the rest cutting contours based on a ray method, if so, judging that the current cutting contour is not the outermost contour, otherwise, judging that the current cutting contour is the outermost contour, setting i as i +1 and number1 as i, and marking the group number of the current outermost contour as number1 and the hierarchy number as number 2;
s23, updating the current cutting contour to be the next cutting contour, and returning to execute the step S22 until all cutting contours are traversed;
s24, acquiring the sub-contours of the outermost contours based on a ray method, marking the group numbers of the sub-contours as the group numbers corresponding to the outermost contours, and dividing the cutting contours with the same group numbers into an integral contour;
s25, marking all cutting contours of all overall contours in ascending order by level numbering based on a ray method, and arranging all cutting contours of all overall contours in the reverse order by level numbering;
s3, judging whether the type of the cutter is more than one, if not, grouping all the overall outlines into one group and sequencing each group of overall outlines, if so, grouping all the overall outlines according to the type of the cutter, traversing each group of overall outlines and sequencing each group of overall outlines, wherein the method specifically comprises the following steps:
s31, obtaining the initial position of the cutter of the current group of overall outlines, if the current group of overall outlines is the first group, judging whether the layout to be cut has a preset site, if so, the initial position of the cutter is a preset positioning point, if not, the initial position of the cutter is the origin of coordinates of the layout to be cut, and if the current group of overall outlines is not the first group, the initial position of the cutter is the terminal point of the last cutting outline of the previous group of overall outlines;
s32, storing the initial position of the cutter and the starting point of the outermost layer contour of each overall contour into a first data set, and performing path optimization on data points in the first data set based on an ant colony algorithm from the initial position of the cutter to obtain an optimized path;
s33, removing the initial position of the cutter in the optimized path, wherein the sequencing of the rest data points in the optimized path is the cutting sequence of the corresponding overall contour;
s34, sequencing all the cutting contours in the overall contours according to the cutting sequence of the overall contours, which is specifically as follows:
s341, sorting the starting points of the first layer of cutting contours based on a greedy algorithm by taking the starting position of the cutter as the starting point of the first overall contour, and adding the corresponding cutting contours into a cutting contour set according to the sequence of the sorted data points;
s342, updating the starting point to be the end point of the last cutting contour in the cutting contour set, sequencing the starting points of the next layer of cutting contours based on a greedy algorithm, adding the corresponding cutting contours into the cutting contour set according to the sequence of the sequenced data points, and executing in a circulating manner until all cutting contours in the current overall contour are traversed;
s343, updating the starting point as the end point of the last cutting contour in the cutting contour set, and sequencing all cutting contours in the next overall contour until the current group of overall contours is traversed;
and S4, obtaining the cutting contour set which is finished by sequencing, and finishing the cutting operation of the layout to be cut according to the sequencing of the data points in the cutting contour set.
2. The path optimization method of a multi-layered nested contour of claim 1, characterized by: in step S22, the method for determining whether there is a parent contour of the current cutting contour in the remaining cutting contours based on the ray method specifically includes:
and taking a contour point of the current cutting contour, making a ray from the contour point along any direction, matching the contour point with any selected cutting contour in the other cutting contours, judging the number of intersection points of the ray and the selected cutting contour, if the number is an odd number, considering that the current cutting contour is positioned in the selected cutting contour, and considering that the selected cutting contour is a father contour of the current cutting contour, and if the number is an even number, considering that the current cutting contour is positioned outside the selected cutting contour, and not considering that the selected cutting contour is the father contour of the current cutting contour.
3. The path optimization method of a multi-layered nested contour of claim 1, characterized by: in step S25, the step of marking all cutting contours of each overall contour in ascending order by hierarchical numbering based on the ray method includes:
and acquiring the outermost layer contour of all unmarked layer numbered cutting contours in the whole contour based on a ray method, setting k to be k +1 and number2 to be k, marking the layer number to be number2, and executing in a circulating way until all cutting contours of the whole contour are traversed.
4. The path optimization method of a multi-layered nested contour of claim 1, characterized by: in step S32, performing path optimization on the data points in the first data set based on the ant colony algorithm from the start position of the tool to obtain an optimized path, which is specifically as follows:
s321, sequencing data points in the first data set based on a greedy algorithm from the initial position of the cutter to obtain an initial path;
s322, updating pheromone based on the shortest path length L obtained in the nth iteration of the ant colony algorithm;
s323, comparing the initial path length BestL with the shortest path length L, updating the initial path length BestL ═ min { BestL, L }, updating the path as a corresponding path, setting n ═ n +1, and returning to execute step S322 until the iteration is completed, thereby obtaining an optimized path.
5. The path optimization method of a multi-layered nested contour of claim 1, characterized by: the ant colony algorithm adopts the following parameters:
the initialization pheromone concentration is 5, the ant number m is the outline number multiplied by 1.5, the pheromone factor is equal to 1, the heuristic function factor beta is 5, the pheromone volatilization factor rho is 0.1, and the iteration frequency is 50 times.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210425783.2A CN114589343A (en) | 2022-04-21 | 2022-04-21 | Path optimization method of multilayer nested contours |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210425783.2A CN114589343A (en) | 2022-04-21 | 2022-04-21 | Path optimization method of multilayer nested contours |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN114589343A true CN114589343A (en) | 2022-06-07 |
Family
ID=81821154
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210425783.2A Pending CN114589343A (en) | 2022-04-21 | 2022-04-21 | Path optimization method of multilayer nested contours |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114589343A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115781043A (en) * | 2022-11-14 | 2023-03-14 | 浙江大学 | Laser common edge cutting processing path generation method |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1993003452A1 (en) * | 1991-08-05 | 1993-02-18 | Motorola, Inc. | Multiple layer road memory storage device and route planning system |
| CN101451305A (en) * | 2008-12-18 | 2009-06-10 | 浙江工业大学 | Control method of cutter idle stroke path during clothing piecing and cloth sample cutting process |
-
2022
- 2022-04-21 CN CN202210425783.2A patent/CN114589343A/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1993003452A1 (en) * | 1991-08-05 | 1993-02-18 | Motorola, Inc. | Multiple layer road memory storage device and route planning system |
| CN101451305A (en) * | 2008-12-18 | 2009-06-10 | 浙江工业大学 | Control method of cutter idle stroke path during clothing piecing and cloth sample cutting process |
Non-Patent Citations (3)
| Title |
|---|
| 刘想；张永林；陈利敏: "包含多重嵌套轮廓线的激光切割空移路径规划" * |
| 李坚;朱海飞;黎奕辉;张浩;管贻生;杨宇峰;李国标;: "包含多重嵌套封闭环的平面切割建模与优化" * |
| 汪冲;李俊;李波;张粤;: "改进的蚁群与粒子群混合算法求解旅行商问题" * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115781043A (en) * | 2022-11-14 | 2023-03-14 | 浙江大学 | Laser common edge cutting processing path generation method |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102799745B (en) | Method for quickly and automatically assembling residual steel plates | |
| GB2592335A (en) | Partitioning knowledge graph | |
| CN109325316B (en) | Efficient Parallel Slicing Method for STL Model Based on Common Point Welding Sorting | |
| CN114589343A (en) | Path optimization method of multilayer nested contours | |
| CN104573039A (en) | Keyword search method of relational database | |
| CN109308303B (en) | Multi-table connection online aggregation method based on Markov chain | |
| CN106843153B (en) | A Reusable NC Process Mapping Method Oriented to Process Scheme | |
| CN107239549A (en) | Method, device and the terminal of database terminology retrieval | |
| CN112935575A (en) | Cutting path optimization method and device and computer readable storage medium | |
| CN111652463A (en) | APS (active pixel System) recursive system, method and equipment based on fractal self-similarity principle | |
| Khachay et al. | PCGLNS: A heuristic solver for the precedence constrained generalized traveling salesman problem | |
| CN117314078A (en) | Deadlock-free scheduling method of flexible manufacturing system based on Petri network and neural network | |
| CN115700647A (en) | Workshop flexible operation scheduling method based on tabu search genetic algorithm | |
| CN112462704A (en) | Mixed flow batch scheduling optimization method for sensor workshop production | |
| CN107067200B (en) | Operation method and device for bill of material data | |
| Cuellar‐Usaquén et al. | Modeling and solving the endpoint cutting problem | |
| CN114833461B (en) | Free steering method and sorting device for non-closed contour of laser cutting path | |
| CN102081678B (en) | A Search Method for Optimal Execution Plan in Database Query | |
| US20220214669A1 (en) | System and method to facilitate a search for a hybrid-manufacturing process plan | |
| CN111881171A (en) | Drawing identification recommendation method and system based on data analysis | |
| CN103324640B (en) | A kind of method, device and equipment determining search result document | |
| Chen et al. | Algorithms for interval structures with applications | |
| Strasser | PACE solver description: Tree depth with FlowCutter | |
| CN116128177A (en) | Planar cutting path planning method, system and computer storage medium | |
| CN109726895B (en) | Multi-target-point task execution planning method and device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20220607 |
|
| RJ01 | Rejection of invention patent application after publication |