liveBook · Manning

Open traveling salesman problem

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

An open traveling salesman problem seeks a minimum-cost route visiting each specified location without requiring the route to return to its starting location.

An open traveling salesman problem seeks the shortest route through every specified location exactly once, starting from a designated city without returning to it. Ant colony optimization (ACO) models this routing task with geographic distances, pheromone trails, and probabilistic city selection. section 10.3.5

A practical ACO solution proceeds by:

  • Building a city coordinate dictionary and calculating pairwise haversine distances in a distance matrix. section 10.3.5

Twenty-city route

A custom ACO run produces a New York City-to-San Francisco route covering 20 major US cities with a reported length of 7,937.115.

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Explains route construction, probability calculation, pheromone updating, parameters, and iterative best-route tracking.
Examples
Uses twenty US cities, Python listings, geographic coordinates, route visualizations, and reported ACO and ACOpy paths.
What it assumes
Assumes familiarity with Python arrays, graphs, distance calculations, and basic ant colony optimization parameters.
What you can do after
Builds an ACO solver that returns a best route and its total distance.
How it connects
Connects ant colony optimization with haversine distance, distance matrices, pheromone evaporation, and graph representations.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.