The Travelling Salesman Problem describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each one during his trip, and finishes where he was at first. Each city is connected to other close by cities, or nodes, by airplanes, or by road or railway. Each of those links between the cities has one or more weights (or the cost) attached. The cost describes how “difficult” it is to traverse this edge on the graph, and may be given, for example, by the cost of an airplane ticket or train ticket, or perhaps by the length of the edge, or time required to complete the traversal. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible.
While there are many solutions out there in Java and other languages, I thought I would create an implementation using PL/SQL and Oracle Spatial alone.
The main Oracle Spatial function that I use is the nearest neighbour SDO_NN operator.
The implementation requires:
Table of points coded only in SDO_POINT_TYPE;
Points can be 2D or 3D;
Table has unique integer column (either primary key or unique constraint/index);
Table is spatially indexed;
One can create a sample dataset that implements these requirements as follows.
DROPTABLE ProjPoint2D PURGE;
CREATETABLE ProjPoint2D ( id INTEGER, geom mdsys.sdo_geometry );