Research On Schedule Recommendation Algorithm Under Multi-Constraint

Recently,Point of Interest(POI)Recommendation is widely used in LBS(Location-Based Service)navigation systems.It makes use of the real-time GPS locations of users as well as their preferences to recommend POIs that mostly match these preferences and the paths leading to the POIs.Previous studies are focused on the following two issues:(1)Similarity measurement between POIs and the user preferences,and(2)Optimum path selection from the user location to the recommended POIs.However in most scenarios,users need not only some isolated POIs,but a combination of several POIs that covers the user preferences as well as the paths connecting them.Essentially,it is the schedule planning problem.Schedule planning is usually with strict time limits,and equivalent to Generalized Traveling Sales Man Problem(GTSP)which was proved a NP-hard problem.This imposes great challenge to its solution.In addition,the POIs(or activities)is usually with two important constraints:(1)temporal and spatial constraint(such as,the user would like to have dinner about 6:00 pm in the evening)and(2)order constraint(e.g.,user would like to have dinner after shopping,rather than shopping after dinner),which makes the problem we faced complex further.In this thesis,we formalize the problem of Schedule Planning with strict Time Constraint(SPwTC).Especially,we wrap the static paths between POIs into path activities,thus a globally unified model of user activity can be defined.According to the different situations,we introduce different algorithms.We propose Schedule Recommendation algorithm based on Genetic Algorithm(SRBGA)to solve SPwTC,and we modify the SRBGA to deal with the SPwTC with fixed activities(i.e.,temporal and spatial constraint),furthermore,we use the Simple Reverse Search(SRS)to solve the SPwTC with order constraints.Subsequently,we propose the recommendation function for sorting the recommended schedule plans so as to make the recommended result more in line with user expectation.At the end of this thesis,we verify the efficiency of the algorithm as well as its rationality of the recommended result with real road network data.The result of experiment show that we can recommend reasonable schedules to user within an acceptable time with a high recommendation degree.