Researchers in the United States have developed sophisticated software capable of quickly solving TSP-related questions involving thousands of points. In theory, however, the complexity of the X-and-Y-axes TSP remained an open question.
Dr Vladimir Deineko
Researchers at the University of Warwick, Graz University of Technology and Eindhoven University have solved a 30-year-old special case concerning the travelling salesman problem (TSP). The team succeeded in proving that it is possible to find an optimal solution to the X-and-Y-axes TSP special case within a polynomial – or mathematically reasonable – amount of time.
The TSP was defined approximately 150 years ago and concerns the identification of the optimal route for a salesperson calling at numerous addresses. The salesperson must visit each of their customers once and return to their starting point within the shortest possible period of time. Solutions relating to the TSP provide useful applications within fields such as haulage, air traffic control and even DNA sequencing.
Dr Vladimir Deineko, Associate Professor of Operational Research at Warwick Business School, spoke to
ScienceOmega.com about his findings. As he explained, accurately judging the complexity of TSP-related problems is no simple matter.
"The TSP belongs to a class known as the NP-hard problems," he said. "When you are attempting to tackle a practical problem, it is important to know whether or not it is possible to reach an exact solution within a reasonable amount of time. In mathematical terms, this is known as polynomial time."
Dr Deineko and his colleagues were specifically interested in developing an algorithm to prove that a special case of this problem, known as the X-and-Y-axes TSP, could be solved within this period of time.
"Researchers in the United States have developed a sophisticated piece of software called Concorde, which is capable of quickly solving TSP-related questions involving thousands of points," Dr Deineko explained. "In theory, however, the complexity of the X-and-Y-axes TSP remained an open question. Imagine that the travelling salesman’s destinations run along a single straight line; all of his customers live on the same street. In this situation, it is clearly very easy to find the optimum route; the problem is trivial. When these points exist on two perpendicular lines – along the X and Y axes – the problem becomes slightly more difficult. It was not previously known whether or not this case was solvable in polynomial time. We were the first people to identify an algorithm relating to the complexity of the X-and-Y-axes TSP."
The TSP is a mathematical problem with a wide range of practical implications. Whilst Dr Deineko’s algorithm for the X-and-Y-axes special case does not have any immediate real-life applications, it is an extra string to the collective bow of interested practitioners.
"I am not aware of any practical applications that result from our findings," conceded Dr Deineko. "Somebody once said that problems such as the TSP are a paradise for researchers but a graveyard for practitioners. However, by taking a step-by-step approach, we can gradually add to our understanding of this problem. I work within the field of operational research and yet my paper is largely theoretical. My colleagues often ask me how my findings might be used in practice. I answer them by alluding to the following analogy. Imagine that a football player is performing an exercise that is difficult to master, such as keeping the ball in the air for a sustained period of time. Whilst this skill might not be of any practical use, it improves his technique and thus increases his overall capability as a player.
"Similarly, my students can now learn how to deal with this seemingly simple case of the TSP," he concluded. "In this way, they develop transferable skills that can be used to solve real-life problems. I too have used this approach in the past. I worked alongside a city council to try to solve vehicle-routing problems concerning waste collection services. The algorithm that we have created will help others to tackle similar practical problems. It won’t simplify our lives overnight, but it’s an extra skill to add to our collection."
As we are not nocturnal animals by nature, then we must benefit from sunlight, in several ways. It then follows that we can deal with sunlight - maybe we need to be more in touch with how to deal with exposure. This research shows that we do not know all the ways that we use sunlight naturally, which is probably true of other environmental factors. I will be very interested in outcomes of further research. Is there any research about sunlight and cognition?
