Article Sidebar

PDF
Date Published: 10/10/2022
Online Published: 10/10/2022
Abstract Views: 113
Views PDF: 145
DOI: https://doi.org/10.52714/dthu.11.5.2022.977
Issue
Vol. 11 No. 5 (2022): Natural Sciences Issue (English)
Section
Natural Sciences Issue
How to Cite
Pham, M. H. (2022). Travelling salesman problem modelling by mixed integer linear programming of python (MIP). Dong Thap University Journal of Science, 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)

My Hanh Pham1,
1 An Giang University, Vietnam National University, Ho Chi Minh City, Vietnam

Main Article Content

Abstract

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.

Article Details

Creative Commons License

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

Keywords

Mixed integer linear programming, python, travelling salesman problem

References

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.