Please use this identifier to cite or link to this item: https://doi.org/10.1109/TKDE.2013.46
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
trajectory
Issue Date: Mar-2014
Source: 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. https://doi.org/10.1109/TKDE.2013.46
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
URI: http://scholarbank.nus.edu.sg/handle/10635/77824
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.

SCOPUSTM   
Citations

10
checked on Jan 15, 2018

WEB OF SCIENCETM
Citations

7
checked on Jan 15, 2018

Page view(s)

72
checked on Jan 23, 2018

Google ScholarTM

Check

Altmetric


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