Concierge service problem for location-based services: Combined-cost and multi objective approaches.

摘要

The Concierge Service Problem (CSP) is to guide users with a route and locations of multiple Point-of-Interests (POIs) to visit with minimum (or optimum) cost including the purchasing, stopping, and travel costs as in Location-Based Services. The largest hurdle in deploying this service model on a commercial scale is the efficiency of the solution algorithm. Because the concierge service problem is an NP-hard problem, the success of this service depends on how efficiently and accurately the solution algorithm gives responses to a user's query.;There are two cost components in this problem: monetary cost (purchasing, parking, toll etc.) and time cost spent on the road. Combined-cost approach is to use a predefined time value represented by dollar-per-hour and to find the minimum total cost. Multi-objective approach provides multiple solutions having lower cost than other feasible solutions either in a monetary cost or in a time cost.;In this research, we defined and formulated CSP for both general and simple cases, and developed exact and heuristic solution algorithms for both combined-cost and multi-objective approaches. The exact algorithms include the adaptive dynamic programming with or without multiple alternative solutions. The heuristic solution algorithms vary from the Euclidean heuristic, the modified K-th shortest path method, the single minimum cost POI method, and Genetic Algorithms. The computational performance of suggested algorithms has been evaluated for its efficiency and validated by implementing them using large size metropolitan networks; Chicago, Illinois and Seoul, Korea for various service scenarios.