A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem

Yuichi Nagata
Yuichi Nagata
[email protected]
Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Yokohama, Kanagawa 226-8503, Japan
Search for more papers by this author
,
Shigenobu Kobayashi
Shigenobu Kobayashi
[email protected]
Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Yokohama, Kanagawa 226-8503, Japan
Search for more papers by this author

Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Yokohama, Kanagawa 226-8503, Japan

Search for more papers by this author

Shigenobu Kobayashi

[email protected]

Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Yokohama, Kanagawa 226-8503, Japan

Search for more papers by this author

Published Online:4 May 2012https://doi.org/10.1287/ijoc.1120.0506

Supplemental Material

ijoc.1120.0506-sm-ec.pdf (144 KB)

Cited by
- A population-based large neighborhood search algorithm for the multi-depot multiple traveling salesman problem
  Expert Systems with Applications, Vol. 330
- Recent developments in location-routing problems
  European Journal of Operational Research, Vol. 332, No. 3
- A speed-up for Helsgaun’s TSP heuristic by relaxing the positive gain criterion
  Computers & Operations Research, Vol. 191
- Combining hash-based Tabu search and frequent pattern mining for job-shop scheduling
  1 August 2025 | IISE Transactions, Vol. 58, No. 6
- Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Potential Unified Tool
  IEEE Transactions on Evolutionary Computation, Vol. 30, No. 3
- An effective memetic algorithm for traveling repairman problem with profits
  Results in Engineering, Vol. 30
- A multi-pheromone ant colony optimization for large-scale traveling salesman problems
  Applied Soft Computing, Vol. 40
- Limited Budget Optimization of the Asteroid Routing Problem
  7 April 2026 | SN Computer Science, Vol. 7, No. 4
- Hierarchical Genetic Algorithm for the Multi-Solution Traveling Salesman Problem
  IEEE Transactions on Evolutionary Computation, Vol. 30, No. 2
- A Comprehensive Review of Metaheuristics for the Modern Traveling Salesman Problem and Drone-Assisted Delivery
  2 April 2026 | Algorithms, Vol. 19, No. 4
- Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem and its Variants
  14 January 2026 | Journal of Heuristics, Vol. 32, No. 1
- An improved actor-critic architecture with PPO for the traveling salesman problem
  Expert Systems with Applications, Vol. 298
- What Makes a Transformer Solve the TSP? A Component-Wise Analysis
  13 March 2026 | Mathematics, Vol. 14, No. 6
- Reinforcement Learning for the Vehicle Routing Problem: Methodologies, Applications, and Research Outlook
  21 October 2025 | Arabian Journal for Science and Engineering, Vol. 51, No. 5
- Evolutionary multi-objective optimization with the heuristic solver for multiple traveling salesman problem
  28 January 2026 | Artificial Life and Robotics, Vol. 31, No. 1
- Improving analytic approximations of TSP tour lengths with adjustment factors
  29 April 2024 | Transportmetrica A: Transport Science, Vol. 22, No. 1
- Learning-guided iterated local search for the minmax multiple traveling salesman problem
  Computers & Operations Research, Vol. 185
- A generalized neural solver based on LLM-guided heuristic evoluation framework for solving diverse variants of vehicle routing problems
  Expert Systems with Applications, Vol. 296
- Metaheuristics algorithms for solving the mobile robot scheduling problem in FMS environment: A comparative study
- Meta-learning-based adaptive operator selection for traveling salesman problem
  Applied Soft Computing, Vol. 185
- Cooperative Coevolutionary Genetic Algorithm for Multirobot Task Scheduling in Antarctica region
  Swarm and Evolutionary Computation, Vol. 99
- Edge assembly combined with arc-based crossover for undirected traveling salesman with profits
  24 September 2025 | Journal of King Saud University Computer and Information Sciences, Vol. 37, No. 8
- The travelling salesperson problem and the challenges of near-term quantum advantage
  16 May 2025 | Quantum Science and Technology, Vol. 10, No. 3
- Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood
  Giuseppe Lancia,
  Paolo Vidoni
  11 November 2024 | INFORMS Journal on Computing, Vol. 37, No. 5
- Solving the traveling salesman problem with machine learning: a review of recent advances and challenges
  4 June 2025 | Artificial Intelligence Review, Vol. 58, No. 9
- A hybrid genetic algorithm with cycle reassembly for solving colored traveling salesman problems
  19 August 2025 | Journal of King Saud University Computer and Information Sciences, Vol. 37, No. 7
- Capacitated profitable tour problem with cross-docking
  Computers & Operations Research, Vol. 181
- Metaheuristic approaches for the stochastic capacitated multi-depot vehicle routing problem with pickup and delivery
  Expert Systems with Applications, Vol. 290
- Clearing the Combinatorial Fog: Tracing the Hidden Paths of TSP Heuristics
  27 August 2025
- Solving soft and hard-clustered vehicle routing problems: A bi-population collaborative memetic search approach
  European Journal of Operational Research, Vol. 324, No. 3
- To Repair or Not to Repair? Investigating the Importance of AB-Cycles for the State-of-the-Art TSP Heuristic EAX
  13 July 2025
- Dramatically Faster Partition Crossover for the Traveling Salesman Problem
  13 July 2025
- On the Use of Matching Algorithms to Transfer Solutions for the Travelling Salesperson Problem
  13 July 2025
- A Hybrid Genetic Algorithm with Multi-Population for Capacitated Location Routing
  Pengfei He,
  Jin-Kao Hao,
  Qinghua Wu
  11 July 2025 | INFORMS Journal on Computing, Vol. 0, No. 0
- An improved adaptive fuzzy-genetic algorithm based on local search for integrated production and mobile robot scheduling in job-shop flexible manufacturing system
  Computers & Industrial Engineering, Vol. 204
- A contextual framework for learning routing experiences in last-mile delivery
  Transportation Research Part B: Methodological, Vol. 194
- A Two-Individual Evolutionary Algorithm for Cumulative Capacitated Vehicle Routing With Single and Multiple Depots
  IEEE Transactions on Evolutionary Computation, Vol. 29, No. 2
- Coevolutionary Construction of Parallel Algorithm Portfolio Optimization
  16 April 2025
- Graph Representation Learning and Optimization for Spherical Emission Source Microscopy System
  IEEE Transactions on Automation Science and Engineering, Vol. 22
- An effective multi-level memetic search with neighborhood reduction for the clustered team orienteering problem
  European Journal of Operational Research, Vol. 318, No. 3
- An Algorithm with Edge Assembly Crossover Based on Neighborhood Measure for TSP Tours
- A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem
  Computers & Operations Research, Vol. 170
- Edge Assembly Crossover Incorporating Tabu Search for the Traveling Salesman Problem
  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E107.A, No. 10
- Optimization through Iterative Smooth Morphological Transformations
  14 July 2024
- Large Language Models as Evolutionary Optimizers
- On the Use of Quality Diversity Algorithms for the Travelling Thief Problem
  8 June 2024 | ACM Transactions on Evolutionary Learning and Optimization, Vol. 4, No. 2
- Adaptive fuzzy-genetic algorithm operators for solving mobile robot scheduling problem in job-shop FMS environment
  Robotics and Autonomous Systems, Vol. 176
- Evolutionary Multimodal Multiobjective Optimization for Traveling Salesman Problems
  IEEE Transactions on Evolutionary Computation, Vol. 28, No. 2
- A hybrid genetic algorithm for the Hamiltonian p ‐median problem
  20 November 2023 | Networks, Vol. 83, No. 2
- An effective memetic algorithm for the close-enough traveling salesman problem
  Applied Soft Computing, Vol. 153
- Traveling Salesman Problem
  24 May 2024
- Generalizing and Unifying Gray-Box Combinatorial Optimization Operators
  7 September 2024
- Dancing to the State of the Art?
  7 September 2024
- A Variant of Parallel-Hybrid Genetic Algorithm for Large-Scale Traveling Salesman Problem
  17 July 2024
- Using Reinforcement Learning for Per-Instance Algorithm Configuration on the TSP
- Bi-objective parameter setting problem of a genetic algorithm: an empirical study on traveling salesperson problem
  2 September 2023 | Applied Intelligence, Vol. 53, No. 22
- Hybrid genetic algorithm for undirected traveling salesman problems with profits
  21 June 2023 | Networks, Vol. 82, No. 3
- Highly feasible, energy-minimizing and time window-guaranteeing last-mile delivery routes generation based on clustering and local search considering package densities
  6 July 2023 | Korean Journal of Chemical Engineering, Vol. 40, No. 10
- A two-stage data-driven metaheuristic to predict last-mile delivery route sequences
  Engineering Applications of Artificial Intelligence, Vol. 125
- A reinforced hybrid genetic algorithm for the traveling salesman problem
  Computers & Operations Research, Vol. 157
- How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem
  IEEE Computational Intelligence Magazine, Vol. 18, No. 3
- Memetic search for the minmax multiple traveling salesman problem with single and multiple depots
  European Journal of Operational Research, Vol. 307, No. 3
- Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problem
  Toni Pacheco,
  Rafael Martinelli,
  Anand Subramanian,
  Túlio A. M. Toffolo,
  Thibaut Vidal
  28 October 2022 | Transportation Science, Vol. 57, No. 2
- General Edge Assembly Crossover-Driven Memetic Search for Split Delivery Vehicle Routing
  Pengfei He,
  Jin-Kao Hao
  11 October 2022 | Transportation Science, Vol. 57, No. 2
- Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence
  3 August 2022 | SCIENTIA SINICA Technologica, Vol. 53, No. 2
- A Variant of Parallel-Hybrid Genetic Algorithm for Large-Scale Traveling Salesman Problem
  13 August 2023
- Reinforced Lin–Kernighan–Helsgaun algorithms for the traveling salesman problems
  Knowledge-Based Systems, Vol. 260
- A study on the effects of normalized TSP features for automated algorithm selection
  Theoretical Computer Science, Vol. 940
- Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems
  IEEE Transactions on Intelligent Transportation Systems, Vol. 23, No. 9
- A Novel Discrete Group Teaching Optimization Algorithm for TSP Path Planning with Unmanned Surface Vehicles
  15 September 2022 | Journal of Marine Science and Engineering, Vol. 10, No. 9
- On the use of quality diversity algorithms for the traveling thief problem
  8 July 2022
- Exploring the feature space of TSP instances using quality diversity
  8 July 2022
- Evolutionary diversity optimisation for the traveling thief problem
  8 July 2022
- An effective iterated two-stage heuristic algorithm for the multiple Traveling Salesmen Problem
  Computers & Operations Research, Vol. 143
- Hybrid search with neighborhood reduction for the multiple traveling salesman problem
  Computers & Operations Research, Vol. 142
- A list-based simulated annealing algorithm with crossover operator for the traveling salesman problem
  9 January 2022 | Neural Computing and Applications, Vol. 34, No. 10
- Co-evolutionary Diversity Optimisation for the Traveling Thief Problem
  14 August 2022
- Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem
  6 November 2021 | Computational Optimization and Applications, Vol. 81, No. 1
- Improving the state-of-the-art in the Traveling Salesman Problem: An Anytime Automatic Algorithm Selection
  Expert Systems with Applications, Vol. 187
- A Two-Stage Data-Driven Metaheuristic to Predict Last-Mile Delivery Route Sequences
  SSRN Electronic Journal, Vol. 6
- Solving the clustered traveling salesman problem via traveling salesman problem methods
  13 June 2022 | PeerJ Computer Science, Vol. 8
- Reproducibility in Evolutionary Computation
  13 October 2021 | ACM Transactions on Evolutionary Learning and Optimization, Vol. 1, No. 4
- Multi-Modal Multi-Objective Traveling Salesman Problem and its Evolutionary Optimizer
- On Optimizing a Multi-Mode Last-Mile Parcel Delivery System with Vans, Truck and Drone
  15 October 2021 | Electronics, Vol. 10, No. 20
- On the potential of normalized TSP features for automated algorithm selection
  6 September 2021
- Computing diverse sets of high quality TSP tours by EAX-based evolutionary diversity optimisation
  6 September 2021
- Grouping memetic search for the colored traveling salesmen problem
  Information Sciences, Vol. 570
- Discrete Social Spider Algorithm for Solving Traveling Salesman Problem
  13 August 2021 | International Journal of Computational Intelligence and Applications, Vol. 20, No. 03
- Towards Feature-free TSP Solver Selection: A Deep Learning Approach
- A parallel ensemble genetic algorithm for the traveling salesman problem
  26 June 2021
- An efficient implementation of iterative partial transcription for the traveling salesman problem
  26 June 2021
- Entropy-based evolutionary diversity optimisation for the traveling salesperson problem
  26 June 2021
- Few-Shots Parallel Algorithm Portfolio Construction via Co-Evolution
  IEEE Transactions on Evolutionary Computation, Vol. 25, No. 3
- esearch on Credit Card Fraud Classification Based on GA-SVM
- Implementation of Evolutionary Methods of Solving the Travelling Salesman Problem in a Robotic Warehouse
  21 June 2020
- Population Based Search
  29 March 2021
- Applications
  29 March 2021
- Evolutionary operators for the Hamiltonian completion problem
  10 June 2020 | Soft Computing, Vol. 24, No. 23
- High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman Problem
  Evolutionary Computation, Vol. 28, No. 4
- Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection
- Edge Assembly Crossover with Tabu for Traveling Salesman Problem
- Evolving diverse sets of tours for the travelling salesperson problem
  26 June 2020
- Dynamic bi-objective routing of multiple vehicles
  26 June 2020
- Advanced statistical analysis of empirical performance scaling
  26 June 2020
- The node weight dependent traveling salesperson problem
  26 June 2020
- A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling between Local Optima
  Evolutionary Computation, Vol. 28, No. 2
- A multi-objective perspective on performance assessment and automated selection of single-objective optimization algorithms
  Applied Soft Computing, Vol. 88
- A genetic algorithm for the picture maze generation problem
  Computers & Operations Research, Vol. 115
- A Genetic Algorithm Approach to Multi-Agent Mission Planning Problems
  11 December 2019
- Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem
  31 August 2020
- Meta-heuristic Hybrid Algorithmic Approach for Solving Combinatorial Optimization Problem (TSP)
  2 April 2020
- Development of evolutionary algorithms in the problems of managing the assortment of network pharmacies
  Artificial Intelligence, Vol. 24, No. 3-4
- A Consensus-Edge Initializer for Multi-start 2-opt on the Symmetric Euclidean Travelling Salesman Problem
  30 March 2026 | Ekoist: Journal of Econometrics and Statistics, Vol. 0, No. 0
- Effective Recycling Planning for Dockless Sharing Bikes
  5 November 2019
- Solving Traveling Salesman Problem with Image-Based Classification
- A New Method for Identification of Recombining Components in the Generalized Partition Crossover
- An Expressway Based TSP Model for Vehicle Delivery Service Coordinated with Truck + UAV
- A collaborative control protocol for agricultural robot routing with online adaptation
  Computers & Industrial Engineering, Vol. 135
- Evolving diverse TSP instances by means of novel and creative mutation operators
  27 August 2019
- Discrete pigeon-inspired optimization algorithm with Metropolis acceptance criterion for large-scale traveling salesman problem
  Swarm and Evolutionary Computation, Vol. 48
- An experimental comparison of algebraic differential evolution using different generating sets
  13 July 2019
- The massively parallel mixing genetic algorithm for the traveling salesman problem
  13 July 2019
- Implementation issues in optimization algorithms: do they matter?
  5 March 2019 | Journal of Experimental & Theoretical Artificial Intelligence, Vol. 31, No. 4
- A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem
  International Journal of Cognitive Informatics and Natural Intelligence, Vol. 13, No. 3
- Solving the Traveling Salesman Problem with a Multi-Agent System
- Automated Algorithm Selection: Survey and Perspectives
  Evolutionary Computation, Vol. 27, No. 1
- Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms
  28 February 2019 | International Journal on Artificial Intelligence Tools, Vol. 28, No. 01
- Bi-objective Orienteering: Towards a Dynamic Multi-objective Evolutionary Algorithm
  3 February 2019
- Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers
  28 March 2019
- Next Generation Genetic Algorithms: A User’s Guide and Tutorial
  21 September 2018
- Collision-Free Path Planning and Delivery Sequence Optimization in Noncoplanar Radiation Therapy
  IEEE Transactions on Cybernetics, Vol. 49, No. 1
- On the empirical scaling of running time for finding optimal solutions to the TSP
  9 June 2018 | Journal of Heuristics, Vol. 24, No. 6
- Edge Assembly Crossover using Multiple Parents for Traveling Salesman Problem
- A Fast Algorithm on Minimum-Time Scheduling of an Autonomous Ground Vehicle Using a Traveling Salesman Framework
  1 August 2018 | Journal of Dynamic Systems, Measurement, and Control, Vol. 140, No. 12
- Leveraging TSP Solver Complementarity through Machine Learning
  Evolutionary Computation, Vol. 26, No. 4
- Applying Deep Learning and Reinforcement Learning to Traveling Salesman Problem
- Search-maps
  6 July 2018
- Parameterization of state-of-the-art performance indicators
  6 July 2018
- Local search effects in bi-objective orienteering
  2 July 2018
- Algebraic Crossover Operators for Permutations
- New hybrid heuristic algorithm for the clustered traveling salesman problem
  Computers & Industrial Engineering, Vol. 116
- Algorithm Configuration Landscapes:
  21 August 2018
- Exploration and Exploitation Without Mutation: Solving the Jump Function in $$\varTheta (n)$$ Time
  21 August 2018
- Elitism and Distance Strategy for Selection of Evolutionary Algorithms
  IEEE Access, Vol. 6
- SRT-GA: Smart real-time system using a powerful genetic algorithm for school bus routing problem
- On Production and Green Transportation Coordination in a Sustainable Global Supply Chain
  11 November 2017 | Sustainability, Vol. 9, No. 11
- Combining two local searches with crossover
  1 July 2017
- Building a better heuristic for the traveling salesman problem
  1 July 2017
- Fitness with diversity information for selection of evolutionary algorithms
- On the Effect of Adding Nodes to TSP Instances: An Empirical Analysis
  20 November 2016
- Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem
  Expert Systems with Applications, Vol. 67
- Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing – tabu search algorithm to solve the symmetrical traveling salesman problem
  Applied Soft Computing, Vol. 49
- Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
  Information Sciences, Vol. 374
- Travel itinerary problem
  Transportation Research Part B: Methodological, Vol. 91
- Memory-based statistical learning for the travelling salesman problem
- Application of improved ant colony optimization algorithm on traveling salesman problem
- Population Diversity Measures Based on Variable-Order Markov Models for the Traveling Salesman Problem
  31 August 2016
- Revisiting Additive Quantization
  17 September 2016
- Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference
  5 November 2016
- The Impact of Automated Algorithm Configuration on the Scaling Behaviour of State-of-the-Art Inexact TSP Solvers
  1 December 2016
- Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers
  1 December 2016
- A Switching Condition of Search Stages and a Multi-start Strategy in GA-EAX for TSPs
  Transactions of the Society of Instrument and Control Engineers, Vol. 52, No. 4
- Maintenance scheduling of geographically distributed assets with prognostics information
  European Journal of Operational Research, Vol. 245, No. 2
- On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances
  28 November 2014 | Optimization Letters, Vol. 9, No. 6
- On the Empirical Scaling Behaviour of State-of-the-art Local Search Algorithms for the Euclidean TSP
  11 July 2015
- Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection
  29 May 2015
- An improvement of fruit fly optimization algorithm for solving traveling salesman problems
- Machine scheduling with outsourcing
  The International Journal of Logistics Management, Vol. 25, No. 1
- THE USE OF HEURISTIC ALGORITHMS TO OPTIMIZE THE TRANSPORT ISSUES ON THE EXAMPLE OF MUNICIPAL SERVICES COMPANIES
  Archives of Transport, Vol. 29, No. 1
- Developing Programming Tools to Handle Traveling Salesman Problem by the Three Object-Oriented Languages
  Applied Computational Intelligence and Soft Computing, Vol. 2014
- A parallel genetic algorithm with edge assembly crossover for 100,000-city scale TSPs
- Path planning of a data mule in wireless sensor network using an improved implementation of clustering-based genetic algorithm

cover image INFORMS Journal on Computing

Volume 25, Issue 2

Spring 2013

Pages 193-393

Article Information

Supplemental Material

Metrics

Information

Received:March 01, 2011
Accepted:February 01, 2012
Published Online:May 04, 2012

Cite as

Yuichi Nagata, Shigenobu Kobayashi, (2012) A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing 25(2):346-363.

https://doi.org/10.1287/ijoc.1120.0506

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem

Supplemental Material

Volume 25, Issue 2

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News