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.


    Access

    Download


    Export, share and cite



    Title :

    Toward practical algorithms for activity chain optimization


    Contributors:

    Published in:

    Transportation Letters ; 13 , 1 ; 64-76


    Publication date :

    2021-01-02


    Size :

    13 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown





    Toward Practical Aerodynamic Design through Numerical Optimization

    Zingg, D. / Billing, L. / American Institute of Aeronautics and Astronautics | British Library Conference Proceedings | 2007