Testing the Efficiency of Flexible Activity Planning Solutions Using Activity Chains

Abstract

Time-based Activity Chain Optimization (tACO) is a method for flexible, activity-based trip planning. It consists of finding a tour that visits exactly one location for each required activity while respecting time window constraints and returning to the starting location as early as possible. An activity can be performed at any one of several equally suitable locations, while not all locations are suitable for all activities. We compare our previous dynamic programming (DP) based exact tACO algorithm with our new mixed integer linear programming (MILP) model and show that using a straightforward formulation on a commercial solver we still cannot match the speed of the DP implementation. The experimental results obtained on 135 real-world problems underline the practical importance of our previous work and confirm the relevance of DP approaches on realistic problem sizes and in resource constrained environments, e.g. used in real-time trip planning systems and possibly running on embedded or mobile devices. The measurements also corroborate the assumed correctness of both implementations, as the optima coincide in each case (although the produced itineraries may vary considerably).