Please use this identifier to cite or link to this item:
Title: Automatic itinerary planning for traveling services
Authors: Chen, G.
Wu, S.
Zhou, J.
Tung, A.K.H. 
Keywords: itinerary planning
location-based service
Map reduce
team orienteering problem
Issue Date: Mar-2014
Citation: Chen, G., Wu, S., Zhou, J., Tung, A.K.H. (2014-03). Automatic itinerary planning for traveling services. IEEE Transactions on Knowledge and Data Engineering 26 (3) : 514-527. ScholarBank@NUS Repository.
Abstract: Creating an efficient and economic trip plan is the most annoying job for a backpack traveler. Although travel agency can provide some predefined itineraries, they are not tailored for each specific customer. Previous efforts address the problem by providing an automatic itinerary planning service, which organizes the points-of-interests (POIs) into a customized itinerary. Because the search space of all possible itineraries is too costly to fully explore, to simplify the complexity, most work assume that user's trip is limited to some important POIs and will complete within one day. To address the above limitation, in this paper, we design a more general itinerary planning 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. To reduce the processing cost, a two-stage planning scheme is proposed. In its preprocessing stage, single-day itineraries are precomputed via the MapReduce jobs. In its online stage, an approximate search algorithm is used to combine the single day itineraries. In this way, we transfer the TOP problem with no polynomial approximation into another NP-complete problem (set-packing problem) with good approximate algorithms. Experiments on real data sets show that our approach can generate high-quality itineraries efficiently. © 2014 IEEE.
Source Title: IEEE Transactions on Knowledge and Data Engineering
ISSN: 10414347
DOI: 10.1109/TKDE.2013.46
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Aug 12, 2019


checked on Aug 12, 2019

Page view(s)

checked on Aug 9, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.