Comparing Greedy Constructive Heuristic Subtour Elimination Methods for the Traveling Salesman Problem
This paper further defines the class of fragment constructive heuristics used to compute feasible solutions for the Traveling Salesman Problem into arc-greedy and node-greedy subclasses. Since these subclasses of heuristics can create subtours, two known methodologies for subtour elimination on symmetric instances are reviewed and are expanded to cover asymmetric problem instances. This paper introduces a third novel methodology, the Greedy Tracker, and compares it to both known methodologies. Computational results are generated across multiple symmetric and asymmetric instances. The results demonstrate the Greedy Tracker is the fastest method for preventing subtours for instances below 400 nodes. A distinction between fragment constructive heuristics and the subtour elimination methodology used to ensure the feasibility of resulting solutions enables the introduction of a new node-greedy fragment heuristic called Ordered Greedy.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
Assignment-Routing Optimization: Solvers for Problems Under Constraints
We study the Joint Routing-Assignment (JRA) problem in which items must be assigned one-to-one to placeholders while simultaneously determining a Hamiltonian cycle visiting all nodes exactly once. Extending previous exac…
Motion PlanningGreedy Selection under Independent Increments: A Toy Model Analysis
We study an iterative selection problem over N i.i.d. discrete-time stochastic processes with independent increments. At each stage, a fixed number of processes are retained based on their observed values. Under this sim…
Optimizing Elimination Templates by Greedy Parameter Search
We propose a new method for constructing elimination templates for efficient polynomial system solving of minimal problems in structure from motion, image matching, and camera tracking. We first construct a particular af…
Pose EstimationLearning Elimination Ordering for Tree Decomposition Problem
We propose a Reinforcement Learning-based approach to approximately solve the Tree Decomposition problem. Recently, it was shown that learned heuristics could successfully solve combinatorial problems. We establish tha…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Tree DecompositionEfficient Wrapper Feature Selection using Autoencoder and Model Based Elimination
We propose a computationally efficient wrapper feature selection method - called Autoencoder and Model Based Elimination of features using Relevance and Redundancy scores (AMBER) - that uses a single ranker model along w…
feature selectionGeneral Classification