Maximizing Total Net Profit for Traveling Salesman Problem with Profits Using Metaheuristic Algorithms
Researchers developed two metaheuristic algorithms to solve the Traveling Salesman Problem with Profits, a complex optimization problem.
The Traveling Salesman Problem with Profits (TSPP) is a variation of the classic Traveling Salesman Problem where not all nodes must be visited, but profit is collected from visited nodes. To solve this complex problem, researchers proposed two metaheuristic algorithms: Simulated Annealing with Many-moves and Variable Neighborhood Search. These algorithms were tested on three different problem instances and compared for efficiency.
Abstract
Travelling Salesman Problem with profits (TSPP) is a special case of the general Travelling Salesman Problem, all nodes must not be visited, but profit is collected from visited nodes. It is a well-known NP-hard combinatorial optimization problem in the literature. Because of the problem's complexity, exact methods cannot find the global optimum solution to this problem, so many heuristic and metaheuristic solution techniques are studied to find a feasible solution in a reasonable time. In this research, two different metaheuristic algorithms, Simulated Annealing with Many-moves and Variable Neighborhood Search, are proposed to solve the TSPP. Proposed algorithms are tested with three different problem instances and compared in terms of the efficiency of algorithms.
References
- 1.G. Laporte, "The traveling salesman problem: An overview of exact and approximate algorithms," Eur. J. Oper. Res., vol. 59, no. 2, pp. 231–247, 1992, doi: 10.1016/0377-2217(92)90138-Y.DOI
- 2.R. Matai, S. Singh, and M. Lal, "Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches," Travel. Salesm. Probl. Theory Appl., 2010, doi: 10.5772/12909.DOI
- 3.D. Feillet, P. Dejax, and M. Gendreau, "Traveling salesman problems with profits," Transp. Sci., vol. 39, no. 2, pp. 188–205, 2005, doi: 10.1287/trsc.1030.0079.DOI
- 4.B. Zhu, J. Suzuki, and P. Boonma, "Solving the Probabilistic Traveling Salesperson Problem with Profits (pTSPP ) with a Noise-aware Evolutionary Multi-objective Optimization Algorithm," 2011.
- 5.N. Jozefowiez, F. Glover, and M. Laguna, "Multi-objective meta-heuristics for the traveling salesman problem with profits," J. Math. Model. Algorithms, vol. 7, no. 2, pp. 177–195, 2008, doi: 10.1007/s10852-008-9080-2.DOI
- 6.J. F. Bérubé, M. Gendreau, and J. Y. Potvin, "An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits," Eur. J. Oper. Res., vol. 194, no. 1, pp. 39–50, 2009, doi: 10.1016/j.ejor.2007.12.014.DOI
- 7.E. Angelelli, C. Bazgan, M. G. Speranza, and Z. Tuza, "Complexity and approximation for Traveling Salesman Problems with profits," Theor. Comput. Sci., vol. 531, pp. 54–65, 2014, doi: 10.1016/j.tcs.2014.02.046.DOI
- 8.R. Lahyani, M. Khemakhem, and F. Semet, "A unified matheuristic for solving multi-constrained traveling salesman problems with profits," EURO J. Comput. Optim., vol. 5, no. 3, pp. 393–422, 2017, doi: 10.1007/s13675-016-0071-1.DOI
- 9.M. Zhang, J. Qin, Y. Yu, and L. Liang, "Traveling salesman problems with profits and stochastic customers," Int. Trans. Oper. Res., vol. 25, no. 4, pp. 1297–1313, 2018, doi: 10.1111/itor.12310.DOI
- 10.A. Jaszkiewicz, “Many-Objective Pareto Local Search,” Eur. J. Oper. Res., vol. 271, no. 3, pp. 1001–1013, 2018, doi: 10.1016/j.ejor.2018.06.009.DOI
- 11.O. Osicka, M. Guajardo, and K. Jörnsten, "Cooperation of customers in traveling salesman problems with profits," Optim. Lett., vol. 14, no. 5, pp. 1219–1233, 2020, doi: 10.1007/s11590-019-01429-6.DOI
- 12.C. Archetti and M. G. Speranza, "Chapter 12: Arc Routing Problems with Profits," in Arc Routing, pp. 281–299.
- 13.A. Gunawan, H. C. Lau, and P. Vansteenwegen, "Orienteering Problem: A survey of recent variants, solution approaches and applications," Eur. J. Oper. Res., vol. 255, no. 2, pp. 315–332, 2016, doi: 10.1016/j.ejor.2016.04.059.DOI
- 14.S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science (80-. )., vol. 220, no. 4598, pp. 671–680, 1983, [Online]. Available: https://www.jstor.org/stable/1690046.Link
- 15.T. L. Friesz, H. J. Cho, N. J. Mehta, R. L. Tobin, and G. Anandalingam, "Simulated annealing approach to the network design problem with variational inequality constraints," Transp. Sci., vol. 26, no. 1, pp. 18–26, 1992, doi: 10.1287/trsc.26.1.18.DOI
- 16.P. Hansen and N. Mladenović, "Variable neighborhood search," Handb. Heuristics, vol. 1–2, pp. 759–787, 2018, doi: 10.1007/978-3-319-07124-4_19.DOI
Işık, E. E., Şimşir, M. (2023). Maximizing Total Net Profit for Traveling Salesman Problem with Profits Using Metaheuristic Algorithms. *The European Journal of Research and Development*, 3(1), 46-59. https://doi.org/10.56038/ejrnd.v3i1.228
Bibliographic Info
Indexing & License
More from The European Journal of Research and Development
Challenges in Maize Root Phenotyping: Preprocessing Limits and Class Imbalance in Deep Learning
Hüdanur Engin, Ali Murat Tiryaki
2026 · Vol 6 · Issue 1
The Bleaching of Woven Fabrics Using the Foam Application Technique
Aylin Kuşen, Onur Balcı, Koray Pektaş
2026 · Vol 6 · Issue 1
Automated Monkeypox Disease Classification Using Texture and Focus-Based Image Features
Tuğba Şentürk, Çiğdem Gülüzar Altıntop, Fatma Latifoğlu
2026 · Vol 6 · Issue 1
EEG-Based Assessment of Stress Levels Using Time–Frequency Features and Machine Learning
Sevde Samsa, Çiğdem Gülüzar Altıntop
2026 · Vol 6 · Issue 1
A Compact Non-Intrusive Measurement System for Critical Dimensions and Calibration Chart Generation of Underground Fuel Tanks
İlker Değirmencioğlu, Savaş Barış, Yusuf Kaya
2025 · Vol 5 · Issue 1
An AI-Based Question–Answering System for Corporate Documents: VK ArtiFin
Zeynep Örpek, Büşra Tural, Zeynep Destan
2025 · Vol 5 · Issue 1