The Travelling Salesman Problem in the Modern Era

First formulated back in the Nineteenth Century, study into the Travelling Salesman Problem (TSP) was notably enhanced by the American mathematician Merrill M. Flood in the 1930s as he set out to solve a school-bus routing problem. TSP is a mathematical problem in which the shortest possible route has to be found along a set of points (bus stops in this case). The defined route must pass through each point once only before returning to the original starting point.

Generally speaking, the order in which each stop or point is visited is not a principal factor, as long as the salesman visits each of them once. Despite the phenomenal simplicity of its formulation, TSP is an NP-hard problem in combinatorial optimization and can be used as a model in which to test optimization techniques when applied to a variety of problems including dynamic shared-vehicle dispatch.

On a more abstract level, TSP can be described by means of graph theory, as an undirected weighted network, whose nodes represent cities and whose links have certain weights indicating distances between those cities. In this context, finding the optimal solution of TSP means finding the shortest path and connecting all nodes within the network. A variety of algorithms that analyze the structural properties of a network whilst looking for its shortest paths are available in literature and lie at the core of traditional graph-theory. The application of these algorithms within complex networks is encountered in established fields like mathematics, biology, and social sciences. 

It is astonishing that although these algorithms are based on and were developed as a means to tackle a relatively simplistic problem today their predictive power is also harnessed to facilitate complex industrial operations. Industries of paramount importance in our daily lives like the delivery of goods on a local, national and international scale, the maritime industry, airport networks, public transportation networks in big metropolitan cities are just some examples that use variations of TSP algorithms to make our life’s easier. 

Finding the shortest path on a TSP variation can be achieved by calculating all possible route combinations. This brute force approach works when N is sufficiently small but is virtually unfeasible for large N. In the latter case, heuristic search algorithms provide excellent approximate solutions. The main benefit of heuristic search algorithms lies in their ability to obtain solutions of TSP variation, which although may not be exact, are sufficiently more practical and most importantly are obtained quickly and with low computational cost. This makes heuristic search algorithms popular and suitable for software services where computational resources are limited and the response in real-time is crucial, especially when the demand scales up.

Shotl technology uses modern scientific methods which allow for the utilization of previous and current research within complex networks and optimization algorithms. The provided service, supported by an agile engineering design is built around a robust algorithmic core that finds optimal solutions on a TSP variation formulated according to the constraints implied by the specific situation. 

Our algorithmic solution matches multiple passengers, that are heading in the same direction, with a moving vehicle, minimizing ride distances and waiting time, thus offering a better transportation service and experience.