In the paper a parallelizable system based on simulated annealing to solve vehicle routing problem with time window (VRPTW) problems is described. The system consists of two optimization phases: a global one, and local one, both based on simulated annealing and parallizable. For the first phase different parallelization strategies are presented and evaluated. The importance of the co-operation among processors has been made clear: the communication of partial solutions improves the efficiency of optimal solution's search. Two algorithms, a synchronous one and an asynchronous one, stand out due to their good average behaviour related to the quality of solutions found, and due to their stability when augmenting the number of processors. The second phase has shown to be a great complement of the global search that permits to obtain a very fast and practical, low cost parallel system. This system has been able to reach the optimal solution published for the Solomon's benchmark in an 85% of the problems, and more important, the averages of any set of random executions are less than 5% worse than the best published.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Low cost parallel solutions for the VRPTW optimization problem


    Contributors:


    Publication date :

    2001


    Size :

    6 Seiten, 12 Quellen




    Type of media :

    Conference paper


    Type of material :

    Print


    Language :

    English




    Search Algorithm for the Constraint Satisfaction Problem of VRPTW

    Cruz-Chavez, Marco Antonio / Diaz-Parral, Ocotlan / Hernandez, J.A. et al. | IEEE | 2007


    Flower Pollination Algorithm for Vehicle Routing Problem with Time Windows (VRPTW)

    Pratiwi, Asri Bekti / Rakhmawati, Ismi Yayuk / Winarko, Edi | BASE | 2021

    Free access

    An Analysis of Exact VRPTW Solutions on ITS Data-based Logistics Instances

    Qureshi, Ali Gul / Taniguchi, Eiichi / Yamada, Tadashi | Springer Verlag | 2011



    A Communication Scheme for an Experimental Grid in the Resolution of VRPTW Using an Evolutionary Algorithm

    Rodríguez-León, Abelardo / Cruz-Chavez, M A / Rivera-López, Rafael et al. | IEEE | 2010