旅行銷售員問題所要求解的是銷售員到n座城市推展業務，經過每座城市一次並回到起始城市的最短路徑。旅行銷售員問題一直是計算機科學、數學等學術領域欲解決的問題之一，也廣泛應用於不同的產業，如宅配業的路徑規劃、印刷版的鑽孔路徑等。本文提出以編碼-解碼的網路架構搭配啟發式解法求解大規模旅行銷售員問題，以先分群後合併的方法求解出最佳解，並以傳統旅行銷售員的解法為基礎，提出時間相依型旅行銷售員問題的啟發式解法，透過將原始路經分段，再以啟發式方法將各路徑片段合併，逐漸完成最佳解。實驗部分，大規模旅行銷售員問題中，分別於節點規模為300、500、800、1000的範例中實測，於總共40個範例中，路徑長度皆優於蟻群演算法。時間相依型旅行銷售員問題中，設計了10個節點規模為300個節點的範例，10個範例中有8個範例的行徑時間優於貪婪法。文末則以台灣台南市的境內超商地圖作為測試範例，其結果也是優於貪婪法，顯示本文解法的可行性。

The traveling salesman problem is to seek the shortest path for a salesman to sell his business in n cities, passing through each city once and then returning to the starting city. The traveling salesman problem has been one of the most important problems in the academic fields of computer science and mathematics, as well as being widely used in different industries, such as path planning in the delivery industry and drilling paths for PCB. In this paper, we propose a heuristic method using Encoder-Decoder network structure to solve the large-scale traveling salesman problem. In the experimental part, the path length of the large-scale traveling salesman problem outperforms ant colony optimization for a total of 40 examples with node sizes of 300, 500, 800, and 1000. In the time dependent traveling salesman problem, 10 examples with 300 nodes are designed, and 8 out of 10 examples outperformed the greedy method.

Bahdanau, D., Cho, K., & Bengio, Y. (2014). Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473.

Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.

Bodin, L. (1983). Routing and scheduling of vehicles and crews, the state of the art. Comput. Oper. Res., 10(2), 63-211.

Chorowski, J. K., Bahdanau, D., Serdyuk, D., Cho, K., & Bengio, Y. (2015). Attention-based models for speech recognition. Advances in neural information processing systems, 28.

Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the third annual ACM symposium on Theory of computing,

Costa, P. R. d. O., Rhuggenaath, J., Zhang, Y., & Akcay, A. (2020). Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning Proceedings of The 12th Asian Conference on Machine Learning, Proceedings of Machine Learning Research. https://proceedings.mlr.press/v129/costa20a.html

Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., & Rousseau, L.-M. (2018). Learning heuristics for the tsp by policy gradient. International conference on the integration of constraint programming, artificial intelligence, and operations research,

Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28-39.

Dwivedi, V., Chauhan, T., Saxena, S., & Agrawal, P. (2012). Travelling salesman problem using genetic algorithm. IJCA proceedings on development of reliable information systems, techniques and related issues (DRISTI 2012), 1, 25.

Flood, M. M. (1956). The traveling-salesman problem. Operations research, 4(1), 61-75.

Goh, Y. L., Lee, W. S., Bresson, X., Laurent, T., & Lim, N. (2022). Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem. arXiv preprint arXiv:2203.00903.

Hartigan, J. A., & Wong, M. A. (1979). Algorithm AS 136: A k-means clustering algorithm. Journal of the royal statistical society. series c (applied statistics), 28(1), 100-108.

Kitaev, N., Kaiser, Ł., & Levskaya, A. (2020). Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451.

Kool, W., Van Hoof, H., & Welling, M. (2018). Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475.

Mele, U. J., Gambardella, L. M., & Montemanni, R. (2021). A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem. Algorithms, 14(9), 267. https://www.mdpi.com/1999-4893/14/9/267

Padberg, M., & Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review, 33(1), 60-100.

Song, C.-H., Lee, K., & Lee, W. D. (2003). Extended simulated annealing for augmented TSP and multi-salesmen TSP. Proceedings of the International Joint Conference on Neural Networks, 2003.,

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., & Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems,

Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. arXiv preprint arXiv:1506.03134.