# An Approach of Path Optimization Algorithm for 3D Concrete Printing Based on Graph Theory
## 1 Introduction  
Three-dimensional concrete printing is a kind of additive manufacturing based on the digital model, with special \"ink\" made of cementitious materials, admixtures, additives, special fibers, and aggregates [1]. The printing process converts the architectural model into a three-dimensional design drawing with computer graphics, moves according to the set printing path, continuously extrudes the concrete slurry, and adds material layer by layer through layered processing and superposition molding to build the building [2]. The molding process is like fused deposition modelling (FDM), which is a linear lamination molding of the slurry extruded through the print head without the aid of a template [3]. In recent research, 3D concrete printing technology has shown great application potential in the construction field because it has higher construction efficiency, lower production cost, and less human resource investment than conventional construction methods [4]. Designers can also design the internal structure of concrete components according to mechanical principles to complete more complex and high-quality architectural designs because of the characteristics of the layered printing mode of 3D concrete printing [5]. However, the current 3D concrete printing technology is not yet mature, and there are still problems, such as the rough surface of concrete components, low forming quality, and long printing time [6]. These problems have seriously affected the development of 3D concrete printing. At present, scholars are solving the problem of long printing time by optimizing the printing path [7]. In the work of [PERSON] et al. [8], the nozzle path planning problem is formulated as an undirected rural postman problem (URPP), and a computationally efficient heuristic search algorithm is proposed to find fast routes and mitigate overheads in printing processes. Both simulation and experimental results concur that the proposedalgorithm can significantly speed up printing processes. [PERSON] et al. [9] presented a graphical model of the three-dimensional (3D) printing process and used the solution to the Chinese postman problem (CPP) to optimize the motion of an extruder on a given mesh. It enables the printer to print arbitrary lattice structures at the optimal time. This method significantly saves printing time, which is essential for better AM. Transitions are movements of the nozzle from a path endpoint to a path start point. These transitions diminish printing quality by causing strings. [PERSON] et al. [10] proposed a method that minimizes the number of transitions based on directional parallel line segments. A genetic algorithm solver was developed by designing a TSP-oriented mutation method. Compared with other algorithms, their algorithm generates paths with fewer transitions. [PERSON] et al. presents a novel type of foamed concrete [11]. This novel material can keep its shape in the fresh state due to enhanced consistency and viscosity. This peculiarity lends itself to being implemented in automated extrusion production processes and 3D printing applications without the use of formwork. [PERSON] et al. [1] described an algorithm for minimizing the nonproductive time or 'airtime' for milling by optimally connecting different nozzle path segments. This problem is formulated as a generalized traveling salesman problem with precedence constraints and is solved using a heuristic method. This method gives a significant improvement over random solutions and local search methods. The time savings depend on the problem size, and as the size of the problem increases, the benefits of the algorithm become apparent. In addition, scholars have proposed a variety of path optimization algorithms to solve various problems encountered in 3D concrete printing. Among them, [PERSON] et al. [12] proposed a support generation method through printing path planning, with the aim of solving 3D concrete printing still suffering from redundant support material usage when printing parts with overhanging features.