| 摘要(英) |
Owing to the universality of high-tech production technology and high-speed internet infrastructure, remote manufacturing and automatically process scheduling has been much more common these days in modern factory. To reduce both time and financial costs, we must improve the efficiency of algorithm, which can curtail both computing time and obtain majorized and operational path sequence. Hence, developing specialized solution algorithm for restricted condition can’t be more important nowadays.
This research aims to discuss the sequential solution of computer numerical control machine or robotic arm that is subject to designed capacity, which requires suppling materials from one depot through reciprocating motion. Since this kind of problem is similar to the specialized Vehicle Routing Problem (VRP), it is impossible to obtain the best solution in non-deterministic polynomial time. Therefore, we decided to create an algorithm by improving exiting algorithm and combine it with other algorithms for this research. This algorithm should obtain approximate solution in all feasible path sequence and reduce both computational burden and time complexity.
The core concept of this algorithm is based on K-means algorithm and is implemented by C# in this research. The initialized method this algorithm is a customized binary outliers’ method. After that, the algorithm will recursively pick appropriate nodes as clusters and renew the unsatisfied node list till the list is completely traversed. By comparison, this algorithm is confirmed to achieve better performance on path cost than Greedy algorithm, Zipzap sorting method, or typical K-means algorithms when the number of unsorted nodes is above a dozen. Furthermore, the computation time of this algorithm is also far below sorting nodes by complete induction method, which can be deemed as predictable finite time. |
| 參考文獻 |
[1]G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem”, Management Science, Vol. 6, No. 1, pp. 80-91, Oct. 1959
[2]Steinhaus, H., “Sur la division des corps mat ́eriels en parties”, Bulletin de l’acad ́emiepolonaise des sciences, Cl. III — Vol. IV, No. 12, 1956.
[3]MacQueen, J. B, “Some Methods for classification and Analysis of Multivariate Observations”, Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability., University of California Press: 281–297, 1967.
[4]Marco Capó, Aritz Pérez, and José A. Lozano, “A Recursive K-means Initialization Algorithm for Massive Data”, Actas de la XVI Conferencia CAEPIA, Albacete, 2015.
[5]Adyan Nur Alfiyation, Wayan Firdaus Mahmudi, and Yusuf Priyo Anggodo, “K-Means Clustering and Genetic Algorithm to Solve Vehicle Routing Problem with Time Windows Problem”, Indonesian Journal of Electrical Engineering and Computer Science, Vol. 11, No. 2, pp.462-468, Aug. 2018.
[6]Pranavi Singanamala, K. Dharma R, and P. venkataramaiahh, “Solution to a Multi Depot Vehicle Routing Problem Using K-means Algorithm, Clarke and Wright Algorithm and Ant Colony Optimization’, International Journal of Applied research ISSN 0973-4562, Vol.13, No. 21, pp. 15236-15246, 2018.
[7]J. Oyelade, et al., "Data Clustering: Algorithms and Its Applications", 2019 19th International Conference on Computational Science and Its Applications (lCCSA), pp. 71-81, 2019.
[8]David Arthur, Sergei Vassilviskii, “K-Means++: The Advantages of Careful Seeding”, SODA ′07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp.1027-1035, 2007.
[9]Leonard Kaufman, Peter J. Rousseeuw, “Partitioning Around Medoids (Program PAM)”, Wiley Series in Probability and Statistics, 1990.
[10]Robert Tarjan, “Depth-First Search and linear graph algorithm”, 12th Annual Symposium on Switching and Automata Theory, 1971. |
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
至系統瀏覽論文 (2026-8-30以後開放)
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit