Thanh bên bài viết

PDF
Ngày xuất bản: 10/10/2022
Ngày xuất bản Online: 10/10/2022
Số lượt xem tóm tắt: 137
Số lượt xem PDF: 184
DOI: https://doi.org/10.52714/dthu.11.5.2022.977
Số xuất bản
Tập 11 Số 5 (2022): Chuyên san Khoa học Tự nhiên (Tiếng Anh)
Chuyên mục
Khoa học Tự nhiên (Tiếng Anh)
Trích dẫn bài báo
Pham, M. H. (2022). Travelling salesman problem modelling by mixed integer linear programming of python (MIP). Tạp chí Khoa học Đại học Đồng Tháp, 11(5), 29-34. https://doi.org/10.52714/dthu.11.5.2022.977

Travelling salesman problem modelling by mixed integer linear programming of python (MIP)

Pham My Hanh1,
1 An Giang University, Vietnam National University, Ho Chi Minh City, Vietnam

Nội dung chính của bài viết

Tóm tắt

A famous travelling salesman problem, appearing simple to state but complex to solve, has been widely investigated and various algorithms have been proposed. In this article, mixed integer linear programming of python (MIP) is used to model this problem with varying input data. The result shows that with small input data the modelling code of MIP executing quickly and converging to optimal value, while large scale input data require plenty of computation time; thereby algorithm improvement as well as parallel implementation are suggested.

Chi tiết bài viết

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Từ khóa

Mixed integer linear programming, python, travelling salesman problem

Tài liệu tham khảo

Asani, E. O., Okeyinka, A. E., & Adebiyi, A. A. (2020). A construction tour technique for solving the travelling salesman problem based on convex hull and nearest neighbour heuristics. In 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS) IEEE, 1-4.
Chawda, B. V., & Sureja, N. M. (2012). An ACO approach to solve a variant of TSP. International Journal of Advance Research in Computer Engineering and Technology, 1(5), 222-226.
Dantzig, G., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 2(4), 393-410.
Dhakal, S., & Chiong, R. (2008, August). A hybrid nearest neighbour and progressive improvement approach for Travelling Salesman Problem. In 2008 International Symposium on Information Technology. IEEE, 1, 1-4.
Diamond, S., & Boyd, S. (2016). CVXPY: A Python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1), 2909-2913.
Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. Biosystems, 43(2), 73-81.
Hart, W. E., Laird, C. D., Watson, J. P., Woodruff, D. L., Hackebeil, G. A., Nicholson, B. L., & Siirola, J. D. (2017). Pyomo-optimization modeling in python (Vol. 67). Berlin: Springer.
Hoffman, K. L., Padberg, M., & Rinaldi, G. (2013). Traveling salesman problem. Encyclopedia of operations research and management science, 1, 1573-1578.
Liberti, L., & Maculan, N. (Eds.). (2006). Global optimization: from theory to implementation (Vol. 84). Springer Science & Business Media.
Linderoth, J. T., & Lodi, A. (2010). MILP software. Wiley encyclopedia of operations research and management science, 5, 3239- 3248.
Mitchell, S., OSullivan, M., & Dunning, I. (2011). PuLP: a linear programming toolkit for python. The University of Auckland, Auckland, New Zealand, 65. Retrieved from https://www.dit.uoi.gr/e- class/modules/document/file.php/216/PAPER S/2011.%20PuLP%20- %20A%20Linear%20Programming%20Toolk it%20for%20Python.pdf
Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32-38.
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.