Constrained Optimal Routes in 3D Space
Constrained Optimal Routes in 3D Space
Given a set of constraints, what is an optimal travel route between given points? Such problems are usually posed in 2D or on a surface; for example, finding the shortest path through a set of points on the surface of Earth. This Demonstration highlights a subset of such optimization problems in 3D, as might be needed in outer space or under water.
Imagine you need to travel on a spaceship to land on several different planets, exactly once each. This would be the traveling salesman problem if you were not subject to a constraint. For example, the more fuel you carry the less cargo you can have, so it is advantageous to limit the ship’s carrying fuel capacity. Therefore you might have to refuel on different planets, but remote planets might not be accessible. You will be able to traverse only a so-called "percolation network," where an edge exists only between planets close enough to travel between without refueling. An optimal tour on such a network is different (if possible at all) from the traveling salesman tour. This Demonstration visualizes the difference between these cases.
In the limit, for very large settings of the "range" control, the routes on the percolation network and traveling salesman route coincide.