Generalized Profitable Tour Problems for Online Activity Routing System
- 1 January 2012
- journal article
- Published by SAGE Publications in Transportation Research Record: Journal of the Transportation Research Board
- Vol. 2284 (1) , 1-9
Abstract
A next-generation system for online route guidance and activity recommendations was studied to support decisions that considered multiple activity itineraries whose utilities account for their spatial proximities for a user. For the solution of the underlying problem, the problem of the profitable tour and the problem of the prize-collecting traveling salesman were extended to generalized cases with the expansion of single nodes to clusters to handle various activity types. The generalized formulations addressed several uses, including routing with refueling, the pub crawl problem, and the romantic date problem. Test cases compared an insertion heuristic and a multisolution genetic algorithm with exact solutions. Both algorithms worked well even with the constraints of time windows and with the fast computational times that are necessary for online decision support. The multisolution genetic algorithm tended to be slower than the insertion heuristic was, but the multisolution algorithm could handle a wider variety of problems and could provide a set of solutions from which a user could browse to account for unobserved preferences.Keywords
This publication has 15 references indexed in Scilit:
- Traveling Salesman Problems with ProfitsTransportation Science, 2005
- On approximating a geometric prize-collecting traveling salesman problem with time windowsJournal of Algorithms, 2005
- A bridge between travel demand modeling and activity-based travel analysisTransportation Research Part B: Methodological, 2001
- New classes of efficiently solvable generalized Traveling Salesman ProblemsAnnals of Operations Research, 1999
- On Prize‐collecting Tours and the Asymmetric Travelling Salesman ProblemInternational Transactions in Operational Research, 1995
- The household activity pattern problem: General formulation and solutionTransportation Research Part B: Methodological, 1995
- A note on the prize collecting traveling salesman problemMathematical Programming, 1993
- The selective travelling salesman problemDiscrete Applied Mathematics, 1990
- The prize collecting traveling salesman problemNetworks, 1989
- Generalized travelling salesman problem through n sets of nodes: the asymmetrical caseDiscrete Applied Mathematics, 1987