{"id":"9f887313ab1f4061","slug":"world-airports-shortest-roundtrip-tsp","trashed":false,"description":"","likes":26,"publish_level":"public","forks":0,"fork_of":{"id":"546b88f86e8150ca","slug":"world-airports-voronoi","title":"World airports Voronoi","owner":{"id":"863951e3ebe4c0ae","avatar_url":"https://avatars.observableusercontent.com/avatar/5af16e327a90b2873351dda8a596c0d2d3bf954f64523deefe80177c9764d0f7","login":"d3","name":"D3","bio":"Bring your data to life.","home_url":"https://d3js.org","type":"team","tier":"pro_2024"},"version":319},"has_importers":false,"update_time":"2019-12-22T12:59:26.663Z","first_public_version":null,"paused_version":null,"publish_time":"2019-12-19T10:54:47.784Z","publish_version":575,"latest_version":575,"thumbnail":"d2352fee71da4e044d888263c2d206d73b231fdea1d79f42400a693b5101d601","default_thumbnail":"d2352fee71da4e044d888263c2d206d73b231fdea1d79f42400a693b5101d601","roles":[],"sharing":null,"owner":{"id":"78f29d059906819a","avatar_url":"https://avatars.observableusercontent.com/avatar/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","login":"mourner","name":"Volodymyr Agafonkin","bio":"Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦","home_url":"https://agafonkin.com","type":"team","tier":"starter_2024"},"creator":{"id":"3954cddf6608132f","avatar_url":"https://avatars.observableusercontent.com/avatar/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","login":"mourner","name":"Volodymyr Agafonkin","bio":"Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦","home_url":"https://agafonkin.com","tier":"pro"},"authors":[{"id":"3954cddf6608132f","avatar_url":"https://avatars.observableusercontent.com/avatar/02cfd655debb6fc593dfe4bcacd9520f73e6b33cedef382248d08ecc40822a1b","name":"Volodymyr Agafonkin","login":"mourner","bio":"Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦","home_url":"https://agafonkin.com","tier":"pro","approved":true,"description":""}],"collections":[],"files":[{"id":"580b7e73da032db49aa901c1491efecdb68b0962db1b8b8a4e572960854106f231e554f892f57e5dd0a8d04ea6b9d2a69b90b8ae3394089e4e549a3a5ee8864c","url":"https://static.observableusercontent.com/files/580b7e73da032db49aa901c1491efecdb68b0962db1b8b8a4e572960854106f231e554f892f57e5dd0a8d04ea6b9d2a69b90b8ae3394089e4e549a3a5ee8864c","download_url":"https://static.observableusercontent.com/files/580b7e73da032db49aa901c1491efecdb68b0962db1b8b8a4e572960854106f231e554f892f57e5dd0a8d04ea6b9d2a69b90b8ae3394089e4e549a3a5ee8864c?response-content-disposition=attachment%3Bfilename*%3DUTF-8%27%27airports.tsp","name":"airports.tsp","create_time":"2019-12-20T15:16:27.060Z","mime_type":"application/octet-stream","status":"public","size":110259,"content_encoding":null,"private_bucket_id":null},{"id":"efa4394abe610fe34bca1960b7a78bca5d09b61bac0875a4b9c8e7af54577d0b75492536a38a3c014235336d68984ad11e849e4be6341f36fb2f14f560cfd964","url":"https://static.observableusercontent.com/files/efa4394abe610fe34bca1960b7a78bca5d09b61bac0875a4b9c8e7af54577d0b75492536a38a3c014235336d68984ad11e849e4be6341f36fb2f14f560cfd964","download_url":"https://static.observableusercontent.com/files/efa4394abe610fe34bca1960b7a78bca5d09b61bac0875a4b9c8e7af54577d0b75492536a38a3c014235336d68984ad11e849e4be6341f36fb2f14f560cfd964?response-content-disposition=attachment%3Bfilename*%3DUTF-8%27%27airports.sol","name":"airports.sol","create_time":"2019-12-20T15:16:33.235Z","mime_type":"application/octet-stream","status":"public","size":14802,"content_encoding":null,"private_bucket_id":null}],"comments":[],"commenting_lock":null,"suggestion_from":null,"suggestions_to":[],"version":575,"title":"World Airports Shortest Roundtrip (TSP)","license":null,"copyright":"","nodes":[{"id":0,"value":"md`# World Airports Shortest Roundtrip (TSP)\n\nBelow you can find a visualization of the [shortest roundtrip](https://en.wikipedia.org/wiki/Travelling_salesman_problem) through **3119** world airports (546,110,050 meters total).\n\nI obtained it with **William Cook**'s [Concorde TSP](http://www.math.uwaterloo.ca/tsp/concorde/index.html) exact solver in ~2.5 hours on my Macbook Pro. Curiously, a previous run on an older, 5% smaller airport list completed in 25 minutes, so it varies a lot. Concorde also contains a <code>linkern</code> utility for finding approximate solutions fast — it got a result of 546,982,750 meters (0.16% longer than optimal) in 16 seconds total (over 5 runs).\n\nFor comparison, **Keld Helsgaun**'s [LKH](http://akira.ruc.dk/~keld/research/LKH/), a state-of-the-art approximate TSP solver, got a _nearly_ optimal route of 546,123,685 meters (only 0.0025% longer) using default parameters in just 2 minutes. \n\n**Update:** Keld Helsgaun contacted me after seeing this notebook and shared some parameter tweaks (see <code>parameterFile</code> cell) that make LKH find the _optimal_ route in 15 seconds (as opposed to 2.5 hours) — astonishing!\n\nTo learn more about this fascinating area of mathematics, check out William Cook's book [In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation](https://press.princeton.edu/books/paperback/9780691163529/in-pursuit-of-the-traveling-salesman).\n\nAirport data from [OurAirports](https://ourairports.com/data/) (narrowed down to medium and large airports with scheduled services). Globe visualization by [Mike Bostock](https://observablehq.com/@mbostock/world-airports-voronoi).\n`","pinned":false,"mode":"js","data":null,"name":null},{"id":28,"value":"chart = {\n  const context = DOM.context2d(size, size);\n  const path = d3.geoPath(mutable projection, context).pointRadius(1.5);\n  const graticule = d3.geoGraticule10();\n\n  function render() {\n    context.clearRect(0, 0, size, size);\n\n    context.beginPath();\n    path(graticule);\n    context.lineWidth = 0.5;\n    context.strokeStyle = \"#aaa\";\n    context.stroke();\n\n    context.beginPath();\n    path(tour);\n    context.lineWidth = 1;\n    context.strokeStyle = \"#000\";\n    context.stroke();\n\n    context.beginPath();\n    path({type: \"Sphere\"});\n    context.lineWidth = 1.5;\n    context.strokeStyle = \"#000\";\n    context.stroke();\n\n    context.beginPath();\n    path({type: \"MultiPoint\", coordinates: points});\n    context.fillStyle = \"#f00\";\n    context.fill();\n  }\n  \n  function dragged() {\n    mutable projection = mutable projection;\n    render();\n  }\n\n  return d3.select(context.canvas)\n    .call(drag(mutable projection).on(\"drag.render\", dragged))\n    .call(render)\n    .node();\n}","pinned":false,"mode":"js","data":null,"name":null},{"id":505,"value":"points = problemFile.trim().split('\\n').slice(6).map(line => line.split(' ').map(Number).slice(-2).reverse())","pinned":true,"mode":"js","data":null,"name":null},{"id":356,"value":"tour = ({\n  type: 'LineString', \n  coordinates: solutionFile.split(/\\W+/).slice(1).map(i => points[+i]).concat([points[0]])\n})","pinned":true,"mode":"js","data":null,"name":null},{"id":354,"value":"solutionFile = FileAttachment(\"airports.sol\").text()","pinned":true,"mode":"js","data":null,"name":null},{"id":414,"value":"problemFile = FileAttachment(\"airports.tsp\").text()","pinned":true,"mode":"js","data":null,"name":null},{"id":561,"value":"parameterFile = `\nPROBLEM_FILE = airports.tsp\nTOUR_FILE = airports.tour\nOPTIMUM = 546110050\nRUNS = 1\nCANDIDATE_SET_TYPE = POPMUSIC\nRECOMBINATION = GPX2\nPRECISION = 10\nPATCHING_C = 3\nPATCHING_A = 2`","pinned":false,"mode":"js","data":null,"name":null},{"id":56,"value":"mutable projection = d3.geoOrthographic()\n    .fitExtent([[1, 1], [size - 1, size - 1]], {type: \"Sphere\"})\n    .rotate([0, -30])","pinned":false,"mode":"js","data":null,"name":null},{"id":530,"value":"size = Math.min(width, 640)","pinned":false,"mode":"js","data":null,"name":null},{"id":216,"value":"import {drag} from \"@d3/versor-dragging\"","pinned":false,"mode":"js","data":null,"name":null},{"id":7,"value":"d3 = require(\"d3@5\")","pinned":false,"mode":"js","data":null,"name":null}],"resolutions":[],"schedule":null,"last_view_time":null}