Skip to main content
SpringerLink
Log in

Metaheuristics for the distance constrained generalized covering traveling salesman problem

  • Theoretical Article
  • Published:
OPSEARCH Aims and scope Submit manuscript

Abstract

In this work, we present an extension of the generalized covering salesman problem as distance constrained generalized m-covering salesman problem. Given a set of vertices including a depot, facilities, customer locations and demand associated with each customer location, the objective is to determine an optimal tour of each salesman such that the total covered demand is maximized and the tour length is minimized. A bi-objective mixed-integer programming model is formulated for the problem. The proposed model is solved using GUROBI 8.0 solver’s in-built hierarchical optimization approach. However, the computational complexity of the problem demands a specialized solution approach. To solve the problem efficiently, we propose two metaheuristics ant colony optimization (ACO) algorithm and greedy randomized adaptive search procedure (GRASP). Extensive computational experiments were performed using the benchmark instances from the literature. The results of computational experiments show the efficiency and effectiveness of the proposed metaheuristics algorithms. Although, the GRASP metaheuristics outperform the ACO algorithm in case of medium and large size instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393–410 (1954)

    Google Scholar 

  2. Current, J.R., Schilling, D.A.: The covering salesman problem. Transp. Sci. 23(3), 208–213 (1989)

    Article  Google Scholar 

  3. Current, J.R., Schilling, D.A.: The median tour and maximal covering tour problems: formulations and heuristics. Eur. J. Oper. Res. 73(1), 114–126 (1994)

    Article  Google Scholar 

  4. Church, R., ReVelle, C.: The maximal covering location problem. In: Papers of the Regional Science Association, vol. 32, no. 1, pp. 101–118. Springer, Berlin (1974)

  5. Ozbaygin, G., Yaman, H., Karasan, O.E.: Time constrained maximal covering salesman problem with weighted demands and partial coverage. Comput. Oper. Res. 1(76), 226–237 (2016)

    Article  Google Scholar 

  6. Hachicha, M., Hodgson, M.J., Laporte, G., Semet, F.: Heuristics for the multi-vehicle covering tour problem. Comput. Oper. Res. 27(1), 29–42 (2000)

    Article  Google Scholar 

  7. Shaelaie, M.H., Salari, M., Naji-Azimi, Z.: The generalized covering traveling salesman problem. Appl. Soft Comput. 1(24), 867–878 (2014)

    Article  Google Scholar 

  8. Pandiri, V., Singh, A.: An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem. Appl. Soft Comput. 1(78), 481–495 (2019)

    Article  Google Scholar 

  9. Cohen, L., Greco, M., Ma, H., Hernández, C., Felner, A., Kumar, T.S., Koenig, S.: Anytime focal search with applications. In: IJCAI, pp. 1434–1441 (2018)

  10. Jiang, L., Dhiaf, M., Dong, J., Liang, C., Zhao, S.: A traveling salesman problem with time windows for the last mile delivery in online shopping. Int. J. Prod. Res. 22, 1–2 (2019)

    Google Scholar 

  11. Tripathy, S.P., Tulshyan, A., Kar, S., Pal, T.: A metameric genetic algorithm with new operator for covering salesman problem with full coverage. Int. J. Control Theory Appl. 10, 245–252 (2017)

    Google Scholar 

  12. Álvarez-Miranda, E., Sinnl, M.: A branch-and-cut algorithm for the maximum covering cycle problem. Ann. Oper. Res. 284(2), 487–499 (2020)

    Article  Google Scholar 

  13. Dorigo, M.: Optimization, learning and natural algorithms. PhD Thesis, Politecnico di Milano (1992)

  14. Yang, J., Shi, X., Marchese, M., Liang, Y.: An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 18(11), 1417–1422 (2008)

    Article  Google Scholar 

  15. Stützle, T., Dorigo, M.: ACO algorithms for the traveling salesman problem. Evol. Algorithms Eng. Comput. Sci. 29(4), 163–183 (1999)

    Google Scholar 

  16. Mohsen, A.M.: Annealing ant colony optimization with mutation operator for solving TSP. Comput. Intell. Neurosci. 2016, 1–12 (2016)

    Article  Google Scholar 

  17. Feo, T.A., Resende, M.G.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2), 67–71 (1989)

    Article  Google Scholar 

  18. Mestria, M., Ochi, L.S., de Lima, Martins S.: GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem. Comput. Oper. Res. 40(12), 3218–3229 (2013)

    Article  Google Scholar 

  19. Marinakis, Y., Migdalas, A., Pardalos, P.M.: Expanding neighborhood GRASP for the traveling salesman problem. Comput. Optim. Appl. 32(3), 231–257 (2005)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Industrial Management Group, Department of Mechanical Engineering, Indian Institute of Technology (BHU), Varanasi, 221005, India

    Prashant Singh, Ankush R. Kamthane & Ajinkya N. Tanksale

Authors
  1. Prashant Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ankush R. Kamthane
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ajinkya N. Tanksale
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ajinkya N. Tanksale.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Singh, P., Kamthane, A.R. & Tanksale, A.N. Metaheuristics for the distance constrained generalized covering traveling salesman problem. OPSEARCH 58, 575–609 (2021). https://doi.org/10.1007/s12597-020-00503-3

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12597-020-00503-3

Keywords

Search

Navigation