Font Size: a A A

Study On Paths Recommendation Algorithm For Passenger Traveling Based On Schedules

Posted on:2016-10-02Degree:MasterType:Thesis
Country:ChinaCandidate:T J LiFull Text:PDF
GTID:2310330503488297Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
With the rapid development of the aviation industry, large route networks are formed which brought great convenience for people travelling. When it comes to choose travelling route, people always choose the best path according to their needs. Therefore, it is a complex and urgent problem to recommend path that meet passengers' travelling needs, according to their preferences and transport running schedule. Like other public transport, the feature of flight networks is its operation constrained by running schedule. Therefore, the optimal path recommendation algorithm based on schedule is researched in this paper. There are mainly three elements:First, in this paper, we construct time-extended network(time-expanded) model based on schedules by using the characteristics of flight and rail schedules.Second, depth-first strategy is used to search for the top K paths for travelers in the time-extended networks based on flight schedules. In this paper, we first construct a time-expanded model for flight schedules; then in view that the covering space of flight networks is very wide, we propose an implementation of depth-first search algorithm with dynamic restricted the search area to improve the efficiency of the path searching. In theory,the search area relaxation factor ?, the transfer time ? and the numbers of transfer ? affect directly the efficiency of the path searching. And the affection of these factors on correctness of the paths recommended is analyzed by experiments. From the perspective of entire journey with the shortest time, the algorithm is verified and it can well recommend paths which fit passengers' needs.Third, for single-objective PRDFS_D algorithm can't meet passenger demand for multi-objective path selection, we propose the bi-objective paths recommendation algorithm which considers the earliest arrival and the path reliability. Based on the flight and train schedules, we established the transfer time reliability model in the transfer node according to the reliability theory, and combine this model with the PRDFS_D algorithm. First, the improved PRDFS_D algorithm is used to calculate the path set which meet the conditions,then use the constructed auxiliary function find out the top K earliest arrival paths through the multiple iterations gradually within the path set. And the relationship between the auxiliaryfunction and regulation factor ? is verified by experiment, the same as the bi-objective function with regulation factor ?. And the relationship between the number of iterations and threshold of L is verified when calculate the top K earliest arrival paths, these relationships are consistent with theoretical analysis.
Keywords/Search Tags:schedule, path recommendation algorithm, depth-first search, bi-objective connecting path
PDF Full Text Request
Related items