LAUSR

ABSTRACT Activity Chain Optimization (ACO) is the task of finding a minimum-cost tour that visits exactly one location for each required activity while respecting time window constraints. We develop an exact algorithm that efficiently solves the ACO problem in all practical cases that involve hundreds of locations offering up to 10–15 activities and returns the optimal route with minimal time spent traveling and waiting. We also introduce a greedy heuristic that simulates human decision-making for comparison. Our experimental results highlight the practical significance of our work as we can reduce travel and wait times on 45 realistic Budapest inner-city routing problems by 16.65% on average compared to our baseline. Our algorithms’ computational and memory requirements for solving practical ACO instances are shown to be low enough to be employed on embedded devices, e.g. smartphones and navigation systems.