期刊名称：International Journal of Engineering and Computer Science
印刷版ISSN：2319-7242
出版年度：2015
卷号：4
期号：10
页码：15016-15019
DOI：10.18535/Ijecs/v4i11.26
出版社：IJECS
摘要：Itinerary planning is the important process for the travelling agencies which need to be done carefully to satisfy therequirements of the users. Creating an efficient and economic trip plan is the most annoying job for a backpack traveler. Although travelagency can provide some predefined itineraries, they are not tailored for each specific customer. Previous efforts address the problem byproviding an automatic itinerary planning service, which organizes the points-of-interests (POIs) into a customized itinerary. Because thesearch space of all possible itineraries is too costly to fully explore, to simplify the complexity, most work assume that user’s trip is limited tosome important POIs and will complete within one day. To address the above limitation, in this paper, we design a more general itineraryplanning service, which generates multiday itineraries for the users. In our service, all POIs are considered and ranked based on the users’preference. The problem of searching the optimal itinerary is a team orienteering problem (TOP), a well-known NP-complete problem. Toreduce the processing cost, a two-stage planning scheme is proposed. In its preprocessing stage, single-day itineraries are pre computed viathe Map Reduce jobs. In its online stage, an approximate search algorithm is used to combine the single day itineraries. In this way, wetransfer the TOP problem with no polynomial approximation into another NP-complete problem (set-packing problem) with goodapproximate algorithms. Experiments on real data sets show that our approach can generate high-quality itineraries efficiently.
关键词：Point Of Interest ; Map-reduce ; Team Oriented Problem
