Flinders University ‘Kookaburra’ discovery may boost logistics productivity

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 was achieved by the Flinders Mathematical Sciences Laboratory Hamiltonian Cycle Project over the past three years and 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, said 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,” Ejov said. “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 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.
 
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.