An improved genetic algorithm and its application to resolve cutting stock problem arc presented. It is common to apply simple genetic algorithm （SGA） to cutting stock problem, but the huge amount of computing of SG...An improved genetic algorithm and its application to resolve cutting stock problem arc presented. It is common to apply simple genetic algorithm （SGA） to cutting stock problem, but the huge amount of computing of SGA is a serious problem in practical application. Accelerating genetic algorithm （AGA） based on integer coding and AGA＇s detailed steps are developed to reduce the amount of computation, and a new kind of rectangular parts blank layout algorithm is designed for rectangular cutting stock problem. SGA is adopted to produce individuals within given evolution process, and the variation interval of these individuals is taken as initial domain of the next optimization process, thus shrinks searching range intensively and accelerates the evaluation process of SGA. To enhance the diversity of population and to avoid the algorithm stagnates at local optimization result, fixed number of individuals are produced randomly and replace the same number of parents in every evaluation process. According to the computational experiment, it is observed that this improved GA converges much sooner than SGA, and is able to get the balance of good result and high efficiency in the process of optimization for rectangular cutting stock problem.展开更多
This study presents a two-echelon inventory routing problem (2E-IRP) with an end-of-tour replenishment (ETR) policy whose distribution network consists of a supplier, several distribution centers (DCs) and several ret...This study presents a two-echelon inventory routing problem (2E-IRP) with an end-of-tour replenishment (ETR) policy whose distribution network consists of a supplier, several distribution centers (DCs) and several retailers on a multi-period planning horizon. A formulation of the problem based on vehicle indices is proposed in the form of a mixed integer linear program (MILP). The mathematical model of the problem is solved using a branch and cut (B&C) algorithm. The results of the tests are compared to the results of a branch and price (B&P) algorithm from the literature on 2E-IRP with a classical distribution policy. The results of the tests show that the B&C algorithm solves 197 out of 200 instances (98.5%). The comparison of the B&C and B&P results shows that 185 best solutions are obtained with the B&C algorithm on 197 instances (93.9%). Overall, the B&C algorithm achieves cost reductions ranging from 0.26% to 41.44% compared to the classic 2E-IRP results solved with the B&P algorithm, with an overall average reduction of 18.08%.展开更多
The concept of cutting platform is proposed and realized based on the latest two step automated tape laying (Two step ATL)technology,which separates prepreg cutting process from tape laying to improve productivity for...The concept of cutting platform is proposed and realized based on the latest two step automated tape laying (Two step ATL)technology,which separates prepreg cutting process from tape laying to improve productivity for large parts with small features.Two step ATL is more efficient than conventional layup because ply patches are pre cut in a separate operation.The concept of the prepreg tape cutting experimental platform with two cutters is introduced.Further,based on the automatic tape laying trajectory planning software,a two cutter cutting algorithm is proposed.Cutting experiments are reported to validate both the concept of cutting platform and cutting algorithm.展开更多
Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and ...Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.展开更多
Four new trigonometric Bernstein-like basis functions with two exponential shape pa- rameters are constructed, based on which a class of trigonometric Bézier-like curves, anal- ogous to the cubic Bézier curv...Four new trigonometric Bernstein-like basis functions with two exponential shape pa- rameters are constructed, based on which a class of trigonometric Bézier-like curves, anal- ogous to the cubic Bézier curves, is proposed. The corner cutting algorithm for computing the trigonometric Bézier-like curves is given. Any arc of an eliipse or a parabola can be represented exactly by using the trigonometric Bézier-like curves. The corresponding trigonometric Bernstein-like operator is presented and the spectral analysis shows that the trigonometric Bézier-like curves are closer to the given control polygon than the cu- bic Bézier curves. Based on the new proposed trigonometric Bernstein-like basis, a new class of trigonometric B-spline-like basis functions with two local exponential shape pa- rameters is constructed. The totally positive property of the trigonometric B-spline-like basis is proved. For different values of the shape parameters, the associated trigonometric B-spline-like curves can be C2 N FC3 continuous for a non-uniform knot vector, and C3 or C5 continuous for a uniform knot vector. A new class of trigonometric Bézier-like basis functions over triangular domain is also constructed. A de Casteljau-type algorithm for computing the associated trigonometric Bézier-like patch is developed. The conditions for G1 continuous joining two trigonometric Bézier-like patches over triangular domain arededuced．展开更多
基金This project is supported by National Natural Science Foundation of China (No.50575153)Provincial Key Technology Projects of Sichuan, China (No.03GG010-002)
文摘An improved genetic algorithm and its application to resolve cutting stock problem arc presented. It is common to apply simple genetic algorithm （SGA） to cutting stock problem, but the huge amount of computing of SGA is a serious problem in practical application. Accelerating genetic algorithm （AGA） based on integer coding and AGA＇s detailed steps are developed to reduce the amount of computation, and a new kind of rectangular parts blank layout algorithm is designed for rectangular cutting stock problem. SGA is adopted to produce individuals within given evolution process, and the variation interval of these individuals is taken as initial domain of the next optimization process, thus shrinks searching range intensively and accelerates the evaluation process of SGA. To enhance the diversity of population and to avoid the algorithm stagnates at local optimization result, fixed number of individuals are produced randomly and replace the same number of parents in every evaluation process. According to the computational experiment, it is observed that this improved GA converges much sooner than SGA, and is able to get the balance of good result and high efficiency in the process of optimization for rectangular cutting stock problem.
文摘This study presents a two-echelon inventory routing problem (2E-IRP) with an end-of-tour replenishment (ETR) policy whose distribution network consists of a supplier, several distribution centers (DCs) and several retailers on a multi-period planning horizon. A formulation of the problem based on vehicle indices is proposed in the form of a mixed integer linear program (MILP). The mathematical model of the problem is solved using a branch and cut (B&C) algorithm. The results of the tests are compared to the results of a branch and price (B&P) algorithm from the literature on 2E-IRP with a classical distribution policy. The results of the tests show that the B&C algorithm solves 197 out of 200 instances (98.5%). The comparison of the B&C and B&P results shows that 185 best solutions are obtained with the B&C algorithm on 197 instances (93.9%). Overall, the B&C algorithm achieves cost reductions ranging from 0.26% to 41.44% compared to the classic 2E-IRP results solved with the B&P algorithm, with an overall average reduction of 18.08%.
基金supported by the National Science and Technology Major Project(No.2016ZX04002-005)
文摘The concept of cutting platform is proposed and realized based on the latest two step automated tape laying (Two step ATL)technology,which separates prepreg cutting process from tape laying to improve productivity for large parts with small features.Two step ATL is more efficient than conventional layup because ply patches are pre cut in a separate operation.The concept of the prepreg tape cutting experimental platform with two cutters is introduced.Further,based on the automatic tape laying trajectory planning software,a two cutter cutting algorithm is proposed.Cutting experiments are reported to validate both the concept of cutting platform and cutting algorithm.
基金supported by the Deutsche Forschungsgemeinschaft, project PAWS (NI 369/10)supported by the Studienstiftung des Deutschen Volkes+2 种基金supported by DFG "Cluster of Excellence Multimodal Computing and Interaction"supported by DIAMANT (a mathematics cluster of the Netherlands Organization for Scientific Research NWO)the Alexander von Humboldt Foundation, Bonn, Germany
文摘Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.
基金We, wish to express our gratitude to the referees for their valuable re- marks for improvements. The research is supported by the National Natural Science Foun-dation of China （No. 60970097, No. 11271376）, Postdoctoral Science Foundation of China （2015M571931）, and Graduate Students Scientific Research Innovation Project of Hunan Province （No. CX2012Blll）.
文摘Four new trigonometric Bernstein-like basis functions with two exponential shape pa- rameters are constructed, based on which a class of trigonometric Bézier-like curves, anal- ogous to the cubic Bézier curves, is proposed. The corner cutting algorithm for computing the trigonometric Bézier-like curves is given. Any arc of an eliipse or a parabola can be represented exactly by using the trigonometric Bézier-like curves. The corresponding trigonometric Bernstein-like operator is presented and the spectral analysis shows that the trigonometric Bézier-like curves are closer to the given control polygon than the cu- bic Bézier curves. Based on the new proposed trigonometric Bernstein-like basis, a new class of trigonometric B-spline-like basis functions with two local exponential shape pa- rameters is constructed. The totally positive property of the trigonometric B-spline-like basis is proved. For different values of the shape parameters, the associated trigonometric B-spline-like curves can be C2 N FC3 continuous for a non-uniform knot vector, and C3 or C5 continuous for a uniform knot vector. A new class of trigonometric Bézier-like basis functions over triangular domain is also constructed. A de Casteljau-type algorithm for computing the associated trigonometric Bézier-like patch is developed. The conditions for G1 continuous joining two trigonometric Bézier-like patches over triangular domain arededuced．
