32:T5fd,# Solving Single-Pickup Multi-Dropoff as Traveling Salesman Problem _[related tweet thread](https://twitter.com/MattDzugan/status/1438927293661995012)_ The well-researched [Traveling Salesman Problem]() can be used to connect a series of N points in an order than minimizes the total distance needed to visit each city once and return back to the origin city. However, the optimal solution to the afforementioned scenario is **NOT ALWAYS THE SAME** as a similar problem, where I no longer need to revisit the original location. And in this scenario where the sequence is no longer a cycle, I might want to indicate which point in particular is my starting point. I'll call this the **Single-Pickup Multi-Dropoff** problem. Here's the fun puzzle though: 🤔 > *How can I use the well-researched, well studied "traveling salesman problem" (and its related algorithmic solutions) to solve the **Single-Pickup Multi-Dropoff** problem?* Answer: Add a few *ghost points* with some special properties 👻 Specifically, we can create 2 points `Ghost1` and `Ghost2`. `Ghost 1` has a zero-distance connection to all destinations, and a zero-distance connection to the `Ghost 2` (and an implied infinite distance connection to the origin). You can think of `Ghost 1` as a "Destination Sink". `Ghost 2` connects `Ghost 1` to the `Origin`. When a Traveling-Salesman-Problem solver finds the optimal route, all we need to do is remove the `Ghost` points from its path, and voila - we've solved the **Single-Pickup Multi-Dropoff** problem.33:T4e8,viewof circles = { const context = DOM.context2d(width, height); const canvas = context.canvas; // An assortment of randomly-positioned colorful circles. const circles = canvas.value = d3.range(N_dest+3).map(i => ({ i:i, x: Math.random() * (width - radius * 2) + radius, y: Math.random() * (height - radius * 2) + radius, color: (i == 0 ) ? '#f9ca24' : ((i > N_dest ) ? '#c7ecee' : '#4834d4') })); // Whenever the circles move, redraw the canvas. function render() { context.clearRect(0, 0, width, height); for (const {i, x, y, color, active} of circles) { context.beginPath(); context.moveTo(x + radius, y); context.arc(x, y, radius, 0, 2 * Math.PI); context.fillStyle = color; context.fill(); if (active) { context.lineWidth = 2; context.stroke(); } //canvas.dispatchEvent(new CustomEvent("input")); } canvas.dispatchEvent(new CustomEvent("input")); //canvas.dispatchEvent(new CustomEvent("input")); } // Bind the drag behavior for interaction. d3.select(context.canvas).call(drag(circles) .on("start.render drag.render end.render", render)); // Render the initial canvas. render(); return canvas; }34:T8c8,{ const context = DOM.context2d(width, height); const canvas = context.canvas; // Whenever the circles move, redraw the canvas. function render() { context.clearRect(0, 0, width, height); if (showLines.includes("connectivity")){ for(var ii=0; ii { const dist = (a, b) => adjacencyMatrix[a][b] let result = []; for (let i = 0; i < N; i++) { let row = new Float32Array(N); for (let j = 0; j < N; j++) { row[j] = dist(i, j); } result.push(row); } return result; })(); function firstTwoOptImprovement(tour) { const next = current => (current + 1) % tour.length; const pick = d3.randomInt(tour.length - 2); function delta(i, j) { let ni = tour[next(i)]; let nj = tour[next(j)]; let ci = tour[i]; let cj = tour[j]; return ( distances[ci][cj] + distances[ni][nj] - distances[ci][ni] - distances[cj][nj] ); } function move(from, to) { let result = [...tour]; let count = to - from; for (let i = 0; i < count; i++) { result[from + 1 + i] = tour[to - i]; } return result; } for ( let times = 0, start = pick(); times < tour.length; times++, start = next(start) ) { for (let end = start + 2; end < tour.length; end++) { let variation = delta(start, end); if (variation < ESPILON) { return { tour: move(start, end), delta: variation }; } } } return { tour: tour, delta: 0 }; } const random = () => d3.shuffle(d3.range(N)); let current = { tour: random(), delta: Number.MIN_SAFE_INTEGER }; //yield current.tour; console.log("delta " + current.delta); while (current.delta < 0) { //yield current.tour; current = firstTwoOptImprovement(current.tour); } //yield current.tour; return(current.tour); }37:[] 30:{"title":"Solving Single-Pickup Multi-Dropoff as Traveling Salesman Problem","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":402,"value":"## Define our Origin and Destinations","pinned":false,"hidden":false,"mode":"md"},{"id":47,"value":"viewof N_dest = Inputs.range([2, 10], {value: 5, step: 1, label: \"Number of Destinations\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":443,"value":"_drag these circles around to modify their positions_","pinned":false,"hidden":false,"mode":"md"},{"id":139,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":272,"value":"## Solutions","pinned":false,"hidden":false,"mode":"md"},{"id":351,"value":"### Framed as Traditional Traveling Salesman Problem\nNote how this framing optimizes for the shortest _full cycle_","pinned":false,"hidden":false,"mode":"md"},{"id":167,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":277,"value":"### Framed as Single-Pickup Multi-Dropoff\nNote how the final destination may be quite far from the origin","pinned":false,"hidden":false,"mode":"md"},{"id":178,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":382,"value":"## Graphic Aesthetics","pinned":false,"hidden":false,"mode":"md"},{"id":345,"value":"viewof showLines = Inputs.checkbox([\"connectivity\", \"solution\"], {label: \"Draw Lines:\", value:[\"solution\"]})","pinned":false,"hidden":false,"mode":"ojs"},{"id":386,"value":"viewof showGhosts = Inputs.toggle({label: \"Draw Ghosts 👻 ?\", value: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":425,"value":"## Solve the TSP\n### First we compute the distance matrices","pinned":false,"hidden":false,"mode":"md"},{"id":181,"value":"adjacencyMatrix = {\n var m = [];\n const N = circles.length-2;\n\n \n for(var ii=0; ii d3.range(N+2).map(x => 0))\n\n for(var ii=0; ii d3.ascending(a.i, b.i))","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"sample = [[ 0, 10, 15, 20 ], // City 1 to cities 2, 3, and 4\n [ 10, 0, 35, 25 ], // City 2 to cities 1, 3, and 4\n [ 15, 35, 0, 30 ], // City 3 to cities 1, 2, and 4\n [ 20, 25, 30, 0 ]] // City 4 to cities 1, 2, and 3","pinned":false,"hidden":false,"mode":"ojs"},{"id":431,"value":"### Now execute the solver","pinned":false,"hidden":false,"mode":"md"},{"id":23,"value":"v1 = solveTSP(adjacencyMatrix)","pinned":false,"hidden":false,"mode":"ojs"},{"id":229,"value":"v2 = solveTSP(adjacencyMatrix_adjusted)","pinned":false,"hidden":false,"mode":"ojs"},{"id":436,"value":"### And re-organize the (cyclical) arrays so they now start at Origin","pinned":false,"hidden":false,"mode":"md"},{"id":248,"value":"v1_0 = startFrom0(v1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"v2_0 = startFrom0(v2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"## Core TSP Solver Algorithm","pinned":false,"hidden":false,"mode":"md"},{"id":10,"value":"$36","pinned":true,"hidden":false,"mode":"ojs"},{"id":303,"value":"## Array Helper Functions","pinned":false,"hidden":false,"mode":"md"},{"id":232,"value":"function arrayRotate(arr, reverse) {\n if (reverse) arr.unshift(arr.pop());\n else arr.push(arr.shift());\n return arr;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":242,"value":"function startFrom0(array){\n var a = JSON.parse(JSON.stringify(array));\n while(a[0] != 0){\n a = arrayRotate(a);\n }\n\n if(a[1]>a[a.length-1]){\n return [0].concat(a.slice(1).reverse())\n }else{\n return a\n }\n \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"## Aesthetics","pinned":false,"hidden":false,"mode":"md"},{"id":41,"value":"height = 200","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"radius = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"## imports","pinned":false,"hidden":false,"mode":"md"},{"id":28,"value":"import {drag} from \"@d3/hello-d3-drag\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}