China
Africa
Explore chapters and articles related to this topic
Applications of Artificial Intelligence and Machine Learning Using Additive Manufacturing Techniques
Published in Harish Kumar Banga, Rajesh Kumar, Parveen Kalra, Rajendra M. Belokar, Additive Manufacturing with Medical Applications, 2023
Raj Kumar, Harish Kumar Banga, Parveen Kalra, R. M. Belokar, Rajesh Kumar, Rajender Kumar, Ganesh S. Jadhav
The optimum printing path guides the nozzle to make specific shapes and also helps to reduce the printing and computational time. The nozzle primarily spends time traversing the print segment and transition segment during printing. Thus, there is an immense need to obtain an optimal path with shortened traversing time or distance. Fok et al. presented a 3D-printing trajectory optimiser method for computing the traversing period of the printing nozzle. The travelling salesman problem (TSP) formulates the path optimisation problem by comparing every single print segment to a town and obtaining the quickest route for visiting the entire nation. In every single layer, the optimisation is implemented at the inter-partition level, i.e. print area, and the intra-partition level, i.e. blank area, according to the borders of the areas. Between every inter-partition, TSP is able to compute the route manner and begin the route for visiting every single area. Further, a Christofides algorithm is implemented for getting the shortest visiting time period. At the intra-partition level, the transition segment is the link between the two closest endpoints situated in two neighbouring print areas.
Optimization Using Heuristic Search
Published in Kaushik Kumar, Divya Zindani, J. Paulo Davim, Optimizing Engineering Problems through Heuristic Techniques, 2020
Kaushik Kumar, Divya Zindani, J. Paulo Davim
Although approximation and heuristic algorithms yield feasible solution, there exists some differences between heuristics and approximation algorithms. The difference lies that approximations guarantee quality of the solutions on the basis of worst-case scenarios. As for instance, the Christofides’ algorithm that is used for solving the traveling salesman problem has a worst quality ratio of 1.5. Another example is that of next fit algorithm that has the worst quality ratio of 2. On the other hand, most heuristics have no similar mathematical bounds that can aid in adjudging their quality. However, research in this direction is underway to evaluate the quality of such non-optimal algorithms.
Hamilton Cycles
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
This gives a graph G − T + M which is Eulerian. It is quite possible that G is a multigraph. We now find an Euler tour in G and use it to construct a TSP tour C of cost at most W(T) + W(M). This is called Christofides’ algorithm.
Toward practical algorithms for activity chain optimization
Published in Transportation Letters, 2021
Domokos Esztergár-Kiss, Viktor Remeli
If the problem size or structure is such that the exact optimum is not efficiently obtainable, approximations and heuristics can be employed. The most important TSP approximation to note is the Christofides algorithm (Christofides 1976), which runs in polynomial time () and guarantees that the obtained solution’s cost will be within of the optimum, but also requires the TSP to be metric (i.e. edge weights have to satisfy the triangle condition). No other polynomial algorithm to date can deliver a tighter bound. The nearest neighbor heuristic, in contrast, only guarantees an upper approximation ratio bound of in the case of metric TSP, and provides no guarantees otherwise (Cook 2012). An even looser bound of is given by the fast-running Lin–Kernighan (LKH) heuristic (Helsgaun 2000) which gradually employs so-called 2-opt, 3-opt and 5-opt improvements and very often produces optimal results in practice (Rego et al. 2011). Other heuristic approaches include large neighborhood searches (Smith and Imeson 2017), simulated annealing (Barach et al. 2012), ant colony optimization (Kona and Burde 2015; Yao et al. 2016; Nadizadeh and Kafash 2019) and genetic algorithms (Grefenstette 1985). (Esztergár-Kiss, Rózsa, and Tettamanti 2018) describe a genetic algorithm approach to the ACO problem.
Bi-sided facility location problems: an efficient algorithm for k-centre, k-median, and travelling salesman problems
Published in International Journal of Systems Science: Operations & Logistics, 2023
In this section, we propose an efficient heuristic algorithm for FL&TSP using Delaunay triangulation and Christofides Algorithm. Before going into details, we explain it roughly. The algorithm starts with a population of random solutions. It computes the values of the objective of the solutions. To this end, we use -approximation algorithm for finding TSP tour. Then, algorithms exploit non-dominated solutions and generate a new population of solutions using the Delaunay triangulation graph of all potential facilities. This process is repeated to achieve a set of admissible non-dominated solutions.
A short survey of sustainable material extrusion additive manufacturing
Published in Australian Journal of Mechanical Engineering, 2023
As a critical step in the process planning of AM, path planning plays a significant role in affecting the production time and energy consumption by means of determining the paths for the print head’s movement. Path planning is the process of planning the nozzle moving paths along the sliced parts. Investigations have been conducted on improving path generation/path optimisation for saving more energy, material consumption or fabrication time. Jin et al. (Jin et al. 2017c) proposed a non-retraction path planning approach in extrusion-based AM for avoiding the retraction during the deposition process, and hence the time moving along these retracting paths can be saved and the discontinuous deposition can be avoided. They (Jin et al. 2017b) also introduced a path generation method that can fabricate high-quality products while saving overlapped materials in a manufacturing process. For reducing material consumption and production time when building large-volume objects, Jin et al. (Jin, He, and Du 2017) developed a method for printing thin-walled structures through path planning. A novel trajectory generation and planning algorithm is proposed by Luo et al. (Luo and Tseng 2017) for reducing the transition travels between multiple objects when printing many objects simultaneously, thus saving the total cost and time for fabricating those parts. Fok et al. (Fok et al. 2016) developed a path optimiser based on Christofides algorithm (An, Kleinberg, and Shmoys 2015) which can reduce the length of motion paths for saving production time and energy. Thompson and Yoon (Thompson, Yoon, and Yoon 2014) proposed a path planning algorithm that can control motion of an X-Y stage for an arbitrary printing path and desired velocity while minimising material waste. A multi-material-based toolpath planning methodology was proposed by Ozbolat et al. (Ozbolat and Koc 2011) for fabricating hollow structures, saving both material usage and path lengths. Most recently, Jiang (Jiang 2020) proposed a multi-layer path planning method for AM that can save fabrication time.