[ARTICLE] This study extends the classic "traveling salesman" problem by allowing for variable-sized targets and rewards, aiming to find the most efficient route that maximizes collected benefits while minimizing travel distance.

by Claudia Archetti (ESSEC Business School), Andrea Di Placido, Bruce Golden, Carmine Cerrone

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.

[Please read the research paper here]