On solving close enough orienteering problems with overlapped neighborhoods

Qiuchen Qian, Yanran Wang and David Boyle

European Journal of Operational Research, 2024, vol. 318, issue 2, 369-387

Abstract: The Close Enough Traveling Salesman Problem (CETSP) is a well-known variant of the classic Traveling Salesman Problem whereby the agent may complete its mission at any point within a target neighborhood. Heuristics based on overlapped neighborhoods, known as Steiner Zones (SZ), have gained attention in addressing CETSPs. While SZs offer effective approximations to the original graph, their inherent overlap imposes constraints on the search space, potentially conflicting with global optimization objectives. Here we show how such limitations can be converted into advantages in the Close Enough Orienteering Problem (CEOP) by aggregating prizes across overlapped neighborhoods. We further extend the classic CEOP with Non-uniform Neighborhoods (CEOP-N) by introducing non-uniform cost considerations for prize collection. To tackle CEOP (and CEOP-N), we develop a new approach featuring a Randomized Steiner Zone Discretization (RSZD) scheme coupled with a hybrid algorithm based on Particle Swarm Optimization (PSO) and Ant Colony System (ACS) — CRaSZe-AntS. The RSZD scheme identifies sub-regions for PSO exploration, and ACS determines the discrete visiting sequence. We evaluate the RSZD’s discretization performance on CEOP instances derived from established CETSP instances and compare CRaSZe-AntS against the most relevant state-of-the-art heuristic focused on single-neighborhood optimization for CEOP instances. We also compare the performance of the interior search within SZs and the boundary search on individual neighborhoods in the context of CEOP-N. Our experimental results show that CRaSZe-AntS can yield comparable solution quality with significantly reduced computation time compared to the single neighborhood strategy, where we observe an averaged 140.44% increase in prize collection and 55.18% reduction of algorithm execution time. CRaSZe-AntS is thus highly effective in solving emerging CEOP-N, examples of which include truck-and-drone delivery scenarios.

Keywords: Metaheuristics; Close enough orienteering problem; Steiner zone discretization; Non-uniform neighborhood; Truck-and-drone problems (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724003916
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:318:y:2024:i:2:p:369-387

DOI: 10.1016/j.ejor.2024.05.032

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 ().