Graphical TSP Instances

used in A New Integer Programming Formulation of the Graphical Traveling Salesman Problem

Click here for computational results

Instanced based on United States Highways. |V|=216, |E|=358.

File listing all edges, one per line.
  Interstate.txt - Format: city_1 city_2 distance

File listing all cities alphabetically, one per line.
  citylist.txt - Format: city_number city_name (degree: #)

Lists of city numbers from citylist.txt for instances, cities separated by white space
  ALLcities.txtn = 216Entire graph
  AtoJcities.txtn = 101Cities beginning with letters from A to J
  CAPcities.txtn = 4948 state capitals plus Washington D.C.
  CtoWcities.txtn = 182Cities beginning with letters from C to W
  dakota3path.txtn = 113-path configuration in northern plains
  deg3cities.txtn = 171Cities in original graph with degree ≥ 3
  ESTcities.txtn = 139Cities east of the Mississippi River
  MSAcities.txtn = 145Centers of 145 metropolitan statistical areas
  NFLcities.txtn = 30Cities with National Football League teams
  NScities.txtn = 174Cities that Neil Simonetti has visited
  NWcities.txtn = 43Cities in the Northwest region


Many helpful discussions contributed to this paper.
Special thanks goes to Dave Gay, Cindy Phillips, Warren Craft, Ojas Parekh