To revisit this article, visit My Profile, then View saved stories .

- The Big Story
- Newsletters
- Steven Levy's Plaintext Column
- WIRED Classics from the Archive
- WIRED Insider
- WIRED Consulting

## Flying Math: Bees Solve Traveling Salesman Problem

By Virginia Morell, * Science *NOW

Bumblebees foraging in flowers for nectar are like salesmen traveling between towns: Both seek the optimal route to minimize their travel costs. Mathematicians call this the "traveling salesman problem," in which scientists try to calculate the shortest possible route given a theoretical arrangement of cities. Bumblebees, however, take the brute-force approach: For them, it's simply a matter of experience, plus trial and error , scientists report in the current issue of PLoS Biology .

A team of researchers from Queen Mary, University of London outfitted seven bumblebees with tiny radar transponders, which they stuck on the bees' backs with double-sided tape. They trained the bees to forage nectar from five blue artificial flowers (see video). Each artificial flower had a yellow landing platform and a single drop of sucrose, just enough to fill one-fifth of a bumblebee's tank capacity, to ensure that the bees would visit all five flowers on each foraging bout.

The scientists placed the flowers in a field at Rothamsted Research, a biological research station north of London, in October — a time of year when there are few natural sources of nectar and pollen and the bees are more likely to focus on the artificial flowers. They arranged the flowers in a pentagon and spaced them 50 meters apart; that distance is more than three times as far as bumblebees can see, so the bees must actively fly around to locate their next target. A motion-triggered webcam was attached to each flower to record the bees' visits. Then, every day for a month, each bee was freed to forage for 7 hours.

"We'd done a similar experiment in our lab," says Mathieu Lihoreau, the lead author of the study and a behavioral ecologist now at the University of Sydney in Australia. "But that was in quite a small area for a bee — only 7 by 7 meters." Seeing the bees forage in the wild was entirely different. At first, Lihoreau says, he tried to track the bees' movements by running alongside them as they flew from flower to flower, "but they are so fast, it wasn't possible." The transponders eliminated the need for Lihoreau's sprints, and also collected each bee's flight trajectory, travel distance, and ground speed. From all those data, the scientists recreated the bees' journeys and modeled them mathematically — and discovered that they may be employing a relatively simple method to find the most efficient route between the flowers.

"Initially, the bees' routes were long and complex, and they revisited empty flowers several times," Lihoreau says. "But they gradually refined their routes through trial and error."

At first, the bees visited the flower nearest to their nest, and then the next closest flower. They kept track — that is, they remembered — the total distance traveled on each foraging trip. They tried new routes to increase their efficiency, and if a route was shorter, they kept it. If not, they abandoned it. As their experience increased, they rarely altered the sequence of flowers they visited.

After trying about "20 of the 120 possible routes, the bees were able to select the most efficient path to visit the flowers," Lihoreau says. "They did not need to compute all the possibilities." A naïve bee traveled almost 2,000 meters on its first foraging bout among the pentagonal array; by her final trip, she'd reduced that distance to a mere 458 meters.

Perhaps most surprising to the scientists was how quickly the bumblebees learned from their trial-and-error method. Before this study, such sophisticated learning was "thought to be something only larger-brained animals were capable of," says Lars Chittka, a behavioral ecologist at Queen Mary, University London and another member of the team.

Although the researchers did not set out to test whether bumblebees use cognitive maps, the study's results suggest that they do not. "The idea of a cognitive map is very contentious," Lihoreau says. "But it's not a very parsimonious hypothesis; it seems a lot to expect from a small brain with less than one million neurons." Using a simple rule, as the bumblebees did in this test, may better explain what appears to us as complex behavior, he says.

"It's a lovely study," says Mandyam Srinivasan, a neuroethologist at the University of Queensland in Brisbane, Australia. "It shows that bumblebees, with their diminutive 1 milligram brains, are capable of finding a nearly perfect solution to the traveling salesman problem, with relatively few attempts and in a relatively short time." This doesn't prove that bumblebees do not possess a cognitive map, he adds, "but it does demonstrate that they can get by without one."

*This story provided by Science NOW, the daily online news service of the journal *Science.

Advertisement

## Bumblebees solve the travelling salesman problem on the fly

By New Scientist and Press Association

11 December 2017

A bumblebee outfitted with a tiny tracking device

Joe Woodgate/PA

Bumblebees aren’t just hard workers, they’re efficient, too. These insects have a grasp of maths that enables them to crack the classic travelling salesman problem as they forage for pollen and nectar.

The problem, a benchmark of computer science, poses the question, “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”

This was the conundrum facing bumblebees let loose on an array of artificial flower feeding stations at…

## Sign up to our weekly newsletter

Receive a weekly dose of discovery in your inbox! We'll also keep you up to date with New Scientist events and special offers.

To continue reading, subscribe today with our introductory offers

No commitment, cancel anytime*

Offer ends 10 September 2024.

*Cancel anytime within 14 days of payment to receive a refund on unserved issues.

Inclusive of applicable taxes (VAT)

Existing subscribers

## More from New Scientist

Explore the latest news, articles and features

## Spiders use fireflies as flashing lures to catch more prey

## Consumer insecticides are useless for fighting cockroach infestations

## Mathematics

The surprising connections between maths and poetry.

Subscriber-only

## Environment

Streetlights may make tree leaves tough and hard for insects to eat, popular articles.

Trending New Scientist articles

- The Inventory

## Bees can solve the Traveling Salesperson Problem

Technology has made navigation easy for humans, with electronic maps that instruct us aloud so we needn’t learn directions at all. Bees, obviously, don’t have that option, and they also have very small brains—yet their navigation skills rival those of even the most adept human travelers.

According to a study published in Scientific Reports on Dec. 11, the flight of the bumblebee even becomes more efficient over time. A research team, led by Joseph Woodgate of the biological and experimental psychology department at Queen Mary University of London, used a harmonic radar tracking system to study bee navigation, following the insects’ flight paths within a set of artificial flowers. They discovered that bees are in a continual process of optimizing their routes over time.

Until now, scientists have studied bees’ movement by looking at the length of their flights, as well as where they land. No prior study created a brand new environment to follow bees continuously as they navigate it. The researchers say that new tracking technology enabled them to track the insects while they were learning new paths, collecting location data every three seconds. Their experiment suggests that the small-brained bugs are capable of solving complex routing issues, skillfully contending with what’s known as “the traveling salesperson problem.”

Traveling salespeople learn the fastest route from Point A to Point B to Point C. The most efficient paths are not always most direct, nor are they necessarily the same coming and going from a single location. The challenge is to find a route that visits each destination while traveling the shortest possible distance. The study’s coordinator, zoologist Lars Chittka explained this conundrum in a statement :

Imagine a sales[person] from London who needs to call at Manchester, Leeds, Glasgow, Edinburgh, and Inverness before returning home. From Manchester, it is tempting to make the short trip across to Leeds, and from Glasgow it is tempting to visit Edinburgh, but a sales[person] who does that will soon find themselves stranded in Inverness with a very long drive home. The better solution is to travel up one side of the UK and return down the other.

Past research that looked only at the order in which small foragers like birds and bees arrive at each destination, showed that they often find optimal solutions—but it couldn’t explain how the animals decreased flight times. To figure that out, the bee research team set up five artificial flowers, which were not as attractive as real flowers but did offer the bees sweet nectar when they landed. Scientists then tracked the insects over two days as they explored the paths and developed routes.

Like people, bees are creatures of habit. The study’s bees established favorite paths early on and followed them regularly, limiting exploration with time. They also became better navigators with each flight, changing route sequences to improve speed from one feeder to another until they found the best paths, and becoming increasingly adept at their favorite flights. They never became completely set in their ways, however.

The research team believes their work can inform a few very different fields of study. For one, it improves understanding of how bees and other pollinating insects search for food and operate, which can help humans minimize risks posed by habitat loss and increased agriculture. The study also adds to a growing body of knowledge on animal cognition, used to understand both animal and human brains. Lastly, the researchers say, their findings could come in handy for technologists developing machines that navigate. In the future, when your GPS tells you to turn left, you may have a bee to thank for the information.

## 📬 Sign up for the Daily Brief

Our free, fast, and fun briefing on the global economy, delivered every weekday morning.

- Newsletters
- Account Activating this button will toggle the display of additional content Account Sign out

## What Willy Loman Could Learn From the Birds and Bees

Animals solve a wildly complex mathematical problem that humans still struggle with..

Photo by Dave Menke/U.S. Fish and Wildlife Service.

It’s Saturday; you’ve got errands to run. Your spouse wants bread from the bakery, you need to pick up the dry cleaning, your kids need new shoes, and you’ve got a dentist appointment. None of this is any fun, so you might as well do it as quickly as possible by calculating the fastest and most efficient route that takes you to each stop.

Who should you ask to help you plot your path: a mathematician or a honeybee?

It may seem like it should be a matter of simple math, but the solution to this so-called “traveling salesman” problem is surprisingly elusive. The issue was first identified in an 1832 brochure for actual traveling salesmen in Germany, but mathematicians only began seriously investigating it 100 years later, when Karl Menger and Hassler Whitney proposed the problem at Harvard and Princeton, respectively. (Which institution has a stronger claim to the genesis of the puzzle remains a point of debate for both Ivies.) Menger and Whitney both discovered that the number of possible routes between stops increases exponentially with each additional destination. In a typical model, for instance, three stops yield six routes, while eight stops yield 40,320. As the number of potential routes skyrockets, it becomes nearly impossible to account for the nuanced differences in distance between potential routes—differences that can add up after only a few stops. Computer scientists have recently proposed various algorithms to solve the problem, and one professor seems to have actually found a solution . His wildly complex computer program, however, is probably inapplicable to your weekend chores.

That’s where the bees come in.

Researchers at University of London have discovered that bees calculate the fastest route among the flowers with the most pollen and nectar. By setting up five artificial flowers in a pentagon shape and tracking each bee’s path, the researchers discovered that every bee optimized its route, visiting the highest-reward flowers in the shortest possible amount of time. It took only a brief moment of exploration of the fake flowers for the bees to calculate a perfect route, and each seemed to accomplish the feat independently—no groupthink or supercomputer required. The bees were especially keen when faced with the issue of short-term inconvenience for longer-term reward, going slightly out of their way to visit the higher-yield flowers even when it cost them a few seconds of travel time.

And it turns out bees aren’t the only animals that beat humans to solving the traveling salesman problem. Researchers at the University of New Hampshire have suggested that birds called Clark’s Nutcrackers perform a similar algorithm when collecting the 30,000 pine nuts they bury in 5,000 caches throughout the winter. Clark’s Nutcrackers, the researchers speculated, use landmarks to remember the location of each stash and calculate the fastest route between each bush or rock when collecting their nuts. Even more impressively, the birds could use dead reckoning , an ability to return directly to an earlier spot without the use of visual aids.

How do these brilliant creatures do in their tiny brains what humans still struggle to do with computers? Nobody really knows. Evolution must have favored faster-calculating brains—the savvier birds and bees found more food faster and had more offspring—but the specific mental mechanism behind these calculations remains unknown. It’s also not clear what, if anything, humans can learn from the animals’ problem-solving abilities, though in theory we might be able to utilize their physical and mental prowess to maximize human efficiency. That was one of California governor and railroad magnate Leland Stanford’s goals when he asked Eadweard Muybridge to capture a horse’s gallop on his zoopraxiscope: Stanford, a consummate industrialist, was always looking to build a better machine and wasn’t above cribbing a few tips from the animal kingdom.

Although Muybridge’s motion picture never led to a galloping train (Amtrak’s Northeast Regional may come close), inventors and businessmen alike were inspired by the elegant efficiency of a horse’s trot. There’s no reason that kind of inspiration shouldn’t continue today, mixed, perhaps, with a bit of awe at the genius of supposedly lesser creatures. As humans become increasingly isolated from the rest of the animal kingdom, the traveling salesman problem is an important reminder that no matter how much we innovate and calculate, we can still get scooped by bees.

## How bumblebees tackle the traveling salesman problem

It is a mathematical puzzle which has vexed academics and travelling salesmen alike, but new research from Queen Mary, University of London's School of Biological and Chemical Sciences, reveals how bumblebees effectively plan their route between the most rewarding flowers while travelling the shortest distances.

The research, led by Dr Mathieu Lihoreau and published in the British Ecological Society's Functional Ecology , explored the movement of bumblebees, Bombus terrestris , as they collected nectar from five artificial flowers varying in reward value.

"Animals which forage on resources that are fixed in space and replenish over time, such as flowers which refill with nectar, often visit these resources in repeatable sequences called trap-lines," said Dr Lihoreau, "While trap-lining is a common foraging strategy found in bees, birds and primates we still know very little about how animals attempt to optimise the routes they travel."

Research into optimising routes based on distance and the size of potential rewards is reminiscent of the well known Travelling Salesman problem in mathematics, which was first formulated in 1930, but remains one of the most intensively studied problems in optimisation.

"The Travelling Salesman must find the shortest route that allows him to visit all locations on his route," explained co-author Dr Nigel Raine, "Computers solve it by comparing the length of all possible routes and choosing the shortest. However, bees solve simple versions of it without computer assistance using a brain the size of grass seed."

The team set up a bee nest-box, marking each bumblebee with numbered tags to follow their behaviour when allowed to visit five artificial flowers which were arranged in a regular pentagon.

"When the flowers all contain the same amount of nectar bees learned to fly the shortest route to visit them all," said Dr Lihoreau. "However, by making one flower much more rewarding than the rest we forced the bees to decide between following the shortest route or visiting the most rewarding flower first."

In a feat of spatial judgement the bees decided that if visiting the high reward flower added only a small increase in travel distance, they switched to visiting it first. However, when visiting the high reward added a substantial increase in travel distance they did not visit it first.

The results revealed a trade-off between either prioritising visits to high reward flowers or flying the shortest possible route. Individual bees attempted to optimise both travel distance and nectar intake as they gained experience of the flowers.

"We have demonstrated that bumblebees make a clear trade-off between minimising travel distance and prioritising high rewards when considering routes with multiple locations," concluded co-author Professor Lars Chittka. "These results provide the first evidence that animals use a combined memory of both the location and profitability of locations when making complex routing decisions, giving us a new insight into the spatial strategies of trap-lining animals."

- Insects (including Butterflies)
- Animal Learning and Intelligence
- Artificial Intelligence
- Distributed Computing
- Computer Science
- Computer Graphics
- Yellow fever
- Orchidaceae
- Hummingbird
- Radiography
- Flowering plant
- American Quarter Horse
- Origin of life

Story Source:

Materials provided by Queen Mary, University of London . Note: Content may be edited for style and length.

Journal Reference :

- Mathieu Lihoreau, Lars Chittka, Nigel E. Raine. Trade-off between travel distance and prioritization of high-reward sites in traplining bumblebees . Functional Ecology , 2011; DOI: 10.1111/j.1365-2435.2011.01881.x

Cite This Page :

## Explore More

- Two Epicenters in Japan's Recent Earthquake
- NASA Changed Shape, Orbit of Asteroid Moon
- Solar Geoengineering Research
- New Light On Ultra-Fast Atomic Processes
- Colorful Traits in Primates Ease Tensions
- Fisheries Research Overestimates Fish Stocks
- DNA for Both Data Storage and Computing
- 'One-Step' Conversion of Methane to Methanol
- How Mosquitoes Track Down Humans
- New Gels Protect Buildings During Wildfires

## Trending Topics

Strange & offbeat.

## Flying Math: Bees Solve Traveling Salesman Problem

Bumblebees foraging in flowers for nectar are like salesmen traveling between towns: Both seek the optimal route to minimize their travel costs. Mathematicians call this the “traveling salesman problem,” in which scientists try to calculate the shortest possible route given a theoretical arrangement of cities. Bumblebees, however, take the brute-force approach: For them, it’s simply a matter of experience, plus trial and error, scientists report in the current issue of PLoS Biology. Read the full story at Wired.

## About Shelly Palmer

Shelly Palmer is the Professor of Advanced Media in Residence at Syracuse University’s S.I. Newhouse School of Public Communications and CEO of The Palmer Group, a consulting practice that helps Fortune 500 companies with technology, media and marketing. Named LinkedIn’s “Top Voice in Technology,” he covers tech and business for Good Day New York , is a regular commentator on CNN and writes a popular daily business blog . He's a bestselling author , and the creator of the popular, free online course, Generative AI for Execs . Follow @shellypalmer or visit shellypalmer.com .

- Top Stories

## Get Briefed Every Day!

Subscribe to my daily newsletter featuring current events and the top stories in technology, media, and marketing.

- News Releases

## How bumblebees tackle the traveling salesman problem

Queen Mary University of London

image: An artificial flower is being visited by a bumblebee ( Bombus terrestris ) worker. The bee obtains a small sugar solution reward when it visits the flower. The flower can be refilled by remote control so the behaviour of bees was not disturbed during the experiment. view more

Credit: Mathieu Lihoreau

It is a mathematical puzzle which has vexed academics and travelling salesmen alike, but new research from Queen Mary, University of London's School of Biological and Chemical Sciences, reveals how bumblebees effectively plan their route between the most rewarding flowers while travelling the shortest distances.

The research, led by Dr Mathieu Lihoreau and published in the British Ecological Society's Functional Ecology , explored the movement of bumblebees, Bombus terrestris , as they collected nectar from five artificial flowers varying in reward value.

"Animals which forage on resources that are fixed in space and replenish over time, such as flowers which refill with nectar, often visit these resources in repeatable sequences called trap-lines," said Dr Lihoreau, "While trap-lining is a common foraging strategy found in bees, birds and primates we still know very little about how animals attempt to optimise the routes they travel."

Research into optimising routes based on distance and the size of potential rewards is reminiscent of the well known Travelling Salesman problem in mathematics, which was first formulated in 1930, but remains one of the most intensively studied problems in optimisation.

"The Travelling Salesman must find the shortest route that allows him to visit all locations on his route," explained co-author Dr Nigel Raine, "Computers solve it by comparing the length of all possible routes and choosing the shortest. However, bees solve simple versions of it without computer assistance using a brain the size of grass seed."

The team set up a bee nest-box, marking each bumblebee with numbered tags to follow their behaviour when allowed to visit five artificial flowers which were arranged in a regular pentagon.

"When the flowers all contain the same amount of nectar bees learned to fly the shortest route to visit them all," said Dr Lihoreau. "However, by making one flower much more rewarding than the rest we forced the bees to decide between following the shortest route or visiting the most rewarding flower first."

In a feat of spatial judgement the bees decided that if visiting the high reward flower added only a small increase in travel distance, they switched to visiting it first. However, when visiting the high reward added a substantial increase in travel distance they did not visit it first.

The results revealed a trade-off between either prioritising visits to high reward flowers or flying the shortest possible route. Individual bees attempted to optimise both travel distance and nectar intake as they gained experience of the flowers.

"We have demonstrated that bumblebees make a clear trade-off between minimising travel distance and prioritising high rewards when considering routes with multiple locations," concluded co-author Professor Lars Chittka. "These results provide the first evidence that animals use a combined memory of both the location and profitability of locations when making complex routing decisions, giving us a new insight into the spatial strategies of trap-lining animals."

Functional Ecology

Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.

- Supplier Network

## Search menu

Electronics, bees solve 'travelling salesman problem'.

Researchers at Queen Mary and Royal Holloway, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order.

Bees are effectively solving what is widely known as the ’Travelling Salesman Problem’, and are the first animals that have been found to do this.

The ’Travelling Salesman’ must find the shortest route that allows him to visit all locations on his route. Computer programs solve the problem by comparing the length of all possible routes and choosing the shortest.

Prof Lars Chittka from the Queen Mary School of Biological and Chemical Sciences said: ’In nature, bees have to link hundreds of flowers in a way that minimises travel distance, and then reliably find their way home - not a trivial feat. Studying how bee brains solve such challenging tasks might allow us to identify the minimal neural circuitry required for complex problem solving.’

The team used artificial flowers to test whether bees would follow a route defined by the order in which they discovered the flowers or if they would find the shortest route. After exploring the location of the flowers, bees quickly learnt to fly the shortest route.

As well as enhancing scientists’ understanding of how bees move - pollinating crops and wild flowers - the research has other applications.

Human beings rely on traffic networks, computer networks and business supply chains; by gaining an understanding of how bees can solve their problem with such a tiny brain, researchers hope to be able to understand how they might be able to optimise the management of such networks without needing a lot of computer time.

Queen Mary researcher Dr Mathieu Lihoreau said: ’There is a common perception that smaller brains constrain animals to be simple reflex machines. But our work with bees shows advanced cognitive capacities with very limited neuron numbers.’

## Related Articles

## Honeybees can solve maths tests without using numbers

Problem solving.

## Bees fitted with sensors to monitor environment

Latest comments, comment: with great projects come great people - the story of our energy grid .

I think that the use of great here is nothing to do with being the best; it is about big projects with big companies creating big & expensive...

## Building projects are getting greener, latest NBS report finds

I am always interested to read about the progress being made in our industries. Does anyone know what impact the increase in the target of new homes...

I checked RIBA´s own definition of net zero for a building’s construction: ´when the amount of carbon emissions associated with a building´s product...

## Parameter tuning for combinatorial bees algorithm in travelling salesman problems

- Article contents
- Figures & tables
- Supplementary Data
- Peer Review
- Reprints and Permissions
- Cite Icon Cite
- Search Site

Natalia Hartono , Asrul Harun Ismail , Sultan Zeybek , Mario Caterino , Kaiwen Jiang , Murat Sahin; Parameter tuning for combinatorial bees algorithm in travelling salesman problems. AIP Conf. Proc. 8 August 2023; 2485 (1): 090005. https://doi.org/10.1063/5.0106177

Download citation file:

- Ris (Zotero)
- Reference Manager

Bees Algorithm is one of the most used nature-inspired algorithms. There are five parameters applied in the basic combinatorial version of Bees Algorithm: number of scout bees, number of elite bees, number of best bees, number of elite sites, and number of best sites. Parameter tuning is one of the critical and time-consuming steps in metaheuristic algorithms. This research is the first parameter tuning study for Combinatorial Bees Algorithm (BA) for solving the Travelling Salesman Problem (TSP). The experiments are designed using Fractional Factorial Design, and four steps, including parameter setting and statistical analysing, are carried out. The TSP problem's goal is to minimise the total path and find the lower number of the best cost. Comprehensive experiments have been done using varying TSPLIB datasets between 51 and 575 cities to minimise the total path and find the lower number of the best cost. Statistical results show that the best combinatorial BA parameters are the balanced scenario of local and global search.

## Citing articles via

Publish with us - request a quote.

## Sign up for alerts

- Online ISSN 1551-7616
- Print ISSN 0094-243X
- For Researchers
- For Librarians
- For Advertisers
- Our Publishing Partners
- Physics Today
- Conference Proceedings
- Special Topics

## pubs.aip.org

- Privacy Policy
- Terms of Use

## Connect with AIP Publishing

This feature is available to subscribers only.

Sign In or Create an Account

- Movies & TV
- Big on the Internet
- About Us & Contact

## Enough Already: Bees Haven’t Solved the Traveling Salesman Problem

This past week, we’ve been doing our best to ignore a perniciously misleading science story that’s been making its way through both blogs and mainstream media. According to these reports, bees have managed to solve an NP-hard problem in mathematics and computer science known as the Traveling Salesman Problem , which consists , when “given a collection of cities and the cost of travel between each pair of them,” of “find[ing] the cheapest [lowest-distance] way of visiting all of the cities and returning to your starting point.”

Many news stories about this, which stem from research done by scientists at Queen Mary, University of London and Royal Holloway, University of London, take the angle that this somehow proves that humble bumblebees have beaten computers and those egghead scientists that rely on them. “Bees’ tiny brains beat computers, study finds” proclaims The Guardian ‘s headline .

As a writer who regularly attempts to cover scientific developments in a way that’s easily understandable by a broad readership, I can understand the appeal of this strategy: It takes the forbidding topic of the Traveling Salesman Problem, to which volumes of arcane computer science literature have been devoted, and makes it into an emotionally resonant populist narrative. “See, bees can beat computers after all!” Read that headline and you don’t have to know or care what the Traveling Salesman Problem is or what the research consists of; you just know that the bees have bested machines. Sadly, this isn’t true.

First, consider the research, which was treated to the usual somewhat hyped-up university press release treatment. (See this excellent SMBC comic on the topic of how science reporting works.)

Professor Lars Chittka from Queen Mary’s School of Biological and Chemical Sciences said: “In nature, bees have to link hundreds of flowers in a way that minimises travel distance, and then reliably find their way home – not a trivial feat if you have a brain the size of a pinhead! Indeed such travelling salesmen problems keep supercomputers busy for days. Studying how bee brains solve such challenging tasks might allow us to identify the minimal neural circuitry required for complex problem solving.” The team used computer controlled artificial flowers to test whether bees would follow a route defined by the order in which they discovered the flowers or if they would find the shortest route. After exploring the location of the flowers, bees quickly learned to fly the shortest route. As well as enhancing our understanding of how bees move around the landscape pollinating crops and wild flowers, this research, which is due to be published in The American Naturalist this week, has other applications. Our lifestyle relies on networks such as traffic on the roads, information flow on the web and business supply chains. By understanding how bees can solve their problem with such a tiny brain we can improve our management of these everyday networks without needing lots of computer time.

OK. There’s a key difference, though, between what the bees did — finding the shortest distance between a set of flowers — and producing a general solution for the mathematical problem known as the Traveling Salesman Problem . To wit: The formal definition of the TSP is, “We are given a complete undirected graph G that has a nonnegative integer cost (weight) associated with each edge, and we must find a hamiltonian cycle (a tour that passes through all the vertices) of G with minimum cost.”

Even if we had exceptionally tireless bees map a route between a million flowers, would we be able to say that we found a general solution for this? How would we know that they had really found the shortest possible route between flowers and not merely an approximation of the shortest route? Why, we’d have to mathematically set up a Traveling Salesman problem and sic supercomputers on it for days. Even if the supercomputer’s solution and the bees’ solution wound up syncing up perfectly, how would we know that the bees’ solution would be optimal if it was a million and one flowers instead of a million? And so on. It should be clear that the practical application is not and cannot be a mathematical solution.

This isn’t to say that what the bees did isn’t impressive, especially given their limited hardware: And as the press release notes, there are likely to be practical applications to this research, perhaps comparable to the research done by the Japanese and British scientists who discovered that slime molds could uncannily approximate the Tokyo rail system. But very good, very fast approximations of the TSP have existed for a long time. Per Wikipedia , “Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution.” (The link goes into more detail.)

Why does any of this matter? Because it trivializes the hard work done by math and science professionals. Imagine being a researcher who’s dove deep into the arcana of the TSP only to hear from some relative that they read in the newspaper that bees solved it. You could try to explain that the newspaper was wrong, and why, but their eyes might glaze over. The stakes are higher than hurt feelings, though: Pop-science stories that wildly misreport basic facts in the headlines serve to push science literacy deeper into the mud. And yes, there are potentially millions of grant dollars hanging in the balance, which could wind up not going to researchers whose work could lead to promising, useful applications because the basics of what they’re all about are misunderstood by the populace and by government officials. Science can and should be popularized, but when media outlets misrepresent the facts in favor of soundbites and narratives, they’re doing more harm than good.

If you didn’t click it before, see that SMBC comic again, because it really nails it.

## Solving the Traveling Salesman Problem for Efficient Route Planning Through Swarm Intelligence Based Optimization

- Conference paper
- First Online: 21 August 2024
- Cite this conference paper

- Frederick Kin Hing Phoa ORCID: orcid.org/0000-0002-7417-8982 9 &
- Kin To Wong 10

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14789))

Included in the following conference series:

- International Conference on Swarm Intelligence

59 Accesses

The Traveling Salesman Problem (TSP) has long been a challenging optimization puzzle, prompting the development of various methodologies to seek efficient solutions. In this paper, we propose an improved method utilizing a Swarm Intelligence-based approach. Besides the traditional MIX and MOVE operations, our major contribution lies in the introduction of a new MIX operation specifically tailored for the TSP. This new operation offers an advantage over the traditional MIX operation by providing more comprehensive domain exploration. We compare our improved method to conventional optimization techniques, namely the Genetic Algorithm and Ant Colony Optimization. For a TSP involving 50 popular U.S. landmarks, our proposed method outperforms the others in terms of solution quality and computational time. Results are visualized on maps for reference.

This work is partially supported by the Academia Sinica grant number AS-IA-112-M03 and the National Science and Technology Council (Taiwan) grant number 111-2118-M-001-007-MY2.

This is a preview of subscription content, log in via an institution to check access.

## Access this chapter

Subscribe and save.

- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Available as EPUB and PDF
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Flood, M.M.: The traveling-salesman problem. Oper. Res. 4 (1), 61–75 (1956)

Article Google Scholar

Hoffman, K.L., Padberg, M., Rinaldi, G.: Traveling salesman problem. Encycl. Oper. Res. Manag. Sci. 1 , 1573–1578 (2013)

Google Scholar

Miller, C., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM 7 (4), 326–329 (1960)

Article MathSciNet Google Scholar

Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9 (1), 61–63 (1962)

Rosenkrantz, D.J., Stearns, R.E., Lewis, P.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6 (3), 563–581 (1977)

Reinelt, G.: TSPLIB - a traveling salesman problem library. ORSA J. Comput. 3 (4), 376–384 (1991)

Jiang, H., He, Z., Ye, G., Zhang, H.: Network intrusion detection based on PSO-XGBoost model. IEEE Access 8 , 58392–58401 (2020)

Phoa, F.K.H., Chen, R.B., Wang, W.C., Wong, W.K.: Optimizing two-level supersaturated designs using swarm intelligence techniques. Technometrics 58 (1), 43–49 (2016)

Phoa, F.K.H.: A Swarm Intelligence Based (SIB) method for optimization in designs of experiments. Nat. Comput. 16 (4), 597–605 (2017)

Lin, F.P.C., Phoa, F.K.H.: An efficient construction of confidence regions via swarm intelligence and its application in target localization. IEEE Access 6 , 8610–8618 (2017)

Lin, F.P.C., Phoa, F.K.H.: Runtime estimation and scheduling on parallel processing super-computers via instance-based learning and swarm intelligence. Int. J. Mach. Learn. Comput. 9 , 592–598 (2019)

Hsu, T.-C., Phoa, F.K.H.: A smart initialization on the swarm intelligence based method for efficient search of optimal minimum energy design. In: Tan, Y., Shi, Y., Tang, Q. (eds.) ICSI 2018. LNCS, vol. 10941, pp. 78–87. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93815-8_9

Chapter Google Scholar

Phoa, F.K.H., Liu, H.-P., Chen-Burger, Y.-H.J., Lin, S.-P.: Metaheuristic optimization on tensor-type solution via swarm intelligence and its application in the profit optimization in designing selling scheme. In: Tan, Y., Shi, Y. (eds.) ICSI 2021. LNCS, vol. 12689, pp. 72–82. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-78743-1_7

Liu, H.P., Phoa, F.K.H., Chen-Burger, Y.H., Lin, S.P.: An efficient swarm intelligence approach to the optimization on high-dimensional solutions with cross-dimensional constraints with applications in supply chain management. Front. Comput. Neurosci. 18 , 1283974 (2024)

Sun, W.H., Phoa, F.K.H.: Network community detection via an improved swarm intelligence approach. In: Tan, Y., Shi, Y., Niu, B. (eds.) Advances in Swarm Intelligence, vol. 13344, pp. 419–431. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-09677-8_35

Huang, E.C.H., Phoa, F.K.H.: A uniform placement of alters on spherical surface (U-PASS) for ego-centric networks with community structure and alter attributes. Adv. Complex Syst. 26 , 2340003 (2023)

Sutrisno, H., Phoa, F.K.H.: Anomalous subsequence detection in time series: mathematical formulation and a novel evolutionary algorithm based on clustering and swarm intelligence. Appl. Intell. 53 , 29585–29603 (2023)

Yen, P.-C., Phoa, F.K.H.: Traveling salesman problem via swarm intelligence. In: Tan, Y., Shi, Y. (eds.) ICSI 2021. LNCS, vol. 12689, pp. 106–115. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-78743-1_10

Olson, R.S.: Computing the optimal road trip across the U.S. (2015)

Download references

## Acknowledgement

Wong is supported by the master student scholarship provided by the Institute of Statistical Science, Academia Sinica. Part of this work was a version included in the master thesis of Mr. Kin To Wong.

## Author information

Authors and affiliations.

Institute of Statistical Science, Academia Sinica, Taipei, 115, Taiwan

Frederick Kin Hing Phoa

Data Science Degree Program, National Taiwan University, Taipei, 106, Taiwan

Kin To Wong

You can also search for this author in PubMed Google Scholar

## Corresponding author

Correspondence to Frederick Kin Hing Phoa .

## Editor information

Editors and affiliations.

Peking University, Beijing, China

Southern University of Science and Technology, Shenzhen, China

## Rights and permissions

Reprints and permissions

## Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

## About this paper

Cite this paper.

Phoa, F.K.H., Wong, K.T. (2024). Solving the Traveling Salesman Problem for Efficient Route Planning Through Swarm Intelligence Based Optimization. In: Tan, Y., Shi, Y. (eds) Advances in Swarm Intelligence. ICSI 2024. Lecture Notes in Computer Science, vol 14789. Springer, Singapore. https://doi.org/10.1007/978-981-97-7184-4_1

## Download citation

DOI : https://doi.org/10.1007/978-981-97-7184-4_1

Published : 21 August 2024

Publisher Name : Springer, Singapore

Print ISBN : 978-981-97-7183-7

Online ISBN : 978-981-97-7184-4

eBook Packages : Computer Science Computer Science (R0)

## Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

- Publish with us

Policies and ethics

- Find a journal
- Track your research

## IMAGES

## COMMENTS

Mathematicians call this the "traveling salesman problem," in which scientists try to calculate the shortest possible route given a theoretical arrangement of cities. Bumblebees, however, take the ...

While buzzing between flowers, bees can solve the maths dilemma called the travelling salesman problem by finding the shortest route that visits every blossom Close Advertisement

The better solution is to travel up one side of the UK and return down the other. Past research that looked only at the order in which small foragers like birds and bees arrive at each destination ...

And it turns out bees aren't the only animals that beat humans to solving the traveling salesman problem. Researchers at the University of New Hampshire have suggested that birds called Clark ...

Bees are effectively solving the 'Travelling Salesman Problem', and these are the first animals found to do this. The Travelling Salesman must find the shortest route that allows him to visit all ...

"The Travelling Salesman must find the shortest route that allows him to visit all locations on his route," explained co-author Dr Nigel Raine, "Computers solve it by comparing the length of all ...

How bumblebees tackle the traveling salesman problem. ScienceDaily . Retrieved August 16, 2024 from www.sciencedaily.com / releases / 2011 / 06 / 110628191339.htm

How bumblebees tackle the traveling salesman problem. June 29 2011. It is a mathematical puzzle which has vexed academics and travelling salesmen alike, but new research from Queen Mary ...

"The bees may be able to help us solve the travelling salesman problem," explained Dr Raine. This well-studied problem is based on the journey of a salesman who has to leave his home and visit a ...

Bee. Bumblebees foraging in flowers for nectar are like salesmen traveling between towns: Both seek the optimal route to minimize their travel costs. Mathematicians call this the "traveling salesman problem," in which scientists try to calculate the shortest possible route given a theoretical arrangement of cities.

Travelling Salesman Problem (TSP) is a list of cities that must visit all cities that start and end in the same city to find the minimum cost of time or distance. The Artificial Bee Colony (ABC ...

News Release 28-Jun-2011. How bumblebees tackle the traveling salesman problem. Peer-Reviewed Publication. Queen Mary University of London. image: An artificial flower is being visited by a ...

Bees solve 'Travelling Salesman Problem' News Researchers at Queen Mary and Royal Holloway, University of London have discovered that bees learn to fly the shortest possible route between flowers even if they discover the flowers in a different order. Bees are effectively solving what is widely known as the 'Travelling Salesman Problem ...

Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the U.S. government to solve the most elusive problem in computer-science history: P vs. NP. [ 77] Solutions to the problem are used by mathematician Robert A. Bosch in a subgenre called TSP art.

A quick introduction to the Traveling Salesman Problem, a classic problem in mathematics, operations research, and optimization.

This research is the first parameter tuning study for Combinatorial Bees Algorithm (BA) for solving the Travelling Salesman Problem (TSP). The experiments are designed using Fractional Factorial Design, and four steps, including parameter setting and statistical analysing, are carried out.

Using the concept of swap operation and swap sequence on the sequence of paths of a Traveling Salesman Problem(TSP) Artificial Bee Colony (ABC) algorithm is modified to solve multi-objective TSP. The fitness of a solution is determined using a rule following the dominance property of a multi-objective optimization problem. This fitness is used for the selection process of the onlooker bee ...

Artificial bee colony (ABC) is a quite popular optimization approach that has been used in many fields, with its not only standard form but also improved versions. ... Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics. Eneko Osaba, Xin-She Yang and Javier Del Ser. 1 Jan 2020.

Animals that travel between multiple destinations and return to a home base - like bees, birds, primates and humans - face a predicament known to mathematicians as the Travelling Salesman Problem. The challenge is to find a route that visits each destination while travelling the shortest possible distance.

Multiple travelling salesman problem is a combinatorial optimisation problem. • Bees Algorithm can present better solution using suitable local search operator. • Multiple traveling salesman problem is a special type of vehicle routing problems. • Bees algorithm performs explorative and exploitative search.

Bees Algorithm for Travelling Salesman Problems. It is the Bees Algorithm for TSP. Just run the ba_tsp.m file. You can find detailed information in the paper. Please refer to this paper if you use it in your work. Prepared in Matlab R2018a.

321 The bumblebee travelling salesman The problem is as follows, if you are given a list of cities and the distances between each pair of cities what is the ...

According to these reports, bees have managed to solve an NP-hard problem in mathematics and computer science known as the Traveling Salesman Problem, which consists, when "given a collection of ...

The simple version of the traveling salesman problem assumes that the points are in a blank and open canvas. In reality, there will be designated roads and obstacles. For example, when travelling through a city, you can't go through buildings and can't go off-road. How would one come about dealing with that?

The Traveling Salesman Problem (TSP) has long been a challenging optimization puzzle, prompting the development of various methodologies to seek efficient solutions. In this paper, we propose an improved method utilizing a Swarm Intelligence-based approach. Besides the traditional MIX and MOVE operations, our major contribution lies in the ...