TL;DR
This paper introduces EAX-EDO, a novel evolutionary approach to the Traveling Salesperson Problem (TSP) that doesn't just find one "best" route, but a diverse set of high-quality alternatives. By modifying the state-of-the-art Edge Assembly Crossover (EAX) to prioritize population entropy, the authors outperform existing methods in generating robust, near-optimal solutions even when the true global optimum is unknown.
What Problem Does This Paper Address?
In classical optimization, the goal is usually to find the single best solution (the global optimum). However, for real-world Traveling Salesperson Problems—like logistics or air traffic control—the "mathematically optimal" route might be risky. What if a specific road is closed? What if a decision-maker prefers to visit a certain city earlier for non-mathematical reasons?
To handle this, we need Evolutionary Diversity Optimisation (EDO): finding a set of solutions that are all "good enough" (within a certain percentage of the optimal cost) but structurally different from one another. Most existing TSP diversity research assumes the optimal solution is already known or relies on simple local search operators (like $k$-OPT) that struggle with large, complex maps. The authors aim to bridge this gap by using a more powerful genetic operator to find diverse, high-quality tours from scratch.
Methods
The core contribution is the EAX-EDO Crossover. It builds upon the high-performing Edge Assembly Crossover (EAX), which typically works by combining edges from two parent tours to create "AB-cycles" and then merging resulting sub-tours into a valid path.
Standard EAX merges these sub-tours to minimize cost. EAX-EDO changes the rules:
- Entropy-Based Diversity: Instead of just counting unique edges, the algorithm uses an information-theoretic entropy measure ($H$). A population has high entropy if edges are distributed roughly equally across the set, rather than everyone using the same "popular" edges.
- Modified Connection Step: When the algorithm connects sub-tours to form a final tour, it evaluates potential edge additions based on how much they increase the population's total entropy, provided the final tour length stays below a quality threshold ($c_{max}$).
- Single-Stage vs. Two-Stage: The authors propose two frameworks for when the optimum is unknown. The Two-stage version alternates between minimizing cost and maximizing diversity. The Single-stage version (which proved superior) optimizes both simultaneously by generating two offspring per iteration: one focused on quality and one on diversity.
Datasets
The researchers evaluated their approach using standard benchmarks from TSPlib, a widely recognized library for TSP instances. Specifically, they tested on:
- Small instances: eil51, eil76, eil101 (used for diversity measure comparisons).
- Larger instances: a280, pr439, u574, rat575, p654, rat783, u1060, pr2392, and fnl4461.
Key Insights and Ideas
- Entropy > Distance: The authors found that using entropy as a fitness function yields more structurally diverse populations than traditional distance-based measures (like mean pairwise distance).
- The "Greedy" Trap: In the "Unknown Optimum" scenario, alternating between cost and diversity (Two-stage) often leads to a "negative impact on efficiency." The Single-stage approach is more robust because it maintains a "hall of fame" ($P^*$) of the best solutions found so far to prevent the diversity search from drifting too far into low-quality territory.
- Robustness as a Feature: A diverse population isn't just a curiosity; it's a safety net. The authors demonstrated that if you randomly "break" (remove) edges from the optimal tour, the EAX-EDO population is significantly more likely to contain a high-quality alternative that avoids those broken edges compared to standard solvers.
Key Results
- Superior Diversity: EAX-EDO consistently outperformed $k$-OPT and standard EAX in generating diverse sets. For example, on the
eil101instance, the Single-stage EAX-EDO found 758 unique edges across the population, compared to only 238 found by the standard EAX or the Gurobi exact solver. - Quality Maintenance: Despite the focus on diversity, EAX-EDO maintained very high solution quality, often finding tours within a fraction of a percent of the optimal cost.
- Robustness: In experiments where 1–3 edges of the optimal tour were made unavailable, the Single-stage EAX-EDO population provided viable alternative tours in 82% to 90% of cases, whereas standard EAX and Gurobi often failed to provide even a single alternative.
Limitations and Future Work
- Computational Cost: EAX is a complex operator. While the authors mention that many calculations can be shared between the two offspring in the single-stage approach, it is still more computationally intensive than simpler heuristics.
- Parameter Tuning: The algorithms require tuning several parameters (like the quality threshold $\alpha$ and the failure limit $M$). While they used
iRacefor automatic configuration, these settings might vary significantly across different types of TSP instances. - Future Directions: The authors suggest exploring methods to select populations from a larger pool of offspring and individuals to further boost performance, as well as applying these EDO techniques to real-world logistics problems where constraints change dynamically.
Summary updated