The travelling salesman problem (TSP) asks the following question: “Given a list of locations and the distances between each pair of locations, what is the shortest possible route that visits each location exactly once and returns to the origin location?”
The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of locations can be solved completely and even problems with millions of locations can be approximated within limited time.
The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. In these applications, the concept location represents, for example, customers and the concept distance represents travelling times or cost. In many applications, additional constraints such as limited resources or time windows may be imposed.
In this video we will understand how to solve TSP and provide routing facility on WebGIS application using Leaflet.
