Travelling salesperson benchmarks

Routing makes edge structure visible: every decision connects one location to the next, and the quality of the complete tour emerges from those local relationships.

The dissertation evaluates COIN on Grötschel24, Grötschel48 and Grötschel120, and studies a bi-objective kroA/B100 formulation. Population size, local optimization, learning mode and generation count are examined against other approaches used in the study.

The reported experiments support COIN as a competitive edge-based method in that experimental setting. They also suggest that negative correlation learning can help resist premature convergence and accelerate parts of the search.

A population is a landscape of trade-offs

In multi-objective routing there is no single best route unless the decision-maker has already decided how objectives should be traded. The algorithm instead produces alternatives that are non-dominated under the selected measures.

Population clouds across generations in a bi-objective kroA100 and kroB100 travelling salesperson problem
Original dissertation figure: population clouds move across the bi-objective search space from generation 1 to generations 100 and 500.
Pareto fronts produced by reward, punishment and combined COIN updates at different generations
Original dissertation figure: trade-off fronts under reward-only, punishment-only and combined updates.
Decision principle

Optimization should expand the quality of available choices. It should not quietly make the policy decision that belongs to the organization.

U-shaped assembly-line balancing

Line balancing assigns tasks to workers or stations under precedence and cycle-time constraints. U-shaped layouts allow a worker to access tasks from both sides of the line, increasing flexibility while making the assignment problem more complex.

The dissertation compares COIN with NSGA-II on established problem sets. The algorithm must balance competing operational outcomes rather than optimize an abstract score alone.

U-shaped assembly-line sequencing

Sequencing adds another layer: the order of tasks or models influences workload, walking and production behavior. Permutation encoding fits naturally, but redundancy and feasibility remain important. Two different sequences may represent operationally equivalent assignments, wasting evaluations unless the representation or decoder recognizes that equivalence.

The source study reports competitive results for COIN across the selected real-world applications. A modern presentation should retain the exact benchmark definitions and indicators before generalizing beyond them.

What industry would require in 2026

  • Constraint fidelity: precedence, skills, safety, equipment and changeovers must be encoded or repaired.
  • Data governance: cycle times and demand assumptions must be traceable and versioned.
  • Scenario analysis: managers need alternatives under uncertainty, not one brittle optimum.
  • Explainability: the system should show why a sequence improved and which constraints shaped it.
  • Re-optimization: plans must adapt when workers, machines or demand change.
  • Human validation: operators should be able to challenge technically feasible but practically unrealistic plans.
Marketing, without exaggeration: COIN offers a distinctive research foundation for sequence-intensive decisions. Turning it into an industrial system would require a modern solver implementation, validated data pipelines, domain constraints, benchmarking and decision-support interfaces.

Research opportunities

Students can extend this work through dynamic routing, workforce scheduling, warehouse picking, maintenance planning, energy-aware production and human-in-the-loop optimization. The worthwhile question is not “Where can COIN be applied?” but “Where does learning from rejected structure improve decisions enough to justify the added model?”

← Empirical AnalysisReturn to COIN overview →