#4447 Mathematica TSP Studies

Quantum supremacy just ran into an unexpected rival: An ordinary laptop armed with new math

https://phys.org/news/2026-05-quantum-supremacy-ran-unexpected-rival.html

#4447 Can I get Mathematic to create a graph for a list of cities with mileages along edges?

Yes, you absolutely can! In Wolfram Mathematica, you can easily create graphs from a list of cities and the distances (mileages) between them using the built-in Graph and WeightedAdjacencyGraph functions.

Depending on how your data is structured, here are the two easiest ways to do it.

Method 1: Using a List of Rules (Best for direct city-to-city connections)

If you have a list showing which city connects to which, you can use the DirectedEdge (->) or UndirectedEdge (<->) format and style the edges with their weights (mileages).

(* Define the connections with distances as weights *)
cityGraph = Graph[
  {"New York" <-> "Chicago", "Chicago" <-> "Los Angeles", "Los Angeles" <-> "New York"},
  EdgeWeight -> {790, 2015, 2790},
  VertexLabels -> "Name",
  EdgeLabels -> "EdgeWeight",
  GraphLayout -> "SpringEmbedding",
  VertexStyle -> Blue,
  VertexSize -> Medium
]

Method 2: Using a Distance Matrix (Best for a complete table of distances)

If you have a grid or matrix of mileages between all cities, you can use WeightedAdjacencyGraph. Use Infinity ( $\infty$ ) for cities that aren't directly connected.

(* Define the cities *)
cities = {"Chicago", "Houston", "Miami"};

(* Define the mileage matrix (0 on the diagonal for a city to itself) *)
mileageMatrix = {
   {0, 1080, 1380},  (* Chicago to others *)
   {1080, 0, 1190},  (* Houston to others *)
   {1380, 1190, 0}   (* Miami to others *)
};

(* Create the graph *)
Graph[cities, WeightedAdjacencyGraph[mileageMatrix],
 VertexLabels -> "Name",
 EdgeLabels -> "EdgeWeight",
 VertexLabelStyle -> Directive[Bold, 12],
 ImageSize -> Large]

Pro-Tip: Use Real Geographic Coordinates

If you want the graph to actually look like a map instead of a generic network diagram, you can use Mathematica's built-in geographic data to position the vertices:

cities = {"New York", "Chicago", "Los Angeles", "Miami"};

(* Fetch real coordinates *)
coords = EntityValue[GeoPosition[Interpreter["City"][#]] & /@ cities, "Quantity"];

Graph[cities, 
 {"New York" <-> "Chicago", "Chicago" <-> "Los Angeles", "Los Angeles" <-> "Miami", "Miami" <-> "New York"},
 EdgeWeight -> {790, 2015, 2730, 1280},
 VertexCoordinates -> Table[Reverse[coords[[i]][[1]]], {i, Length[cities]}],
 VertexLabels -> "Name",
 EdgeLabels -> "EdgeWeight",
 GraphBackground -> LightGray]

Note: When using VertexCoordinates with latitude and longitude, you usually want to Reverse the coordinates so they map correctly to standard $(x, y)$ Cartesian coordinates (Longitude = $x$ , Latitude = $y$ ).

How is your data currently formatted? If you paste a sample of your city list, I can write the exact code to format it for you!

List and describe the various capabilities within Mathematica for Traveling Salesman Problem studies

Wolfram Mathematica has a highly robust, enterprise-grade environment for studying, simulating, and solving the Traveling Salesman Problem (TSP). It combines core graph theory, built-in optimization algorithms, geographic datasets, and visualization tools into a single workflow.

Mathematica’s TSP capabilities are organized into five primary functional areas:

1. The Core Solver: `FindShortestTour`

The powerhouse for any TSP study in Mathematica is FindShortestTour. It is highly adaptive and polymorphic, accepting multiple types of input data:

Coordinate Data: Passing a list of 2D or 3D Cartesian coordinates ({{x1, y1}, {x2, y2}, ...}) solves the Euclidean TSP.
Graph Objects: Passing a Graph object (directed, undirected, or weighted) solves the Graph-based TSP, utilizing the network's underlying edge weights.
Text/Entities: Passing real-world entities (like a list of cities) tells Mathematica to automatically pull geographic metadata to compute the route.

Path Customization (Open vs. Closed Tours)

Standard TSP (Closed Loop): FindShortestTour[data] finds the shortest tour that returns to the starting point.
Fixed Endpoints (Open Path): FindShortestTour[data, start, end] solves a Hamiltonian path variant where you specify exactly where the "salesman" begins and ends.

2. Algorithm Control and Algorithmic Study

For academic or performance studies, Mathematica allows you to bypass its Automatic selection and explicitly dictate which algorithm solves the problem via the Method option. This is invaluable for comparing heuristic accuracy vs. computational time.

Method	Description / Best Use Case
"IntegerLinearProgramming"	Finds the exact, mathematically optimal solution. Highly intensive; best for small to medium-sized city lists.
"SimulatedAnnealing"	A metaheuristic that uses stochastic global optimization to jump out of local minima. Great for benchmarking.
`"TwoOpt"` & `"OrOpt"`	Classic iterative local search heuristics that swap edges to untangle and optimize the route.
"CCA"	(Convex hull, Cheapest insertion, and Angle selection) An aggressive geometric heuristic for fast approximations.
"SpaceFillingCurve"	Uses fractal curves (like the Hilbert curve) to order points spatially. Incredibly fast for massive datasets (millions of points).

Mathematica also allows you to plug in a custom DistanceFunction (e.g., Manhattan distance, Chebyshev distance, or a custom cost metric), enabling asymmetric TSP studies where traveling from $A \to B$ has a different cost than $B \to A$ .

3. Real-World Geographic Integration

One of Mathematica's greatest advantages over standard graph libraries is its built-in curated knowledge base (GeoPosition and Entity framework):

Geodesic Distance: By giving FindShortestTour a list of geographic entities (e.g., Entity["City", "Paris"]), it calculates distances across the Earth's curved surface (oblate spheroid) using GeoDistance, rather than flat Euclidean math.
Live Routing Integration: Through TravelDistanceList, you can hook into live map data to solve the TSP based on actual driving times or driving distances instead of "as the crow flies" straight lines.

4. Visualizing and Graphing the Results

Once a tour is solved, Mathematica offers extensive visual tools to plot and analyze the data:

HighlightGraph: Easily highlight the winning TSP cycle directly on a network graph alongside edge weights.
GeoGraphics: Automatically overlay the solved TSP route onto an interactive, highly detailed world map using GeoPath.
Computational Geometry: For Euclidean studies, functions like MeshRegion and ConvexHullMesh can be paired with the TSP path to study geometric properties of the tour (like crossing eliminations).

5. Related Optimization Variants

Beyond standard TSP, Mathematica includes native functions to study adjacent combinatorial problems:

FindHamiltonianCycle / FindHamiltonianPath: Solves the unweighted decision-problem version (finding any valid path that visits all vertices exactly once).
FindPostmanTour: Solves the "Chinese Postman Problem," minimizing the path length required to traverse every edge at least once (instead of every vertex).
FindMinimumCostFlow / LinearOptimization: Allows you to build highly customized, specialized routing constraints (such as Capacitated Vehicle Routing Problems, or TSP with time windows) from scratch using traditional operations research frameworks.

From <https://gemini.google.com/app/> Google Gemini (3.5 Flash)

Search This Blog

Learning from ChatGPT