In this section
@article{Qian:2024:10.1016/j.ejor.2024.05.032,
author = {Qian, Q and Wang, Y and Boyle, D},
doi = {10.1016/j.ejor.2024.05.032},
journal = {European Journal of Operational Research},
pages = {369--387},
title = {On solving close enough orienteering problems with overlapped neighborhoods},
url = {http://dx.doi.org/10.1016/j.ejor.2024.05.032},
volume = {318},
year = {2024}
}
TY - JOUR
AB - The Close Enough Traveling Salesman Problem (CETSP) is a well-known variant of the classic TravelingSalesman 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 inaddressing CETSPs. While SZs offer effective approximations to the original graph, their inherent overlapimposes constraints on the search space, potentially conflicting with global optimization objectives. Here weshow 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-uniformNeighborhoods (CEOP-) by introducing non-uniform cost considerations for prize collection. To tackle CEOP(and CEOP-), 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 determinesthe discrete visiting sequence. We evaluate the RSZD’s discretization performance on CEOP instances derivedfrom established CETSP instances and compare CRaSZe-AntS against the most relevant state-of-the-art heuristicfocused on single-neighborhood optimization for CEOP instances. We also compare the performance of theinterior search within SZs and the boundary search on individual neighborhoods in the context of CEOP-. Ourexperimental results show that CRaSZe-AntS can yield comparable solution quality with significantly reducedcomputation 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 highlyeffective in solving emerging CEOP-, examples of which include truck-and-drone delivery scenarios.
AU - Qian,Q
AU - Wang,Y
AU - Boyle,D
DO - 10.1016/j.ejor.2024.05.032
EP - 387
PY - 2024///
SN - 0377-2217
SP - 369
TI - On solving close enough orienteering problems with overlapped neighborhoods
T2 - European Journal of Operational Research
UR - http://dx.doi.org/10.1016/j.ejor.2024.05.032
UR - http://hdl.handle.net/10044/1/113552
VL - 318
ER -
Dyson School of Design Engineering
Imperial College London
25 Exhibition Road
South Kensington
London
SW7 2DB
design.engineering@imperial.ac.uk
Tel: +44 (0) 20 7594 8888