Prey Predator Algorithm for Travelling Salesman Problem: Application on the Ethiopian Tourism Sites

Prey Predator Algorithm for Travelling Salesman Problem: Application on the Ethiopian Tourism Sites

Surafel Luleseged Tilahun (University of Zululand, South Africa), Natnael Nigussie Goshu (Addis Ababa Science and Technology University, Ethiopia) and Jean Medard T. Ngnotchouye (University of KwaZulu-Natal, South Africa)
DOI: 10.4018/978-1-5225-1054-3.ch019


Visiting most, if not all, tourist destination of a country while visiting a country is an ideal plan of a tourist. In most cases if the tour is not carefully planned, it will be costly and time taking to travel between tourist destinations of a country. If we consider Ethiopia, a country which has been named as best tourism destination for 2015 by the European Council on Tourism and Trade (ECTT); there are many tourist destinations all over the country. The problem of determining the optimum route to visit all the tourist sites with minimum traveling time can be formulated as a travel salesman problem. In this study 17 of the famous tourist destination of Ethiopia will be selected and a travel salesman model will be formulated. Due to the NP hardness of the travel salesman problem, metaheuristic based algorithms are found to be more effective. Hence, a recently introduced swarm based metaheuristic algorithm, called prey predator algorithm will be used to deal with the formulated problem. The simulation result suggests that the best route to visit the selected destination is Addis Ababa ? Sof Omar Caves ? Bale Mountain National Park ? Abijiata-Shalla Lakes ? Netchisar National Park ? Mago National Park ? Omo National Park ? Gambella National Park ? Bahir Dar ? Lalibela ? Gonder ? Semien Mountain National Park ? Axum ? Ertale ? Yangudi Rassa National Park ? Awash National Park ? Harar ? Addis Ababa. It should be noted in some of the sites there is no direct route and hence a route through other cities is used and hence it should be recomputed in the future when a direct route between these tourist destinations is constructed.
Chapter Preview


Tourism can be recognized as long as people have traveled. Food, water, safety or acquisition of resources (trade) was the early travel motivations. But the idea of travel for pleasure or exploration soon emerged. Travel has always been depending on technology, to provide the means or mode of travel. The earliest travelers walked or rode domesticated animals. The invention of the wheel and the sail provided new modes of transportation. Each improvement in technology increased individuals’ opportunities to travel. As roads were improved and governments stabilized, interest in travel increased for education, sightseeing, and religious purposes. One of the earliest travel guides was written by Pausanias, a Greek, which was a 10 volume guide to Greece, for Roman tourists in 170 A.D (Satta, 2005). However, there is no consensus concerning the definition of tourism it varies source by source, person by person.

The first definition of tourism was made by Guyer Feuler in 1905 (Bogahavatta, 2013). He defined Tourism as:

A phenomenon unique to modern time which is dependent on the people’s increasing need for a change and relaxing, the wish of recognizing the beauties of nature and art and the belief that nature gives happiness to human beings and which helps nations and communities’ approaching to each other thanks to the developments in commerce and industry and the communication and transportation tools’ becoming excellent.

In 1976, the Tourism Society of England defined Tourism as “Tourism is the temporary, short-term movement of people to destination outside the places where they normally live and work and their activities during the stay at each destination. It includes movements for all purposes.” (Bogahavatta, 2013). Mathieson and Wall (1982) created a good working definition of tourism as “the temporary movement of people to destinations outside their normal places of work and residence, the activities undertaken during their stay in those destinations, and the facilities created to cater to their needs.” According to Macintosh and Goeldner (1986) tourism is “the sum of the phenomena and relationships arising from the interaction of tourists, business suppliers, host governments and host communities in the process of attracting and hosting these tourists and other visitors.” But when it comes to explain it with the basic terms, we can sum it up as follows; Tourism is a collection of activities, services and industries which deliver a travel experience comprising

  • Transportation,

  • Accommodation,

  • Eating and drinking establishments,

  • Retail shops,

  • Entertainment businesses and other hospitality services provided for individuals or groups traveling away from home not more than one consecutive year.

According to The World Tourism Organization (WTO) 2014 report, tourism is currently the world largest industry with annual revenues of over $1.5 trillion dollars (World Tourism Organization (UNWTO), 2016).

Tourism consists of certain components (dimensions), four of which may be considered as basic. These four basic component of tourism are;

  • 1.

    Attractions: Usually focus on natural resources, culture, ethnicity or entertainment.

  • 2.

    Facilities: When tourists arrive at attractions place they require facilities to provide services like lodging, food & beverage, support services, and communication infrastructure.

  • 3.

    Hospitality: The community’s attitude which permeates every tourism location that makes the tourist feels welcome and safe. It is the result of the interaction between the tourist and the local population.

  • 4.


Key Terms in this Chapter

Algorithm: (Pronounced AL-go-rith-um) Is a procedure or formula for solving a problem. The word derives from the name of the mathematician, Mohammed ibn-Musa al-Khwarizmi, who was part of the royal court in Baghdad and who lived from about 780 to 850.

Lucy: The common name of AL 288-1, several hundred pieces of bone fossils representing 40 percent of the skeleton of a female of the hominin species Australopithecus afarensis . In Ethiopia, the assembly is also known as Dinkinesh, which means “you are marvelous” in the Amharic language.

Metaheuristic: A higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem, especially with incomplete or imperfect information or limited computation capacity.

Ark of the Covenant: Also known as the Ark of the Testimony, was a wooden chest clad with gold containing the two stone tablets of the Ten Commandments as well as, according to various texts within the Hebrew Bible, Aaron’s rod and a pot of manna.

Rift Valley: A linear-shaped lowland between several highlands or mountain ranges created by the action of a geologic rift or fault.

Lava Lakes: Large volumes of molten lava, usually basaltic, contained in a volcanic vent, crater, or broad depression.

NP-Hardness: (Non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, “at least as hard as the hardest problems in NP”.

UNESCO World Heritage Site: A place (such as a forest, mountain, lake, island, desert, monument, building, complex, or city) that is listed by the United Nations Educational, Scientific and Cultural Organization (UNESCO) as of special cultural or physical significance.

Complete Chapter List

Search this Book: