travelling salesman bees

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 15 December 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

Antidote to deadly pesticides boosts bee survival

Ants change the way they build nests to stop diseases spreading

Subscriber-only

Mathematics

The mathematical theory that made the internet possible.

Wild bees have found a surprising place to nest in cities

Popular articles.

Trending New Scientist articles

• 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.  

• 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.

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

• Powerful Effect of Repetition On Beliefs
• Rapid Loss of Antarctic Ice After 2100 Likely
• New Rules? Redefining 'Sustainable Fishing'
• Origins of Horseback Riding
• Food Fussiness Is a Largely Genetic Trait
• Complex Dance of Our Beliefs
• Global Action On Microplastics?
• Lake Ice Quality Degrading as Planet Warms
• Lava from Hotspots from Worldwide Reservoir
• Slap Fighting: Risk to Neurological Health

Trending Topics

Strange & offbeat.

• 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.

Parameter tuning for combinatorial bees algorithm in travelling salesman problems

[email protected]

[email protected]

[email protected]

[email protected]

[email protected]

• 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

An Efficient Meta-Heuristic Methods for Travelling Salesman Problem

• Conference paper
• First Online: 01 March 2023
• Cite this conference paper

• Mohamed Abid 9 ,
• Said El Kafhali   ORCID: orcid.org/0000-0001-9282-5154 9 ,
• Abdellah Amzil 9 &
• Mohamed Hanini 9  

Part of the book series: Lecture Notes on Data Engineering and Communications Technologies ((LNDECT,volume 164))

Included in the following conference series:

• The International Conference on Artificial Intelligence and Computer Vision

660 Accesses

3 Citations

Over the past several decades, researchers have increasingly attempted to create an autonomous problem solver that might address problems in computer science, mathematics, economics, and engineering. When faced with a problem, people often go to nature for inspiration. Intelligent multi-agent systems have been inspired by the collective behavior of social insects like ants and bees, as well as other animals, such as bird flocking and fish schooling. Solutions to NP-hard issues, including the Traveling Salesman Problem (TSP), may be found through the application of algorithms such as Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Artificial Bee Colony (ABC), Genetic Algorithm (GA), Simulated Annealing (SA), and Tabu Search (TS). The TSP is a classic example of an NP-hard problem that has received a great deal of attention from researchers. Numerous mathematical models, software implementations, and methodological proposals have been made for TSP. TSP has been the subject of several exact and metaheuristic methods. In this research, we applied six effective metaheuristic algorithms to solve seven benchmark TSPs, including Bays29, att48, eil51, berlin52, st70, pr76 and kroa100. Using the identical settings for each simulation, we assessed the empirical data that existed in a certain arrangement. We illustrate the performance of optimal and metaheuristic solutions for TSP. ABC is shown to be near-optimal with only 1.5% degradation.

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

Similar content being viewed by others

Application of Metaheuristic Algorithms and Their Combinations to Travelling Salesman Problem

An Investigation of Hybrid Tabu Search for the Traveling Salesman Problem

Solving the Traveling Salesman Problem Using Ant Colony Metaheuristic, A Review

Del Ser, J., et al.: Bio-inspired computation: Where we stand and what’s next. Swarm Evolut. Comput. 48 , 220–250 (2019)

Google Scholar  

Huerta, I.I., Neira, D.A., Ortega, D.A., Varas, V., Godoy, J., Asín-Achá, R.: Improving the state-of-the-art in the traveling salesman problem: an anytime automatic algorithm selection. Expert Syst. Appl. 187 , 115948 (2022)

El Kafhali, S., El Mir, I., Salah, K., Hanini, M.: Dynamic scalability model for containerized cloud services. Arab. J. Sci. Eng. 45 (12), 10693–10708 (2020)

Hanini, M., El Kafhali, S.: Cloud computing performance evaluation under dynamic resource utilization and traffic control. In: Proceedings of the 2nd international Conference on Big Data, Cloud and Applications, pp. 1–6 (2017)

El Kafhali, S., Hanini, M.: stochastic modeling and analysis of feedback control on the QoS VoIP Traffic in a single cell IEEE 802.16 e networks. IAENG Int. J. Comput. Sci. 44 (1), 19–28 (2017)

Roy, A., Manna, A., Kim, J., Moon, I.: IoT-based smart bin allocation and vehicle routing in solid waste management: a case study in South Korea. Comput. Indus. Eng. 171 , 108457 (2022)

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

Skinderowicz, R.: Improving ant colony optimization efficiency for solving large TSP instances. Appl. Soft Comput. 120 , 108653 (2022)

Jiang, H.: Artificial bee colony algorithm for traveling salesman problem. In: 2015 4th International Conference on Mechatronics, Materials, Chemistry and Computer Engineering, pp. 468–472. Atlantis Press (2015)

Zhang, J.: An improved genetic algorithm with 2-Opt local search for the traveling salesman problem. In: Sugumaran, V., Xu, Z., Zhou, H. (eds.) MMIA 2021. AISC, vol. 1385, pp. 404–409. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-74814-2_57

Chapter   Google Scholar  

Demiral, M.F., Işik, A.H.: Simulated annealing algorithm for a medium-sized TSP data. In: Hemanth, D.J., Kose, U. (eds.) ICAIAME 2019. LNDECT, vol. 43, pp. 457–465. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-36178-5_35

Khan, M.U.R., Asadujjaman, M.: A tabu search approximation for finding the shortest distance using traveling salesman problem. IOSR J. Math. 12 (05), 80–84 (2016)

Jabor, F.K., Omran, G.A., Mhana, A., Gheni, H.M.: Optimization of particle swarms for travelling salesman problem. In: 2022 International Congress on Human-Computer Interaction, Optimization and Robotic Applications (HORA), pp. 1–6. IEEE (2022)

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

Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B (Cybernetics) 26 (1), 29–41 (1996)

Tereshko, V., Loengarov, A.: Collective decision making in honey-bee foraging dynamics. Comput. Inf. Syst. 9 (3), 1 (2005)

Tsujimura, Y., Gen, M.: Entropy-based genetic algorithm for solving TSP. In: 1998 Second International Conference. Knowledge-Based Intelligent Electronic Systems. Proceedings KES1998 (Cat. No. 98EX111), Vol. 2, pp. 285–290. IEEE (1998)

Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chemi. Phys. 21 (6), 1087–1092 (1953)

Edelkamp, S., Schrödl, S.: Selective search. Heuristic Search. Morgan Kaufmann, San Francisco, pp. 633–669 (2012)

Poli, R., Kennedy, J., Blackwell, T.: Particle swarm optimization. Swarm Intell. 1 (1), 33–57 (2007)

Download references

Author information

Authors and affiliations.

Faculty of Sciences and Techniques, Computer, Networks, Modeling, and Mobility Laboratory (IR2M), Hassan First University of Settat, 26000, Settat, Morocco

Mohamed Abid, Said El Kafhali, Abdellah Amzil & Mohamed Hanini

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Said El Kafhali .

Editor information

Editors and affiliations.

Faculty of Computer and AI, Cairo University, Giza, Egypt

Aboul Ella Hassanien

Faculty of Sciences and Techniques, Hassan 1st University, Settat, Morocco

Abdelkrim Haqiq

College of Computer and Information Sciences, Prince Sultan University, Riyadh, Saudi Arabia

Ahmad Taher Azar

Department of Computer Science, University of South Dakota, Vermillion, SD, USA

Vardhaman College of Engineering, Hyderabad, Telangana, India

M. A. Jabbar

Department of Electronics and Computer Science, Koszalin University of Technology, Koszalin, Poland

Adam Słowik

Department of Computer Science, Avinashilingam University for Women, Coimbatore, Tamil Nadu, India

Parthasarathy Subashini

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Abid, M., El Kafhali, S., Amzil, A., Hanini, M. (2023). An Efficient Meta-Heuristic Methods for Travelling Salesman Problem. In: Hassanien, A.E., et al. The 3rd International Conference on Artificial Intelligence and Computer Vision (AICV2023), March 5–7, 2023. AICV 2023. Lecture Notes on Data Engineering and Communications Technologies, vol 164. Springer, Cham. https://doi.org/10.1007/978-3-031-27762-7_46

Download citation

DOI : https://doi.org/10.1007/978-3-031-27762-7_46

Published : 01 March 2023

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-27761-0

Online ISBN : 978-3-031-27762-7

eBook Packages : Intelligent Technologies and Robotics Intelligent Technologies and Robotics (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

• 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.

Reinforcement Learning for Solving Colored Traveling Salesman Problems: An Entropy-Insensitive Attention Approach

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.