The capacitated-vehicle routing problem (CVRP) is a classical problem that has been well studied by the transportation science community. A special case of the CVRP in which the network is constrained to have a tree structure (TCVRP) is studied here. Such tree networks arise when the cost of constructing and maintaining roads is much more than the routing cost—or when the transportation network consists of a main highway (e.g., Interstate system) and the customer locations are located off the highway. A new variant of the TCVRP, in which the customers are divided into two subsets—line haul and backhaul customers (TCVRPB)—is introduced in this paper. Line haul customers require delivery from the depot, and backhaul customers have supply that needs to be delivered to the depot. In any vehicle tour, line haul customers must be serviced before backhaul customers. The TCVRPB's relationship to the two-dimensional bin-packing problem is studied and, with the use of that problem, conditions for the lower bound on the problem are derived. An integer-programming (IP) formulation of the problem is presented. A two-approximation algorithm, which gives a feasible set of vehicle routes and customer assignments, is also presented. The problem is tested on two real-world treelike networks of varying sizes and on a randomly generated test network. The IP formulation works exceptionally well on small and medium-sized networks, and the gap between the approximation algorithm and the IP solution did not exceed 2% for nine of the 12 problem instances tested.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Capacitated-Vehicle Routing Problem with Backhauls on Trees


    Subtitle :

    Model, Properties, Formulation, and Algorithm


    Additional title:

    Transportation Research Record


    Contributors:


    Publication date :

    2011-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Genetic Algorithm for Vehicle Routing Problem with Backhauls

    WA, W.Nurfahizul Ifwah. / Shaiful, M. / Shamsunarnie, M.Z et al. | BASE | 2012

    Free access


    An Exact Algorithm for the Vehicle Routing Problem with Backhauls

    Toth, P. / Vigo, D. | British Library Online Contents | 1997


    A Heuristic Algorithm for the Vehicle Routing Problem with Backhauls

    Toth, P. / Vigo, D. / Italian National Research Council; Progetto Finalizzato Transporti et al. | British Library Conference Proceedings | 1996