Exploratory Heuristics for Scalable Combinatorial Optimization

This paper introduces a deterministic insertion-based heuristic named the Localized Selective Insertion Heuristic, which incorporates adaptive mechanisms such as dynamic adjustment of evaluated neighbors and systematic seed route initialization, contributing to the heuristic's novelty and robust performance, designed to provide a reliable balance between the quality of solutions and computational efficiency. The proposed heuristic builds a complete solution incrementally, systematically inserting each unvisited node into an evolving tour by evaluating a limited number of potential insertion points based on their spatial proximity to already visited locations. This localized and selective evaluation strategy substantially reduces computational effort, typically allowing large problem instances to be solved in under 150 milliseconds, with achieved solution quality consistently within 2–14% of known optimal values. To clearly illustrate the effectiveness of this trade-off, we propose a Normalized Performance Index, integrating both solution accuracy and computational speed into a unified metric. The Localized Selective Insertion Heuristic demonstrated superior performance according to this index, achieving the best score in 16 out of 17 tested benchmark scenarios. The simplicity, deterministic nature, minimal parameter sensitivity, and ease of practical implementation make the proposed approach particularly suitable for applications requiring scalability, consistent performance, and straightforward reproducibility, such as logistics, transportation planning, and industrial automation.