30:Tf8f,mapboxMap = { const container = html`

`; yield container; mapboxgl.accessToken = "pk.eyJ1IjoidG9mZmkiLCJhIjoiY2lvMDBxMzR3MDB1eHZza2x4NGI2YjI5OSJ9.IEaNA05pWbT92nOu-lEOYw"; var map = new mapboxgl.Map({ container: container, //style: "mapbox://styles/mapbox/dark-v10", style: { version: 8, sources: { "raster-tiles": { type: "raster", tiles: [ "https://stamen-tiles.a.ssl.fastly.net/watercolor/{z}/{x}/{y}.jpg" ], tileSize: 256, attribution: 'Map tiles by Stamen Design, under CC BY 3.0. Data by OpenStreetMap, under CC BY SA' }, "terrain-labels": { type: "raster", tiles: [ "https://stamen-tiles.a.ssl.fastly.net/terrain-labels/{z}/{x}/{y}.jpg" ], tileSize: 256 } }, layers: [ { id: "simple-tiles", type: "raster", source: "raster-tiles", minzoom: 0, maxzoom: 22 }, { id: "simple-labels", type: "raster", source: "terrain-labels", minzoom: 0, maxzoom: 22 } ] }, center: [5.0801921, 45.3061884], zoom: 4 }); const markers = []; map.on("load", () => { // add markers for the cities in the initial cities array mutable cities.forEach((city) => { const el = document.createElement("div"); el.innerText = city.city; el.className = "marker"; const marker = new mapboxgl.Marker(el) .setLngLat(city.position) .addTo(map); markers.push({ city: city.city, marker: marker }); }); map.addSource("connection", { type: "geojson", data: viewof route.value }); map.addLayer({ id: "outline", type: "line", source: "connection", layout: {}, paint: { "line-color": "#000", "line-width": 3 } }); }); map.on("click", (e) => { const lng = e.lngLat.lng; const lat = e.lngLat.lat; const distance_per_pixel_zoom = 78.192 * Math.E ** (-0.693 * map.getZoom()); let closestCities = geokdbush.around( cities_index, lng, lat, Infinity, 25 * distance_per_pixel_zoom ); if (!closestCities || !closestCities.length) { closestCities = geokdbush.around(cities_index, lng, lat, 1); console.log(closestCities); } const closestCity = closestCities.sort( (a, b) => b.population - a.population )[0]; const cityIndex = markers.findIndex((m) => m.city === closestCity.city); if (cityIndex > -1) { mutable cities.splice(cityIndex, 1); mutable cities = mutable cities; const toRemove = markers.splice(cityIndex, 1); console.log(toRemove, toRemove.marker); toRemove[0].marker.remove(); } else { const el = document.createElement("div"); el.innerText = closestCity.city; el.className = "marker"; const marker = new mapboxgl.Marker(el) .setLngLat([closestCity.lng, closestCity.lat]) .addTo(map); mutable cities = [ ...mutable cities, { city: closestCity.city, position: [closestCity.lng, closestCity.lat] } ]; //cities.push(closestCity.city); markers.push({ city: closestCity.city, marker: marker }); } }); viewof route.addEventListener("input", () => { // update the routes source geojson map.getSource("connection").setData(viewof route.value); }); invalidation.then(() => map.remove()); }31:T54a,result = { // retrieve an initial result let updatedResult = solver.Solve(tsp_model); // await Generators.queue(worker(tsp_model)).next().value; //solver.Solve(tsp_model) // yield initial; let edges = countEdges(updatedResult); // check if the solver found a solution to a subset of the actual TSP // if so, we constraint the use of this subroute, and re-solve while (edges.length < cities.length) { const updatedModel = tsp_model; //JSON.parse(JSON.stringify(tsp_model)); const options = []; for (let index = 0; index < edges.length; ++index) { const start = edges.slice(undefined, index); const end = edges.slice(index); options.push( [...end, ...start].map((p) => `${p[0]}::${p[1]}`).join("::") ); } edges.forEach((pair) => { const cityCombi = `${pair[0]}::${pair[1]}`; options.forEach((permutation) => { updatedModel.variables[cityCombi][permutation] = 1; }); }); options.forEach((permutation) => { updatedModel.constraints[permutation] = { max: edges.length - 1 }; }); // re-run the model updatedResult = await Generators.queue(worker(updatedModel)).next().value; yield updatedResult; // check the number of edges again edges = countEdges(updatedResult); console.log(edges.length); } yield updatedResult; }32:[{"id":"96f362b7366438d045f2b1db80f2085ef990bd18d650171bd88ce21510bc3259eec2e37b1c40b9eccb25c0ef6713b52e350a765137fd0fb48aec003722962aaf","href":"https://static.observableusercontent.com/files/96f362b7366438d045f2b1db80f2085ef990bd18d650171bd88ce21510bc3259eec2e37b1c40b9eccb25c0ef6713b52e350a765137fd0fb48aec003722962aaf","name":"worldcities.csv","type":"text/csv","lastModified":1619632309546.153,"size":2859311}] 2e:{"title":"Holiday planner 🌴","cells":[{"id":0,"value":"md`# Holiday planner 🌴\n\nAre you looking to get the most out of your holidays? \nThen surely you'd like to minimize the time spend in a train or car!\n\nThis notebook will help you find the shortest path for visiting all the cities you'd like to visit. \n**Click on the map to add a destination**. Clicking the label again will remove it. \n\nThe shortest path to visiting these ${\n cities.length\n} cities is ~${result.result.toFixed(0)} km.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":62,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":678,"value":"md`\nIn order to solve this [travelling salespeson problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem), we use a (naïve) mixed-integer approach.\nFor solving the actual mixed-integer problem, the [jsLPSolver](https://github.com/JWally/jsLPSolver) library is used.\n\nThis approach does not incorporate any heuristics, and is therefore quite slow when compared to other implementations! In the future, I'd like to try and compare this approach with using the [glpk.js](https://github.com/jvail/glpk.js) library. \nIf you have any improvements, please let me know 😊\n### Ressources:\nhttps://opensourc.es/blog/mip-tsp/ \nhttps://observablehq.com/@fil/som-tsp \nhttps://observablehq.com/@fil/travelling-salesperson-approximation-with-t-sne \nhttps://observablehq.com/@fil/travelling-salesperson-approximation-on-the-globe-with-um \nhttps://observablehq.com/@oscarlvp/tsp-art\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":140,"value":"mutable cities = [\n { city: \"Madrid\", position: [-3.6919, 40.4189] },\n { city: \"Vienna\", position: [16.3731, 48.2083] },\n { city: \"Milan\", position: [9.19, 45.4669] },\n { city: \"Paris\", position: [2.3522, 48.8566] },\n { city: \"Cologne\", position: [6.9578, 50.9422] }\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"distances = cities.reduce((wrapper, fromCity) => {\n wrapper[fromCity.city] = cities.reduce(\n (obj, toCity) => (\n (obj[toCity.city] = turf.distance(fromCity.position, toCity.position)),\n obj\n ),\n {}\n );\n return wrapper;\n}, {})","pinned":false,"hidden":false,"mode":"ojs"},{"id":407,"value":"viewof route = new View({})","pinned":false,"hidden":false,"mode":"ojs"},{"id":395,"value":"{\n // filter the city pairs from the result object\n const combinations = Object.keys(result).filter(\n (k) => defaults.indexOf(k) === -1\n );\n // create a line for each pair\n const features = combinations.map((pair) => {\n const cityPair = pair.split(\"::\");\n return turf.lineString([\n cities.find((c) => c.city === cityPair[0]).position,\n cities.find((c) => c.city === cityPair[1]).position\n ]);\n });\n const featureCollection = turf.featureCollection(features);\n set(viewof route, featureCollection);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":381,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":320,"value":"tsp_model = {\n const model = {\n optimize: \"distance\",\n tolerance: 0.1,\n opType: \"min\",\n constraints: {},\n variables: {},\n binaries: {}\n };\n // insert variables\n\n cities.forEach((fromCity) => {\n model.constraints[fromCity.city] = { min: 2 };\n\n cities.forEach((toCity) => {\n if (fromCity === toCity) return;\n if (\n model.variables[`${fromCity.city}::${toCity.city}`] ||\n model.variables[`${toCity.city}::${fromCity.city}`]\n )\n return;\n const route1 = `${fromCity.city}::${toCity.city}`;\n const route2 = `${toCity.city}::${fromCity.city}`;\n\n model.constraints[route1] = { max: 1 };\n model.variables[`${fromCity.city}::${toCity.city}`] = {\n distance: distances[fromCity.city][toCity.city],\n [fromCity.city]: 1,\n [toCity.city]: 1,\n [route1]: 1,\n [route2]: 1\n };\n model.binaries[`${fromCity.city}::${toCity.city}`] = 1;\n });\n });\n\n return model;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":491,"value":"function countEdges(modelResult) {\n const cityPairArray = Object.keys(modelResult)\n .filter((k) => defaults.indexOf(k) === -1)\n .map((p) => p.split(\"::\"));\n const start = cityPairArray[0][0];\n const travelledRoute = [cityPairArray[0]];\n let keepGoing = true;\n let cityToLookFor = cityPairArray[0][1];\n while (travelledRoute.length < cityPairArray.length && keepGoing) {\n // find the next matching city pair\n const nextStop = cityPairArray.find(\n (pair) =>\n (pair[0] == cityToLookFor || pair[1] == cityToLookFor) &&\n travelledRoute.indexOf(pair) === -1\n );\n if (!nextStop) {\n break;\n }\n //cityToLookFor = travelledRoute[travelledRoute.length - 1][1];\n if (nextStop[0] === cityToLookFor) {\n cityToLookFor = nextStop[1];\n } else {\n cityToLookFor = nextStop[0];\n }\n travelledRoute.push(nextStop);\n if (cityToLookFor === start) keepGoing = false;\n }\n return travelledRoute;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":450,"value":"defaults = [\"feasible\", \"result\", \"bounded\", \"isIntegral\"]","pinned":false,"hidden":false,"mode":"ojs"},{"id":275,"value":"worker = function (model) {\n const workertext = `\nimportScripts(\"https://unpkg.com/javascript-lp-solver/prod/solver.js\");\n\nonmessage = function(d){\n var results = solver.Solve(d.data);\n postMessage(results);\n};\n`;\n const b = new Blob([workertext], { type: \"text/javascript\" });\n return function (notify) {\n const url = URL.createObjectURL(b);\n const worker = new Worker(url);\n worker.addEventListener(\"message\", (r) => notify(r.data));\n worker.postMessage(model);\n return () => {\n worker.terminate();\n URL.revokeObjectURL(url);\n };\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":611,"value":"html`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":379,"value":"function set(input, value) {\n input.value = value;\n input.dispatchEvent(new Event(\"input\"));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":66,"value":"mapboxgl = {\n const gl = require(\"mapbox-gl@2\");\n if (!gl.accessToken) {\n // token allowed only this Observable\n gl.accessToken =\n \"pk.eyJ1IjoidG9mZmkiLCJhIjoiY2lvMDBxMzR3MDB1eHZza2x4NGI2YjI5OSJ9.IEaNA05pWbT92nOu-lEOYw\";\n const href = await require.resolve(\"mapbox-gl@2/dist/mapbox-gl.css\");\n document.head.appendChild(html``);\n }\n return gl;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"cities_index = new kdbush(\n worldcities,\n (p) => p.lng,\n (p) => p.lat\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":227,"value":"turf = require(\"@turf/turf\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":75,"value":"geokdbush = require(\"https://bundle.run/geokdbush@1.1.0\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":73,"value":"kdbush = require(\"https://bundle.run/kdbush@3.0.0\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":362,"value":"import { View } from \"@mbostock/synchronized-views\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":53,"value":"worldcities = FileAttachment(\"worldcities.csv\").csv({ typed: true })","pinned":true,"hidden":false,"mode":"ojs"},{"id":4,"value":"solver = require(\"https://unpkg.com/javascript-lp-solver/prod/solver.js\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}