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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Low cost parallel solutions for the VRPTW optimization problem


    Beteiligte:
    Arbelaitz, O. (Autor:in) / Rodriguez, C. (Autor:in) / Zamakola, I. (Autor:in)


    Erscheinungsdatum :

    2001


    Format / Umfang :

    6 Seiten, 12 Quellen




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch




    Search Algorithm for the Constraint Satisfaction Problem of VRPTW

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


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

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


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

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

    Freier Zugriff