The Capacity Vehicle Routing Problem (CVRP) pertains to the combinatorial optimization problem of identifying the optimal route for vehicles with a capacity constraint of k to travel from the depots to customers, which minimizes the total distance traveled. The Capacitated Vehicle Routing Problem (CVRP), which is essential to modelling logistics networks, has drawn a lot of interest in the field of combinatorial optimization. It has been established that the CVRP (Capacitated Vehicle Routing Problem) with a value of k greater than or equal to three exhibits computational complexity that is classified as NP-hard. Furthermore, it has been established that the problem is APXhard. It has been previously established that the solution is not approximatable in a metric space. Furthermore, this constitutes the principal challenge among the array of issues that confront Arora’s approximation algorithm. The outstanding matter concerns the presence of a (1+$\epsilon$) PTAS (polynomial time approximation scheme) for the capacity vehicle routing problem in Euclidean space, regardless of the vehicle’s capacity. The objective of this manuscript is to furnish a thorough and all-encompassing survey of the research progressions in the domain, encompassing the evolution of the field from its inception to the most recent cutting-edge discoveries.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Approximation Schemes for Capacity Vehicle Routing Problems: A Survey


    Beteiligte:
    Chen, Yongyu (Autor:in)


    Erscheinungsdatum :

    23.06.2023


    Format / Umfang :

    245415 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    A Framework for Vehicle Routing Approximation Schemes in Trees

    Becker, Amariah / Paul, Alice | ArXiv | 2018

    Freier Zugriff

    Vehicle routing problems over time: a survey

    Mor, A. / Speranza, M. G. | Springer Verlag | 2022


    Machine Learning to Solve Vehicle Routing Problems: A Survey

    Bogyrbayeva, Aigerim / Meraliyev, Meraryslan / Mustakhov, Taukekhan et al. | IEEE | 2024


    Workload Equity in Vehicle Routing Problems: A Survey and Analysis

    Matl, P. / Hartl, R. F. / Vidal, T. | British Library Online Contents | 2018


    Hierarchial Vehicle Routing Problems

    A. M. Spaccamela / A. H. G. Rinnooykan / L. Stougie | NTIS | 1982