Research On The Utility Of An Advanced ACA In
Context-Aware Tour Planning System
Fudan University, Shanghai, 200433, PRC
Abstract. Nowadays, tourism has become an irreplaceable part of our daily life. Context-aware service, which acquires contextual information of user and environment, provides high level of customization in mobile commerce, and context-aware tour guide system brings convenience to travellers around the world. In this paper, we improved the performance of Ant Colony Algorithm (ACA) by focusing on user preferences. Then, in order to research on its utility performance, we implemented the prototype system following information system design theories of context-aware system, and finally validated the improvement by user testing and survey, to demonstrate the significant theoretical and practical value of our research.
Keywords: Ant Colony Algorithm; Context-aware Service; Tour Planning; Information System Design
1. Introduction
A. Research background
The mobile service based on context awareness is a new application research area, and the competitive advantage of tourism has gradually changed from resource to the multi-dimensional combination of resource, information and service. The kind of mobile commerce service which is based on context awareness technology is called “context awareness service” [1] in many literatures, and how to provide proper context awareness service to CAIS (context-aware information system) users is a popular research subject.
Ant Colony Algorithm (ACA) is a representative of heuristic algorithm inspired from the behaviors of ants. When chasing for food in an open area, ants are able to find the optimized tour from home to the destination. Such method was used in optimization algorithms and has been serving an important part in solving operation research problems and for practical use, including tour-planning problems [3].
The research of improvement and utility of ACA in tour planning has become a hot topic in the field, which attracted much attention of scholars all over the world. They established impressing achievements, and the solution to tour planning problem is continuously updating, providing increasing convenience to people on their trips.
B. The value of our research
Our research focuses on improvement of the Ant Colony Algorithm under the background of context awareness service, taking context-aware tour planning as the real situation context. The fundamental idea is to take into account the context information, such as weather condition, customer flow etc. , as part of the weighting factors of the ants' information factor when searching for the shortest tour, thus improving the performance in customer satisfaction of original ACA in solving the tour planning problem.
1) Compared with existing researches in improving the algorithm performance of ACA, our innovation focuses on providing better customization rather than higher efficiency or optimization results, in aim of chasing a tighter combination with practical needs and utility value.
2) The improved ACA adopts context information directly into the calculation of the algorithm's core program instead of simply refer to the data as an outer part of the function. This guaranteed the full use of contextual information of our algorithm, as well as a better performance in user customization.
3) Following the existing information system design theory, we designed a set of proper functions accordingly with our improved algorithm to strengthen its advantages in user interaction, user preference analysis, etc. Therefore, our improvement can be evaluated and validated by user testing and survey with specially designed prototype system.
In this research, we bring up an advanced ACA with better user customization performance to solve the problem of context-aware tour planning. We hope this paper can offer a trivial but effective advanced ACA, as well as bringing more attention to the study of user experience improvement, to provide a new train of thoughts for the following researches.
2. Literature Review
A. Ant Colony Algorithm
Ant Colony Algorithm (ACA) was firstly derived from the ant colony functioning, and the "Ant System" was inspired to be a potential basic algorithm solution to many optimization problems (Colorni & al. 1991) [3]. The algorithm was then applied to various kinds of combinatorial problems, including the tour planning problem such as Travelling Salesman Problem (TSP), the Vehicle Routing Problem (VRP), etc. [4]
In ACA, the ants of a specific region randomly walk among spots to find a better route for chasing food. While walking, they send out pheromone, called 'information factor', along the route that can attract all the other ants of the colony to come close.
The earliest use of ACA in tour planning can be described as follows:
Let n represents the number of all spots, is the total number of the ant colony, (i,j = 1,2,…, ) denotes the distance between spot i and spot j；let be the t generation of information factor between spot i and spot j. At the beginning the density of information factor on every route is a constant value . We also have (k = 1,2,…, ), which is the set of all spots that ant k has visited during its walk up till now; and means at time t, the state transit probability for ant k to transit from spot i to spot j. Then we have: [6,7]
. (1)
The rule of ants’ choosing to transit from one spot to another obeys the fake random rule. Moreover, whenever an ant chooses its next spot, the algorithm generates a random value within [0, 1], and the system decides its transit direction according to the following equation:
. (2)
After time m, the ant finishes one round of travelling among all spots, the system updates the information factors on each route; will gradually decrease by time, and its decreasing rate is defined as . Finally, ants will find the shortest route from home to food according to the density of information factor.
Until now, researches have brought up many improvements on ACA in solving tour planning problem. These includes the Max-Min Ant System Algorithm [8], or using time-varied function Q(t) to replace the information factor density p [9], and also the definition of ‘intelligent ants’ in literature [10]. All these improvements focus on higher computing speed or better overall optimizing ability [7].
However, improvements for utility purpose and better customer experience are still in an early stage without consensus methods. One of the key problems that is puzzling researchers of context-aware tour planning information system design is how to find a best way of utilizing context information in the functioning design, in order to provide best user experience in customization and recommendation. Therefore, in this paper we come up with a new way of combining context information into the core computing part of the advanced ACA to get better customized results.
B. Context-awareness service
Anind K.Dey and Gregory D. Abowd [2] gave a formal definition of “context”: Context is any information that can be used to characterize the situation of an entity. Any entity is a person, place, or object that is considered relevant to the interaction between a user and an application, including the user and applications themselves.
Existing researches of context-aware systems are primarily confined to the definition and acquirement of contextual information, or bring forth the structure of context awareness services, experimenting on prototype systems or comparatively simple context-aware service [1,5]. Obviously, these researches are dispersive, concerning only one small aspect of context-aware service or confined to one specific simple application. Besides, when combined with tourism, context awareness service can give birth to a new field of research. Tour guide system is one of the earliest applications of context-aware service. However, these practices only involved simple contextual information, and almost all the recent prototype systems abstract context information from the context and directly present to the user in their designed functions. This may not offer the best effect in user experience and customization.
3. Advanced ACA and function design
A. Our improvement on ACA utilization
Generally speaking, existing researches on ACA, context awareness services and tour route planning have provided fundamental value of reference for later researches. However, most of the improvement of ACA mentioned above focused on higher efficiency or better optimization results, but few was done on finding a more feasible way of ACA utilization in real functioning systems. We adopt context information into the calculation of the algorithm's core program in our advanced ACA instead of simply refer to the data as an outer part of the function.
Moreover, previous researches into ACA had done adjustments on the information factors, but no one has directly put context information value into the calculation and optimizing process. In our advanced ACA, context information, such as weather and customer flow, are given corresponding values and standardized to be a weighing factor of the information system sent out by the ants. This guaranteed the full use of contextual information of our algorithm, as well as a better performance in user customization.
Following the existing information system design theory, we designed a set of proper functions accordingly with our improved algorithm to strengthen its advantages in user interaction, user preference analysis, etc. in order to evaluate and validate the algorithm utility by user testing and survey on specially designed prototype system.
B. Advanced ACA
In tour route planning problem, how to make full use of the context information is of crucial importance to the customization performance of the system. In order to emphasize the influence of context information to the optimizing results, we quantized the context information such as weather, customer flow, gave them a standardized value within [1, 2], and multiplied as an weighing factor in the ant colony’s information factor updating process.
The pseudo code of the advanced ant colony algorithm is as follows:
GetUserInfo(); //get user information
GetSpotsInfo(); //get user preference of the sites
{ Input UserKeySpots(Array_rec_spots[j]); //ask the user to set key points
Check
if(tmp > N_CITY_COUNT || tmp < 1) && if (Available);
GetTotalNum(int);
}
RecommendSpot() //system recommending process
{ GetUserInfo();
for (int a = 0; a < total_spot_num; a++) {
spots[a] = rec_spots[a]; }// recommendation complete
}
//Main function
InitializeCities;
For(int i>k；i<=n；i++) //for all the sites
{ For(int j=1; j<=m; j++) //the number of ants is m
Calc(prob(i,j))
}
GetOptimizedPath(p);
ContextInfo(dbTEMP); //weighting of weather and customer flow
Refresh(); //update the information factor
OutputPath(p); //Output the optimized route
//Multi-choice output
For(bset tour spots)
{ Calc( cost(p), customerflow(p), recommend(p));
Output(Array[cost,p],Array[rush,p],Array[prep,p]);
}
Check(repeat); //whether to choose the spots again
In the improved algorithm, we weighed the information factor by context information as follows:
dbTemp = pow(dbTemp,0.5) * weather[final_spots[j]] * cust_flow_index[final_spots[j]] ;
This demonstrates the adjustment of adding an weighing factor to the Ant System. This may not offer higher efficiency or optimizing ability to the algorithm, but for the purpose of reaching an advanced customized context-aware service level and providing better user experiences.
C. User satisfaction function
On valuing the user satisfaction on his experience with the advanced ACA prototype system, we referred to some research results from existing literatures which focused on motivation, satisfaction and destination loyalty. Harrison (2004) [11] and Huo and Miller (2007) [12] thought the satisfaction came from spots, service and experience, which were positively correlated to satisfaction. They also took demographical factors (age, gender, education background and so on) as parameters to test and verify the correlation.
In our research, we suppose that the satisfaction comes from the whole travel; and under a given budget and time constraint, the travelling process can be simplified as sequential visits to several separated spots. Therefore, the total satisfaction value equals to the sum of each spot’s satisfaction. Here we referred to the satisfaction model of Huo and Miller (2007), which has been verified and widely recognized.
The expectation of travel can be described as:
. (3)
Here “i” denotes a specific tourist spot, “f” means the evaluation on facilities, “s” means the evaluation on services, and “e” means the evaluation on past experience. The expectation is the sum of these three values multiplied by weights, including “ ” representing the preference of visitors (effected by age, gender, profession and so on), subjective weight, and objective weights , and . This theory has already been validated and we will use it here as our standard to measure the performance of our advanced ACA [12].
4. System testing and analysis
We implemented the prototype system according to the above designed functions, in order to see whether the advanced ACA can indeed perform better in the aspect of user experience and preference when utilized in such context-aware tour planning system. Functions for our prototype tour planning include user information input (age, number of visitors, etc.), user setting key sites (that are sure to be visited), system recommending other sites according to users’ preference, context information abstracting, route optimizing, and multi-choice result presentation.
A. Testing: Some Computational Results
In this section of our research, we used a real case of the Shanghai Zoo as a testing background; this would not only serve better in user satisfaction measurement, but also attach higher practical value to our advanced ACA and system function design.
In order to verify the efficiency and effectiveness of the advanced ACA, the following two tests (Test 1, Test 2) are designed to gather information about its running condition under a specific scenario. They both focus directly on the algorithm performance itself to get a reflection of the scientific rigorousness of our improvement.
Test 1: Efficiency. We used a set of data to test whether the advanced algorithm is able to get the optimized results in an acceptable time period, and whether it can calculate the best route in an efficient and convenient method.
Tab.1 Testing Set and Results of Test 1 for Efficiency
| Testing Set 1 |
| User Input： |
| Number of users | 2 |
| User ages | 24,25 |
| Key point sites | 1,4,7 |
| Total NO. of sites | 7 |
| System Output |
| Recommend sites | 2,3,5,8 |
| All sites to visit | 1,2,3,4,5,7,8 |
| Times of Iteration | Sys Run Time (ms) | Optimized route | Total weighed value of the route |
| 1 | 0 | Start -> 1 -> 4 -> 7 -> 2 -> 3 -> 5 -> 8 -> End | 95 |
| 2 | 20 | Start -> 8 -> 1 -> 4 -> 7 -> 2 -> 3 -> 5 -> End | 89 |
| 3 | 37 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 4 | 57 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 5 | 77 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 6 | 97 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 7 | 117 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 8 | 140 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 9 | 160 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| 10 | 182 | Start -> 2 -> 1 -> 4 -> 7 -> 3 -> 5 -> 8 -> End | 88 |
| Testing Set 2 |
| User Input： |
| Number of users | 4 |
| User ages | 13,15,37,39 |
| Key point sites | 3,6,9,12,13 |
| Total NO. of sites | 8 |
| System Output |
| Recommend sites | 1,4,5 |
| All sites to visit | 1,3,4,5,6,9,12,13 |
| Times of Iteration | Sys Run Time (ms) | Optimized route | Total weighed value of the route |
| 1 | 0 | Start -> 4 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 5 -> End | 124 |
| 2 | 22 | Start -> 4 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 5 -> End | 124 |
| 3 | 42 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 4 | 52 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 5 | 62 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 6 | 85 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 7 | 97 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 8 | 112 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 9 | 125 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
| 10 | 142 | Start -> 5 -> 3 -> 6 -> 9 -> 12 -> 13 -> 1 -> 4 -> End | 120 |
Analysis: In test 1, each test group was traced for 10 steps, and the program was all the time able to get the optimized results under the constraints. The running times of all tests are around 100 ms quantitative level. At the same time, with a complexity of 15 spots involved, the program managed to provide a shortest tour plan in 10 times of iteration. In the 0.182s solving time of test 1, the program reached the final result on the third iteration at 0.037s. Test 2 took 0.142s while calculating, and the optimized result appeared at 0.042s during the third time of iteration. Therefore, for tour planning problems with proper mathematical scope, the advanced ACA system is effective and efficient.
Test 2: Effectiveness. The system was tested under several specific scenarios to see whether it can offer rational results that satisfy the users’ preferences in those cases. In such concrete situation, the algorithm must have the ability to analysis and process the users’ customized information in order to include proper sites in the recommended tour.
Tab.2 Testing Scenario and Results of Test 2 for Effectiveness
| Scenario 2.1 | User Input： | System Output: |
| Number of Visitors | 2 | Recommend Sites | 9,5,15,12 |
| Visitors’ Ages | 10,11 | All sites to be visited | 9,5,15,12, 1,2,7,10,14 |
| Key Point Sites | 1,2,7,10,14 | Sites Info：Panda, Kids’ Zoo, Glonde Park for kids, Marine Mammals’ Show, Science Edu Pavillion, Grand Show Square, Pets’ World, Lion Mountain, Mammals’ Povillion |
| Number of Sites | 9 |
| Scenario 2.2 | User Input： | System Output: |
| Number of Visitors | 4 | Recommend Sites | 6,3,11,8,4 |
| Visitors’ Ages | 25,26,27,28 | All sites to be visited | 6,3,11,8,4,2,10,13 |
| Key Point Sites | 2,10,13 | Sites Info：Swan Lake, Peacock Park, Horse-Riding, Beasts’ Show, Interactive Birds Garden, Grand Show Square, Elephant’s Park |
| Number of Sites | 8 |
Analysis: In test 2, according to the characteristics of each group in the designed scenario, the system was able to analyze their preference under such age level and group scope, and recommended proper sites respectively. From this we can tell that the advanced algorithm has the ability to catch and process the user’s preference information. Therefore, for tour planning problems with proper mathematical scope, the designed functions are all reasonable and the advanced ACA system is effective in processing the user’s customized information to provide rational results.
Apart from testing of the system itself, we also considered the test of user satisfaction improvement, which has to be designed as a contrast test comparing with another system as a control group, and use real user testing methods and survey to validate the results. Therefore, we designed a contrast experiment Test 2 to see the advanced ACA’s performance on user experience and satisfaction in the prototype system.
Test 3: Contrast Experiment. The control group is designed to be a tour planning system with exactly the same functioning process and user interface, but with the original ACA as its optimizing algorithm. However, this difference won’t be sensed by the user when they are simply interacting with the system. The adjustment will only be reflected in the system’s optimized recommending tour result.
In our experiment, we use user survey and statistics analysis to testify the user experience performance – which is the best and only convincible way to verify such measurement. Some of our survey rating statements are like these:
‘I am satisfied with the customer flow of those recommended sites in the optimized route.’
‘I can accept the weather condition of those system recommended sites.’
‘I feel comfortable with the interaction between me and the system.’
‘I will recommend my friends to adopt this tour planning system when they are travelling in an unfamiliar area.’
Tab.3 Some Survey Data from Users On the Contrast Experiment
| User A | Statement # | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Sys 1 (Advanced) | 4 | 3 | 5 | 3 | 4 | 4 | 4 | 3 | 3 | 2 | 4 | 4 | 3 | 3 |
| Sys 2 (Control) | 4 | 3 | 5 | 3 | 4 | 4 | 4 | 3 | 3 | 2 | 4 | 3 | 3 | 2 |
| User B | Statement # | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Sys 1 (Advanced) | 4 | 4 | 5 | 4 | 2 | 4 | 4 | 3 | 3 | 4 | 4 | 4 | 3 | 3 |
| Sys 2 (Control) | 4 | 3 | 5 | 3 | 2 | 4 | 4 | 3 | 3 | 4 | 4 | 3 | 3 | 3 |
According to the above survey statistics, we can calculate the users’ satisfaction index:
User A: Exp1=0.5*(4+3+5+4+2+4+3+3)/8+0.5*(3+4+4+3+3+4)/6=3.69
Exp2=0.5*(4+3+5+4+2+4+3+2)/8+0.5*(3+3+4+3+3+3)/6=3.40; ∴Exp1>Exp2;
User B: Exp1=0.5*(4+4+5+4+4+4+3+3)/8+0.5*(4+2+4+3+3+4)/6=3.60;
Exp2=0.5*(4+3+5+4+4+4+3+3)/8+0.5*(3+2+4+3+3+3)/6=3.38; ∴Exp1>Exp2;
From the above statistics we can see that these two cases can to some extent reflect the improvement in user satisfaction with the advanced ACA. Even though the data scale was not large enough, but the partial results do have value for further reference, and we expect to see a more convincing breakthrough from continuing surveys.
5. Conclusions
Our research analyzed the problem facing existing researchers that it is of much significant as well as great difficulty of finding a best way of utilizing context information when designing the functions of context-aware tour planning information system in order to provide best user experience in customization and recommendation. Then we proposed an advanced ACA, which quantized context information and processed it as weights of ants’ information factor. Finally, we build up a prototype system, set a real case background of the Shanghai Zoo, design and implemented both single-program and contrast experiments to verify the efficiency, effectiveness and user satisfaction improvement of the advanced algorithm.
However, since our research is restricted by the authors’ knowledge limitation, there are inevitably inadequate points in our research. We inevitably missed some real context factors, and the scale of testing is still to be enlarged.
Therefore, we hope the continuing research on this topic can focus on:
1) Establishing a mass user testing application to implement system test to a large scale, in order to reach a more convincing and reliable result.
2) Including more context information factors in the weights of the advanced ACA to see whether a better customization performance can be reached.
3) Specifying the recommendation process of the system, which will probably help much in gaining higher user satisfaction.
References
[1] Hong, J., Suh, E., Kim, S., Context-aware systems: A literature review and classification, Expert Systems with Applications 36 (2009) 8509–8522
[2] K. Dey and Gregory D. Abowd，Towards a Better Understanding of Context and Context-Awareness. GIT, GVU Technical Report GIT-GVU-99-22, June 1999.K. Cheverst, K. Mitchell, N. Davies, The role of adaptive hypermedia in a context-aware tourist GUIDE, Communications of the ACM, Vol. 45, No. 5,2002, pp. 47 - 51
[3] Johann Dreo and Patrick Siarry, A New Ant Colony Algorithm Using the Heterarchical Concept Aimed at Optimization of Multiminima Continuous Functions, Third International Workshop, ANTS 2002, Vol. 2463 (2002)
[4] Marco Dorigo, Senior Member, IEEE, and Luca Maria Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 1, NO. 1, APRIL 1997
[5] JG Walls, GR Widmeyer, OA El Sawy, “Building an Information System Design Theory for Vigilant EIS”, Information Systems Research, vol. 3, no. 1, 1992, pp. 36-59..
[6] XU Jinrong, LI Yun at el., Hybrid Genetic Ant Colony Algorithm for Traveling Salesman Problem, Computer Applications, Aug 2008, Vol.28, No.8
[7] XU Feng, DU Junping．Study on travel route planning based on improved ant colony algorithm．Computer Engineering and Applications, 2009，45(23),pp.193
[8] Stutzl T, Hoos H H．The MAX-MIN ant system and local search for the traveling salesman problem[C]//Proc IEEE International Conference on Evolutionary Computation (ICEC’97)，Indianapolis,USA.1997：309-314．
[9] Tan Gangli, Yang Jiaben, Ant Colony Algorithm with Adaptive Information Factor [J], Information and Control．2002,31(3): pp198—201.
[10] Cao Lang-cai，Luo Jian． An improved intelligence algorithm over ACS for TSP[C]//Proc of CCC, 2008:65-69．
[11] Paul Harrison; Robin Shaw, Consumer Satisfaction and Post-purchase Intentions: An Exploratory Study of Museum Visitors[J]. International Journal of Arts Management; Winter 2004; 6, 2; ABI/INFORM Global pg. 23
[12] Yang Huo, Douglas Miller, Satisfaction Measurement of Small Tourism Sector (Museum): Samoa [J], Asia Pacific Journal of Tourism Research, Vol. 12, No. 2, June 2007
