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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Approximation Schemes for Capacity Vehicle Routing Problems: A Survey


    Contributors:


    Publication date :

    2023-06-23


    Size :

    245415 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    A Framework for Vehicle Routing Approximation Schemes in Trees

    Becker, Amariah / Paul, Alice | ArXiv | 2018

    Free access

    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


    Probabilistic vehicle routing problems

    Jézéquel, Antoine | DSpace@MIT | 1985

    Free access