A Relaxation Scheme for TSP-based 3D Printing Path Optimizer

Kai-Yin Fok; Chi-Tsun Cheng; Chi K. Tse; Nuwan Ganganath

doi:10.1109/CyberC.2016.80

A Relaxation Scheme for TSP-based 3D Printing Path Optimizer

Kai-Yin Fok^*
, Chi-Tsun Cheng
, Chi K. Tse
, Nuwan Ganganath

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

18 Citations (Scopus)

Abstract

Additive-layered manufacturing has gained attention in recent years as it has many advantages over conventional injection moulding methods. The optimization of printing trajectories can be formulated as a travelling salesman problem (TSP) and solved accordingly. However, computational complexities of ordinary TSP solvers can increase tremendously with the scale of the problem, which make them impractical. In this work, a relaxation scheme for TSP-based 3D printing path optimizer is proposed. Simulation results show that the proposed scheme can significantly shorten the computational time of the optimization process with insignificant impact on solution quality.

Original language	English
Title of host publication	Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016)
Publisher	IEEE
Pages	382-385
ISBN (Electronic)	978-1-5090-5154-0
DOIs	https://doi.org/10.1109/CyberC.2016.80
Publication status	Published - Oct 2016
Externally published	Yes
Event	8th International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016 - Chengdu, China Duration: 13 Oct 2016 → 15 Oct 2016

Publication series

Name	Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016

Conference

Conference	8th International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016
Place	China
City	Chengdu
Period	13/10/16 → 15/10/16

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Research Keywords

3D printing
Additive manufacturing
Optimisation
Relaxation
TSP

Access Output

10.1109/CyberC.2016.80

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Fok, K.-Y., Cheng, C.-T., Tse, C. K., & Ganganath, N. (2016). A Relaxation Scheme for TSP-based 3D Printing Path Optimizer. In Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016) (pp. 382-385). Article 7864265 (Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016). IEEE. https://doi.org/10.1109/CyberC.2016.80

Fok, Kai-Yin ; Cheng, Chi-Tsun ; Tse, Chi K. et al. / A Relaxation Scheme for TSP-based 3D Printing Path Optimizer. Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016). IEEE, 2016. pp. 382-385 (Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016).

@inproceedings{c1a4aae01c4e4edbb530e66d1315af3c,

title = "A Relaxation Scheme for TSP-based 3D Printing Path Optimizer",

abstract = "Additive-layered manufacturing has gained attention in recent years as it has many advantages over conventional injection moulding methods. The optimization of printing trajectories can be formulated as a travelling salesman problem (TSP) and solved accordingly. However, computational complexities of ordinary TSP solvers can increase tremendously with the scale of the problem, which make them impractical. In this work, a relaxation scheme for TSP-based 3D printing path optimizer is proposed. Simulation results show that the proposed scheme can significantly shorten the computational time of the optimization process with insignificant impact on solution quality.",

keywords = "3D printing, Additive manufacturing, Optimisation, Relaxation, TSP",

author = "Kai-Yin Fok and Chi-Tsun Cheng and Tse, \{Chi K.\} and Nuwan Ganganath",

year = "2016",

month = oct,

doi = "10.1109/CyberC.2016.80",

language = "English",

series = "Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016",

publisher = "IEEE",

pages = "382--385",

booktitle = "Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016)",

address = "United States",

note = "8th International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016 ; Conference date: 13-10-2016 Through 15-10-2016",

}

Fok, K-Y, Cheng, C-T, Tse, CK & Ganganath, N 2016, A Relaxation Scheme for TSP-based 3D Printing Path Optimizer. in Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016)., 7864265, Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016, IEEE, pp. 382-385, 8th International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016, Chengdu, China, 13/10/16. https://doi.org/10.1109/CyberC.2016.80

A Relaxation Scheme for TSP-based 3D Printing Path Optimizer. / Fok, Kai-Yin; Cheng, Chi-Tsun; Tse, Chi K. et al.
Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016). IEEE, 2016. p. 382-385 7864265 (Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A Relaxation Scheme for TSP-based 3D Printing Path Optimizer

AU - Fok, Kai-Yin

AU - Cheng, Chi-Tsun

AU - Tse, Chi K.

AU - Ganganath, Nuwan

PY - 2016/10

Y1 - 2016/10

N2 - Additive-layered manufacturing has gained attention in recent years as it has many advantages over conventional injection moulding methods. The optimization of printing trajectories can be formulated as a travelling salesman problem (TSP) and solved accordingly. However, computational complexities of ordinary TSP solvers can increase tremendously with the scale of the problem, which make them impractical. In this work, a relaxation scheme for TSP-based 3D printing path optimizer is proposed. Simulation results show that the proposed scheme can significantly shorten the computational time of the optimization process with insignificant impact on solution quality.

AB - Additive-layered manufacturing has gained attention in recent years as it has many advantages over conventional injection moulding methods. The optimization of printing trajectories can be formulated as a travelling salesman problem (TSP) and solved accordingly. However, computational complexities of ordinary TSP solvers can increase tremendously with the scale of the problem, which make them impractical. In this work, a relaxation scheme for TSP-based 3D printing path optimizer is proposed. Simulation results show that the proposed scheme can significantly shorten the computational time of the optimization process with insignificant impact on solution quality.

KW - 3D printing

KW - Additive manufacturing

KW - Optimisation

KW - Relaxation

KW - TSP

UR - https://www.scopus.com/pages/publications/85015824258

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85015824258&origin=recordpage

U2 - 10.1109/CyberC.2016.80

DO - 10.1109/CyberC.2016.80

M3 - RGC 32 - Refereed conference paper (with host publication)

T3 - Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016

SP - 382

EP - 385

BT - Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016)

PB - IEEE

T2 - 8th International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016

Y2 - 13 October 2016 through 15 October 2016

ER -

Fok KY, Cheng CT, Tse CK, Ganganath N. A Relaxation Scheme for TSP-based 3D Printing Path Optimizer. In Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC 2016). IEEE. 2016. p. 382-385. 7864265. (Proceedings - 2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, CyberC 2016). doi: 10.1109/CyberC.2016.80

A Relaxation Scheme for TSP-based 3D Printing Path Optimizer

Abstract

Publication series

Conference

UN SDGs

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this