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 | 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. 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.