O
Orclever
Back to Journal
Research Article Open AccessOrclever Native

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

Eyüp Ensar Işık1✉,
Mısra Şimşir2
1a:1:{s:5:"en_US";s:27:"Yildiz Technical University";}
2Yildiz Technical University
Published:March 28, 2023
DOI: 10.56038/ejrnd.v3i1.228
Vol. 3, No. 1

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.

Keywords
Arc routing with profitsTraveling salesman problem with profitsMetaheuristic algorithmsSimulated annealingVariable neighborhood search

References

  1. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 12.C. Archetti and M. G. Speranza, "Chapter 12: Arc Routing Problems with Profits," in Arc Routing, pp. 281–299.
  13. 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. 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. 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. 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
Download PDF
Cite This Article
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

JournalThe European Journal of Research and Development
Volume3
Issue1
Pages46–59
PublishedMarch 28, 2023
eISSN2822-2296