A genetic-based pairwise trip planner recommender system

The rapid growth of internet users nowadays has impacted many countries in the world. This growth also occurred in Southeast Asia. In a most recent published annual report by Google, Temasek and Bain & Company on Southeast Asia’s (SEA) digital economy, titled e-Conomy SEA 2020 [1], it has been revealed that there is a massive increasing amount of internet users with 40 millions of new users in the year 2020 alone. The total of active internet users in SEA has reached 400 million in 2020. The outbreak of COVID-19 was considered to be the major reason for the digital market acceleration. The new users tried to use digital services to fullfil their need during the pandemic and the countries’ lockdown policy. This new phenomenon can have a good impact on the country’s economy as this new trend seems to be sticky. Of all those new digital internet users, it has been reported that the 94% of them intend to continue with the current service even after the pandemic situation is over. This is a good opportunity for businesses to keep improving their digital services.

A smart way to improve digital businesses has been proven by big web services companies like Youtube, Amazon, Netflix, Instagram and Facebook through the implementation of the recommender systems. They are a technology to suggest the most suitable contents to their users and match with the user preferences. During the last couple of decades, it was no doubt that the implementation of this technology was able to make them stand out significantly from their competitors. In addition to that, recommender systems are not only beneficial for the businesses, but also for the users [2]. For the users, they can minimize the cost of choosing the most suitable product in the context of internet shopping [3]. The example of costs that can be minimized is the cost of buying the wrong and unnecessary services from the wrong providers and costs of browsing. Another benefit for the users, as mentioned by Pathak et al. [4], is that the recommender systems can improve the decision making process and quality.

Currently, there are many various techniques used to build the recommender systems such as collaborative filtering, content-based filering and hybrid filtering [5]. The Collaborative Filtering (CF) technique is the most well-known and most commonly implemented in industries. It works by recommending the items based on the other users with similar taste. The second most commonly used is Content-Based (CB) filtering. This technique works by recommending similar items based on the particular user’s information without taking into consideration the other users. There is also a hybrid filtering that combines more than one technique of recommender system algorithms.

Most of the common approaches use single point feedback as the input to the system such as rating score with a linear scale of 1 to 5 (1 for the worst and 5 for the best). Based on these ratings, the system can calculate the recommendation score for each other item. although has been very well implemented, this single point feedback approach still has some drawbacks as mentioned in [6], such as the ratings are quite personal. Even though two users have similar preferences, it is very likely they will give different ratings to the same items. The other drawback is inconsistency. Users easily forget what ratings did they give for the items with similar properties in the past, so whenever they are asked to give a rating to the similar items, they can give a different score. A user may also feel difficult to give a slightly lower preference to some items because the rating scale does not normally have a half score. Therefore, there is another approach, called pairwise elicitation, which has been introduced by the researchers in this domain which shows pair choices to the users. The problem of eliciting preference by using the pairwise method itself still become an interest for the researchers, such as in [6‐13]. By using this approach, a user will be shown with a series of pair options and a preference can be expressed by selecting only one of the most preferred item between the two items (a pair) at a time. This technique can reduce the confusion of a rating number. In this paper, we want to focus on the use of the pairwise elicitation method to learn about user preferences. Some studies have also shown the combination of the pairwise elicitation with the use of CF as well as the CB filtering method in a recommender system, such as the one introduced by Liu et al. [7]. Our study will propose a different approach, i.e. using a genetic algorithm to optimize the searching strategy combined with pairwise preferences as the elicitation method.

Recommender systems are very popular nowadays due to the benefit being offered as explained earlier. In an e-commerce context, they can reduce the cost of searching and finding suitable items and direct the customers to buy products they mostly liked. Similar to that, in the tourism domain, the travellers often face the problem of spending too much time browsing the possible destinations before visiting a new place which can waste their time and energy. The searching action can be more complicated in the case of the limited budget and the trip duration which can be spent by the travellers. They need to choose the destinations wisely so that they still can spend the money and time in an effective way. One possible solution is by using Google Maps and choose the destination manually. We can see there is a gap between the existing solution and the research to address this problem. Often with the same difficulties as faced by the e-commerce users, the travel application users also feel overwhelmed with many choices available. The pairwise choices can simplify the options and generate a list of recommendation even before they provide ratings to the items. This is one of the advantages of our proposed approach.

In 2020, we proposed a system design of an e-tourism mobile application as a solution to promote tourism in Indonesia which has been worsened due to the COVID-19 pandemic situation, called SONIA (pariwiSata ONline IndonesiA or Indonesia Online Tourism) [14]. In this paper, we will discuss in more detail the recommender system module of the system. In summary, the contributions of this study are as follows: (1) publish a dataset of tourist attractions in Jakarta, Indonesia to be used for further study, (2) propose an approach of a trip recommender system based on a genetic algorithm with pairwise options, and (3) conduct a user evaluation study on the implemented pairwise trip recommender system with real-life data.

Genetic Algorithm (GA) has been around for decades, but the use of this optimization algorithm in recommender system is still limited. GA has been used in many domains with optimization and search problems. In general, a recommendation problem can also be considered as a searching problem for the best items. All the recommender system algorithms aim to give as least error as possible. GA is believed to be an effective algorithm that can provide a near-optimal solution in a reasonable time. Henceforth, there is no reason why GA is not suitable for solving a recommendation problem.

In the Recommender System (RS) domain, GA has been utilized for clustering, such as the study performed by Kim and Ahn in 2008 [15], Zhang and Chan in 2006 [16], and Mohammadpour et al. in 2019 [17]. The researchers in this area also used GA to increase the accuracy of recommendation proposal generated by classic RS algorithms, such as collaborative filtering and content-based filtering. GA works in improving the population of recommendation solutions in each iteration. A study by Kilani et al. [18] proposed the GA-based matrix factorization hybrid approach of RS. They use the approach to predict items for the active user. This is an improvement work of a study by Navgaran et al. [19]. They show that their approach can perform faster than the previous work with better recall and precision values in some datasets. Recently, Alhijawi and Kilani in 2020 [20] proposed a novel GA-based collaborative filtering that aims to select the best items which meet the active user’s preferences based on multi-filtering criteria. Another recent study by Gasmi et al. in 2021 [21] also proposed a user-based collaborative filtering combined with the GA based meta-heuristic. A study by Xiao [22] proposed a combination of item-based collaborative filtering with GA which is called itemCFGA. This study also proposed a novel similarity function that uses the average rating of each user. For a hybrid RS model, GA is used in [23] and  [24]. Another related work in this area has been introduced in [25] and [26].

As our first contribution, we share the dataset we have collected and used in this study. The dataset was built by scraping information from many sources in the period between May–June 2020. The data has been checked again for the updated one by the time of submitting this manuscript on April 2021. The dataset focuses on the famous tourist destinations in Jakarta, Indonesia. It was the time when the COVID-19 outbreak was still affecting the country. Due to the lockdown policy, the data of some entrance fees, opening and closing hours, may be different from the regular condition. We will keep updating the data once the condition is already back to normal. The dataset consists of 201 POI entries, with 10 columns. Each of the dataset columns is described in Table 1. We also published the distance matrix together with duration matrix data which were collected by using Google Maps API. The sample of the distance matrix database is shown in Table 2 and the duration matrix is shown in Table 3.

We implemented the trip recommender system and evaluate the system by using both offline and online experiment. For the offline experiment, we tried out the algorithm with default values as the inputs several times. The algorithm was executed on a machine with 8GB RAM with a 2.9 GHz Intel Core i5 processor. We show the report of the last 10 experiments average fitness value and average time execution in Table 5. The result shows that the algorithm average fitness is 0.2773 and the time execution is 0.0146 seconds. We also evaluate the result manually and all the list produced by the algorithm have good quality.

We evaluated the system by using an online experiment. We used the standard evaluation framework for the recommender systems, known as ResQue (Recommender systems’ Quality of user experience) [28]. The framework aims to measure the recommended items quality, the system’s usability, usefulness, interface and interaction qualities, users’ satisfaction with the systems, and the influence of these qualities on users’ behavioral intentions. The questionnaire is shown in Figs. 13 and 14 in the Appendix. We also collected the demography of the participants, including age, gender, how often they go travelling, and how long they have been living in Jakarta. There are a total of 17 questions in the survey.

In this paper, we have shown the design implementation of a trip planner recommender system that employs the genetic algorithm as the search method combined with pairwise elicitation preferences. We have proposed the approach which has successfully implemented as a working web-based application with three-layer architecture. We have also published an attraction dataset that can be used for further study. The evaluation of the system shows a very satisfying result, although some improvement may still need to be performed, such as designing an adequate and interactive layout. Feedback from the user was also collected in the form of a survey which can be used for future development. We plan to improve the algorithm by weighting the places with a higher rating more than the ones with a lower rating. We also need to work on the interface design to make sure the user understand how to use the pairwise feature. This approach can also be expanded for other cities with a more complete place labelling and more accurate data of travel cost. When a more complete dataset has been obtained, then the performance of the proposed approach can be evaluated on a bigger dataset.