The generalized close enough traveling salesman problem

Andrea Di Placido, Claudia Archetti, Carmine Cerrone and Bruce Golden

European Journal of Operational Research, 2023, vol. 310, issue 3, 974-991

Abstract: This paper studies a generalization of the close enough traveling salesman problem referred to as the generalized close enough traveling salesman problem (GCETSP). The canonical problem contains a set of customers, each associated with an area (neighborhood) that is generally circular. In the GCETSP, each customer is associated with a set of disks with different radii. Having multiple disks around the customer allows us to model several real-world applications, in which a higher benefit is gained by more closely approaching each target. A prize is assigned to each disk and is collected if the disk is traversed. The goal is to determine the route that visits each customer and the depot and maximizes the difference between the total collected prize and the route length. The total collected prize is given by the sum of the customer prices’ associated with the innermost disk traversed by the route. We propose a heuristic algorithm and an evolutionary approach, specifically, a genetic algorithm (GA), to solve this problem. We evaluate the GA’s performance on instances generated from benchmark CETSP and TSP instances. We then compare GA solutions with CETSP solutions and solutions obtained through an alternative approach based on pre-selecting intersection points with customers’ disks. The results show that the GA can identify high-quality solutions with a short computing time.

Keywords: Metaheuristics; Close enough traveling salesman problem; Genetic algorithms; Conic programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172300293X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:310:y:2023:i:3:p:974-991

DOI: 10.1016/j.ejor.2023.04.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().