CONFERENCE PROCEEDINGS
Advanced Search
Home > Proceedings > Volume 12259 > Article
Paper
17 May 2022 Research on the application of linear programming to the travelling salesman problem
Wenjie Bi
Author Affiliations +
Proceedings Volume 12259, 2nd International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2022); 1225946 (2022) https://doi.org/10.1117/12.2638695
Event: 2nd International Conference on Applied Mathematics, Modelling, and Intelligent Computing, 2022, Kunming, China
Abstract
The travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”. This paper focuses on a relatively small case of TSP and uses JAVA and LpSolve (a linear programming solver) to simulate a situation where one wants to choose two to five cities out of ten cities and find the shortest distance to connect those chosen cities. This paper randomly selects ten cities which are Shanghai, Beijing, Qingdao, Seattle, LA, Las Vegas, Boston, Chicago, Orlando, and Miami. And this paper gets the result that when choosing two cities, the path between Orlando and Miami is the shortest. When choosing three cities, the path among Beijing, Qingdao, and Shanghai is the shortest. When choosing four cities, the shortest path connects Boston, Chicago, Orlando, and Miami. And when choosing five cities, the path among LA, Las Vegas, Chicago, Orlando, and Miami is the shortest. When choosing two and three cities, it takes LpSolve a few seconds to get the result. However, when choosing four and five cities, LpSolve spends much more time on generating the results. Therefore,despite that LpSolve can be applied to solve small casese of TSP, when sovling more complicated cases, a more efficient method must be considered.
© (2022) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Citation Download Citation
Wenjie Bi "Research on the application of linear programming to the travelling salesman problem", Proc. SPIE 12259, 2nd International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2022), 1225946 (17 May 2022); https://doi.org/10.1117/12.2638695
ACCESS THE FULL ARTICLE
ORGANIZATIONAL
Sign in with credentials provided by your organization.
INSTITUTIONAL
Select your institution to access the SPIE Digital Library.
SELECT YOUR INSTITUTION
PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.
PERSONAL SIGN IN
No SPIE Account? Create one
PURCHASE THIS CONTENT
SUBSCRIBE TO DIGITAL LIBRARY
50 downloads per 1-year subscription
Members: $195
Non-members: $335 ADD TO CART
25 downloads per 1 - year subscription
Members: $145
Non-members: $250 ADD TO CART
PURCHASE SINGLE ARTICLE
Includes PDF, HTML & Video, when available
Members: $17.00
Non-members: $21.00 ADD TO CART
PROCEEDINGS
 5 PAGES
DOWNLOAD PAPER SAVE TO MY LIBRARY
GET CITATION
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Computer programming
Java
Binary data
Evolutionary algorithms
Mathematics
Bismuth
Genetic algorithms
RELATED CONTENT
Subscribe to Digital Library
Receive Erratum Email Alert
Back to Top