Santa’s legendary parcel-delivery service, based on the shortest journey between cities, has just been enlightened by a breakthrough in one of the most intensively studied problems in mathematics.
Flinders University researchers believe they have cracked a long-running quest for an optimal solution to the classic algorithm question in computer science known as the Travelling Salesman Problem (TSP).
The TSP focuses on finding the most efficient and cheapest way for a travelling salesman to visit all of his cities and return to a starting point.
An optimal answer could lead to lucrative productivity gains in a range of industries and complex tasks, from logistics and transport to more cost-efficient manufacturing, gene sequencing and even drone mission planning.
The solution achieved by the Flinders Mathematical Sciences Laboratory Hamiltonian Cycle Project over the past three years has already broken more than 20 records, solving open TSP problems listed on the international register maintained by the University of Waterloo in Canada.
It is shaping up as a powerful new tool to develop better software systems for a range of industries, says Associate Professor Vladimir Ejov, director of the Flinders Mathematical Sciences Laboratory.
“In a resource-restrained world, optimal solutions are increasingly necessary in ever-more-complex processes,” Associate Professor Ejov says. “We hope this TSP solver could become a world leader in highly competitive market of solving difficult logistics and many other industrial problems by the virtue of its highest quality outcome.”
The Flinders algorithm, tentatively named Kookaburra, incorporates the Flinders “Snakes and Ladders” Hamiltonian Cycle problem-solving software with two other state-of-the-art tools – the computer code Concorde (developed at the University of Waterloo and Georgia Institute of Technology, US) and one of the world’s best, the LKH (based at Roskilde University, Denmark).
“Working together these three tools are producing phenomenal results. They can certify optimality of existing solutions previously unknown to be optimal or improve them to optimality,” says Associate Professor Ejov, from the School of Computer Science, Engineering and Mathematics. Computer engineer Serguei Rossomakhine says the Flinders software has the potential to capitalise and improve on long-running international efforts to refine the classic enigmatic math problem.
“Being able to find and certify the best solution to Travelling Salesman Problems could have an enormous impact in operations research, optimisation and computer science,” says Mr Rossomakhine.
The history of the TSP dates back to Sir William Hamilton’s early investigations of the dodecahedral graph in 1857 and his Hamiltonian Cycle Problem has puzzled math minds ever since. It is summarised as: Given a graph containing N vertices determine whether it contains a simple cycle of length N.
The study of the contemporary TSP began about 80 years ago in 1930s in Vienna and Harvard when mathematician Karl Menger observed the non-optimality of nearest neighbour approach. “Here at Flinders, it took us three years of trial and error experiments to see how our software could fit in and improve existing state-of-the-art TSP algorithms and now we have a piece of software that is likely to be the best in the world,” Associate Professor Ejov says.
“We believe our solutions cannot be further improved because Kookaburra certifies the solution, so any other solution is either equally optimal or worse.”
Ahead of seeking out possible industrial and research partners, PhD students Alex Newcombe and Pouya Baniasadi are putting the software to work in a range of applications while lecturer Dr Michael Haythorpe is looking to upgrade computer cluster facilities Colossus.
Further results will be promoted by the Flinders University team in coming months.