Metaheuristics for the distance constrained generalized covering traveling salesman problem

Prashant Singh (), Ankush R. Kamthane () and Ajinkya N. Tanksale ()
Additional contact information
Prashant Singh: Indian Institute of Technology (BHU)
Ankush R. Kamthane: Indian Institute of Technology (BHU)
Ajinkya N. Tanksale: Indian Institute of Technology (BHU)

OPSEARCH, 2021, vol. 58, issue 3, No 4, 575-609

Abstract: 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.

Keywords: Travelling salesman problem; Covering salesman problem; Ant colony optimization; GRASP; Humanitarian logistics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s12597-020-00503-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:opsear:v:58:y:2021:i:3:d:10.1007_s12597-020-00503-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/12597

DOI: 10.1007/s12597-020-00503-3

Access Statistics for this article

OPSEARCH is currently edited by Birendra Mandal

More articles in OPSEARCH from Springer, Operational Research Society of India
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().