We develop a general framework for designing polynomial-time approximation schemes (PTASs) for various vehicle routing problems in trees. In these problems, the goal is to optimally route a fleet of vehicles, originating at a depot, to serve a set of clients, subject to various constraints. For example, in Minimum Makespan Vehicle Routing, the number of vehicles is fixed, and the objective is to minimize the longest distance traveled by a single vehicle. Our main insight is that we can often greatly restrict the set of potential solutions without adding too much to the optimal solution cost. This simplification relies on partitioning the tree into clusters such that there exists a near-optimal solution in which every vehicle that visits a given cluster takes on one of a few forms. In particular, only a small number of vehicles serve clients in any given cluster. By using these coarser building blocks, a dynamic programming algorithm can find a near-optimal solution in polynomial time. We show that the framework is flexible enough to give PTASs for many problems, including Minimum Makespan Vehicle Routing, Distance-Constrained Vehicle Routing, Capacitated Vehicle Routing, and School Bus Routing, and can be extended to the multiple depot setting.


    Access

    Download


    Export, share and cite



    Title :

    A Framework for Vehicle Routing Approximation Schemes in Trees


    Contributors:

    Publication date :

    2018


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English





    Capacitated-Vehicle Routing Problem with Backhauls on Trees

    Kumar, Roshan / Unnikrishnan, Avinash / Waller, S. Travis | Transportation Research Record | 2011


    Directed trees in multicast routing

    Nicolau, Maria João / Costa, António / Santos, Alexandre et al. | BASE | 2003

    Free access

    Routing Schemes for Intersatellite Link Segment

    Gutierrez, G. / Munoz, D. / Canada et al. | British Library Conference Proceedings | 1999