This is an interactive representation of the Traveling Salesperson Problem (TSP)
In this simulation you can generate random maps containing 5-15 nodes. Click on a node/box to connect it to the distribution path. When all nodes are connected you will see the total length of the loop. To make things more interesting you are also able to place distribution hubs by clicking in an empty space. Clicking on an active node or hub will remove it from the current path.
The task is to find the shortest path that connects all nodes (creating a round trip) without using any node more than once. This is a type of optimization problem that is NP-hard, which (simplified) means that it is very hard or impossible to verify a proposed solution without actually testing it. With a very small set of nodes it's often quite easy to visually find a solution for the shortest path, but already at 10 or more nodes the solution often requires some experimentation.
TSP makes up a large part of the challenge in planning home delivery logistics, commonly referred to as the Last Mile Problem. One easy way to imagine a real life application is to think of the nodes as households and the path a representation of food delivery, when it’s essential to find a reasonably short path in order to keep the food warm or cold. From an environmental and economical perspective there is also a large incentive to keep ordinary package deliveries on a short path, to reduce the time and resources needed.
