It depends on what you want to call a city. For the traveling salesman problem we need only a collection of interesting points, so we've taken the full set of 199,123 Populated Places compiled by the U. S. Geological Survey, pruned it down to the 48 lower states and removed points that were closer than one mile to another point.

Populated Places are defined by the USGS as Named features with human habitation--cities towns, villages, etc. So, for example, rather than just a single point for New York City, the data set includes Washington Heights, West Village, Tudor City, and Inwood as destinations in Manhattan, as well as areas in The Bronx, Brooklyn, Queens, and Staten Island.

The USGS data set was downloaded on July 7, 2012. Removing data for Alaska, Hawaii, and regions outside of the 50 states left 193,698 locations. I next removed points listed as historical, such as Black Gum Corners, Alabama, and any points where the latitude and longitude were not specified. This left 179,056 points, but some of these were very near to each other, including different village names for the same latitude-longitude location. I then ran a small code to remove points that were less than 0.02 total difference in lat-long from another named placed. The result is our list of 115,475 spots to visit in the 48 states.

My apologies to Alaska and Hawaii--having such separated locations in the tour would also be an interesting TSP, but I wanted to avoid creating an instance that would suggest immediately a divide-and-conquer approach (piecing together separate tours for the lower 48, Alaska, and Hawaii).

The Cities, Towns, and Villages

The final data set runs from Lincoln (population 6,226) in Talladega County, Alabama to Vista West (population 1,008) in Natrona County, Wyoming. Here is the list of all 115,475 cities, towns, and villages, grouped by states. The ordering is that same as the one used in the TSPLIB file usa115475.tsp.

I was happy to see my childhood town of Florence in Burlington County, New Jersey, as city 65,264 on the list. Sorry if your home town was cut off by the pruning process--when two points were given nearly the same coordinates, the process deleted the first of the two points as in the original ordering in the USGS list.

City 65,264: Florence, New Jersey