k-RNN: Extending NN-heuristics for the TSP
In this paper we present an extension of existing Nearest-Neighbor heuristics to an algorithm called k-Repetitive-Nearest-Neighbor. The idea is to start with a tour of k nodes and then perform a Nearest-Neighbor search from there on. After doing this for all permutations of k nodes the result gets selected as the shortest tour found. Experimental results show that for 2-RNN the solutions quality remains relatively stable between about 10% to 40% above the optimum.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The External Interface for Extending WASP
Answer set programming (ASP) is a successful declarative formalism for knowledge representation and reasoning. The evaluation of ASP programs is nowadays based on the Conflict-Driven Clause Learning (CDCL) backtracking s…
Abstract Interpretation for Generalized Heuristic Search in Model-Based Planning
Domain-general model-based planners often derive their generality by constructing search heuristics through the relaxation or abstraction of symbolic world models. We illustrate how abstract interpretation can serve as a…
Heuristic SearchHierarchical Task Network Planning with LLM-Generated Heuristics
HTN planning is a variation of classical planning where, instead of searching for a linear sequence of actions, an algorithm decomposes higher-level tasks using a method library until only executable actions remain. On o…
SyncSDE: A Probabilistic Framework for Diffusion Synchronization
There have been many attempts to leverage multiple diffusion models for collaborative generation, extending beyond the original domain. A prominent approach involves synchronizing multiple diffusion trajectories by mixin…
SpecificityML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
Mixed Binary Quadratic Programs (MBQPs) are an important and complex set of problems in combinatorial optimization. As solving large-scale combinatorial optimization problems is challenging, primal heuristics have been d…