none
none

KOOKABURRA HAS THE LAST LAUGH SOLVING TRAVELING SALESMAN PROBLEM

18-04-2017
by 
in 

A “missing puzzle piece” to help solve the infamous Travelling Salesman Problem (TSP) has been developed in Australia, researchers say.

The algorithm, called Kookaburra, was developed at Flinders University in South Australia and works in conjunction with the North American computer code Concorde and the Danish algorithm LKH.

The TSP is a classic algorithm question in computer science that focuses on finding the most efficient way for a travelling salesman to visit all of his cities and return to a starting point.

Unlike previous solutions, which have been targeted at one particular TSP, Kookaburra has been used to help optimally solve more than 20 problems listed on the international register of TSPs maintained by the University of Waterloo, Canada.

There are numerous techniques that aim to solve particular TSPs but many scientists believe it is impossible to develop a comprehensive model that can address every problem.

Director of the Flinders Mathematical Sciences Laboratory Vladimir Ejov said although the TSP would never theoretically be solved, the Kookaburra was now the best and most reliable TSP solver worldwide in very strong competition.

“We’ll keep improving Kookaburra but it's already remarkably the best bird in the world,” Associate Professor Ejov said.

“It (Kookaburra) is the missing piece of the puzzle because together with the versions from Denmark and Concorde, as a team, they solved problems that were outstanding for a long time.

“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.”

Concorde was developed by the University of Waterloo in Canada and the Georgia Institute of Technology in the United States while LKH is the product of research at Denmark’s Roskilde University.

The study of contemporary TSPs began about 80 years ago in Vienna and Harvard when mathematician Karl Menger observed the non-optimality of nearest neighbour approach.

The Kookaburra algorithm has many potential practical applications such as cost-efficient manufacturing, ordering features of the human genome and planning drone missions.

Associate Professor Ejov said Kookaburra and the other two models were shaping up as the most efficient tool for developing better software systems that would not only benefit technologies such as driverless cars but also help companies save millions of dollars.

Now, Kookaburra and the other two models are not only able to calculate the best possible candidate to multiple problems but they can ensure it is the optimal result.

“There are many types of problems for different types of Travelling Salesman Problems but our method can solve graphs, 2D problems and more – it is the universal tool,” he said.

“We believe our solutions cannot be further improved because Kookaburra certifies the solution, so any other solution is either equally optimal or worse.”

Further results from the University of Waterloo register will be published in the coming months.

The group is also looking to commercialise their TSP-solving solution, which has been made available by Flinders Partners.

Associate Professor Ejov said they would explore more industrial applications and were not looking to restrict the model to any specific field.

Related news & editorials

  1. 21.06.2017
    21.06.2017
    by      In
    Billed as the best hydraulic training system in the world, the Fluid Power Training Institute MF102-H-TSE is available now from Bestech Australia.
    The MF102-H hydraulic training system was designed by renowned hydraulics instructor Rory McLaren, and comes with everything required to help students... Read More
  2. 15.06.2017
    15.06.2017
    by      In
    The Australian Industry Group has released its report on science, engineering, technology and mathematics skills under the title “Strengthening school-industry STEM skills partnerships”.
    This report is the culmination of a two-year research project funded by the Office of the Chief Scientist to... Read More
  3. 14.06.2017
    14.06.2017
    by      In
    This year’s foodpro is set to be an educational experience, with a packed programme of topical seminars and industry expert speakers, including Brett Wiskar of Wiley, Ron Cotterman of Sealed Air and Glen Pinna of Biotech Laboratories.
    The educational sessions will run throughout each day of the... Read More
  4. 06.06.2017
    06.06.2017
    by      In
    One of the biggest education technology expos, EduTECH 2017, is back for another year, aiming to show how 3D printing can change the way we educate our future workers. 
    Exhibition attendance is free, and gives visitors access to a huge range of exhibitors, talks, and demonstrations. 
    "Walking... Read More