Adaptive dynamic programming approach to a multi-purpose location-based concierge service model

The multi-purpose location-based concierge service model is a new value-added service in the location-based service market, designed to provide the route and location of point-of-interests between an origin and destination with minimum total cost, including the purchasing and travel costs, in a multi-purpose shopping trip. Dynamic programming methods are developed to find the exact solutions for given problems. The dynamic programming decomposes complex problems into a sequential form that is easier to solve and the suggested adaptive method reduces the response time significantly. For a case in which multiple optional routes are preferable, a method that finds a second or third optimal solution is also introduced. These solution algorithms are implemented in the Chicago and Seoul metropolitan network. Test results show that the suggested algorithms can solve large size problems efficiently. The suggested methodology can be directly applied to the commercial-scale service model with a small number of shopping categories, and work as a benchmark for testing the accuracy of other heuristic algorithms for more shopping categories.