Maximizing Total Net Profit for Traveling Salesman Problem with Profits Using Metaheuristic Algorithms

Main Article Content

Eyüp Ensar Işık
Mısra Şimşir
https://orcid.org/0009-0007-0907-3862

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.

Downloads

Download data is not yet available.

Article Details

How to Cite
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
Section
Articles

References

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: https://doi.org/10.1016/0377-2217(92)90138-Y

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: https://doi.org/10.5772/12909

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: https://doi.org/10.1287/trsc.1030.0079

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.

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: https://doi.org/10.1007/s10852-008-9080-2

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: https://doi.org/10.1016/j.ejor.2007.12.014

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: https://doi.org/10.1016/j.tcs.2014.02.046

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: https://doi.org/10.1007/s13675-016-0071-1

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: https://doi.org/10.1111/itor.12310

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: https://doi.org/10.1016/j.ejor.2018.06.009

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: https://doi.org/10.1007/s11590-019-01429-6

C. Archetti and M. G. Speranza, "Chapter 12: Arc Routing Problems with Profits," in Arc Routing, pp. 281–299. DOI: https://doi.org/10.1137/1.9781611973679.ch12

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: https://doi.org/10.1016/j.ejor.2016.04.059

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. DOI: https://doi.org/10.1126/science.220.4598.671

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: https://doi.org/10.1287/trsc.26.1.18

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: https://doi.org/10.1007/978-3-319-07124-4_19